Paper Info
Title
Hierarchically organized skew-tolerant histograms for geographic data objects
Abstract
Histograms have been widely used for fast estimation of query result sizes in query optimization. In this paper, we propose a new histogram method, called the Skew-Tolerant Histogram (STHistogram) for two or three dimensional geographic data objects that are used in many real-world applications in practice. The proposed method provides a significantly enhanced accuracy in a robust manner even for the data set that has a highly skewed distribution. Our method detects hotspots present in various parts of a data set and exploits them in organizing histogram buckets. For this purpose, we first define the concept of a hotspot, and provide an algorithm that efficiently extracts hotspots from the given data set. Then, we present our histogram construction method that utilizes hotspot information. We also describe how to estimate query result sizes by using the proposed histogram. We show through extensive performance experiments that the proposed method provides better performance than other existing methods.
Year
DOI
Venue
2010
10.1145/1807167.1807236
SIGMOD Conference
Keywords
Field
DocType
histogram construction method,dimensional geographic data object,query optimization,new histogram method,existing method,histogram bucket,query result size,skew-tolerant histogram,proposed histogram,skewed distribution,three dimensional,spatial database,histograms
Query optimization,Histogram,Data mining,Computer science,Histogram matching,Exploit,Skew,Data objects,Construction method,Hotspot (Wi-Fi),Database
Conference
Citations 
PageRank 
References 
12
0.53
28
Authors
5
Name
Order
Citations
PageRank
Yohan J. Roh1212.87
Jae Ho Kim219722.06
Yon Dohn Chung366648.55
Jin Hyun Son421718.21
Myoung Ho Kim51040273.40