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.2606762e-05
Overall Rank: 5,937 | 58.74%
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,370	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.2392118e-05
4,721	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9647585e-05
7,657	UPI: A Primary Index for Uncertain Databases	2010	VLDB	4.6821809e-05
8,883	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	4.4247207e-05
11,912	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.1905499e-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.00057797415
300	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00028503742
1,499	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643887
1,568	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.0001131667
2,316	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0513688e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,767	Indexing Correlated Probabilistic Databases	2009	SIGMOD	5.3341473e-05
4,094	Ranking Continuous Probabilistic Datasets	2010	VLDB	6.4510938e-05
2,207	Independent Range Sampling	2014	PODS	9.2896559e-05
8,092	Probabilistic Histograms for Probabilistic Data	2009	VLDB	4.5847443e-05
12,386	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	4.1905499e-05
1,703	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010820803
11,912	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.1905499e-05
11,832	Range-Max Queries on Uncertain Data	2016	PODS	4.1905499e-05
1,568	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.0001131667
2,316	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0513688e-05