Top-k query processing in uncertain databases

Mohamed A. Soliman, Ihab F. Ilyas, Kevin Chen Chuan Chang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication23rd International Conference on Data Engineering, ICDE 2007
Number of pages10
StatePublished - 2007
Event23rd International Conference on Data Engineering, ICDE 2007 - Istanbul, Turkey
Duration: Apr 15 2007Apr 20 2007

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Other23rd International Conference on Data Engineering, ICDE 2007

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'Top-k query processing in uncertain databases'. Together they form a unique fingerprint.

Cite this