2007 · 42 citations · 24 references
ComputingComputer ScienceAlgorithmsData MiningInformation RetrievalAlgorithm AnalysisEvaluation Of Retrieval SystemsProbabilistic RetrievalQuery ProcessingSearching AlgorithmsSorting AlgorithmsAttribute RankingInformation Retrieval EvaluationRanking AlgorithmsRuntime PerformanceSortingTop-k Query ProcessingTop-k RankingTop-k Searching
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. 1.
24
Optimal aggregation algorithms for middleware
Ronald Fagin, Amnon Lotem, Moni Naor · Journal of Computer and System Sciences · 2003 · 941 citations
An analysis of time-dependent planning
Thomas Dean, Mark Boddy · National Conference on Artificial Intelligence · 1988 · 778 citations
Ronald Fagin, Ravi Kumar, D. Sivakumar · 2003 · 768 citations