Diamond is a SPARQL query engine for linked data. Linked data is a sub-topic of the Semantic Web where data is represented as a labeled directed graph using the Resource Description Framework (RDF), a conceptual data model for web resources, to affect a web-wide interconnected, distributed labeled graph. SPARQL graph patterns entail portions of this distributed graph. Diamond compiles SPARQL queries into a physical query plan based on a set of newly defined operators that implement a new variant of the Rete match, a well known artificial intelligence (AI) algorithm used for complex pattern-matching problems. / text

Efficient twig pattern matching is essential to XML queries and other tree-based queries. Numerous so-called holistic algorithms have been proposed for efficiently processing the twig patterns in XML queries. However, a more general form of twig pattern, called Boolean-twig (or B-twig for short), which allows arbitrary combination of an arbitrary number of all the three logical connectives, AND, OR, and NOT, in a twig pattern, has not been adequately addressed. The theme of this study is on holistic (and efficient) B-twig pattern matching using region encoding and Dewey encoding schemes. We first adopt region encoding and propose a novel, direct approach called DBTwigMerge for holistic B-twig pattern matching, which although enjoys certain theoretical ``beauty'' and ``elegance'' but does not always outperform our prior approach, BTwigMerge. Based on the experience gained and in-depth investigation, we then come up with another new and more efficient approach, FBTwigMerge, which is proven to be the overall winner among all the holistic approaches using region encoding. In this study, we also studied the holistic B-twig pattern matching problem using Dewey encoding. The unique properties of Dewey encoding bring challenges and also benefits to this problem. By carefully addressing the challenges, this dissertation finally presents the first Dewey based holistic approach, called DeweyNOT, for efficiently solving the pattern matching problem with a subclass of B-twigs, i.e., twig queries involving arbitrary AND/NOT predicates. Extensive experimental studies have been conducted that demonstrate the viability and outstanding performance of the proposed approaches.

In this dissertation, we provide combinatorial methods to obtain the probabilistic mul-tivariate generating function that counts the occurrences of patterns in a text generated by a Markovian source. The generating function can then be expanded into the Taylor series in which the power of a term gives the size of a text and the coeÿcient provides the proba-bilities of all possible pattern occurrences with the text size. The analysis is on the basis of the inclusion-exclusion principle to pattern counting (Goulden and Jackson, 1979 and 1983) and its application that Bassino et al. (2012) used for obtaining the generating function in the context of the Bernoulli text source. We followed the notations and concepts created by Bassino et al. in the discussion of distinguished patterns and non-reduced pattern sets, with modifications to the Markovian dependence. Our result is derived in the form of a linear matrix equation in which the number of linear equations depends on the size of the alphabet. In addition, we compute the moments of pattern occurrences and discuss the impact of a Markovian text to the moments comparing to the Bernoulli case. The methodology that we use involves the inclusion-exclusion principle, stochastic recurrences, and combinatorics on words including probabilistic multivariate generating functions and moment generating functions.<br>

This report explores of the feasibility of using pattern matching for implementing a robust Natural Language Interface (NLI) over a limited Application Programming Interface (API). Because APIs are used to such a great extent today and often in mobile applications, it becomes more important to find simple ways of making them accessible to end users. A very intuitive way to access information via an API is using natural language. Therefore, this study first explores the possibility of building a corpus of the most common phrases used for a particular API. It is then explored how those phrases adhere to patterns, and how these patterns can be used to extract meaning from a phrase. Finally it evaluates an implementation of an NLI using pattern matching system based on the patterns. The result of the building of the corpus shows that although the amount of unique phrases used with our API seems to increase quite steadily, the amount of patterns those phrases follow converges to a constant quickly. This implies that it is possible to use these patterns to create an NLI that is robust enough to query an API effectively. The evaluation of the pattern matching system indicates that this technique can be used to successfully extract information from a phrase if its pattern is known by the system. / Den här rapporten utforskar hur genomförbart det är att använda mönstermatchning för att implementera ett robust användargränssnitt för styrning med naturligt språk (Natural Language Interface, NLI) över en begränsad Application Programming Interface (API). Eftersom APIer används i stor utsträckning idag, ofta i mobila applikationer, har det blivit allt mer viktigt att hitta sätt att göra dem ännu mer tillgängliga för slutanvändare. Ett mycket intuitivt sätt att komma åt information är med hjälp av naturligt språk via en API. I den här rapporten redogörs först för möjligheten att bygga ett korpus för en viss API and att skapa mönster för mönstermatchning på det korpuset. Därefter utvärderas en implementation av ett NLI som bygger på mönstermatchning med hjälp av korpuset. Resultatet av korpusuppbyggnaden visar att trots att antalet unika fraser som används för vårt API ökar ganska stadigt, så konvergerar antalat mönster på de fraserna relativt snabbt mot en konstant. Detta antyder att det är mycket möjligt att använda desssa mönster för att skapa en NLI som är robust nog för en API. Utvärderingen av implementationen av mönstermatchingssystemet antyder att tekniken kan användas för att framgångsrikt extrahera information från fraser om mönstret frasen följer finns i systemet.

The pattern matching is the problem of locating one string, a pattern, inside another, a text, which is required in for example databases, search engines, and text editors. Thus, several algorithms have been created to tackle this problem and this thesis evaluates whether a parallel version of the Naïve algorithm, given a reasonable amount of threads for a personal computer, could become more efficient than some state-of-the-art algorithms used today. Therefore, an algorithm from the Deadzone family, the Horspool algorithm, and a parallel Naïve algorithm was implemented and evaluated on two different sized alphabets. The results show that a parallel Naïve implementation is to be favoured over the Deadzone and Horspool on a alphabet of size 4 for patterns larger than 2 up to 20. Furthermore, for alphabet of size 256 the parallel Naïve should also be used for patterns of lengths 1 to 20.

No description available.

Unmanned vehicles are increasingly being used for mobile sensing missions. These missions can range from target acquisition to chemical and biological sensing. The reason why these vehicles are increasingly being used is because they can carry many different types of sensors and can function as a cheap platform for carrying these sensors. The sensing that will be explained in this thesis is target acquisition. Target acquisition is the act of locating the exact position of an "area of interest." Currently this task can be completed with different types of complex range sensors. This thesis presents a type of target acquisition scheme for unmanned vehicles that will use a combination of cheap, simple vision sensors and robot inertial navigation data in order to accurately measure the location of a target in real world coordinates. This thesis will first develop an accurate waypoint driving algorithm that will either use dead reckoning or GPS/ compass sensors. We will then develop a robust target extraction algorithm that will be able to pick out a target in an image. After this is completed we will develop an algorithm that will be used to find the distance to the target from the robot. This algorithm will be based on a type of active vision system. Finally we will integrate all of these algorithms together in order to develop a target extraction technique that will be able to accurately find the distance to the target. With the distance we can then find the real world location of the target. / Master of Science

Distributed adaptive computing systems (ACS) allow developers to design applications using multiple programmable devices. The ACS API, an API created for distributed adaptive com-puting, gives developers the ability to design scalable ACS systems in a cluster networking environment for large applications. One such application, found in the field of bioinformatics, is the DNA sequence alignment problem. This thesis presents a runtime reconfigurable FPGA implementation of the Smith-Waterman similarity comparison algorithm. Additionally, this thesis presents tools designed for the ACS API that assist developers creating applications in a heterogeneous distributed adaptive computing environment. / Master of Science

La phylogénie permet de reconstituer l'histoire évolutive de séquences ainsi que des espèces qui les portent. Les récents progrès des méthodes de séquençage ont permis une inflation du nombre de séquences disponibles et donc du nombre d'arbres de gènes qu'il est possible de construire. La question qui se pose est alors d'optimiser la recherche d'informations dans ces arbres. Cette recherche doit être à la fois exhaustive et efficace. Pour ce faire, mon travail de thèse a consisté en l'écriture puis en l'utilisation d'un ensemble de programmes capables de parcourir et d'annoter les arbres phylogénétiques. Cet ensemble de programmes porte le nom de TPMS (Tree Pattern Matching Suite). Le premier de ces programmes (tpms_query) permet d'effectuer l'interrogation de collections à l'aide d'un formalisme dédie. Les possibilités qu'il offre sont : La détection de transferts horizontaux : Si un arbre de gènes présente une espèce branchée dans un arbre au milieu d'un groupe monophylétique d'espèces avec lesquelles elle n'est pas apparentée, on peut supposer qu'il s'agit d'un transfert horizontal, si ces organismes sont des procaryotes ou des eucaryotes unicellulaires. La détection d'orthologie : Si une partie d'un arbre de gènes correspond exactement à l'arbre des espèces, on peut alors supposer que ces gènes sont un ensemble de gènes d'orthologues. La validation de phylogénies connues : Quand l'arbre des espèces donne lieu à des débats, il peut est possible d'interroger une large collection d'arbres de gènes pour voir combien de familles de gènes correspondent à chaque hypothèse. Un autre programme, tpms_computations, permet d'effectuer des opérations en parallèle sur tous les arbres, et propose notamment l'enracinement automatique des arbres via différents critères, ainsi que l'extraction de sous arbres d'orthologues (séquence unique par espèce). Il propose aussi une méthode de détection automatique d'incongruences. La thèse présente le contexte, les différents algorithmes à la base de ces programmes, ainsi que plusieurs utilisations qui en ont été faites / Phylogeny allows to reconstruct evolutionnary history of sequences and species that carry them. Recent progress in sequencing methods produced a growing number of available sequences, and so of number of gene trees that one can build. One of the consecutive issues is to optimise the extraction of information from the trees. Such an extraction should be complete and efficient. To address this, my thesis consisted in writing and then using a suite of programs which aim to browse and annotate phylogenic trees. This program suite is named TPMS (Tree Pattern Matching Suite). It browses and annotates trees with several algorithms. The first of them, tpms_query consists in querying collections using a dedicated formalism. This allows to: Detect horizontal transfers If, in a gene tree, a species is nested in a monophyletic group of unrelated species, one can infer this is a horizontal transfer, if this organisms are prokaryotic (also concerning some unicellular eukaryotes). Orthology detection: if a part of a gene tree exactly matches to the species tree, one can suppose these genes are set of orthologues. Validating known phylogenies: when controversy exists concerning the species tree, it is possible to query a lange collection of gene trees to perform a count of families matching to each hypothesis. Another program allows to perform parallel operations on all the trees, such as automating rooting of trees via different criterions. It also allows an automatic detection of incongruencies. The thesis introduces the context, different algorithms which the programs are based on, and several using performed with it

Pattern matching is a well-established concept in the functional programming community. It provides the means for concisely identifying and destructuring values of interest. This enables a clean separation of data structures and respective functionality, as well as dispatching functionality based on more than a single value. Unfortunately, expressive pattern matching facilities are seldomly incorporated in present object-oriented programming languages. We present a seamless integration of pattern matching facilities in an object-oriented and dynamically typed programming language: Newspeak. We describe language extensions to improve the practicability and integrate our additions with the existing programming environment for Newspeak. This report is based on the first author’s master’s thesis.