Range-Max Queries on Uncertain Data

Summary: Index structures for range-max on uncertain points (existence probabilities): first to achieve sub-quadratic space with sub-linear queries for any d≥1, with tunable space/query trade-offs. Also: set-intersection-based conditional lower bound, linear-size polylog-time 1/2-approx for expected max, and extensions to top-k and richer uncertainty models. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1675
Venue: PODS
Year: 2016
Pagerank: 5.093636e-05
Overall Rank: 12,027 | 17.49%
DOI: 10.1145/2902251.2902281

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Pankaj K. Agarwal (Duke University)
2. Nirman Kumar (University of California Santa Barbara)
3. Stavros Sintos (Duke University)
4. Subhash Suri (University of California Santa Barbara)

BibTeX Citation

@inproceedings{agarwal_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Range-Max Queries on Uncertain Data}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902281},
        doi = {10.1145/2902251.2902281},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Agarwal, Pankaj K. and Kumar, Nirman and Sintos, Stavros and Suri, Subhash},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00010229844
2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.24085e-05
3,049	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.8151597e-05
4,850	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	6.480347e-05
7,025	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	5.7234179e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,103	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD
2	2,443	Independent Range Sampling	2014	PODS
3	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
4	4,850	Nearest-Neighbor Searching Under Uncertainty	2012	PODS
5	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
6	1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD
7	9,073	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS
8	1,486	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB
9	2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB
10	5,764	Indexing Uncertain Data	2009	PODS