Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects

Summary: Proposes STHistogram, a skew-tolerant histogram for 2D/3D geographic data objects, delivering robust accuracy under highly skewed distributions. It detects hotspots and uses them to guide bucketization, yielding tighter cardinality estimates and superior performance to prior histograms. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4280
Venue: SIGMOD
Year: 2010
Pagerank: 4.3341665e-05
Overall Rank: 9,507 | 33.87%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
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
367	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025509745
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021380733
668	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00018430721
805	Evaluating Top-k Selection Queries	1999	VLDB	0.00016437265
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
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
2,053	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6728745e-05
2,748	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	8.1785955e-05
3,893	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.6584217e-05
4,146	Selectivity Estimation for Spatio-Temporal Queries to Moving Objects	2002	SIGMOD	6.4100417e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
9,663	Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets	2003	VLDB	4.3089103e-05
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021380733
1,120	Global Optimization of Histograms	2001	SIGMOD	0.00013856211
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
12,519	Scalable Continuous Query Processing by Tracking Hotspots	2006	VLDB	4.1945683e-05
1,695	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	0.00010882793
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
2,053	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6728745e-05
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524