Math @ Duke

Publications [#331366] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Kumar, N; Sintos, S; Suri, S, Rangemax queries on uncertain data,
Journal of Computer and System Sciences, vol. 94
(June, 2018),
pp. 118134, Elsevier BV [doi]
(last updated on 2019/02/17)
Abstract: © 2017 Let P be a set of n uncertain points in Rd, where each point pi∈P is associated with a real value viand exists with probability αi∈(0,1] independently of the other points. We present algorithms for building an index on P so that for a ddimensional query rectangle ρ the expected maximum value or the mostlikely maximum value in ρ can be computed quickly. Our main contributions include the following: (i) The first index of subquadratic size to achieve a sublinear query time in any dimension. (ii) A conditional lower bound for mostlikely rangemax queries, based on the conjectured hardness of the setintersection problem. (iii) A nearlinearsize index for estimating the expected rangemax 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 topk values of the rangemax.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

