Affiliations: [a]
College of Information Science and Engineering, Hunan University, Changsha, Hunan, China
| [b]
Department of Computer Science, State University of New York, New Paltz, NY, USA
Correspondence:
[*]
Corresponding author. Fan Wu, College of Information Science and Engineering, Hunan University, Changsha
410082, Hunan, China. Tel.: +86 18907483881; Fax: +86 0731 88664161; E-mail: wufan_whu@163.com.
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 [s1, s2] 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.
Keywords: Data management, probabilistic top-k query, query processing, range query, uncertain data
