AF: Small: Theoretical Aspects of Repetition-Aware Text Compression and Indexing

AF：小：重复感知文本压缩和索引的理论方面

基本信息

批准号：
2112643
负责人：
Sharma Thankachan
金额：
$ 44.98万
依托单位：
The University of Central Florida Board of Trustees
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-10-01 至 2023-04-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2112643&HistoricalAwards=false
关键词：
AF Small Theoretical Aspects Repetition

项目摘要

Being able to store, search, and analyze massive data sets efficiently is one of today's pressing challenges. To that end, this project will study a collection of problems under text compression and indexing with tremendous current relevance, owing to a specific characteristic prevalent in many modern text data sets, called high repetitiveness. This characteristic makes the data highly compressible using some specialized schemes. However, the theoretical understanding of those schemes is still in a nascent stage. This project will address some of the fundamental open problems on the effectiveness of several schemes that are popular in practice. This project will also introduce new ideas for indexing such data in a highly space-efficient manner and quickly support various (application-specific) queries. The techniques developed in this project will apply to a broad class of algorithmic problems and applications; therefore, they will have a lasting impact on related fields. The main results stem from this research will be disseminated through major conferences, journals, and workshop tutorials. The participation of undergraduates and minorities, including women, will be ensured. Suffix trees and suffix arrays are two fundamental data structures for text indexing with many applications in bioinformatics. However, they are notorious for their space complexity. The FM-index index encodes suffix arrays in space close to the entropy-based lower bound using the Burrows-Wheeler Transformation (BWT). But, the entropy model of compression is less effective in capturing repetitiveness. Therefore, modern applications urge even more space frugal encodings that exploit repetitiveness. Although the community has made some recent progress in exact pattern matching, solutions to many other (more complex) matching problems are still open. To that end, this project will attempt to design repetition-aware indexes for pattern matching under mismatches, edits, and wildcards, along with efficient construction algorithms. This project also aims to develop a unified framework to compress several advanced suffix-tree variants (quasi-suffix trees) that support even more complex matching paradigms such as parameterized and order-isomorphic matching. Novel techniques and concepts that go beyond the existing BWT-based methods will be sought. Additionally, the project will attempt a deeper study on various aspects of BWT-runs and the relative Lempel-Ziv compression scheme from the hardness side.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.

能够有效地存储、搜索和分析海量数据集是当今紧迫的挑战之一。为此，该项目将研究文本压缩和索引下的一系列问题，这些问题与当前具有巨大的相关性，因为许多现代文本数据集中普遍存在一种称为高重复性的特定特征。这一特性使得数据可以使用一些专门的方案进行高度压缩。然而，对这些方案的理论理解仍处于初级阶段。该项目将解决一些关于实践中流行的几种方案有效性的基本开放问题。该项目还将引入以高度节省空间的方式索引此类数据的新想法，并快速支持各种（特定于应用程序的）查询。该项目开发的技术将适用于广泛的算法问题和应用；因此，它们将对相关领域产生持久的影响。这项研究的主要结果将通过主要会议、期刊和研讨会教程进行传播。将确保本科生和包括女性在内的少数民族的参与。后缀树和后缀数组是文本索引的两种基本数据结构，在生物信息学中有许多应用。然而，它们因其空间复杂性而臭名昭著。 FM-index 索引使用 Burrows-Wheeler 变换 (BWT) 对接近基于熵的下界的空间中的后缀数组进行编码。但是，压缩的熵模型在捕获重复性方面效果较差。因此，现代应用程序迫切需要利用重复性的更节省空间的编码。尽管社区最近在精确模式匹配方面取得了一些进展，但许多其他（更复杂）匹配问题的解决方案仍然开放。为此，该项目将尝试设计重复感知索引，用于不匹配、编辑和通配符下的模式匹配，以及高效的构造算法。该项目还旨在开发一个统一的框架来压缩几种高级后缀树变体（准后缀树），这些变体支持更复杂的匹配范例，例如参数化和顺序同构匹配。我们将寻求超越现有基于 BWT 的方法的新技术和概念。此外，该项目将尝试从硬度方面对 BWT 运行和相对 Lempel-Ziv 压缩方案的各个方面进行更深入的研究。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和技术进行评估，被认为值得支持。更广泛的影响审查标准。