Compressed Indexes for Sequence Data: Fast Construction and Dynamism

点击翻译按钮获取中文摘要

Situations when we need to store and analyze very large data volumes frequently arise in different areas of Computer Science. Although computers are becoming faster and memory size is getting larger, the design of efficient algorithms and data structures is not losing its importance. This is a consequence of the growing size of the data that we must store and computational intensity of problems that we must solve. In many applications working with massive data, such as bioinformatics and information retrieval, the data can be represented as a sequence of symbols (string) or as a collection of such sequences. This proposal focuses on efficient data structures for storage and processing of very large volumes of sequential data. ******Space usage plays a key role in the design of efficient algorithms. If we are able to find a space-efficient representation of the data, we can fit a larger fraction of data into the main memory or cache and reduce the number of access operations to the secondary memory. This raises the question about algorithms and data structures that work with data that is stored in compressed form. Although operations on compressed data can be more costly, the algorithms are frequently more efficient: The number of data transfers between different levels of the memory hierarchy is reduced. This results in a performance gain that outweighs the computational overhead. The study of algorithms for processing structured compressed data (strings, trees, graphs) is a thriving research area. ******The topic of this proposal is compressed representation of string indexes. A string index is a data structure that stores a sequence of symbols and answers pattern matching queries on this sequence. The string index and its variants are ubiquitous in algorithms working on string data. Although there is already a large body of work on this subject, many important questions with practical relevance are still open. In this project I will concentrate on two aspects of compressed indexes that are relevant in scenarios when the data must be changed frequently: (1) space-efficient and fast construction algorithms for string indexes and (2) support of dynamism in string indexes. ******I and my students will study efficient algorithm for constructing space-efficient and compact index structures. Special attention will be given to the space usage of these algorithms and to their relation with other models of computation. My students and I will also study the performance of dynamic data structures supporting pattern matching queries and some more involved queries on string data that is stored in compressed form. Rigorous study of structured data is the central topic of this proposal. But my group and I will also pay attention to practical aspects of data storage methods. Practical efficiency will be tested by implementing some of our results. Thus my research program has potential for immediate application and for advancing software industry in Canada.*