Top-k dominating queries in uncertain databases
Xiang Lian, Lei Chen · 2009
Due to the existence of uncertain data in a wide spectrum of real applications, uncertain query processing has become increasingly important, which dramatically differs from handling certain data in a traditional database. In this paper, we formulate and tackle an important query, namely probabilistic top-k dominating (PTD) query, in the uncertain database. In particular, a PTD query re-trieves k uncertain objects that are expected to dynamically domi-nate the largest number of uncertain objects. We propose an effec-tive pruning approach to reduce the PTD search space, and present an efficient query procedure to answer PTD queries. Furthermore, approximate PTD query processing and the case where the PTD query is issued from an uncertain query object are also discussed. Extensive experiments have demonstrated the efficiency and effec-tiveness of our proposed PTD query processing approaches. 1.