The thin-client/server computing model mandates applications running solely on a server and client devices connecting to the server through the Internet for carrying out works. Traditional thin-client/server computing model comprises only a single server and works only within LAN environment, which severely restrict its applicability. To meet the demand of reasonable response time over WAN, a modified thin-client/server computing model, MAS TC/S, was proposed. In MAS TC/S, multiple application servers spreading over WAN are installed, and each client device can freely connect to any application server that is close to it. However, reducing delay associated with fetching absent files, which are stored in other servers, is a challenging issue in MAS TC/S. We propose to employ data prefetching mechanisms to speed up file fetching. We use the suffix tree-like structure to store users¡¦ previous file access records and define two temporal relationships between two records: followed by or concurrent with, to decide the set of files that should be prefetched together. Each file access subsequence is associated with a set of predicted file sets, each carrying a different weight. Given a current file access session, we will first find a matching file access subsequence and then choose the predicted set that has the highest weight. Based on the chosen predicted set, suitable files are prefeteched to the connected server. We compare our method with All-Kth-Order Markov model and find our method gets higher hit ratio under various operating regions.

Over the last decade, biological sequence repositories have been growing at an exponential rate. Sophisticated indexing techniques are required to facilitate efficient searching through these humongous genetic repositories. A particularly attractive index structure for such sequence processing is the classical suffix-tree, a vertically compressed trie structure built over the set of all suffixes of a sequence. Its attractiveness stems from its linearity properties -- suffix-tree construction times are linear in the size of the indexed sequences, while search times are linear in the size of the query strings. In practice, however, the promise of suffix-trees is not realized for extremely long sequences, such as the human genome, that run into the billions of characters. This is because suffix-trees, which are typically an order of magnitude larger than the indexed sequence, necessarily have to be disk-resident for such elongated sequences, and their traditional construction and traversal algorithms result in random disk accesses. We investigate, in this thesis, post-construction techniques for disk-based suffix-tree storage optimization, with the objective of maximizing disk-reference locality during query processing. We begin by focusing on the layout reorganization in which the node-to-block assignments and sequence of blocks are reworked. Our proposed algorithm is based on combining the breadth-first layout approach advocated in the recent literature with probabilistic techniques for minimizing the physical distance between successive block accesses, based on an analysis of node traversal patterns. In our next step, we consider techniques for reducing the space overheads incurred by suffix-trees. In particular, we propose an embedding strategy whereby leaf nodes can be completely represented within their parent internal nodes, without requiring any space extension of the parent node's structure. To quantitatively evaluate the benefits of our reorganized and restructured layouts, we have conducted extensive experiments on complete human genome sequences, with complex and computationally expensive user queries that involve finding the maximal common substring matches of the query strings. We show, for the first time, that the layout reorganization approach can be scaled to entire genomes, including the human genome. In the layout reorganization, with careful choice of node-to-block assignment condition and optimized sequence of blocks, search-time improvements ranging from 25% to 75% can be achieved with respect to the construction layouts on such genomes. While the layout reorganization does take considerable time, it is a one-time process whereas searches will be repeatedly invoked on this index. The internalization of leaf nodes results in a 25% reduction in the suffix-tree space occupancy. More importantly, when applied to the construction layout, it provides search-time improvements ranging from 25% to 85%, and in conjunction with the reorganized layout, searches are speeded up by 50% to 90%. Overall, our study and experimental results indicate that through careful choice of node implementations and layouts, the disk access locality of suffix-trees can be improved to the extent that upto an order-of-magnitude improvements in search-times may result relative to the classical implementations.

O avanço tecnológico dos laboratórios de biologia molecular tem proporcionado um grande aumento no volume de seqüências de nucleotídeos armazenadas em bancos de dados biológicos, introduzindo o desafio de pesquisar eficientemente estes dados. Neste contexto, a árvore de sufixo é um método de acesso utilizado por muitas aplicações que envolvem pesquisa em dados biológicos. Entretanto, o custo de construção das árvores de sufixo é alto devido ao tamanho da estrutura de indexação gerado e à necessidade da árvore de sufixo caber em memória principal para ser construída com complexidade linear em relação ao tempo. Esta dissertação propõe o Perseus, uma nova técnica para tratar árvores de sufixo persistentes. A técnica Perseus apresenta os seguintes diferenciais. Ela introduz uma abordagem que realiza a construção de árvores de sufixo persistentes cujos tamanhos podem exceder a capacidade da memória principal. Além disso, ela provê um algoritmo que constrói árvores de sufixo por meio do particionamento destas árvores somente quando necessário. Esta construção também permite que o usuário escolha quais subseqüências de uma seqüência devem ser indexadas, de acordo com os requisitos particulares de suas aplicações. Por fim, a técnica proposta também introduz um algoritmo de casamento exato que permite a busca por uma seqüência de consulta em árvores de sufixo que podem estar particionadas. A validação do Perseus foi realizada por meio de testes de desempenho considerando genomas de vários organismos, os quais possuem diferentes ordens de magnitude de tamanho. Os resultados obtidos foram comparados com a técnica Trellis+, a qual representa o estado da arte nesta linha de pesquisa. Os testes indicaram que o Perseus construiu árvores de sufixo mais rapidamente do que o Trellis+, reduzindo o tempo total gasto na construção em até 24%. Perseus também criou árvores de sufixo mais compactas, atingindo uma redução média de 27% no espaço de memória secundária utilizado. Já com relação ao tempo total gasto no processamento de consultas, Perseus sempre produziu os melhores resultados, respondendo consultas em média 49% mais rápido do que o seu principal concorrente. Com relação à indexação de subseqüências escolhidas pelo usuário, comparando os resultados obtidos com o Trellis+, os testes mostraram que Perseus proveu uma redução no tempo de construção de árvores de sufixo de 97% na média e uma redução no tempo gasto no processamento de consultas de genes de 93% na média / Due to the technological advances in molecular biology laboratories, biological databases are extremely voluminous and tend to become more voluminous as data on new genome organisms are available. This introduces the challenge of searching nucleotide sequences efficiently. The suffix tree is an access method used for several applications that search for these data. However, the cost of building suffix trees is high, since they are extremely large data structures and they should fit in the main memory to be constructed in linear time. In this masters thesis, we propose the Perseus, a novel technique that handles persistent suffix trees. The Perseus introduces the following distinctive good properties. It is based on an approach that constructs persistent suffix trees whose sizes may exceed the main memory capacity. Furthermore, it provides an algorithm that allows for users to indicate which substrings of the input string should be indexed, according to the requirements of their applications. Moreover, it proposes an extended exact matching algorithm that searches for a query string into suffix trees that may be partitioned. The Perseus was validated through performance tests using genomes of several organisms of different sizes. The results were compared with the Trellis+ technique, which represents the state-of-the-art in this field. The tests showed that the Perseus reduced the time spent on constructing suffix trees by 24%. The Perseus also constructed compacter suffix trees, providing an average reduction in the secondary memory storage of 27%. Furthermore, the Perseus reduced the time spent on query processing of nucleotide sequences by up to 49%. As for the functionality of indexing substrings according to the users requirements, the Perseus greatly improved the query performance in comparison to the Trellis+. The results showed that the Perseus reduced the time spent on constructing suffix trees by 97% on average and the time spent on query processing of genes by 93% on average

Genomic sequence databases, like GenBank, EMBL, are widely used by molecular biologists for homology searching. Because of the increase of the size of genomic sequence databases, the importance of indexing the sequences for fast queries grows. The DNA sequences are composed of 4 base pairs, and these genomic sequences can be regarded as the text strings. Similar to conventional databases, there are some approaches use indexes to provide efficient access to the data. The inverted-list indexing approach uses hashing to store the database sequences. However, the perfect hashing function is difficult to construct, and the collision in a hash table may occur frequently. Different from the inverted-list approach, there are other data structures, such as the suffix tree, the suffix array, and the suffix binary search tree, to index the genomic sequences. One characteristic of those suffix-tree-like data structures is that they store all suffixes of the sequences. They do not break the sequences into words. The advantage of the suffix tree is simple. However, the storage space of the suffix tree is too large. The suffix array and the suffix binary search tree reduce more storage space than the suffix tree. But since they use the binary searching technique to find the query sequence, they waste too much time to do the search. Another data structure, the word suffix tree, uses the concept of words and stores partial suffixes to index the DNA sequence. Although the word suffix tree reduces the storage space, it will lose information in the search process. In this thesis, we propose a new index structure, ACGT-Words tree, for efficiently support query processing in genomic databases. We define the concept of words which is different from the word definition given in the word suffix tree, and separate the DNA sequences stored in the database and in the query sequence into distinct words. Our approach does not store all of the suffixes in the database sequences. Therefore, we need less space than the suffix tree approach. We also propose an efficient search algorithm to do the sequence match based on the ACGT-Words tree index structure; therefore, we can take less time to finish the search than the suffix array approach. Our approach also avoids the missing cases in the word suffix tree. Then, based on the ACGT-Words tree, we propose one improved operation for data insertion and two improved operations for the searching process. In the improved operation for insertion, we sort the ACGT-Words generated and then preprocess them before constructing the tree structure. In the two improved operations, we can provide better performance when the query sequence satisfies some conditions. The simulation results show that the ACGT-Words tree outperforms the suffix tree and the suffix array in terms of storage and processing time, respectively. Moreover, we show that the improved operations in the ACGT-Words tree also require shorter time to construct or search than the original processes or the suffix array.

O avanço tecnológico dos laboratórios de biologia molecular tem proporcionado um grande aumento no volume de seqüências de nucleotídeos armazenadas em bancos de dados biológicos, introduzindo o desafio de pesquisar eficientemente estes dados. Neste contexto, a árvore de sufixo é um método de acesso utilizado por muitas aplicações que envolvem pesquisa em dados biológicos. Entretanto, o custo de construção das árvores de sufixo é alto devido ao tamanho da estrutura de indexação gerado e à necessidade da árvore de sufixo caber em memória principal para ser construída com complexidade linear em relação ao tempo. Esta dissertação propõe o Perseus, uma nova técnica para tratar árvores de sufixo persistentes. A técnica Perseus apresenta os seguintes diferenciais. Ela introduz uma abordagem que realiza a construção de árvores de sufixo persistentes cujos tamanhos podem exceder a capacidade da memória principal. Além disso, ela provê um algoritmo que constrói árvores de sufixo por meio do particionamento destas árvores somente quando necessário. Esta construção também permite que o usuário escolha quais subseqüências de uma seqüência devem ser indexadas, de acordo com os requisitos particulares de suas aplicações. Por fim, a técnica proposta também introduz um algoritmo de casamento exato que permite a busca por uma seqüência de consulta em árvores de sufixo que podem estar particionadas. A validação do Perseus foi realizada por meio de testes de desempenho considerando genomas de vários organismos, os quais possuem diferentes ordens de magnitude de tamanho. Os resultados obtidos foram comparados com a técnica Trellis+, a qual representa o estado da arte nesta linha de pesquisa. Os testes indicaram que o Perseus construiu árvores de sufixo mais rapidamente do que o Trellis+, reduzindo o tempo total gasto na construção em até 24%. Perseus também criou árvores de sufixo mais compactas, atingindo uma redução média de 27% no espaço de memória secundária utilizado. Já com relação ao tempo total gasto no processamento de consultas, Perseus sempre produziu os melhores resultados, respondendo consultas em média 49% mais rápido do que o seu principal concorrente. Com relação à indexação de subseqüências escolhidas pelo usuário, comparando os resultados obtidos com o Trellis+, os testes mostraram que Perseus proveu uma redução no tempo de construção de árvores de sufixo de 97% na média e uma redução no tempo gasto no processamento de consultas de genes de 93% na média / Due to the technological advances in molecular biology laboratories, biological databases are extremely voluminous and tend to become more voluminous as data on new genome organisms are available. This introduces the challenge of searching nucleotide sequences efficiently. The suffix tree is an access method used for several applications that search for these data. However, the cost of building suffix trees is high, since they are extremely large data structures and they should fit in the main memory to be constructed in linear time. In this masters thesis, we propose the Perseus, a novel technique that handles persistent suffix trees. The Perseus introduces the following distinctive good properties. It is based on an approach that constructs persistent suffix trees whose sizes may exceed the main memory capacity. Furthermore, it provides an algorithm that allows for users to indicate which substrings of the input string should be indexed, according to the requirements of their applications. Moreover, it proposes an extended exact matching algorithm that searches for a query string into suffix trees that may be partitioned. The Perseus was validated through performance tests using genomes of several organisms of different sizes. The results were compared with the Trellis+ technique, which represents the state-of-the-art in this field. The tests showed that the Perseus reduced the time spent on constructing suffix trees by 24%. The Perseus also constructed compacter suffix trees, providing an average reduction in the secondary memory storage of 27%. Furthermore, the Perseus reduced the time spent on query processing of nucleotide sequences by up to 49%. As for the functionality of indexing substrings according to the users requirements, the Perseus greatly improved the query performance in comparison to the Trellis+. The results showed that the Perseus reduced the time spent on constructing suffix trees by 97% on average and the time spent on query processing of genes by 93% on average

Indexing and processing strings are very important topics in database management. Strings can be database records, DNA sequences, protein sequences, or plain text. Various string operations are required for several application categories, such as bioinformatics and entity resolution. When the string count or sizes become very large, several state-of-the-art techniques for indexing and processing such strings may fail or behave very inefficiently. Modifying an existing technique to overcome these issues is not usually straightforward or even possible. A category of string operations can be facilitated by the suffix tree data structure, which basically indexes a long string to enable efficient finding of any substring of the indexed string, and can be used in other operations as well, such as approximate string matching. In this document, we introduce a novel efficient method to construct the suffix tree index for very long strings using parallel architectures, which is a major challenge in this category. Another category of string operations require clustering similar strings in order to perform application-specific processing on the resulting possibly-overlapping clusters. In this document, based on clustering similar strings, we introduce a novel efficient technique for record linkage and entity resolution, and a novel method for correcting errors in a large number of small strings (read sequences) generated by the DNA sequencing machines.

Suffix tree is a data structure which enables the performing of fast search-like operations on the text. In order to be used efficiently, it must be created quickly. In this thesis, we focus on the new kind of suffix link simulation called "minimized branching", which aims to increase the speed of suffix tree construction by reducing the number of branching operations. Our main goal is to present a comparison of the currently used methods for the suffix tree construction and to point out some advantages and disadvantages of the individual approaches. We introduce, implement and practically evaluate multiple variations of the standard McCreight's and Ukkonen's algorithms, as well as Partition and Write Only Top Down (PWOTD) algorithm, originally developed for disk-based construction. Our main result is the integrated description and implementation of these algorithms, which are both well-suited to be further built upon. We also present a simple recommendations on when it is advisable to use a particular algorithm's variation and why.

Title: Suffix Graphs and Lossless Data Compression Author: Martin Senft Department: Department of Software and Computer Science Education Supervisor of the doctoral thesis: doc. RNDr. Tomáš Dvorˇák, CSc., Depart- ment of Software and Computer Science Education Abstract: Suffix tree and its variants are widely studied data structures that enable an efficient solution to a number of string problems, but also serve for implementation of data compression algorithms. This work explores the opposite approach: design of compression methods, based entirely on prop- erties of suffix graphs. We describe a unified construction algorithm for suf- fix trie, suffix tree, DAWG and CDAWG, accompanied by analysis of implicit suffix link simulation that yields two practical alternatives. Since the com- pression applications require maintaining text in the sliding window, an in- depth discussionof slidingsuffixgraphsisneeded. Fillinggapsin previously published proofs, we verify that suffix tree is capable of perfect sliding in amortised constant time. On the other hand, we show that this is not the case with CDAWG, thus resolving a problem of Inenaga et al. Building on these investigations,we describea family of data compression methods,based on a description of suffix tree construction for the string to be compressed. While some of...

Ingeniero Civil en Computación / El árbol de sufijos es una de las estructuras más importantes que se han creado para el manejo de cadenas de caracteres. Esta estructura permite encontrar eficientemente las ocurrencias de un patrón, en tiempo proporcional al largo del patrón. Adicionalmente soporta operaciones para resolver problemas complejos sobre una secuencia. Esta estructura tiene muchas aplicaciones en variadas áreas de la investigación , destacándose en la bioinformática, donde los recientes avances tecnológicos han permitido recolectar grandes colecciones de secuencias de ADN. La implementación clásica se vuelve impracticable para grandes volúmenes de información dado que ocupan demasiado espacio, que siempre muchas veces mayor que el texto mismo. Luego, no pueden ser almacenados en memoria principal, lo que en la práctica significa un aumento importante del tiempo de respuesta. Este problema es la principal motivación por la cual se buscan nuevas representaciones comprimidas de esta estructura, dando lugar a los árboles de sufijos comprimidos. Estos contienen la misma información que los árboles de sufijos pero ocupan un espacio considerablemente menor. Existen variadas propuestas teóricas para representar un árbol de sufijos comprimido, que ofrecen espacios y tiempos diferentes. En la práctica, dos estructuras destacan por sobre las demás. La primera fue propuesta por Sadakane e implementada por Välimäki et al. Esta estructura soporta la mayoría de las operaciones de navegación en tiempo constante, pero en la práctica requiere entre 25 y 35 bits por símbolo. La segunda fue propuesta por Fischer et al. e implementada por Cánovas, incorporando variantes y nuevas ideas para todas las estructuras que componen el árbol de sufijos comprimido propuesto por ellos. Una de estas variantes resulta ser superior a la implementación de Sadakane tanto en espacio como en tiempo, utilizando alrededor de 8 a 12 bits por símbolo. Dado que secuencias de ADN relacionadas son altamente similares, por ejemplo dos genomas humanos son muy parecidos, las colecciones pueden ser tratadas como un gran texto que contiene cadenas altamente similares. En este trabajo se propone e implementa una nueva variante del árbol de sufijos comprimido de Fischer et al, optimizada para textos altamente repetitivos. Se reemplazan y/o modifican cada una de las estructuras que componen el árbol por nuevas que presentan mayor compresión en textos repetitivos. El resultado más importante consiste en crear una nueva estructura inspirada en una técnica de compresión basada en gramáticas, aplicable al árbol de sufijos comprimido, que con poco espacio extra acelera considerablemente las operaciones sobre el árbol. Finalmente, la variante se compara experimentalmente sobre textos altamente repetitivos y resulta ser superior a la implementación de Cánovas, tanto en tiempo como en espacio, ocupando entre 3 a 6 bits por símbolo. / Este trabajo ha sido parcialmente financiado por el Instituto Milenio de Dinámica Celular y Biotecnología (ICDB) y el proyecto Fondecyt 1-080019

No description available.