Range search on multidimensional uncertain data
Yufei Tao, Xiaokui Xiao, Reynold C. K. Cheng · ACM Transactions on Database Systems · 2007
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.