STHoles: A Multidimensional Workload-Aware Histogram

Summary: STHoles is a workload-aware multidimensional histogram with nested buckets that capture uniform-density regions. Built without scanning data, it uses query results to place buckets where the workload concentrates, yielding accurate selectivity and often outperforming data-driven histograms. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h0452cd250d7dcceb
Venue: SIGMOD
Year: 2001
Pagerank: 0.00019768921
Overall Rank: 372 | 97.51%
DOI: 10.1145/375663.375686

Incoming Non-self Citations Over Time

Authors

1. Nicolas Bruno (Columbia University)
2. Surajit Chaudhuri (Microsoft)
3. Luis Gravano (Columbia University)

BibTeX Citation

@inproceedings{bruno_sigmod01,
        title = {{STHoles: A Multidimensional Workload-Aware Histogram}},
        author = {Bruno, Nicolas and Chaudhuri, Surajit and Gravano, Luis},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375686},
        url = {https://dl.acm.org/doi/10.1145/375663.375686},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 72 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,342	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB	5.5329816e-05
7,355	Selectivity Functions of Range Queries are Learnable*	2022	SIGMOD	5.529034e-05
7,536	Compact Histograms for Hierarchical Identifiers	2006	VLDB	5.4844135e-05
7,542	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	5.4821664e-05
7,654	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	5.4588598e-05
8,186	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.3653848e-05
8,219	WISK: A Workload-aware Learned Index for Spatial Keyword Queries	2023	SIGMOD	5.359172e-05
8,663	Query Log Compression for Workload Analytics	2019	VLDB	5.2779628e-05
8,883	Adaptive Index Structures	2002	VLDB	5.2436823e-05
9,141	Presto’s History-based Query Optimizer	2024	VLDB	5.2078543e-05
9,229	DataSynth: Generating Synthetic Data using Declarative Constraints	2011	VLDB	5.1900257e-05
9,422	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.1672232e-05
9,667	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	5.1278365e-05
9,753	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	5.1159926e-05
9,859	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD	5.1064323e-05
9,888	Detecting Attribute Dependencies from Query Feedback	2007	VLDB	5.1020175e-05
10,249	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.0412674e-05
10,257	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	5.039379e-05
10,327	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	5.0241309e-05
10,355	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.0156513e-05
10,979	Incremental Query Optimizer Statistics in Amazon Redshift	2026	VLDB	4.9605343e-05
12,598	Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects	2013	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047770864
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047654188
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033847446
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031291457
171	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027063233
234	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00023726296
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023327437
277	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002235043
285	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022143946
450	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.0001806593
457	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017915659
868	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00013336675
1,080	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012114187
1,411	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS	0.00010729946

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	277	Optimal Histograms with Quality Guarantees	1998	VLDB
2	10,014	Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes	2023	SIGMOD
3	1,511	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD
4	285	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
5	2,154	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB
6	868	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD
7	171	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD
8	37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD
9	9,859	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD
10	119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD