Succinct Data Structures with Applications to Large Data Sets

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

• 批准号: RGPIN-2018-05581
• 负责人: He, Meng
• 金额: $ 2.04万
• 依托单位: Dalhousie University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=682826
• 关键词: 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高效算法来最小化内存和辅助存储之间的数据传输，而二级存储通常是计算成本的主导因素。隐式数据结构的思想是在可能的情况下将数据结构编码为其数据元素的排列，从而不需要额外的空间。自适应算法旨在提高对具有更多内在排序的数据的查询效率。并行算法使用多个处理器来实现加速比。我们的工作表明，这些技术和简洁的结构可以结合在一起，为大数据集提供更有效的解决方案，一种技术的进步可能会给另一种技术带来新的结果。*为网络搜索引擎、地理信息系统和生物信息学应用等处理大数据集的现代系统提供理论和实践解决方案，该计划将扩展对简洁数据结构的研究，并开启这一主题的新研究方向。这项拟议的研究将使用简洁的数据结构来开发算法和计算几何中的基本问题的新解决方案，如文本搜索和范围搜索。这项研究不仅将产生比以前工作中设计的数据结构更高效的新数据结构，还将提高标准数据结构的查询和更新效率；后者是通过利用简洁数据结构的紧凑性来存储更多的结构化信息来实现的，从而在不增加空间成本的情况下加快操作。我们还将开始一项新的研究，为生物信息学应用设计简洁的数据结构。