Efficient Top-k Query Evaluation on Probabilistic Data

By Christopher R'e, Nilesh N. Dalvi, Dan Suciu. IEEE International Conference on Data Engineering, 2007

415 citations recorded by the source corpus.

Modern enterprise applications are forced to deal with unreliable, inconsistent and imprecise information. Probabilistic databases can model such data naturally, but SQL query evaluation on probabilistic databases is difficult: previous approaches have either restricted the SQL queries, or computed approximate probabilities, or did not scale, and it was shown recently that precise query evaluation is theoretically hard. In this paper we describe a novel approach, which computes and ranks efficiently the top-k answers to a SQL query on a probabilistic database. The restriction to top-k answers is natural, since imprecisions in the data often lead to a large number of answers of low quality, and users are interested only in the answers with the highest probabilities. The idea in our algorithm is to run in parallel several Monte-Carlo simulations, one for each candidate answer, and approximate each probability only to the extent needed to compute correctly the top-k answers.

Subfields: Computer Networks and Communications, Management Science and Operations Research, Signal Processing

View Paper: https://www.semanticscholar.org/paper/7accedfb9bb0bc6706e61147e1950108923e88ad

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

In Signal Processing

Citations in the corpus

MCDB: a monte carlo approach to managing uncertain data (2008, background): “Although others have suggested the possibility of Monte Carlo techniques in probabilistic databases [31], ours is the first system for which the Monte Carlo approach is fundamental to the entire system design.”
Ranking queries on uncertain data: a probabilistic threshold approach (2008, methodology): “Our contribution. We address an application scenario other than the recent proposals in [26, 22 ].”
SeeDB: Efficient Data-Driven Visualization Recommendations to Support Visual Analytics (2015, methodology): “This technique (called CI) is similar to top-k based pruning algorithms developed in other contexts [13, 27].”
Probabilistic frequent itemset mining in uncertain databases (2009, methodology): “Probabilistic top-k query approaches [14, 17, 12] are usually associated with uncertain databases using the tuple uncertainty model.”
Top-k Query Processing in Uncertain Databases (2007, background): “In parallel to this work, the problem of finding the k most probable query answers in probabilistic databases was addressed in [19].”