Range Search on Multidimensional Uncertain Data

Yufei Tao, Xiaokui Xiao, Reynold Cheng

ACM Transactions on Databases Systems (TODS), 32(3), 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.