Succinct Data Structures with Applications to Large Data Sets

简洁的数据结构及其在大数据集上的应用

• 批准号: 418613-2012
• 负责人: He, Meng
• 金额: $ 1.6万
• 依托单位: Dalhousie University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=573745
• 关键词: Succinct; Data; Structures; Applications; Large

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.

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