CAREER: Scalable and Flexible Indexing of Compressed Sequences

职业：压缩序列的可扩展且灵活的索引

• 批准号: 2337891
• 负责人: Dominik Kempa
• 金额: $ 59.82万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-03-01 至 2029-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2337891&HistoricalAwards=false
• 关键词: CAREER; Scalable; Flexible; Indexing; Compressed

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.

无损数据压缩是一项经典且普遍存在的任务，可降低数据的大小，导致转移或档案的成本降低。但是，现代应用不仅仅需要压缩。在诸如计算生物学之类的领域中，高度可压缩数据的Terabytes以越来越多的速率生成。为了充分利用这些数据，它不仅需要存储在一个小空间中，而且还需要访问和可搜索。近年来，目睹了可以完成这项任务的数据结构的诞生，称为“压缩索引”。但是，到目前为止，这项研究主要集中在静态索引上，遗漏了重要方面，例如对更新和有效构造的支持。该项目的总体目标是开发功能强大的，动态的压缩索引，能够处理一套多功能的查询和各种表示形式，这些索引可以有效地构建。这将使存储和共享高度可压缩数据集（例如DNA收集）的便宜，更快，更节能，从而完全释放了DNA测序中进步的潜力。该项目的进步还将纳入代表性不足的学生以及向非计算机科学专业学生推广的研究经验中。该项目的主要研究目标可以广泛分为以下三个方向。首先，该项目将导致用于构建压缩索引的新有效算法。新方法在于首先使用轻度亚最佳压缩的输入进行预处理，然后在压缩时间（即与预制文本成比例的时间）中构造最终索引。其次，该项目旨在利用和改进现代后缀采样技术来设计新的和强大的索引，这些索引既可以压缩又能够支持强大的查询，包括多弦表示。最后，该项目将研究压缩索引的下限的欠发达景观。当前，只有最基本的查询，例如随机访问，才被理解得很厉害，对更广泛的表示的下限或压缩计算的下限知之甚少。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的审查标准来通过评估来通过评估来获得支持的。