CAREER: Scalable and Flexible Indexing of Compressed Sequences

无损数据压缩是一项经典且普遍存在的任务，它可以减少数据大小，从而降低传输或归档成本。然而，现代应用程序需要的不仅仅是压缩。在计算生物学等领域，数兆字节的高度可压缩数据正在以越来越快的速度产生。为了充分利用这些数据，它不仅需要存储在一个很小的空间里，而且还需要可以访问和搜索。近年来，可以完成这一任务的称为“压缩索引”的数据结构应运而生。然而，到目前为止，研究主要集中在静态索引上，而忽略了对更新和高效构造的支持等重要方面。该项目的总体目标是开发强大的、动态的压缩索引，能够处理一组通用的查询和各种表示，而且可以有效地构建。这将使存储和共享高度可压缩的数据集(如DNA集合)变得更便宜、更快、更节能，从而充分释放DNA测序技术进步的潜力。这一项目的进展也将被整合到为代表不足的学生提供的研究经验中，以及推广到非计算机科学的学生中。该项目的主要研究目标大致可分为以下三个方向。首先，该项目将带来构建压缩索引的新的高效算法。该方法首先对输入数据进行轻度次优压缩，然后在压缩时间内构造最终索引，即时间与预压缩文本成比例。其次，该项目旨在利用和改进现代后缀采样技术来设计新的强大的索引，这些索引既是压缩的，又能够支持强大的查询，包括多字符串表示。最后，该项目将研究压缩指数下限的欠发达景观。目前，只有最基本的查询，如随机访问，被很好地理解，而关于更多功能的表示的下限或压缩计算的下限的了解要少得多。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Lossless data compression is a classical and ubiquitous task that reduces the size of data, leading to a decreased cost of transfer or archival. Modern applications, however, require more than compression. In domains such as computational biology, terabytes of highly compressible data are generated at an increasing rate. To fully take advantage of this data, it needs to be not only stored in a small space but also accessible and searchable. Recent years have witnessed the birth of data structures called "compressed indexes" that can accomplish this task. The research so far, however, has mostly focused on static indexes, leaving out important aspects such as support for updates and efficient construction. This project's overarching goal is to develop powerful, dynamic compressed indexes capable of handling a versatile set of queries and various representations, that can moreover be efficiently constructed. This will make it significantly cheaper, faster, and more energy-efficient to store and share highly compressible datasets such as DNA collections, thereby fully unlocking the potential of advances in DNA sequencing. The advances of this project will also be integrated into research experience for underrepresented students, as well as outreach to non-computer science students.The main research goals of this project can be broadly classified into the following three directions. First, the project will lead to new efficient algorithms for constructing compressed indexes. The new approach lies in first preprocessing the input using lightly sub-optimal compression and then constructing the final index in compressed time, i.e., time proportional to the precompressed text. Second, the project aims to utilize and improve modern suffix sampling techniques to design new and powerful indexes that are both compressed and able to support powerful queries, including multi-string representations. Finally, the project will study the underdeveloped landscape of lower bounds for compressed indexes. Currently, only the most basic queries, such as random access, are well-understood, and much less is known about lower bounds on more versatile representations or lower bounds for compressed computation.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.