Range search on multidimensional uncertain data

Abstract

In an uncertain database, every object o is associated with a probability density function, which describes the likelihood that o appears at each position in a multidimensional workspace. This article studies two types of range retrieval fundamental to many analytical tasks. Specifically, a nonfuzzy query returns all the objects that appear in a search region r q with at least a certain probability t q. On the other hand, given an uncertain object q, fuzzy search retrieves the set of objects that are within distance ε q from q with no less than probability t q. The core of our methodology is a novel concept of probabilistically constrained rectangle, which permits effective pruning/validation of nonqualifying/ qualifying data. We develop a new index structure called the U-tree for minimizing the query overhead. Our algorithmic findings are accompanied with a thorough theoretical analysis, which reveals valuable insight into the problem characteristics, and mathematically confirms the efficiency of our solutions. We verify the effectiveness of the proposed techniques with extensive experiments. © 2007 ACM.