Range-max queries on uncertain data

Published

Journal Article

© 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.

Full Text

Duke Authors

Cited Authors

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

Published Date

  • June 1, 2018

Published In

Volume / Issue

  • 94 /

Start / End Page

  • 118 - 134

Electronic International Standard Serial Number (EISSN)

  • 1090-2724

International Standard Serial Number (ISSN)

  • 0022-0000

Digital Object Identifier (DOI)

  • 10.1016/j.jcss.2017.09.006

Citation Source

  • Scopus