Inverted index compression and query processing with optimized document ordering
Inverted index compression and query processing with optimized document ordering
复制标题
DOI：
10.1145/1526709.1526764
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
Hao Yan;Shuai Ding;Torsten Suel
中科院分区：
文献类型：
--
作者：
Hao Yan;Shuai Ding;Torsten Suel
Web搜索引擎使用高度优化的压缩方案来减少倒排索引的大小并提高查询吞吐量，并且文献中已经研究了许多索引压缩技术。最近几项研究所采用的一种方法首先对集合中的文档ID进行重新编号，将相似的文档分组在一起，然后应用标准压缩技术。众所周知，与随机文档排序相比，这可以显著提高索引压缩。我们研究索引压缩和查询处理技术，这样的重排序索引。以前的工作集中在确定文件的最佳顺序。相反，我们假设这样的排序已经给出，并专注于如何优化压缩方法和查询处理这种情况下。我们对文档ID的压缩技术进行了广泛的研究，并对现有技术进行了新的优化，可以显着提高压缩和解压缩性能。我们还提出了这种情况下，压缩频率值的技术和评估。最后，我们研究了这种方法对查询处理性能的影响。我们的实验表明，非常显着的改进，索引大小和查询处理速度的TREC GOV2收集的2520万个网页。
Web search engines use highly optimized compression schemes to decrease inverted index size and improve query throughput, and many index compression techniques have been studied in the literature. One approach taken by several recent studies first performs a renumbering of the document IDs in the collection that groups similar documents together, and then applies standard compression techniques. It is known that this can significantly improve index compression compared to a random document ordering. We study index compression and query processing techniques for such reordered indexes. Previous work has focused on determining the best possible ordering of documents. In contrast, we assume that such an ordering is already given, and focus on how to optimize compression methods and query processing for this case. We perform an extensive study of compression techniques for document IDs and present new optimizations of existing techniques which can achieve significant improvement in both compression and decompression performances. We also propose and evaluate techniques for compressing frequency values for this case. Finally, we study the effect of this approach on query processing performance. Our experiments show very significant improvements in index size and query processing speed on the TREC GOV2 collection of 25.2 million web pages.