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

在大数据时代，人们需要组织海量数据，以便快速搜索。这需要在原始数据上建立索引。在许多大数据案例中，比如万维网或DNA测序，实际信息含量很低。这些数据是高度可压缩的。另一方面，索引需要的空间是原始数据的几倍。因此，索引和压缩通常是相互冲突的目标。紧凑(或简洁)数据结构领域试图同时实现这两个目标--压缩和索引性。该项目将解决该领域中一些最基本的公开问题。这将对下一代生物序列挖掘数据库产生影响，这些数据库可以简单地在PC内存中工作，而不需要高性能的集群。该项目建立的基础也将影响图像匹配和音乐检索。由于数据结构是计算机科学教育中最基本的领域之一，该项目的研究也将影响数据结构课程。Suffix树是字符串索引的核心，具有无数的应用。然而，众所周知，后缀树占用的文本大小是它们索引的文本的15到50倍。这实际上源于从S的字母表中提取的n个字符的文本的数据大小与索引大小O(Nlogn)比特相比的复杂性差距。Burrow-Wheeler变换(BWT)和Phi-Function技术在过去十年中被引入来解决这一差距。该领域的大多数后续研究都将BWT视为一个黑匣子，压缩其周围的增强结构以满足各种应用。然而，许多问题(如参数化模式匹配和2D模式匹配)在该领域仍然悬而未决。这个项目将试图更深入地超越BWT的理念来解决这些问题。它还将努力建立基础，为不可能使用紧凑指数的问题得出下限。为了更好地理解数据结构空间和查询复杂性，该项目将探索最新的理论模型，称为“编码模型”。该项目还将探索高度重复序列的压缩索引的应用案例。有关更多信息，请参阅项目网站：http://csc.lsu.edu/~rahul/succinct

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 webor 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 matchingand 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