Succinct Data Structures with Applications to Large Data Sets

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

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

有效地存储和检索信息的问题是计算机科学中的一个重要课题。在过去的几十年中，已经开发了各种技术来索引数据，以便通过对关键字或短语执行查询几乎可以立即检索到有用的信息。近年来，随着数据规模的迅速增长，许多适用于小型旧系统的技术对于大型现代应用程序来说变得不可行，因为它们占用了太多的存储空间。这些空间中的大部分不是原始数据，而是为了提高搜索效率而添加的结构化信息。为了解决这个问题，人们提出了简洁的数据结构，这样可以快速地检索大型系统中的信息，但所需的空间比原始数据多一点。