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: 3332
Venue: SIGMOD
Year: 2001
Pagerank: 0.00020041735
Overall Rank: 365 | 97.50%
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 21 of 71 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,206	Selectivity Functions of Range Queries are Learnable*	2022	SIGMOD	5.6731116e-05
7,375	Compact Histograms for Hierarchical Identifiers	2006	VLDB	5.6299286e-05
7,379	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	5.629255e-05
7,554	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	5.6001388e-05
7,655	Plan Stitch: Harnessing the Best of Many Plans	2018	VLDB	5.5741093e-05
8,021	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.5055705e-05
8,048	WISK: A Workload-aware Learned Index for Spatial Keyword Queries	2023	SIGMOD	5.5003171e-05
8,583	Query Log Compression for Workload Analytics	2019	VLDB	5.4079618e-05
8,689	Adaptive Index Structures	2002	VLDB	5.3843737e-05
9,028	DataSynth: Generating Synthetic Data using Declarative Constraints	2011	VLDB	5.3292816e-05
9,209	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.3058708e-05
9,455	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	5.2653318e-05
9,642	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD	5.2434488e-05
9,671	Detecting Attribute Dependencies from Query Feedback	2007	VLDB	5.238674e-05
9,958	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	5.1879626e-05
10,016	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.1764556e-05
10,028	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	5.1745962e-05
10,097	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.1502319e-05
10,875	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	5.093636e-05
11,290	Presto’s History-based Query Optimizer	2024	VLDB	5.093636e-05
12,258	Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects	2013	VLDB	5.093636e-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
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
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
168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027541029
222	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00024193708
235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023783792
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
435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.000185063
448	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00018292618
850	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00013619394
1,053	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012401532
1,370	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS	0.00010997795

Semantically Similar Papers

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