基于分区的Elias-Fano-Golomb-Rice倒排索引压缩算法

doi:10.3969/j.issn.1006-2475.2017.09.007

计算机与现代化

基于分区的Elias-Fano-Golomb-Rice倒排索引压缩算法

北京交通大学计算机与信息技术学院,北京 100044

收稿日期:2016-12-26 出版日期:2017-09-20 发布日期:2017-09-19
作者简介:李俊廷（1991-)，男，安徽阜阳人，北京交通大学计算机与信息技术学院硕士研究生，研究方向：信息检索；瞿有利（1974-），男，高级工程师，博士，研究方向：信息检索。
基金资助:
中央高校基本科研业务费专项资金资助项目（2015JBM035）

A Partitioned Elias-Fano-Golomb-Rice Index Invertal Compression Algorithm

School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China

Received:2016-12-26 Online:2017-09-20 Published:2017-09-19

摘要/Abstract

摘要： 基于分区的Elias-Fano算法被应用于倒排索引压缩，显示出良好的空间压缩性能。本文证明了Golomb-Rice算法的压缩性能优于Elias-Fano算法。结合基于分区的Elias-Fano算法中“分区”思想，提出一种基于分区的Elias-Fano-Golomb-Rice倒排索引压缩算法。实验结果表明，与其他倒排索引压缩算法相比，基于分区的Elias-Fano-Golomb-Rice倒排索引压缩算法有更好的压缩性能。

关键词: 倒排索引, 索引压缩, 分区

Abstract: The partitioned Elias-Fano algorithm was applied to the compression of inverted indexes, showing good compression performance. This paper proves Golomb-Rice algorithm offers better compression than Elias-Fano. Combining with the basic idea ‘partition’ of partitioned Elias-Fano algorithm, we propose partitioned Elias-Fano-Golomb-Rice index compression algorithm. Experimental results show that the partitioned Elias-Fano-Golomb-Rice index compression algorithm provides better compression, compared with partitioned Elias-Fano algorithmand other compression algorithms of inverted indexes.

Key words: inverted index, index compression, partition

中图分类号:

TP391.1

李俊廷，瞿有利. 基于分区的Elias-Fano-Golomb-Rice倒排索引压缩算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2017.09.007.

LI Jun-ting, QU You-li. A Partitioned Elias-Fano-Golomb-Rice Index Invertal Compression Algorithm[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2017.09.007.

参考文献

［1］ Büttcher S, Clarke C L A. Index compression is good, especially for random access［C］// Proceedings of the 16th ACM Conference on Conference on Information and Knowledge Management. 2007:761-770.
［2］ Vigna S. Quasi-succinct indices［C］// Proceedings of the 6th ACM International Conference on Web Search and Data Mining. 2013:83-92.
［3］ Elias P. Universal codeword sets and representations of the integers［J］. IEEE Transactions on Information Theory, 1975,21(2):194-203.
［4］ Anh V N, Moffat A. Inverted index compression using word-aligned binary codes［J］. Information Retrieval, 2005,8(1):151-166.
［5］ Golomb S W. Run-length encodings［J］. IEEE Transactions on Information Theory, 1966,12(3):399-401.
［6］ Rice R, Plaunt J. Adaptive variable-length coding for efficient compression of spacecraft television data［J］. IEEE Transactions on Communication Technology, 1972,19(6):889-897.
［7］ Elias P. Efficient storage and retrieval by content and address of static files［J］. Journal of the ACM (JACM), 1974,21(2):246-260.
［8］ Fano R M. On the number of bits required to implement an associative memory［Z］. Massachusetts Institute of Technology, Project MAC, 1971.
［9］ Sebastiano Vigna. Quasi-succinct indices［C］// ACM International Conference on Web Search & Data Mining. 2012:83-92.
［10］ Stepanov A A, Gangolli A R, Rose D E, et al. SIMD-based decoding of posting lists［C］// Proceedings of the 20th ACM International Conference on Information and Knowledge Management. 2011:317-326.
［11］ Yan Hao, Ding Shuai, Suel T. Inverted index compression and query processing with optimized document ordering［C］// Proceedings of the 18th International Conference on World Wide Web. 2009:401-410.
［12］ Ottaviano G, Venturini R. Partitioned Elias-Fano indexes［C］// Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval. 2014:273-282.
［13］ Wikipedia. Truncated Binary Encoding［EB/OL］. https://en.wikipedia.org/wiki/Truncated_binary_encoding, 2016-10-23.
［14］ Buchsbaum A L, Fowler G S, Giancarlo R. Improving table compression with combinatorial optimization［J］. Journal of the ACM (JACM), 2003,50(6):825-851.

[1]	胡龙,罗军. 基于MapReduce的混合连接算法[J]. 计算机与现代化, 2015, 0(6): 86-91.
[2]	赵敏超;王营冠. 一种针对智能家居中数据采集的改进LEACH算法[J]. 计算机与现代化, 2013, 1(7): 34-039.
[3]	金健;陈群;赵保学. 数据倾斜情况下基于MapReduce模型的连接算法研究[J]. 计算机与现代化, 2013, 1(5): 22-27.
[4]	庞洋;徐巧凤. 基于网格分区确定DBSCAN参数的方法[J]. 计算机与现代化, 2010, 1(5): 16-18.
[5]	邓丽;孙风栋. 基于FAT32的移动电话文件系统研究与实现[J]. 计算机与现代化, 2009, 5(5): 23-0.

基于分区的Elias-Fano-Golomb-Rice倒排索引压缩算法

A Partitioned Elias-Fano-Golomb-Rice Index Invertal Compression Algorithm

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价