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

An Efficient Random Access Block Inverted File Self-Index Technology

作　　者：刘小珠[1,2] 彭智勇[3] 陈旭[3] 

机构地区：[1]武汉大学软件工程国家重点实验室,武汉430072 [2]武汉理工大学自动化学院,武汉430070 [3]武汉大学计算机学院,武汉430072

出　　处：《计算机学报》2010年第6期977-987,共11页Chinese Journal of Computers

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

摘　　要：针对倒排索引空间开销大、查询时间效率低以及难以同时支持连接布尔查询和排序查询的问题,提出了一种同时提高空间效率与查询时间效率的高效随机访问分块倒排文件自索引RABIF.为了在降低空间消耗的同时支持连接布尔查询与排序查询,RABIF将倒排列表进行合理地分块,然后对每个子块的不同部分采用相应的压缩方式,在不需要插入任何附加辅助信息的前提下实现压缩索引的快速定位与随机访问.理论分析及实验结果表明,与忽略倒排文件自索引SIF相比,提出的RABIF空间开销平均减少5.3%,布尔查询时间平均减少17.8%;对于0.2%与1%排序查询,查询时间分别平均减少34.4%与27.5%.In order to overcome the problems of the huge space cost,low query performance and being unable to support conjunctive Boolean query and ranking query simultaneously of inverted index,a time and space efficient random access block inverted file（RABIF） self-index is proposed.To decrease space consumption and support conjunctive Boolean query and ranking query simultaneously,the authors＇ RABIF appropriately divides inverted list into sub-blocks,and then it compresses different parts of each sub-block with corresponding compression method,which makes fast localization and random access of compressed index into reality without inserting any additional auxiliary information.Theoretical analysis and detailed simulation results prove that,compared with existed skipped inverted file（SIF） self-index scheme,the authors＇ RABIF averagely reduces space cost by 5.3%,conjunctive Boolean query time by 17.8%;for 0.2% and 1% ranking queries,RABIF decreases query time averagely by 34.4% and 27.5% respectively.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]