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: 3270
Venue: SIGMOD
Year: 2001
Pagerank: 0.00021380733
Overall Rank: 512 | 96.44%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 71 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,457	Selectivity Functions of Range Queries are Learnable*	2022	SIGMOD	4.7247191e-05
7,459	Compact Histograms for Hierarchical Identifiers	2006	VLDB	4.7243492e-05
7,728	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.666214e-05
7,742	CXHist : An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	4.6628263e-05
7,776	Plan Stitch: Harnessing the Best of Many Plans	2018	VLDB	4.6537231e-05
7,828	Modeling Shifting Workloads for Learned Database Systems	2024	SIGMOD	4.6407986e-05
8,364	Query Log Compression for Workload Analytics	2019	VLDB	4.5357797e-05
8,474	Adaptive Index Structures	2002	VLDB	4.5029015e-05
8,636	WISK: A Workload-aware Learned Index for Spatial Keyword Queries	2023	SIGMOD	4.4801284e-05
8,870	DataSynth: Generating Synthetic Data using Declarative Constraints	2011	VLDB	4.431665e-05
9,061	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	4.4039656e-05
9,380	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	4.3461329e-05
9,507	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD	4.3341665e-05
9,524	Detecting Attribute Dependencies from Query Feedback	2007	VLDB	4.3310217e-05
9,812	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	4.2783272e-05
9,869	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	4.2675361e-05
9,878	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	4.2656547e-05
9,945	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	4.2432653e-05
10,619	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	4.1945683e-05
11,084	Presto’s History-based Query Optimizer	2024	VLDB	4.1945683e-05
12,060	Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects	2013	VLDB	4.1945683e-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
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041786333
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
252	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030632263
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
361	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00025775749
529	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00020828852
996	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014741524
1,241	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013097578
1,479	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS	0.00011749057

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
9,691	Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes	2023	SIGMOD	4.3035354e-05
2,165	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	9.389622e-05
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
2,137	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	9.4719326e-05
996	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014741524
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
9,507	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD	4.3341665e-05
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737