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: 10370
Venue: VLDB
Year: 2011
Pagerank: 5.5614818e-05
Overall Rank: 7,711 | 47.10%
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
3,952	Towards High-Throughput Gibbs Sampling at Scale: A Study across Storage Managers	2013	SIGMOD	6.9967272e-05
8,646	Supporting User-Defined Functions on Uncertain Data	2013	VLDB	5.3928856e-05
12,104	Supporting Data Uncertainty in Array Databases	2015	SIGMOD	5.093636e-05
12,325	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB	5.093636e-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.001157935
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00041071971
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
820	BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models	2008	VLDB	0.00013814535
1,002	Designing And Mining Multi-Terabyte Astronomy Archives: The Sloan Digital Sky Survey	2000	SIGMOD	0.00012706131
1,376	A Demonstration of SciDB: A Science-Oriented DBMS	2009	VLDB	0.00010973814
2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.24085e-05
3,823	Ranking Continuous Probabilistic Datasets	2010	VLDB	7.092508e-05
4,383	Content-Based Routing: Different Plans for Different Data	2005	VLDB	6.7329787e-05
6,049	PODS: A New Model and Processing Algorithms for Uncertain Data Streams	2010	SIGMOD	5.9949334e-05
9,044	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	5.3253644e-05
12,467	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
2	1,594	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD
3	3,698	Optimizing MPF Queries: Decision Support and Probabilistic Inference	2007	SIGMOD
4	2,697	Sketching Probabilistic Data Streams	2007	SIGMOD
5	8,260	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD
6	8,059	Probabilistic Histograms for Probabilistic Data	2009	VLDB
7	2,149	Probabilistic Optimization of Top N Queries	1999	VLDB
8	12,467	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB
9	50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
10	9,044	Threshold Query Optimization for Uncertain Data	2010	SIGMOD