Best Position Algorithms for Top-k Queries
Best Position Algorithms for Top-k Queries
复制标题
DOI：
--
复制
发表时间：
2007-09
期刊：
影响因子：
--
通讯作者：
Reza Akbarinia;Esther Pacitti;P. Valduriez
中科院分区：
文献类型：
--
作者：
Reza Akbarinia;Esther Pacitti;P. Valduriez
回答top-k查询的一般问题可以使用按其本地分数排序的数据项列表来建模。到目前为止，在排序列表上回答top-k查询的最有效算法是阈值算法（TA）。然而，TA仍然可能招致对列表的大量无用访问。在本文中，我们提出了两个新的算法，停止得更快。首先，我们提出了最佳位置算法（BPA），它比TA更有效地执行top-k查询。对于任何数据库实例（即排序列表集），我们证明BPA早在TA时停止，并且其执行成本永远不会高于TA。我们表明，BPA停止的位置可以比TA低（m-1）倍，其中m是列表的数量。我们还表明，我们的算法的执行成本可以是（m-1）倍低于TA。其次，我们提出了比BPA更有效的BPA 2算法。我们表明，访问列表的数量由BPA 2可以是约（m-1）倍低于BPA。我们的性能评估表明，在我们的测试数据库，BPA和BPA 2实现显着的性能增益相比，TA。
The general problem of answering top-k queries can be modeled using lists of data items sorted by their local scores. The most efficient algorithm proposed so far for answering top-k queries over sorted lists is the Threshold Algorithm (TA). However, TA may still incur a lot of useless accesses to the lists. In this paper, we propose two new algorithms which stop much sooner. First, we propose the best position algorithm (BPA) which executes top-k queries more efficiently than TA. For any database instance (i.e. set of sorted lists), we prove that BPA stops as early as TA, and that its execution cost is never higher than TA. We show that the position at which BPA stops can be (m-1) times lower than that of TA, where m is the number of lists. We also show that the execution cost of our algorithm can be (m-1) times lower than that of TA. Second, we propose the BPA2 algorithm which is much more efficient than BPA. We show that the number of accesses to the lists done by BPA2 can be about (m-1) times lower than that of BPA. Our performance evaluation shows that over our test databases, BPA and BPA2 achieve significant performance gains in comparison with TA.