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

doi:10.3969/j.issn.1000-3428.2014.02.016

CORC > 北京大学 > 信息科学技术学院

	基于64位体系结构的倒排索引压缩算法; Inverted Index Compression Algorithms Based on 64-bit Architecture
	张旭东 ; 孙志明 ; 刘亚宁 ; 单栋栋 ; 闫宏飞
刊名	计算机工程
	2014
关键词	倒排索引索引压缩 64 位体系结构搜索引擎信息检索 inverted index index compression 64-bit architecture search engine information retrieval
DOI	10.3969/j.issn.1000-3428.2014.02.016
英文摘要	在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); 0; 2; 71-76
语种	中文
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/172403]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	张旭东,孙志明,刘亚宁,等. 基于64位体系结构的倒排索引压缩算法, Inverted Index Compression Algorithms Based on 64-bit Architecture[J]. 计算机工程,2014.
APA	张旭东,孙志明,刘亚宁,单栋栋,&闫宏飞.(2014).基于64位体系结构的倒排索引压缩算法.计算机工程.
MLA	张旭东,et al."基于64位体系结构的倒排索引压缩算法".计算机工程 (2014).