Succinct Data Structures with Applications to Large Data Sets

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

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

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