Range-max queries on uncertain data

Let P be a set of n uncertain points in Rd, where each point pi∈P is associated with a real value vi and exists with probability αi∈(0,1] independently of the other points. We present algorithms for building an index on P so that for a d-dimensional query rectangle ρ, the expected maximum value or the most-likely maximum value in ρ can be computed quickly. Our main contributions include the following: (i) The first index of sub-quadratic size to achieve a sub-linear query time in any dimension. (ii) A conditional lower bound for most-likely range-max queries, based on the conjectured hardness of the set-intersection problem. (iii) A near-linear-size index for estimating the expected range-max value within approximation factor 1/2 in O(polylog(n)) time. (iv) Extensions of our algorithm to more general uncertainty models and for computing the top-k values of the range-max.