Probabilistic Histograms for Probabilistic Data

Summary: Proposes probabilistic histograms for uncertain relations, preserving possible-worlds semantics for planning and AQP. Then a Dynamic Programming framework builds optimal buckets with per-bucket PDFs under metrics (variation distance, SSE, max error, EMD1)—polynomial-time, compact. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h2c84b233c4e68b9f
Venue: VLDB
Year: 2009
Pagerank: 5.3778354e-05
Overall Rank: 8,206 | 44.83%
DOI: 10.14778/1687627.1687687

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode (AT&T)
2. Antonios Deligiannakis (Technical University of Crete)
3. Minos Garofalakis (Technical University of Crete)
4. Andrew McGregor (University of Massachusetts Amherst)

BibTeX Citation

@article{cormode_vldb09,
        title = {{Probabilistic Histograms for Probabilistic Data}},
        author = {Cormode, Graham and Deligiannakis, Antonios and Garofalakis, Minos and McGregor, Andrew},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687687},
        url = {https://doi.org/10.14778/1687627.1687687},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,874	Accelerating Approximate Aggregation Queries with Expensive Predicates	2021	VLDB	6.953738e-05
12,005	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042936299
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023258672
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022413521
587	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00015933201
696	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00014697176
2,738	Sketching Probabilistic Data Streams	2007	SIGMOD	8.07308e-05
3,038	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.7270848e-05
3,163	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.5789852e-05
8,382	Mining Deviants in a Time Series Database	1999	VLDB	5.3426872e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,758	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB
2	4,213	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
3	448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
4	370	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD
5	742	Dynamic Multidimensional Histograms	2002	SIGMOD
6	7,863	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
7	2,738	Sketching Probabilistic Data Streams	2007	SIGMOD
8	690	Creating Probabilistic Databases from Information Extraction Models	2006	VLDB
9	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
10	587	Management of Probabilistic Data: Foundations and Challenges	2007	PODS