Optimizing Probabilistic Query Processing on Continuous Uncertain Data

Summary: Optimizes probabilistic threshold queries on continuous uncertain data with (i) new indexes to speed joins, (ii) dimensionality reduction and fast filters for selections, and (iii) a dynamic per-tuple query plan. Empirical results on real data and benchmarks show accuracy and substantial performance gains over state-of-the-art threshold optimizers. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h860ecc37350d7ae0
Venue: VLDB
Year: 2011
Pagerank: 5.4367962e-05
Overall Rank: 7,863 | 47.14%
DOI: 10.14778/3402707.3402751

Incoming Non-self Citations Over Time

Authors

1. Liping Peng (University of Massachusetts Amherst)
2. Yanlei Diao (University of Massachusetts Amherst)
3. Anna Liu (University of Massachusetts Amherst)

BibTeX Citation

@article{peng_vldb11,
        title = {{Optimizing Probabilistic Query Processing on Continuous Uncertain Data}},
        author = {Peng, Liping and Diao, Yanlei and Liu, Anna},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {11},
        pages = {1169--1180},
        doi = {10.14778/3402707.3402751},
        url = {https://doi.org/10.14778/3402707.3402751},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,029	Towards High-Throughput Gibbs Sampling at Scale: A Study across Storage Managers	2013	SIGMOD	6.8419186e-05
8,808	Supporting User-Defined Functions on Uncertain Data	2013	VLDB	5.2725914e-05
12,397	Supporting Data Uncertainty in Array Databases	2015	SIGMOD	4.9793485e-05
12,616	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040860054
84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035963861
841	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00013541445
1,018	Designing And Mining Multi-Terabyte Astronomy Archives: The Sloan Digital Sky Survey	2000	SIGMOD	0.00012466304
1,408	A Demonstration of SciDB: A Science-Oriented DBMS	2009	VLDB	0.00010743556
2,104	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0366183e-05
3,893	Ranking Continuous Probabilistic Datasets	2010	VLDB	6.940442e-05
4,106	Content-Based Routing: Different Plans for Different Data	2005	VLDB	6.8032891e-05
6,175	PODS: A New Model and Processing Algorithms for Uncertain Data Streams	2010	SIGMOD	5.8610125e-05
9,214	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	5.2058816e-05
12,758	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,389	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
2	1,615	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD
3	2,738	Sketching Probabilistic Data Streams	2007	SIGMOD
4	3,769	Optimizing MPF Queries: Decision Support and Probabilistic Inference	2007	SIGMOD
5	8,426	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD
6	8,206	Probabilistic Histograms for Probabilistic Data	2009	VLDB
7	2,181	Probabilistic Optimization of Top N Queries	1999	VLDB
8	12,758	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB
9	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
10	9,214	Threshold Query Optimization for Uncertain Data	2010	SIGMOD