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: 4316
Venue: SIGMOD
Year: 2010
Pagerank: 5.3253644e-05
Overall Rank: 9,044 | 37.96%
DOI: 10.1145/1807167.1807203

Incoming Non-self Citations Over Time

Authors

1. Yinian Qi (Purdue University)
2. Rohit Jain (Purdue University)
3. Sarvjeet Singh (Google; Purdue University)
4. Sunil Prabhakar (Purdue University)

BibTeX Citation

@inproceedings{qi_sigmod10,
        title = {{Threshold Query Optimization for Uncertain Data}},
        author = {Qi, Yinian and Jain, Rohit and Singh, Sarvjeet and Prabhakar, Sunil},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807203},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807203},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,711	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB	5.5614818e-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
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
683	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00015005338
820	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00013814535
1,097	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00012181027
1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00011025316
1,486	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00010625076
1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00010229844
2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.24085e-05
3,049	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.8151597e-05
3,139	Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases	2008	SIGMOD	7.7188328e-05
5,450	Indexing Correlated Probabilistic Databases	2009	SIGMOD	6.2142725e-05
5,764	Indexing Uncertain Data	2009	PODS	6.0955299e-05
8,345	URank: Formulation and Efficient Evaluation of Top-k Queries in Uncertain Databases	2007	SIGMOD	5.4474663e-05
9,425	Ranking Distributed Probabilistic Data	2009	SIGMOD	5.2711481e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,698	Optimizing MPF Queries: Decision Support and Probabilistic Inference	2007	SIGMOD
2	8,260	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD
3	9,194	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB
4	50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
5	566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
6	5,537	Uncertainty Aware Query Execution Time Prediction	2014	VLDB
7	1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD
8	2,149	Probabilistic Optimization of Top N Queries	1999	VLDB
9	2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB
10	7,711	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB