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: hb1492c9ff8aa4b6a
Venue: SIGMOD
Year: 2001
Pagerank: 9.8655879e-05
Overall Rank: 1,687 | 88.66%
DOI: 10.1145/375663.375687

Incoming Non-self Citations Over Time

Authors

1. H.V. Jagadish (University of Michigan)
2. Hui Jin (National University of Singapore)
3. Beng Chin Ooi (National University of Singapore)
4. Kian-Lee Tan (National University of Singapore)

BibTeX Citation

@inproceedings{jagadish_sigmod01,
        title = {{Global Optimization of Histograms}},
        author = {Jagadish, H.V. and Jin, Hui and Ooi, Beng Chin and Tan, Kian-Lee},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375687},
        url = {https://dl.acm.org/doi/10.1145/375663.375687},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
115	Executing SQL over Encrypted Data in the Database-Service-Provider Model	2002	SIGMOD	0.00031742473
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
780	Self-tuning Database Technology and Information Services: from Wishful Thinking to Viable Engineering	2002	VLDB	0.00014025444
1,064	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012202282
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011777105
2,140	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	8.9682092e-05
2,250	QueryFormer: A Tree Transformer Model for Query Plan Representation	2022	VLDB	8.7533306e-05
3,052	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	7.7052471e-05
6,221	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.8463347e-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.0023947656
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047863192
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.0003475226
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003137356
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
169	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027134723
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022413521
283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022214789
336	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020657819
806	Universality of Serial Histograms	1993	VLDB	0.00013792174

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD
2	119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD
3	8,206	Probabilistic Histograms for Probabilistic Data	2009	VLDB
4	5,534	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS
5	3,644	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS
6	742	Dynamic Multidimensional Histograms	2002	SIGMOD
7	9,142	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD
8	283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
9	806	Universality of Serial Histograms	1993	VLDB
10	275	Optimal Histograms with Quality Guarantees	1998	VLDB