Succinct Data Structures with Applications to Large Data Sets

有效地存储和检索信息是计算机科学中的一个重要课题。在过去的几十年里，已经开发了各种技术来索引数据，从而可以通过执行对关键字或短语的查询来几乎即时地检索有用的信息。近年来，随着数据大小的快速增长，许多对小而旧的系统有用的技术已经变得不适用于大型的现代应用程序，因为它们占用了太多的存储空间。这些空间中的大部分不是原始数据，而是为提高搜索效率而添加的结构性信息。为了解决这一问题，人们提出了简洁的数据结构，以便快速检索大型系统中的信息，但空间需求与原始数据相差不大。 为了给网络搜索引擎、地理信息系统和生物信息学应用等处理大数据集的现代系统提供理论和实用的解决方案，本项目将扩展对简洁数据结构的研究，并开启这一主题的新的研究方向。这项拟议的研究将使用简洁的数据结构来为算法和计算几何中的基本问题开发新的解决方案，例如文本搜索和范围搜索。这将开启一个新的研究方向，即使用缓存无关模型来提高存储在外部存储器中的大数据集处理应用程序的简洁数据结构的I/O效率。它还将开始一项新的研究，通过为生物信息学应用程序和文本数据库设计简洁的数据结构，解决在这些系统中执行的有用类型的搜索，如近似搜索。此外，还将进行算法工程，以研究我们解决方案在实践中的效率，并将代码贡献给处理简洁数据结构的软件库，使其更加完整，从而对软件开发更有用。

The problem of efficiently storing and retrieving information is an essential topic in computer science. During the past decades, various techniques have been developed to index data so that the useful information can be retrieved almost instantaneously by performing queries for keywords or phrases. In recent years, as the size of the data has grown rapidly, many techniques that were useful for small, older systems have become infeasible for large, modern applications because they occupy too much storage. Most of this space is not the raw data, but structural information added to improve search efficiency. Succinct data structures were proposed to address this problem, so that the information in large systems can be retrieved quickly, but the space requirement is little more than that of the raw data. In order to provide theoretical and practical solutions to modern systems that process large data sets such as web search engines, geographic information systems and bioinformatics applications, this program will extend the research on succinct data structures, and start new research directions on this subject. The proposed research will use succinct data structures to develop new solutions to fundamental problems in algorithms and computational geometry, such as text search and range search. It will start a new research direction that uses cache-oblivious model to improve the I/O efficiency of succinct data structures for applications that deal with large data sets stored in external memory. It will also start a new line of research by designing succinct data structures for bioinformatics applications and text databases by addressing useful types of searches performed in these systems, such as approximate search. In addition, algorithm engineering will be performed to study the efficiency of our solutions in practice, and code will be contributed to software libraries that deal with succinct data structures, to make them more complete and hence more useful for software development.