Global Optimization of Histograms

Summary: Global optimization of histograms across multiple attributes, allocating buckets adaptively to skew and usage to minimize error. DP and greedy algorithms versus equal-bucket baselines; results show large reductions, up to 100x for skewed data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3272
Venue: SIGMOD
Year: 2001
Pagerank: 0.00013863484
Overall Rank: 1,116 | 92.25%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
119	Executing SQL over Encrypted Data in the Database-Service-Provider Model	2002	SIGMOD	0.00045724707
325	The History of Histograms (abridged)	2003	VLDB	0.00027398081
841	Self-tuning Database Technology and Information Services: from Wishful Thinking to Viable Engineering	2002	VLDB	0.00015987128
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
1,727	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010731889
2,136	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	9.4668797e-05
3,167	QueryFormer: A Tree Transformer Model for Query Plan Representation	2022	VLDB	7.4561078e-05
3,924	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	6.6227223e-05
6,724	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	4.9449472e-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
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040465394
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080571183
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
114	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046317654
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041819767
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
223	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032829841
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
431	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00023397171
801	Universality of Serial Histograms	1993	VLDB	0.00016440976

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
114	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046317654
8,092	Probabilistic Histograms for Probabilistic Data	2009	VLDB	4.5847443e-05
5,832	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	5.3085972e-05
4,018	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	6.5250686e-05
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4232868e-05
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538