论文部分内容阅读
在大数据时代，海量数据使得压缩技术变得越来越重要。同样地，对于搜索引擎来讲，高效的压缩算法将会提升倒排索引的查询性能和空间利用率。近十年来，计算机处理器得到了快速发展，提供了性能卓越的SIMD指令集。如果把SIMD指令集应用到搜索引擎索引压缩算法中，将有助于进一步改善搜索引擎的性能。本文使用SIMD指令集对已有倒排索引压缩算法进行两种方式的优化:(1)基于原地优化的SIMD压缩算法。这种方式基本不修改已有算法编码架构，直接对可并行部分使用SIMD指令优化，提出了SIMD-PB，SIMD-PFD，SIMD-Rice和SIMD-Simple算法;(2)基于UPCF的SIMD压缩算法。首先提出一种通用的适于并行的压缩框架UPCF，并将已有压缩算法在UPCF下进行编码结构的修改，使其适于并行化，再应用SIMD指令得到并行算法，如SIMD-Group-Simple，SIMD-Group-Scheme, SIM D-Group-VSEncoding, SIMD-Group-AFOR和SIMD-Group-PFD等。在基于千万网页级别的公开数据集GOV2、ClueWeb09B、Wikipedia和Twitter构建的倒排索引上的实验表明，本文提出的基于SIMD指令集的压缩算法在压缩速度和解压缩速度上均优于对应的串行压缩算法，并具有较好的压缩率和鲁棒性。此外，基于SIMD的压缩算法对倒排索引查询速度也具有提升作用。