Waves: a fast multi-tier top-k query processing algorithm
Waves: a fast multi-tier top-k query processing algorithm
复制标题
Waves：一种快速多层top-k查询处理算法
DOI：
10.1007/s10791-017-9298-6
复制
发表时间：
2017
影响因子：
2.5
通讯作者：
A. Carvalho
中科院分区：
文献类型：
--
作者：
Caio Moura Daoud;E. Moura;D. Oliveira;A. D. Silva;Cristian Rossi;A. Carvalho
在本文中，我们提出了 Waves，一种新颖的一次文档算法，用于快速计算搜索系统中的前 k 个查询结果。 Waves 算法使用多层索引来处理查询。它对结果进行连续的尝试性评估，我们称之为波浪。每个波浪都从特定的层级 i 开始穿过该指数。每波我只能将出现在该层级别的那些文档插入到答案中。处理完一个波后，算法会检查所获得的答案是否会被连续的波改变。仅当有机会改变 top-k 分数时，才会开始新的浪潮。我们通过实验表明，与文献中提出的先前方法相比，这种惰性查询处理策略可以缩短查询处理时间。我们通过实验将 Waves 的性能与最先进的一次文档查询处理方法进行比较，这些方法保留了 top-k 结果，并展示了该方法可以成为计算 top-k 结果的良好替代算法的场景。
In this paper, we present Waves, a novel document-at-a-time algorithm for fast computing of top-k query results in search systems. The Waves algorithm uses multi-tier indexes for processing queries. It performs successive tentative evaluations of results which we call waves. Each wave traverses the index, starting from a specific tier level i. Each wave i may insert only those documents that occur in that tier level into the answer. After processing a wave, the algorithm checks whether the answer achieved might be changed by successive waves or not. A new wave is started only if it has a chance of changing the top-k scores. We show through experiments that such lazy query processing strategy results in smaller query processing times when compared to previous approaches proposed in the literature. We present experiments to compare Waves’ performance to the state-of-the-art document-at-a-time query processing methods that preserve top-k results and show scenarios where the method can be a good alternative algorithm for computing top-k results.