Scholars@Duke

On pruning for top-k ranking in uncertain databases

Publication ,  Conference
Wang, C; Yuan, LY; You, JH; Zaiane, OR; Pei, J
Published in: Proceedings of the VLDB Endowment
January 1, 2011
Published version (DOI)

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. © 2011 VLDB Endowment.

Duke Scholars

Jian Pei
Author Jian Pei Computer Science

Published In

Proceedings of the VLDB Endowment

DOI

10.14778/2021017.2021018

EISSN

2150-8097

Publication Date

January 1, 2011

Volume

4

Issue

10

Start / End Page

598 / 609

Related Subject Headings

  • 4605 Data management and data science
  • 0807 Library and Information Studies
  • 0806 Information Systems
  • 0802 Computation Theory and Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Wang, C., Yuan, L. Y., You, J. H., Zaiane, O. R., & Pei, J. (2011). On pruning for top-k ranking in uncertain databases. In Proceedings of the VLDB Endowment (Vol. 4, pp. 598–609). https://doi.org/10.14778/2021017.2021018
Wang, C., L. Y. Yuan, J. H. You, O. R. Zaiane, and J. Pei. “On pruning for top-k ranking in uncertain databases.” In Proceedings of the VLDB Endowment, 4:598–609, 2011. https://doi.org/10.14778/2021017.2021018.
Wang C, Yuan LY, You JH, Zaiane OR, Pei J. On pruning for top-k ranking in uncertain databases. In: Proceedings of the VLDB Endowment. 2011. p. 598–609.
Wang, C., et al. “On pruning for top-k ranking in uncertain databases.” Proceedings of the VLDB Endowment, vol. 4, no. 10, 2011, pp. 598–609. Scopus, doi:10.14778/2021017.2021018.
Wang C, Yuan LY, You JH, Zaiane OR, Pei J. On pruning for top-k ranking in uncertain databases. Proceedings of the VLDB Endowment. 2011. p. 598–609.

Published In

Proceedings of the VLDB Endowment

DOI

10.14778/2021017.2021018

EISSN

2150-8097

Publication Date

January 1, 2011

Volume

4

Issue

10

Start / End Page

598 / 609

Related Subject Headings

  • 4605 Data management and data science
  • 0807 Library and Information Studies
  • 0806 Information Systems
  • 0802 Computation Theory and Mathematics