Selectivity Estimation for Spatio-Temporal a Overlap Join
Myoung-Sul Lee, Jong-Yun Lee · 2008
A spatio-temporal join is an expensive operation that is commonly used in spatio-temporal database systems. In order to generate an efficient query plan for the queries involving spatio-temporal join operations, it is crucial to estimate accurate selectivity for the join operations. Given two dataset of discrete data and a timestamp , a spatio-temporal join retrieves all pairs of objects that are intersected each other at . The selectivity of the join operation equals the number of retrieved pairs divided by the cardinality of the Cartesian product . In this paper, we propose aspatio-temporal histogram to estimate selectivity of spatio-temporal join by extending existing geometric histogram. By using a wide spectrum of both uniform dataset and skewed dataset, it is shown that our proposed method, called Spatio-Temporal Histogram, can accurately estimate the selectivity of spatio-temporal join. Our contributions can be summarized as follows: First, the selectivity estimation of spatio-temporal join for discrete data has been first attempted. Second, we propose an efficient maintenance method that reconstructs histograms using compression of spatial statistical information during the lifespan of discrete data.