**Papers Published**

- Agarwal, PK; Kumar, N; Sintos, S; Suri, S,
*Range-max queries on uncertain data*, Journal of Computer and System Sciences, vol. 94 (June, 2018), pp. 118-134, Elsevier BV

(last updated on 2019/05/21)**Abstract:**

© 2017 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.