Threshold Query Optimization for Uncertain Data

Summary: PTQ optimization for uncertain data with attribute/tuple uncertainty and cross-attribute correlations, handling selections, projections, and joins. Introduces a tau-operator with push-down rules and plan enumeration; real-UDBMS experiments show notable PTQ speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4255
Venue: SIGMOD
Year: 2010
Pagerank: 4.4247207e-05
Overall Rank: 8,883 | 38.27%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,625	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB	4.6888879e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 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
103	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00049520051
702	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00017848789
974	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00014882804
1,181	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00013447487
1,535	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011461371
1,568	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.0001131667
1,703	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010820803
2,316	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0513688e-05
3,190	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.413338e-05
3,634	Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases	2008	SIGMOD	6.8949444e-05
5,767	Indexing Correlated Probabilistic Databases	2009	SIGMOD	5.3341473e-05
5,937	Indexing Uncertain Data	2009	PODS	5.2606762e-05
8,371	URank: Formulation and Efficient Evaluation of Top-k Queries in Uncertain Databases	2007	SIGMOD	4.5286495e-05
9,280	Ranking Distributed Probabilistic Data	2009	SIGMOD	4.3604461e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,547	Optimizing MPF Queries: Decision Support and Probabilistic Inference	2007	SIGMOD	6.9810773e-05
7,944	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	4.6089395e-05
9,044	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB	4.3997447e-05
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
680	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018193263
6,277	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	5.1260947e-05
1,703	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010820803
2,552	Probabilistic Optimization of Top N Queries	1999	VLDB	8.5540341e-05
2,316	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0513688e-05
7,625	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB	4.6888879e-05