权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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索引使用Burrows-Wheeler变换（BWT）在接近基于熵的下限的空间中对后缀数组进行编码。但是，压缩的熵模型在捕获重复性方面不太有效。因此，现代应用程序甚至敦促更多的节省空间的编码，利用重复性。虽然社区最近在精确模式匹配方面取得了一些进展，但许多其他（更复杂）匹配问题的解决方案仍然是开放的。为此，本项目将尝试设计重复感知索引，用于在不匹配、编辑和通配符下进行模式匹配，并使用沿着的高效构造算法。该项目还旨在开发一个统一的框架来压缩几个高级后缀树变体（准后缀树），这些变体支持更复杂的匹配范例，例如参数化和顺序同构匹配。将寻求超越现有基于BWT的方法的新技术和概念。此外，该项目将尝试从硬度方面对BWT运行的各个方面以及相对的Lempel-Ziv压缩方案进行更深入的研究。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。