DBScholar

Back to papers

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.00019829769
Overall Rank
371 | 97.51%
DOI
10.1145/375663.375686

Incoming Non-self Citations Over Time

Authors

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,320 Distributed Top-N Query Processing with Possibly Uncooperative Local Systems 2003 VLDB 5.5538431e-05
7,332 Selectivity Functions of Range Queries are Learnable* 2022 SIGMOD 5.5499953e-05
7,512 Compact Histograms for Hierarchical Identifiers 2006 VLDB 5.504973e-05
7,519 Comparing Synopsis Techniques for Approximate Spatial Data Analysis 2019 VLDB 5.502959e-05
7,633 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.4792473e-05
8,167 CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation 2005 VLDB 5.3848674e-05
8,196 WISK: A Workload-aware Learned Index for Spatial Keyword Queries 2023 SIGMOD 5.3794981e-05
8,638 Query Log Compression for Workload Analytics 2019 VLDB 5.2978746e-05
8,856 Adaptive Index Structures 2002 VLDB 5.2635701e-05
9,113 Presto’s History-based Query Optimizer 2024 VLDB 5.2276066e-05
9,197 DataSynth: Generating Synthetic Data using Declarative Constraints 2011 VLDB 5.2097089e-05
9,387 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 5.1868213e-05
9,632 Small Selectivities Matter: Lifting the Burden of Empty Samples 2021 SIGMOD 5.1472849e-05
9,718 A Practical Theory of Generalization in Selectivity Learning 2025 VLDB 5.1353964e-05
9,818 Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects 2010 SIGMOD 5.1257999e-05
9,845 Detecting Attribute Dependencies from Query Feedback 2007 VLDB 5.1213286e-05
10,205 Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections 2022 VLDB 5.0603873e-05
10,216 PRICE: A Pretrained Model for Cross-Database Cardinality Estimation 2025 VLDB 5.0584922e-05
10,294 Data-Agnostic Cardinality Learning from Imperfect Workloads 2025 VLDB 5.0431863e-05
10,322 SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index 2026 SIGMOD 5.0346745e-05
10,909 Incremental Query Optimizer Statistics in Amazon Redshift 2026 VLDB 4.9793485e-05
12,549 Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects 2013 VLDB 4.9793485e-05
Previous Page 2 / 2 Next

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.00047863192
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047731453
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
169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027134723
232 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00023792809
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023363722
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
448 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.00018129161
454 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00017962189
866 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD 0.00013381261
1,077 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012154948
1,404 Towards an Analysis of Range Query Performance in Spatial Data Structures 1993 PODS 0.00010767648
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 275 Optimal Histograms with Quality Guarantees 1998 VLDB
2 9,976 Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes 2023 SIGMOD
3 1,508 Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation 2015 SIGMOD
4 283 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD
5 2,140 SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads 2003 VLDB
6 866 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD
7 169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD
8 37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD
9 9,818 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