Math @ Duke

Publications [#318111] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Kumar, N; Sintos, S; Suri, S, Rangemax queries on uncertain data,
Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems, vol. 26June01July2016
(June, 2016),
pp. 465476, ISBN 9781450341912 [doi]
(last updated on 2018/10/22)
Abstract: © 2016 ACM. Let P be a set of n uncertain points in ℝ d , where each point p i ∈ P is associated with a real value v i and a probability α i ∈ (0,1] of existence, i.e., each p i exists with an independent probability α i . 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. The specific contributions of our paper include the following: (i) The first index of subquadratic size to achieve a sublinear query time in any dimension d ≥ 1. It also provides a tradeoff between query time and size of the index. (ii) A conditional lower bound for the mostlikely rangemax queries, based on the conjectured hardness of the setintersection problem, which suggests that in the worst case the product (query time) 2 x (index size) is Ω(n 2 /polylog (n) ). (iii) A linearsize index for estimating the expected rangemax value within approximation factor 1/2 in O(log c n) time, for some constant c > 0; that is, if the expected maximum value is μ then the query procedure returns a value μ′ with μ/2 ≤ μ′ ≤ μ. (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

