【作者】 张华；

【导师】 朱跃龙； 冯钧；

【作者基本信息】 河海大学 ， 计算机应用， 2006， 硕士

【摘要】 空间连接运算是空间数据库中的一种基本操作,但它也是最复杂、最耗时的操作之一。尽管目前已经有许多空间连接算法,但空间连接运算的代价估计和查询优化仍然有待进一步研究,而且这些空间连接算法基本上都是针对静态数据集的,对于有动态数据集参与的空间连接(时空连接)的问题研究的还比较少。 基于上述背景,本文提出了两种时空连接的方法。这两种方法解决了为空间数据集中的每个对象在时空数据集中寻找到某个未来时间的最近邻的问题。 第一种方法,基于时空数据集的单点查询思想找到每个点最近邻,从而完成整个数据集的连接操作。另一种改进算法是基于多点查找思想,在中间过程中循环地对多个点同时进行剪枝和细化,直到叶子结点,最后再进行计算每个点的最近邻,从而得到整个数据集的连接结果。这种方法的效率比第一种要高,因为循环剪枝后的结果集使得计算的范围缩小了。 本文技术方案的特点如下: (1) 利用时空数据集的单点查询方法,组成了一种比较朴素的时空连接的算法。 (2) 在时空数据集中,通过对中间结点的剪枝,使得R-tree中的多个叶子结点可以同时计算其最近邻,从而减少运行时间,提高效率。 最后在VC++6.0环境下实现了这两种算法,并对算法进行测试和评估。实验表明两种方法都切实可行,并且改进算法的效率要比第一种算法效率高。更多还原

【Abstract】 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.更多还原