On Pruning for Top-K Ranking in Uncertain Databases
Top-k ranking for an uncertain database is to rank tuples in it so that the best k of them can be determined. The problem has been formalized under the unified approach based on parameterized ranking functions (PRFs) and the possible world semantics. Given a PRF, one can always compute the ranking function values of all the tuples to determine the top-k tuples, which is a formidable task for large databases. In this paper, we present a general approach to pruning for the framework based on PRFs. We show a mathematical manipulation of possible worlds which reveals key insights in the part of computation that may be pruned and how to achieve it in a systematic fashion. This leads to concrete pruning methods for a wide range of ranking functions. We show experimentally the effectiveness of our approach.
Citation
C. Wang,
L. Yuan,
J. You,
O. Zaiane,
J. Pei.
"On Pruning for Top-K Ranking in Uncertain Databases". International Conference on Very Large Data Bases, Seattle, United States, (ed: Rajesh Bordawekar, Christian A. Lang), pp 598-609, August 2011.
| Keywords: |
|
| Category: |
In Conference |
BibTeX
@incollection{Wang+al:11,
author = {Chonghai Wang and Li-Yan Yuan and Jia H. You and Osmar R. Zaiane
and Jian Pei},
title = {On Pruning for Top-K Ranking in Uncertain Databases},
Editor = {Rajesh Bordawekar, Christian A. Lang},
Pages = {598-609},
booktitle = {International Conference on Very Large Data Bases},
year = 2011,
}Last Updated: January 14, 2020
Submitted by Sabina P 
