Research On Processing And Optimization Of Join Operation For Spatio-temporal Datasets

Spatial join is one of the most complex and time-consuming operations in spatial database systems. Although many spatial join algorithms have been proposed, more in-depth studies still need to be done on cost estimation and query optimization of spatial join operation.This paper proposes two join algorithms for spatio-temporal datasets. These algorithms resolve the problem about searching the nearest neighbor for each of the spatial datasets in the spatio-temporal datasets in some future time.The first algorithm completes the connection operation of the whole data sets by using the way of single point query to inquire the nearest neighbor of each point. The second one, an improved algorithm, is named as multi-points query. Taking the advantages of spatial index R-tree and the spatio-temporal index TPR-tree, the multi-points query method divides the join operation into two loop steps: filtering step and refinement step. At the filtering step, the nodes inside the spatio-temporal index which are decided as "useless" by comparing their approximate information with that of the spatial index are pruned;and at the refinement step, only the objects inside the "useful" nodes are used as the candidates for join operation.. The two steps run in loop for the non-leaf nodes. The efficiency of the latter is higher than that of the former, because the result collection after the cutting course narrows the calculation ranges.The contributions of this paper are as the followings:(1) A simple spatial join algorithm is constructed by the single point query for spatio-temporal datasets.(2) Through pruning the middle nodes, the multi-leaf nodes of the R-tree can compute the nearest neighbors at the same time, so as to reduce the runtime and improve the efficiency.The two algorithms are performed in VC++ 6.0. The experiment results show that the two methods are feasible, and that the improved one is more efficiency than the first one.