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

在大数据时代，人们需要组织大量的数据，以便快速搜索。这需要在原始数据上构建索引。在许多大数据的案例中，比如全球网络DNA测序，实际的信息含量很低。这些数据是高度可压缩的。另一方面，索引需要的空间是原始数据的几倍。因此，索引和压缩常常是相互冲突的目标。紧凑（或简洁）数据结构领域试图同时实现这两个目标——压缩和可索引性。这个项目将解决这个领域中一些最基本的开放性问题。这将对下一代生物序列挖掘数据库产生影响，这些数据库可以简单地在PC机的内存中工作，而不需要高性能集群。这个项目所建立的基础也将影响图像匹配和音乐检索。由于数据结构是计算机科学教育中最基础的领域之一，因此本项目的研究也将影响数据结构课程。后缀树是字符串索引的核心，有无数的应用程序。然而，众所周知，后缀树所占用的数据是它们所索引的文本的15到50倍。这实际上源于数据大小的复杂性差距，数据大小为n log s位，而索引大小为O（n log n）位，对于字母大小为s的n个字符的文本。在过去十年中，引入了Burrows-Wheeler变换（BWT）和phi函数技术来解决这一差距。该领域的大多数后续研究都将BWT视为一个黑盒，压缩其周围的增强结构以解决各种应用问题。然而，在该领域仍存在许多问题（如参数化模式匹配和二维模式匹配）。这个项目将尝试深入并超越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