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: 4254
Venue: SIGMOD
Year: 2010
Pagerank: 4.4289641e-05
Overall Rank: 8,882 | 38.21%
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,623	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB	4.6933659e-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.00057857292
101	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.0004955674
706	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00017845469
980	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00014879747
1,179	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00013457451
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
1,586	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00011250856
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
2,308	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0591406e-05
3,185	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.4192604e-05
3,632	Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases	2008	SIGMOD	6.9009547e-05
5,759	Indexing Correlated Probabilistic Databases	2009	SIGMOD	5.3392211e-05
5,935	Indexing Uncertain Data	2009	PODS	5.2657009e-05
8,372	URank: Formulation and Efficient Evaluation of Top-k Queries in Uncertain Databases	2007	SIGMOD	4.532996e-05
9,274	Ranking Distributed Probabilistic Data	2009	SIGMOD	4.3646295e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,549	Optimizing MPF Queries: Decision Support and Probabilistic Inference	2007	SIGMOD	6.9858057e-05
7,941	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	4.613363e-05
9,044	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB	4.4039656e-05
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
684	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018179769
6,278	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	5.1309442e-05
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
2,556	Probabilistic Optimization of Top N Queries	1999	VLDB	8.5465733e-05
2,308	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0591406e-05
7,623	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB	4.6933659e-05