Succinct Data Structures with Applications to Large Data Sets

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

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

As the size of the data has grown rapidly in recent years, many techniques that were useful for small, older systems have become outdated for large, modern applications, since they occupy too much space to fit into faster levels of memory hierarchy. 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. My main research interests are in the design of succinct data structures to represent fundamental structures such as strings, binary relations, trees and graphs, as well as the design of space-efficient solutions to geometric query problems, text indexing and classic query problems over trees and arrays. My research also involves other algorithmic techniques that can be applied to large data sets. When data are too big to fit in internal memory, I/O-efficient algorithms can be used to minimize the data transfer between internal memory and secondary storage which often dominates computational cost. The idea of implicit data structures is to encode a data structure as a permutation of its data elements if possible, so that no additional space is required. Adaptive algorithms aim at improving query efficiency for data with more inherent sortedness. Parallel algorithms use multiple processors to achieve speedup. Our work shows that these techniques and succinct structures can be combined to provide more efficient solutions for large data sets, and the advancement in one technique may lead to new results for another.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. Not only will this research yield new data structures that are more space-efficient than those designed in previous work, it will also improve the query and update efficiency of standard data structures; the latter is achieved by exploiting the compactness of succinct data structures to store more structural information to speed up operations without increasing the space cost. We will also start a new line of research by designing succinct data structures for bioinformatics applications.

近年来，随着数据量的快速增长，许多对小型旧系统有用的技术对于大型现代应用程序来说已经过时，因为它们占用太多空间，无法适应更快的内存层次结构。这些空间中的大部分不是原始数据，而是为了提高搜索效率而添加的结构化信息。为了解决这个问题，人们提出了简洁的数据结构，这样可以快速地检索大型系统中的信息，但所需的空间比原始数据多一点。我的主要研究兴趣是设计简洁的数据结构来表示基本结构，如字符串，二元关系，树和图，以及设计几何查询问题，文本索引和经典查询问题的空间高效解决方案。我的研究还涉及其他可以应用于大型数据集的算法技术。当数据太大而无法容纳在内部存储器中时，可以使用I/O高效算法来最小化内部存储器和辅助存储器之间的数据传输，这通常主导计算成本。隐式数据结构的思想是尽可能将数据结构编码为其数据元素的排列，这样就不需要额外的空间。自适应算法的目的是提高查询效率的数据具有更多的内在排序。并行算法使用多个处理器来实现加速。我们的工作表明，这些技术和简洁结构可以结合起来，为大数据集提供更有效的解决方案，一种技术的进步可能会导致另一种技术的新结果。为了为处理大数据集的现代系统提供理论和实践解决方案，如网络搜索引擎，地理信息系统和生物信息学应用，该计划将扩展简洁数据结构的研究，并在这个课题上开始新的研究方向。拟议中的研究将使用简洁的数据结构来开发新的解决方案，以解决算法和计算几何中的基本问题，如文本搜索和范围搜索。这项研究不仅会产生新的数据结构，比以前的工作中设计的空间效率更高，它也将提高查询和更新效率的标准数据结构;后者是通过利用简洁的数据结构的紧凑性来存储更多的结构信息，以加快操作，而不增加空间成本。我们还将通过为生物信息学应用设计简洁的数据结构来开始新的研究路线。