Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#331366] of Pankaj K. Agarwal

Papers Published

  1. 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 [doi]
    (last updated on 2019/04/24)

    © 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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320