AF: Small: Compact Data Structures for String Matching and Retrieval

Louisiana State University, Baton Rouge LA

Investigators

Abstract

In the era of big-data, one needs to organize massive amounts of data so that it can be searched quickly. This requires the building of an index over the raw data. In many cases of big-data, like world-wide web or DNA sequencing, the actual information content is low. This data is highly compressible. On the other hand, the indexes require space which is several times the raw data. Thus, indexing and compression are often conflicting goals. The field of compact (or succinct) data structures attempts to achieve both these goals -compression and indexability- simultaneously. This project will address some of the most fundamental open problems in this field. This will have impact on next generation biological sequence mining databases which could simply work within the memory of a PC instead of requiring high-performance clusters. The foundations built by this project will also impact image matching and music retrieval. Since data structures is one of the most fundamental areas in computer science education, research from this project will also impact data structures curriculum. Suffix trees are central to string indexing and have myriads of applications. However, suffix trees are known to take 15 to 50 times the size of the text they index. This actually stems from a complexity gap in the size of data which is n log s bits compared to the size of the index which is O( n log n) bits, for the text of n characters drawn from alphabet size of s. The techniques of Burrows-Wheeler Transform(BWT) and Phi-function were introduced in the last decade to address this gap. Most subsequent research in this field has treated BWT as a black box, compressing augmenting structures around it to address various applications. However, many problems (like parameterized pattern matching and 2D pattern matching) have remained open in this field. This project will attempt to go deeper and beyond the philosophy of BWT to solve such issues. It will also try to build foundations for deriving lower bounds for problems where compact index would be impossible. To create better understanding of data structure space and query complexity, the project will explore the recent theoretical model called "encoding model". The project will also explore the applied case of compressed indexing for highly repetitive sequences. For further information see the project web site at: http://csc.lsu.edu/~rahul/succinct