Efficient Processing of Top-k Queries in Uncertain Databases
- 1 April 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 1406-1408
Abstract
This work introduces novel polynomial-time algorithms for processing top-k queries in uncertain databases, under the generally adopted model of x-relations. An x-relation consists of a number of x-tuples, and each x-tuple randomly instantiates into one tuple from one or more alternatives. Our results significantly improve the best known algorithms for top-k query processing in uncertain databases, in terms of both running time and memory usage. Focusing on the single-alternative case, the new algorithms are orders of magnitude faster.Keywords
This publication has 2 references indexed in Scilit: