Compressed Indexes for Sequence Data: Fast Construction and Dynamism

在计算机科学的不同领域，我们经常需要存储和分析非常大的数据量。尽管计算机变得越来越快，内存越来越大，但高效算法和数据结构的设计并没有失去其重要性。这是我们必须存储的数据越来越大，我们必须解决的问题的计算强度越来越大的结果。在许多处理大量数据的应用中，例如生物信息学和信息检索，数据可以表示为符号序列（字符串）或这些序列的集合。这个建议的重点是有效的数据结构存储和处理非常大量的顺序数据。******空间的使用在高效算法的设计中起着关键作用。如果我们能够找到一种空间高效的数据表示方式，我们就可以将更大一部分数据放入主内存或缓存中，并减少对辅助内存的访问操作次数。这就提出了处理以压缩形式存储的数据的算法和数据结构的问题。尽管对压缩数据的操作成本可能更高，但算法通常更有效：减少了内存层次结构不同级别之间的数据传输数量。这将带来超过计算开销的性能增益。处理结构化压缩数据（字符串、树、图）的算法是一个蓬勃发展的研究领域。******这个提议的主题是字符串索引的压缩表示。字符串索引是一种数据结构，用于存储符号序列并回答该序列上的模式匹配查询。字符串索引及其变体在处理字符串数据的算法中无处不在。虽然在这个问题上已经有了大量的工作，但许多具有实际意义的重要问题仍然没有解决。在这个项目中，我将重点关注压缩索引的两个方面，这两个方面与必须频繁更改数据的场景相关：(1)字符串索引的空间高效和快速构建算法；(2)字符串索引的动态支持。******我和我的学生将学习有效的算法来构建空间高效和紧凑的索引结构。将特别注意这些算法的空间使用以及它们与其他计算模型的关系。我和我的学生还将研究支持模式匹配查询的动态数据结构的性能，以及对以压缩形式存储的字符串数据的一些更复杂的查询。对结构化数据的严格研究是本提案的中心主题。但我和我的小组也会关注数据存储方法的实际方面。实际效率将通过实施我们的一些成果来检验。因此，我的研究项目具有立即应用和推动加拿大软件产业发展的潜力

Situations when we need to store and analyze very large data volumes frequently arise in different areas of Computer Science. Although computers are becoming faster and memory size is getting larger, the design of efficient algorithms and data structures is not losing its importance. This is a consequence of the growing size of the data that we must store and computational intensity of problems that we must solve. In many applications working with massive data, such as bioinformatics and information retrieval, the data can be represented as a sequence of symbols (string) or as a collection of such sequences. This proposal focuses on efficient data structures for storage and processing of very large volumes of sequential data. ******Space usage plays a key role in the design of efficient algorithms. If we are able to find a space-efficient representation of the data, we can fit a larger fraction of data into the main memory or cache and reduce the number of access operations to the secondary memory. This raises the question about algorithms and data structures that work with data that is stored in compressed form. Although operations on compressed data can be more costly, the algorithms are frequently more efficient: The number of data transfers between different levels of the memory hierarchy is reduced. This results in a performance gain that outweighs the computational overhead. The study of algorithms for processing structured compressed data (strings, trees, graphs) is a thriving research area. ******The topic of this proposal is compressed representation of string indexes. A string index is a data structure that stores a sequence of symbols and answers pattern matching queries on this sequence. The string index and its variants are ubiquitous in algorithms working on string data. Although there is already a large body of work on this subject, many important questions with practical relevance are still open. In this project I will concentrate on two aspects of compressed indexes that are relevant in scenarios when the data must be changed frequently: (1) space-efficient and fast construction algorithms for string indexes and (2) support of dynamism in string indexes. ******I and my students will study efficient algorithm for constructing space-efficient and compact index structures. Special attention will be given to the space usage of these algorithms and to their relation with other models of computation. My students and I will also study the performance of dynamic data structures supporting pattern matching queries and some more involved queries on string data that is stored in compressed form. Rigorous study of structured data is the central topic of this proposal. But my group and I will also pay attention to practical aspects of data storage methods. Practical efficiency will be tested by implementing some of our results. Thus my research program has potential for immediate application and for advancing software industry in Canada.*