A Partition Inverted Index Compression Algorithm Based on CRF

doi:10.3969/j.issn.1006-2475.2024.02.006

Abstract

Abstract: Abstract： The inverted index is the core data structure of a large search engine， which is essentially a collection of integer sequences in an inverted table. Inverted index compression can effectively reduce the space occupied by inverted indexes and improve retrieval efficiency of keywords. The partition inverted index compression algorithm based on conditional random field （CRF） mainly focuses on the partition mode of universe partition. The algorithm pre-partitions the sequence and uses conditional random fields to label and reorganize the pre-partitions， which effectively reduces the compression time. According to the partition type， the algorithm uses the corresponding encoding method to further reduce the space occupation after compression. Compared with other inverted index compression algorithms， this algorithm outperforms some current universe partition algorithms in compression ratio， and is equivalent to other universes partition algorithms in decompression time. The algorithm achieves a good balance between time and space.

Key words: Key words： inverted index, data compression, universe partition, conditional random field, search engines

CLC Number:

TP311

WANG Zi-chen, QU You-li. A Partition Inverted Index Compression Algorithm Based on CRF[J]. Computer and Modernization, 2024, 0(02): 36-42.

References

［1］ ILIC M， SPALEVIC P， VEINOVIC M. Inverted index search in data mining［C］// 2014 22nd Telecommunications Forum Telfor （TELFOR）. 2014：943-946.
［2］ SHIN Y， AHN J， IM D H. Join optimization for inverted index technique on relational database management systems［J］. Expert Systems with Applications， 2022，198. DOI: 10.1016/j.eswa.2022.116956.
［3］ WANG H， YUAN Q P， HU W H， et al. A new subsequence similarity retrieval method based on inverted index in EAST［J］. Fusion Engineering and Design， 2022，182. DOI: 10.1016/j.fusengdes.2022.113246.
［4］ CATENA M， MACDONALD C， OUNIS I. On inverted index compression for search engine efficiency［C］// Advances in Information Retrieval. 2014：359-371.
［5］ PIBIRI G E， VENTURINI R. Techniques for inverted index compression［J］. ACM Computing Surveys， 2020，53（6）. DOI: 10.1145/3415148.
［6］ CHMIELOWIEC A， LITWIN P. Efficient inverted index compression algorithm characterized by faster decompression compared with the Golomb-rice algorithm［J］. Entropy， 2021，23（3）. DOI： 10.3390/e23030296.
［7］ LIU X Z， PENG Z Y. An efficient random access inverted index for information retrieval［C］// Proceedings of the 19th International Conference on World Wide Web. 2010：1153-1154.
［8］ ELIAS P. Efficient storage and retrieval by content and address of static files［J］. Journal of the ACM， 1974，21（2）：246-260.
［9］ PIBIRI G E. On slicing sorted integer sequences［J］. arXiv preprint arXiv：1907.01032， 2019.
［10］ CHAMBI S， LEMIRE D， KASER O， et al. Better bitmap performance with roaring bitmaps［J］. Software Practice and Experience， 2014，46（5）：709-719.
［11］ ANH V N， MOFFAT A. Improved word-aligned binary compression for text indexing［J］. IEEE Transactions on Knowledge and Data Engineering， 2006，18（6）：857-861.
［12］ ANH V N， MOFFAT A. Index compression using fixed binary codewords［C］// Proceedings of the 15th Australasian Database Conference-Volume 27. 2004：61-67.
［13］ ZUKOWSKI M， HEMAN S， NES N， et al. Super-scalar RAM-CPU cache compression［C］// 22nd International Conference on Data Engineering （ICDE’06）.2006. DOI: 10.1109/ICDE.2006.150.
［14］ RICE R， PLAUNT J. Adaptive variable-length coding for efficient compression of spacecraft television data［J］. IEEE Transactions on Communication Technology， 1971，19（6）：889-897.
［15］ KAUSHIK R， KRISHNAMURTHY R， NAUGHTON J F， et al. On the integration of structure indexes and inverted lists［C］// Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. 2004：779-790.
［16］ MAHAPATRA A K， BISWAS S. Inverted indexes： Types and techniques［J］. International Journal of Computer Science Issues， 2011，8（4）：384-392.
［17］ DING S， ATTENBERG J， SUEL T. Scalable techniques for document identifier assignment in inverted indexes［C］// Proceedings of the 19th International Conference on World Wide Web. 2010：311-320.
［18］ SONG X S， YANG Y X， JIANG Y， et al. Optimizing partitioning strategies for faster inverted index compression［J］. Frontiers of Computer Science. 2019，13（2）：343-356.
［19］ PIBIRI G E， PETRI M， MOFFAT A. Fast dictionary-based compression for inverted indexes［C］// Proceedings of the 12th ACM International Conference on Web Search and Data Mining. 2019：6-14.
［20］ LEMIRE D， SSI-YAN-KAI G， KASER O. Consistently faster and smaller compressed bitmaps with roaring［J］. arXiv preprint arXiv：1603.06549， 2016.
［21］ 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.
［22］ SUTTON C， MCCALLUM A. An introduction to conditional random fields［J］. arXiv preprint arXiv：1011.4088， 2010.
［23］ LAFFERTY J D， MCCALLUM A， PEREIRA F C N. Conditional random fields： Probabilistic models for segmenting and labeling sequence data［C］// Proceedings of the 18th International Conference on Machine Learning. 2001：282-289.
［24］ VOGEL S， NEY H， TILLMANN C. HMM-based word alignment in statistical translation［C］// Proceedings of the 16th Conference on Computational Linguistics-Volume 2. 1996：836-841.
［25］ VIGNA S. Quasi-succinct indices［C］// Proceedings of the 6th ACM International Conference on Web Search and Data Mining. 2013：83-92.
［26］ SHREE M R， SHAMBHAVI B R. POS tagger model for kannada text with CRF++ and deep learning approaches［J］. Journal of Discrete Mathematical Sciences and Cryptography， 2020，23（2）：485-493.
［27］ SILVESTRI F. Sorting out the document identifier assignment problem［C］// Advances in Information Retrieval. 2007：101-112.

[1]	ZHENG Li-rui, XIAO Xiao-xia, ZOU Bei-ji, LIU Bin, ZHOU Zhan. Named Entity Recognition in Electronic Medical Record Based on BERT [J]. Computer and Modernization, 2024, 0(01): 87-91.
[2]	WANG Yun-qian, WANG Yi-song, CHEN Pan-feng, ZOU Long. Named Entity Recognition of Medicinal Plant Texts Integrated with Attention Mechanism [J]. Computer and Modernization, 2021, 0(11): 100-105.
[3]	SHAO Shi-yun, ZHOU Yu, YANG Lei, ZHONG Mao-sheng, DAI Rui, ZHAO Jia-le. An Efficient Entity Identification Method for Electric Bidding Documents Based on Conditional Random Field [J]. Computer and Modernization, 2020, 0(12): 72-77.
[4]	WANG Rui1, HAN Rui2, Jia Yu-xiang1. #br# Distributed Big Data Machine Learning Algorithms Based on Spark [J]. Computer and Modernization, 2018, 0(11): 119-.
[5]	ZHANG Lei. Research on Named Entity Recognition Method in Specific Fields [J]. Computer and Modernization, 2018, 0(03): 60-.
[6]	ZHANG Jian, WU Qing, YANG Xin-yi, WANG Bin-cong, WU Xuan-wei, XU Xiang-ying, LYU Qiang. Chinese Agricultural Named Entity Recognition Based on Conditional Random Fields [J]. Computer and Modernization, 2018, 0(01): 123-126.
[7]	SHENG Shen-yang, HE Xin. Design of Information Management System for Distributed Generation Monitoring [J]. Computer and Modernization, 2017, 0(1): 89-95.
[8]	DAI Yang, CHEN Fang. Data Compression Algorithm in Real-time Database [J]. Computer and Modernization, 2016, 0(6): 123-126.
[9]	TIAN Hong-zhou1,2, YING Bei-hua2. Analysis and Research on Performance of Compression Algorithm #br# Based on Lifting Scheme Wavelet Transform in WSN [J]. Computer and Modernization, 2015, 0(9): 81-89.
[10]	ZENG Liancheng, ZHOU Xiaoyun. Approach to Data Compression Based on Waveform Storage Infrared Remote Control Transmitter [J]. Computer and Modernization, 2014, 0(4): 195-198.
[11]	YANG Yong-jun;XU Jiang;SHU Yi;XU Shuai. Research on Lossless Data Compression Algorithm for Historical Data of Real-time Database [J]. Computer and Modernization, 2012, 1(6): 165-168.
[12]	YOU Hong-tao;ZHANG Yan-yuan;LIU Sheng. Research on Efficient Storage Optimization of Linux [J]. Computer and Modernization, 2012, 1(11): 62-65.
[13]	JIANG Wen-zhi;GU Jiao-jiao;HU Wen-xuan;LI Fei. Research on Applications of Conditional Random Fields and Its Improvement [J]. Computer and Modernization, 2011, 1(11): 55-4.
[14]	SHAO Yanling;LU Qingbin. Application and Research of Live Broadcast Teaching System  Based on IP Multicast Transmission [J]. Computer and Modernization, 2010, 1(12): 98-101.
[15]	LI Xing;JIANG Zhi-nong. SAR Raw Data Compression Based on Lifting Wavelet Transform and Block Adaptive Quantization [J]. Computer and Modernization, 2009, 1(10): 10-4.