基于64位体系结构的倒排索引压缩算法  

Inverted Index Compression Algorithms Based on 64-bit Architecture

作　　者：张旭东[1] 孙志明[2] 刘亚宁[1] 单栋栋[1] 闫宏飞[1] 

机构地区：[1]北京大学网络与信息系统研究所,北京100871 [2]哈尔滨医科大学附属第一医院信息中心,哈尔滨150001

出　　处：《计算机工程》2014年第2期71-76,共6页Computer Engineering

基　　金：国家自然科学基金资助项目(61272340;61073082);人人游戏基金资助项目(QXWJ-YX-201206017)

摘　　要：在64位体系结构的CPU中,字长从32位扩展到64位,处理器每次可以处理的数据也增加到64位。这对搜索引擎使用的核心数据结构——倒排索引的压缩与解压缩带来一定的影响。针对当前32位整数字对齐压缩算法Simple不适用于64位系统的问题,对其进行改进,并提出3种基于64位的字对齐压缩算法,即SimpleX64-16、SimpleX64-32和SimpleX64-64。3种算法都采用多种压缩模式,并对每个模式进行压缩空间的优化。在64位机器上GOV2和ClueWeb09B数据集的倒排索引实验结果表明,与传统的基于32位字对齐的压缩算法相比,3种基于64位字对齐的算法在解压速度方面最多提高14.5%,在压缩率方面最多提高2.5%。In the 64-bit architecture of the CPU, the word length extends from 32 bit to 64 bit, and the data which CPU can process each time also increases to 64 bit. Few studies are performed to date to answer what influences 64-bit systems have on the compression and decompression of inverted index, which is the primary data structure in search engines. Some compression algorithms of posting lists work well on 32-bit machines, but are inefficient on 64-bit machines. This paper proposes three word-aligned compression algorithms on 64-bit system, namely, SimpleX64-16, SimpleX64-32 and SimpleX64-64. It adopts more modes and optimizes each mode for each algorithm. Experiments based on inverted index of GOV2 and ClueWeb09B show that those algorithms can improve compression ratio by 2.5% and decompression rate by 14.5%, compared with the traditional 32-bit word-aligned compression algorithms, on 64-bit machines.

关 键 词：倒排索引 索引压缩 64位体系结构 搜索引擎 信息检索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]