Indexing Uncertain Data

Summary: Indexes 1D uncertain points (pdfs) to answer range queries with threshold τ, returning points with Pr(point ∈ I) ≥ τ. Develops linear/near-linear-space, logarithmic-query-time structures for histogram, Gaussian and piecewise-algebraic pdfs, with external-memory variants. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1484
Venue: PODS
Year: 2009
Pagerank: 6.0955299e-05
Overall Rank: 5,764 | 60.46%
DOI: 10.1145/1559795.1559816

Incoming Non-self Citations Over Time

Authors

1. Pankaj K. Agarwal (Duke University)
2. Siu-Wing Cheng (Hong Kong University of Science and Technology)
3. Yufei Tao (Chinese University of Hong Kong)
4. Ke Yi (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{agarwal_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Indexing Uncertain Data}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559816},
        doi = {10.1145/1559795.1559816},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Agarwal, Pankaj K. and Cheng, Siu-Wing and Tao, Yufei and Yi, Ke},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,112	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.8944534e-05
4,850	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	6.480347e-05
7,553	UPI: A Primary Index for Uncertain Databases	2010	VLDB	5.6004812e-05
9,044	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	5.3253644e-05
12,103	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	5.093636e-05

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
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
331	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020936658
1,486	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00010625076
1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010361147
2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.24085e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,711	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
2	3,823	Ranking Continuous Probabilistic Datasets	2010	VLDB
3	2,443	Independent Range Sampling	2014	PODS
4	8,059	Probabilistic Histograms for Probabilistic Data	2009	VLDB
5	12,571	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD
6	1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD
7	12,103	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD
8	12,027	Range-Max Queries on Uncertain Data	2016	PODS
9	1,486	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB
10	2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB