基于空间压缩的外存字符串词典索引算法研究

摘要：

随着大数据时代的到来,大规模的数据需要处理,其中字符串词典数据占据着越来越大的比重.现有的字符串词典索引,不是空间占用过大,就是数据的本地引用性能差,无法高效地应用到外存磁盘环境.针对这些问题,提出了一种具有高效I/O的压缩索引SB-trie,该索引不仅解决了以往索引空间占用过大的问题,同时也具有良好的本地引用性能,能够很好地工作于外存磁盘环境.实验结果表明,相比现有的索引,该索引不仅在空间上得到了有效的压缩,同时在磁盘环境下具有高效的查找性能.

关键词：字符串词典索引、外存数据结构、空间压缩、Trie、大数据处理

所属期刊栏目：31

分类号：TP311.12(计算技术、计算机技术)

资助基金：江苏省自然科学基金No.BK2011281;苏州市应用基础研究计划No.SYG201241

在线出版日期：2015-01-07（万方平台首次上网日期，不代表论文的发表时间）

页码：107-115