# Range Queries on Uncertain Data

arXiv: https://arxiv.org/abs/1501.02309 · HTML: https://mlsanity.com/paper/1501.02309/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2015.

## Built on by (most cited first, 1 of 1)

- [Optimal Algorithms for Range Searching over Multi-Armed Bandits](https://mlsanity.com/paper/2105.01390/) (2021)

## Abstract (arXiv)

Given a set P of n uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on P to answer range queries of the following three types for any query interval I: (1) top-1 query: find the point in P that lies in I with the highest probability, (2) top-k query: given any integer k≤ n as part of the query, return the k points in P that lie in I with the highest probabilities, and (3) threshold query: given any threshold τ as part of the query, return all points of P that lie in I with probabilities at least τ. We present data structures for these range queries with linear or nearly linear space and efficient query time.