Histograms Revisited: When are histograms the best approximation method for aggregates over joins?

Summary: Replace the uniform-bucket assumption with a weaker “random arrangement” model, showing it yields the same histogram approximation formulas and permits tight error bounds. Characterize input regimes where histograms beat sampling/sketching for join-aggregate approximation and where they fail on average. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1355
Venue: PODS
Year: 2005
Pagerank: 5.6166792e-05
Overall Rank: 7,443 | 48.94%
DOI: 10.1145/1065167.1065196

Incoming Non-self Citations Over Time

Authors

1. Alin Dobra (University of Florida)

BibTeX Citation

@inproceedings{dobra_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{Histograms Revisited: When are histograms the best approximation method for aggregates over joins?}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065196},
        doi = {10.1145/1065167.1065196},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Dobra, Alin},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,536	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010460864

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00048351457
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00035031529
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
786	Universality of Serial Histograms	1993	VLDB	0.00014053885
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	723	Dynamic Multidimensional Histograms	2002	SIGMOD
2	508	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD
3	8,998	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD
4	5,421	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS
5	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
6	786	Universality of Serial Histograms	1993	VLDB
7	235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB
8	850	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD
9	274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
10	435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB