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: 1485
Venue: PODS
Year: 2009
Pagerank: 5.2657009e-05
Overall Rank: 5,935 | 58.72%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,373	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.2443809e-05
4,724	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9697823e-05
7,659	UPI: A Primary Index for Uncertain Databases	2010	VLDB	4.686672e-05
8,882	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	4.4289641e-05
11,904	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.1945683e-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
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
299	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00028525071
1,502	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643406
1,586	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00011250856
2,308	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0591406e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,623	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB	4.6933659e-05
4,095	Ranking Continuous Probabilistic Datasets	2010	VLDB	6.4556768e-05
2,203	Independent Range Sampling	2014	PODS	9.2981095e-05
8,090	Probabilistic Histograms for Probabilistic Data	2009	VLDB	4.5888589e-05
12,378	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	4.1945683e-05
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
11,904	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.1945683e-05
11,824	Range-Max Queries on Uncertain Data	2016	PODS	4.1945683e-05
1,586	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00011250856
2,308	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0591406e-05