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: 3271
Venue: SIGMOD
Year: 2001
Pagerank: 0.00013856211
Overall Rank: 1,120 | 92.22%
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
118	Executing SQL over Encrypted Data in the Database-Service-Provider Model	2002	SIGMOD	0.00045685662
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
846	Self-tuning Database Technology and Information Services: from Wishful Thinking to Viable Engineering	2002	VLDB	0.00015997985
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
1,737	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010720294
2,137	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	9.4719326e-05
3,169	QueryFormer: A Tree Transformer Model for Query Plan Representation	2022	VLDB	7.4498425e-05
3,924	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	6.6271553e-05
6,740	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	4.944395e-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.0040449103
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
99	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050022914
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041786333
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
429	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00023476494
808	Universality of Serial Histograms	1993	VLDB	0.00016432772

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
8,090	Probabilistic Histograms for Probabilistic Data	2009	VLDB	4.5888589e-05
5,879	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	5.2908101e-05
4,017	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	6.524501e-05
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4275272e-05
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
808	Universality of Serial Histograms	1993	VLDB	0.00016432772
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981