Top-k Query Processing in Uncertain Databases
Top Cited Papers
- 1 April 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 896-905
Abstract
Top-k processing in uncertain databases is semantically and computationally different from traditional top-k processing. The interplay between score and uncertainty makes traditional techniques inapplicable. We introduce new probabilistic formulations for top-k queries. Our formulations are based on "marriage" of traditional top-k semantics and possible worlds semantics. In the light of these formulations, we construct a framework that encapsulates a state space model and efficient query processing techniques to tackle the challenges of uncertain data settings. We prove that our techniques are optimal in terms of the number of accessed tuples and materialized search states. Our experiments show the efficiency of our techniques under different data distributions with orders of magnitude improvement over naive materialization of possible worlds.Keywords
This publication has 13 references indexed in Scilit:
- A Sampling-Based Approach to Optimizing Top-k Queries in Sensor Networks2006
- Clean Answers over Dirty Databases: A Probabilistic Approach2006
- ConQuer2005
- RankSQL2005
- Querying imprecise data in moving object environmentsIEEE Transactions on Knowledge and Data Engineering, 2004
- Supporting Top-k Join Queries in Relational Databases2003
- Real-world Data is Dirty: Data Cleansing and The Merge/Purge ProblemData Mining and Knowledge Discovery, 1998
- ProbViewACM Transactions on Database Systems, 1997
- On the representation and querying of sets of possible worlds1987
- Incomplete Information in Relational DatabasesJournal of the ACM, 1984