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

doi:10.3969/j.issn.1006-2475.2017.09.007

Abstract

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

CLC Number:

TP391.1

LI Jun-ting, QU You-li. A Partitioned Elias-Fano-Golomb-Rice Index Invertal Compression Algorithm[J]. Computer and Modernization, 2017, 0(9): 33-39.

References

［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]	WANG Zi-chen, QU You-li. A Partition Inverted Index Compression Algorithm Based on CRF [J]. Computer and Modernization, 2024, 0(02): 36-42.
[2]	ZENG Yi-pu, DAI Yi-ru, CHEN Yu-tian. Dynamic Particle Swarm Optimization without Velocity Based on Opposition-based Learning and Elite Promotion [J]. Computer and Modernization, 2023, 0(03): 113-120.
[3]	YUAN Jia-li, LIU Meng-chi. Dynamic Data Partition Algorithm for Information Network Model [J]. Computer and Modernization, 2022, 0(10): 100-105.
[4]	XU Xin-qiang, HE Peng, . Enhance Flexibility of Graph Convolutional Filter Based on Graph Filter Framework [J]. Computer and Modernization, 2022, 0(03): 103-110.
[5]	LI Yu-bin, YU Tao. Phase Partition of Batch Process Based on Instantaneous Frequency Response Function [J]. Computer and Modernization, 2022, 0(02): 65-69.
[6]	CHEN Yi-jun, CAO Luo-wei, DU Yu-qian. Improvement of Fuzzy C-Means Clustering Algorithm Based on Self-paced Data Reconstruction Regularization [J]. Computer and Modernization, 2020, 0(06): 120-.
[7]	JIANG Kai-hua1,2, SUN Peng1,2, HAN Rui1. A Cloud Application Decomposition Method Combining GWO with FM Algorithm [J]. Computer and Modernization, 2020, 0(01): 53-.
[8]	OU Qing-fang, XIE Huo-sheng. Fabric Defect Detection Based on Image Reconstruction with Auto-encoder [J]. Computer and Modernization, 2019, 0(01): 27-.
[9]	CAO Xue， WANG Jian-lin， HAN Rui， QIU Ke-peng， LIU Wei-min. Fault Detection of Multi-phase Batch Processes Based on PARAFAC2 Phase Partition [J]. Computer and Modernization, 2018, 0(11): 23-.
[10]	JU Shu-cun1,2, CHENG Wen-jie1,2, XU Jian-peng2, XU Xiang2, XU Yang2. A Fast Clustering Algorithm Based on Cluster-centers and Partition [J]. Computer and Modernization, 2018, 0(08): 16-.
[11]	ZHU Hai-yang1, XU Gen-jiu2, LI Yuan-chen1, ZHANG Meng-qi2. Dynamic Threshold Selection of Local Region Based on Image Partition [J]. Computer and Modernization, 2016, 0(11): 53-57.
[12]	HU Long, LUO Jun. Hybrid Join Algorithm Based on MapReduce [J]. Computer and Modernization, 2015, 0(6): 86-91.
[13]	LIU Che, LIU Xuan, MA Hong-xu. A FCM-based Domain Partition Method for Time Series Data Set [J]. Computer and Modernization, 2015, 0(5): 9-12.
[14]	LIU Shu-ying. A Top-k Closest Pairs Data Search Scheme Based on MapReduce [J]. Computer and Modernization, 2014, 0(8): 38-45.
[15]	ZHAO Min-chao;WANG Ying-guan. An Improved LEACH Algorithm for Smart Home Data Acquisition [J]. Computer and Modernization, 2013, 1(7): 34-039.