Range queries on uncertain data

Given a set P of n uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on P to answer range queries of the following three types for any query interval I: (1) top-1 query: find a point in P that lies in I with the highest probability, (2) top-k query: given any integer k ≤ n as part of the query, return the k points in P that lie in I with the highest probabilities, and (3) threshold query: given any threshold τ as part of the query, return all points of P that lie in I with probabilities at least τ. We present data structures for these range queries with linear or nearly linear space and efficient query time.

Authors

• Jian Li
• Haitao Wang School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou, China

Keywords

• Range queries
• Uncertain data
• Top-k queries
• Threshold queries
• Data structures
• Algorithms