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: h69464a897ff3c0f1
Venue: PODS
Year: 2009
Pagerank: 5.9588542e-05
Overall Rank: 5,882 | 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,196	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.7421052e-05
4,835	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	6.3877419e-05
7,702	UPI: A Primary Index for Uncertain Databases	2010	VLDB	5.4748399e-05
9,214	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	5.2058816e-05
12,396	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.9793485e-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
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042936299
337	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020621631
1,518	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00010396565
1,589	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010139591
2,104	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0366183e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,588	Indexing Correlated Probabilistic Databases	2009	SIGMOD
2	3,893	Ranking Continuous Probabilistic Datasets	2010	VLDB
3	2,495	Independent Range Sampling	2014	PODS
4	8,206	Probabilistic Histograms for Probabilistic Data	2009	VLDB
5	12,861	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD
6	1,396	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD
7	12,396	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD
8	12,322	Range-Max Queries on Uncertain Data	2016	PODS
9	1,518	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB
10	2,104	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB