Probabilistic top- k range query processing for uncertain databases

Abstract

Query processing over uncertain data is very important in many applications due to the existence of uncertainty in real-world data. In this paper, we propose a novel and important query for uncertain data, namely probabilistic top-(k, l) range (PTR) query, which retrieves l uncertain tuples that are expected to meet score range constraint [s₁, s₂] and have the maximum top-k probabilities but no less than a given probability threshold q. In order to accelerate the PTR query, we present some effective pruning techniques to reduce the search space of PTR query, which are integrated seamlessly into an efficient PTR query procedure. Extensive experiments over both real-world and synthetic datasets verify the efficiency and effectiveness of our proposed approaches.