Anytime Measures for Top-k Algorithms
Anytime Measures for Top-k Algorithms
复制标题
DOI：
--
复制
发表时间：
2007-09
期刊：
影响因子：
--
通讯作者：
Benjamin Arai;Gautam Das;D. Gunopulos;Nick Koudas
中科院分区：
文献类型：
--
作者：
Benjamin Arai;Gautam Das;D. Gunopulos;Nick Koudas
在大型多属性数据集上的Top-k查询是信息检索和排序应用中的基本操作。在本文中，我们开始研究的任何时候行为的top-k算法。特别是，给定特定的top-k算法（TA和TA-Sorted），我们有兴趣研究它们在算法执行过程中的任何一点上识别正确结果的进展。我们采用概率方法，在该方法中，我们试图在算法的任何操作点报告已经识别出前k个结果的置信度。当人们对降低top-k计算的运行时成本感兴趣时，这样的功能可以是有价值的资产。我们提出了一个彻底的实验评估，以验证我们的技术，使用合成和真实的数据集。
Top-k queries on large multi-attribute data sets are fundamental operations in information retrieval and ranking applications. In this paper, we initiate research on the anytime behavior of top-k algorithms. In particular, given specific top-k algorithms (TA and TA-Sorted) we are interested in studying their progress toward identification of the correct result at any point during the algorithms' execution. We adopt a probabilistic approach where we seek to report at any point of operation of the algorithm the confidence that the top-k result has been identified. Such a functionality can be a valuable asset when one is interested in reducing the runtime cost of top-k computations. We present a thorough experimental evaluation to validate our techniques using both synthetic and real data sets.