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: 4342
Venue: SIGMOD
Year: 2010
Pagerank: 5.2434488e-05
Overall Rank: 9,642 | 33.85%
DOI: 10.1145/1807167.1807236

Incoming Non-self Citations Over Time

Authors

1. Yohan J. Roh (Samsung)
2. Jae Ho Kim (Korea Advanced Institute of Science and Technology)
3. Yon Dohn Chung (Korea University)
4. Jin Hyun Son (Hanyang University)
5. Myoung Ho Kim (Korea Advanced Institute of Science and Technology)

BibTeX Citation

@inproceedings{roh_sigmod10,
        title = {{Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects}},
        author = {Roh, Yohan J. and Kim, Jae Ho and Chung, Yon Dohn and Son, Jin Hyun and Kim, Myoung Ho},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807236},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807236},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
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
339	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020723773
365	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00020041735
635	Evaluating Top-k Selection Queries	1999	VLDB	0.00015527042
650	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00015319951
723	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014620977
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
2,127	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.127762e-05
3,111	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.7470414e-05
3,893	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	7.04191e-05
4,174	Selectivity Estimation for Spatio-Temporal Queries to Moving Objects	2002	SIGMOD	6.8515543e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	267	Optimal Histograms with Quality Guarantees	1998	VLDB
2	9,825	Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets	2003	VLDB
3	365	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD
4	1,668	Global Optimization of Histograms	2001	SIGMOD
5	274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
6	12,712	Scalable Continuous Query Processing by Tracking Hotspots	2006	VLDB
7	1,729	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB
8	118	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD
9	2,127	Selectivity Estimation in Spatial Databases	1999	SIGMOD
10	723	Dynamic Multidimensional Histograms	2002	SIGMOD