Inverted Index Compression Algorithms Based on 64-bit Architecture

在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.国家自然科学基金资助项目(61272340,61073082)；人人游戏基金资助项目中国科技核心期刊(ISTIC)中国科学引文数据库(CSCD)0271-7