# Range-max queries on uncertain data

Published

Conference Paper

© 2016 ACM. Let P be a set of n uncertain points in ℝd, where each point pi ∈ P is associated with a real value vi and a probability αi ∈ (0,1] of existence, i.e., each pi 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 Ω(n2/polylog(n)). (iii) A linear-size index for estimating the expected range-max value within approximation factor 1/2 in O(logcn) 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.

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Kumar, N; Sintos, S; Suri, S

### Published Date

- June 15, 2016

### Published In

- Proceedings of the Acm Sigact Sigmod Sigart Symposium on Principles of Database Systems

### Volume / Issue

- 26-June-01-July-2016 /

### Start / End Page

- 465 - 476

### International Standard Book Number 13 (ISBN-13)

- 9781450341912

### Digital Object Identifier (DOI)

- 10.1145/2902251.2902281

### Citation Source

- Scopus