倒排索引压缩算法研究综述

Survey on Inverted Index Compressions

不断增长的互联网网页信息和成千上万的用户查询请求给搜索引擎的索引更新和查询访问带来了前所未有的实时性挑战.高效的索引压缩算法能够降低索引数据的存储和传输开销,加快处理器对索引数据的处理速度,因此能直接影响搜索引擎系统的查询性能.首先,概述了倒排索引中倒排链表所包含的d-gap和freq整数序列的存储结构,并依据压缩码字的对齐方式对倒排索引压缩算法进行分类;其次,详细阐述了当前流行的字对齐压缩算法,并总结了Simple、Frame of Reference(FOR)、Optimized Chunk Splitting(OCS)等几类典型的倒排索引压缩算法;之后,综述了倒排索引压缩算法的SIM D并行化研究,即采用SIMD指令集中Shuffle数据置换和垂直布局存储来加速算法对d-gap整数序列的并行处理性能.然后,针对压缩倒排索引的随机访问问题,综述了通常采用的自索引技术和原始序列压缩算法两种策略.最后,对倒排索引压缩算法在搜索引擎系统中的应用进行了分析和总结并对未来倒排索引压缩算法可能的研究方向进行了探讨和展望.

The ever-growing Internet web pages and tens of thousands of user queries have brought about huge challenges to the frequent index updates and real-time query processing in search engines.Efficient index compression algorithms can be used to reduce the costs of index storage and data transfer,as well as to accelerate the speed of CPU processing.In this paper,we present a survey on the techniques and algorithms on inverted index compression in decade,and expect to provide further research directions by classifying and summarizing the existing methods.Firstly,we outline the inverted index structure storing d-gap and freq integer sequences,and categorize the compression algorithms of inverted index according to the alignment of the compressed codewords.Secondly,we detail the most popular word-aligned compression algorithm,and summarize several state-of-the-arts,such as Simple,Frame of Reference(FOR)and Optimized Chunk Splitting(OCS).After that,the random access of the compressed inverted index is reviewed,and two commonused strategies are summarized,which are the self-indexing technique and the original sequence compression algorithms.Then,we reviewa recent research direction of the inverted index compression,i.e.,adopting the SIM D shuffle permutation instruction and vertical layout to parallel the common inverted index compression algorithms.Finally,we summarize the applications of the inverted index compression algorithms in the search engine systems,and discuss the possible future research directions of the inverted index compression.