Development of Practical Succinct Data Structures with Application to Huge Data

开发适用于大数据的实用简洁数据结构

• 批准号: 19680001
• 负责人: SADAKANE Kunihiko
• 金额: $ 12.15万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (A)
• 财政年份: 2007
• 资助国家: 日本
• 起止时间: 2007 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-19680001/
• 关键词: データ圧縮; 情報検索; 文字列検索; 簡潔データ構造; 接尾辞配列; 接尾辞木; 圧縮接尾辞配列; 順序木; アルゴリズム理論; データ構造

There had been only theoretical researches on succinct data structures. In this research, we have developed succinct data structures which solve the problems of using them on actual computers. For ordinal trees, we have reduced the size of succinct data structures by 40%, while supporting various operations which had not been supported in existing data structures. We have also created a library of compressed suffix arrays and compressed suffix trees, which are succinct data structures for string searches. By using it, we can reduce the size of the data structure, which is used for searching text data of 110 Gigabytes, from 680 Gigabytes to 22 Gigabytes.

此前只有简洁数据结构的理论研究。在这项研究中，我们开发了简洁的数据结构，解决了在实际计算机上使用它们的问题。对于序数树，我们将简洁数据结构的大小减少了 40%，同时支持现有数据结构不支持的各种操作。我们还创建了一个压缩后缀数组和压缩后缀树的库，它们是用于字符串搜索的简洁数据结构。通过使用它，我们可以将用于搜索 110 GB 文本数据的数据结构的大小从 680 GB 减少到 22 GB。

项目成果

Random Access to grammar-Compressed Strings

随机访问语法压缩字符串

• 发表时间: 2011
• 作者: Philip Bille; Gad M.L;au; Rajeev Raman; Kunihiko Sadakane; Srinivasa Rao Satti; Oren Weimann
• 通讯作者: Oren Weimann

Breaking a Time-and-Space Barrier in Constructing Full-Text Indices

打破全文索引构建的时空障碍

• 发表时间: 2009
• 作者: W.K.Hon; K.Sadakane; W.K.Sung
• 通讯作者: W.K.Sung

動的簡潔順序木

动态简洁有序树

• 发表时间: 2009
• 作者: 定兼邦彦

括弧列の簡単・簡潔な表現法

一种简单简洁的括号表达方式

• 发表时间: 2008
• 作者: 定兼邦彦

高速復元可能な接尾辞配列圧縮法

快速恢复的后缀数组压缩方法

• 发表时间: 2010
• 作者: 田中洋輔; 小野廣隆; 定兼邦彦; 山下雅史
• 通讯作者: 山下雅史