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: 3333
Venue: SIGMOD
Year: 2001
Pagerank: 0.00010057026
Overall Rank: 1,668 | 88.56%
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
114	Executing SQL over Encrypted Data in the Database-Service-Provider Model	2002	SIGMOD	0.00032363776
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
781	Self-tuning Database Technology and Information Services: from Wishful Thinking to Viable Engineering	2002	VLDB	0.00014085674
1,061	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012369764
1,170	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011827259
2,121	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	9.1402718e-05
2,355	QueryFormer: A Tree Transformer Model for Query Plan Representation	2022	VLDB	8.7022189e-05
3,086	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	7.7708642e-05
6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.9443409e-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.0024089429
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00048351457
89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00035031529
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
118	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031922279
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027541029
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
327	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00021091539
786	Universality of Serial Histograms	1993	VLDB	0.00014053885

Semantically Similar Papers

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