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

Math @ Duke



Publications [#318111] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Kumar, N; Sintos, S; Suri, S, Range-max queries on uncertain data, Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, vol. 26-June-01-July-2016 (June, 2016), pp. 465-476, ISBN 9781450341912 [doi]
    (last updated on 2018/03/19)

    © 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 d-dimensional query rectangle ρ, the expected maximum value or the most-likely maximum value in ρ can be computed quickly. The specific contributions of our paper include the following: (i) The first index of sub-quadratic size to achieve a sub-linear query time in any dimension d ≥ 1. It also provides a trade-off between query time and size of the index. (ii) A conditional lower bound for the most-likely range-max queries, based on the conjectured hardness of the set-intersection problem, which suggests that in the worst case the product (query time) 2 x (index size) is Ω(n 2 /polylog (n) ). (iii) A linear-size index for estimating the expected range-max 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 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