计算机工程

• 体系结构与软件技术 • 上一篇    下一篇

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

张旭东1,孙志明2,刘亚宁1,单栋栋1,闫宏飞1   

  1. (1. 北京大学网络与信息系统研究所,北京 100871;2. 哈尔滨医科大学附属第一医院信息中心,哈尔滨 150001)
  • 收稿日期:2012-12-17 出版日期:2014-02-15 发布日期:2014-02-13
  • 作者简介:张旭东(1989-),男,硕士研究生,主研方向:网络数据挖掘,信息检索;孙志明,工程师;刘亚宁,硕士研究生;单栋栋,博士研究生;闫宏飞,副教授
  • 基金项目:
    国家自然科学基金资助项目(61272340, 61073082);人人游戏基金资助项目(QXWJ-YX-201206017)

Inverted Index Compression Algorithms Based on 64-bit Architecture

ZHANG Xu-dong 1, SUN Zhi-ming 2, LIU Ya-ning 1, SHAN Dong-dong 1, YAN Hong-fei 1   

  1. (1. Institute of Network Computing and Information Systems, Peking University, Beijing 100871, China; 2. Information Center of the First Affiliated Hospital of Harbin Medical University, Harbin 150001, China)
  • Received:2012-12-17 Online:2014-02-15 Published:2014-02-13

摘要: 在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%。

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

Abstract: 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.

Key words: inverted index, index compression, 64-bit architecture, search engine, information retrieval

中图分类号: