高效的随机访问分块倒排文件自索引技术

摘要：

针对倒排索引空间开销大、查询时间效率低以及难以同时支持连接布尔查询和排序查询的问题,提出了一种同时提高空间效率与查询时间效率的高效随机访问分块倒排文件自索引RABIF.为了在降低空间消耗的同时支持连接布尔查询与排序查询,RABIF将倒排列表进行合理地分块,然后对每个子块的不同部分采用相应的压缩方式,在不需要插入任何附加辅助信息的前提下实现压缩索引的快速定位与随机访问.理论分析及实验结果表明,与忽略倒排文件自索引SIF相比,提出的RABIF空间开销平均减少5.3%,布尔查询时间平均减少17.8%;对于0.2%与1%排序查询,查询时间分别平均减少34.4%与27.5%.

关键词：倒排文件、自索引、时间效率、空间效率、随机访问

所属期刊栏目：33

分类号：TP391(计算技术、计算机技术)

资助基金：国家"九七三"重点基础研究发展规划项目基金2007CB310806;国家自然科学基金60573095;武汉大学2008年博士研究生自主科研项目20086350101000066

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

页数：共11页

页码：977-987