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: 1356
Venue: PODS
Year: 2005
Pagerank: 4.8128138e-05
Overall Rank: 7,150 | 50.31%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Alin Dobra

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,978	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	9.8764627e-05

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
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080571183
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
550	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020346247
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
1,065	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00014344675

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
531	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.0002079072
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4232868e-05
5,832	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	5.3085972e-05
1,065	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00014344675
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
995	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014745185
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
360	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00025768448