Optimizing top-k document retrieval strategies for block-max indexes
Optimizing top-k document retrieval strategies for block-max indexes
复制标题
DOI：
10.1145/2433396.2433412
复制
发表时间：
2013-02
期刊：
影响因子：
--
通讯作者：
C. Dimopoulos;Sergey Nepomnyachiy;Torsten Suel
中科院分区：
文献类型：
--
作者：
C. Dimopoulos;Sergey Nepomnyachiy;Torsten Suel
大型的网络搜索引擎每天都要消耗大量的硬件和能源资源来处理数以亿计的查询，如何提高查询处理效率是很多研究的重点。一种被称为提前终止技术的通用优化类在所有主要引擎中使用，并且基本上涉及计算顶部结果，而无需对所有潜在相关索引条目进行穷举遍历和评分。最近的工作[9，7]提出了几个提前终止算法的析取top-k查询处理，基于一个新的增强索引结构，称为块最大索引，使积极跳过索引。在本文中，我们通过研究Block-Max索引的新算法和优化来建立这项工作，这些算法和优化比[9，7]中的工作实现了显着的性能提升。我们首先实现和比较块最大面向算法的基础上著名的Maxscore和WAND方法。然后，我们研究如何构建更好的Block-Max索引结构并设计更好的索引遍历策略，从而在可接受的空间开销下实现比[9]中的最佳结果快2倍的新算法。我们还描述和评估一个新的递归块最大索引结构的分层算法。
Large web search engines use significant hardware and energy resources to process hundreds of millions of queries each day, and a lot of research has focused on how to improve query processing efficiency. One general class of optimizations called early termination techniques is used in all major engines, and essentially involves computing top results without an exhaustive traversal and scoring of all potentially relevant index entries. Recent work in [9,7] proposed several early termination algorithms for disjunctive top-k query processing, based on a new augmented index structure called Block-Max Index that enables aggressive skipping in the index. In this paper, we build on this work by studying new algorithms and optimizations for Block-Max indexes that achieve significant performance gains over the work in [9,7]. We start by implementing and comparing Block-Max oriented algorithms based on the well-known Maxscore and WAND approaches. Then we study how to build better Block-Max index structures and design better index-traversal strategies, resulting in new algorithms that achieve a factor of 2 speed-up over the best results in [9] with acceptable space overheads. We also describe and evaluate a hierarchical algorithm for a new recursive Block-Max index structure.