In this paper, constrained K closest pairs query is introduced, wbich retrieves the K closest pairs satisfying the given spatial constraint from two datasets. For data sets indexed by R trees in spatial databases, thr...In this paper, constrained K closest pairs query is introduced, wbich retrieves the K closest pairs satisfying the given spatial constraint from two datasets. For data sets indexed by R trees in spatial databases, three algorithms are presented for answering this kind of query. Among of them, two-phase Range＋Join and Join＋Range algorithms adopt the strategy that changes the execution order of range and closest pairs queries, and constrained heap-based algorithm utilizes extended distance functions to prune search space and minimize the pruning distance. Experimental results show that constrained heap-base algorithm has better applicability and performance than two-phase algorithms.展开更多
As early as in 1975, Shamos and Hoey first gave an O（n lg n）-time divide-and-conquer algorithm （Stt algorithm in short） for the problem of finding the closest pair of points. In one process of combination, the Euc...As early as in 1975, Shamos and Hoey first gave an O（n lg n）-time divide-and-conquer algorithm （Stt algorithm in short） for the problem of finding the closest pair of points. In one process of combination, the Euclidean distances between 3n pairs of points need to be computed, so the overall complexity of computing distance is then 3n lgn. Since the computation of distance is more costly compared with other basic operation, how to improve SH algorithm from the aspect of complexity of computing distance is considered. In 1998, Zhou, Xiong and Zhu improved SH algorithm by reducing this complexity to 2n lg n. In this paper, we make further improvement. The overall complexity of computing distances is reduced to （3n lg n）/2, which is only half that of SH algorithm.展开更多
We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle...We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.展开更多
定义了满足空间约束的 K 最接近对查询,该查询检索两个数据集在给定约束区域中的 K 最接近对。在空间数据库中,对采用 R 树类型索引存储的数据集给出了三个查询处理算法。其中两阶段的 RJ 和 JR 算法采用了变换范围查询和最接近对查询...定义了满足空间约束的 K 最接近对查询,该查询检索两个数据集在给定约束区域中的 K 最接近对。在空间数据库中,对采用 R 树类型索引存储的数据集给出了三个查询处理算法。其中两阶段的 RJ 和 JR 算法采用了变换范围查询和最接近对查询执行顺序的策略。单阶段基于堆的 SPH 算法采用了最好优先的策略,并利用给出的裁减规则、更新规则和访问顺序规则来提高查询处理效率。实验表明 SPH 具有较好的适用性和性能。展开更多
基金Supported by National Natural Science Foundationof China (60073045)
文摘In this paper, constrained K closest pairs query is introduced, wbich retrieves the K closest pairs satisfying the given spatial constraint from two datasets. For data sets indexed by R trees in spatial databases, three algorithms are presented for answering this kind of query. Among of them, two-phase Range＋Join and Join＋Range algorithms adopt the strategy that changes the execution order of range and closest pairs queries, and constrained heap-based algorithm utilizes extended distance functions to prune search space and minimize the pruning distance. Experimental results show that constrained heap-base algorithm has better applicability and performance than two-phase algorithms.
基金This work is supported by the National Natural Science Foundation of China （Grant No. 60496321） and Shanghai Science and Technology Development Fund （Grant No. 025115032）.
文摘As early as in 1975, Shamos and Hoey first gave an O（n lg n）-time divide-and-conquer algorithm （Stt algorithm in short） for the problem of finding the closest pair of points. In one process of combination, the Euclidean distances between 3n pairs of points need to be computed, so the overall complexity of computing distance is then 3n lgn. Since the computation of distance is more costly compared with other basic operation, how to improve SH algorithm from the aspect of complexity of computing distance is considered. In 1998, Zhou, Xiong and Zhu improved SH algorithm by reducing this complexity to 2n lg n. In this paper, we make further improvement. The overall complexity of computing distances is reduced to （3n lg n）/2, which is only half that of SH algorithm.
基金This work is partially supported by Utah State University under Grant No.A13501.
文摘We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.
文摘定义了满足空间约束的 K 最接近对查询,该查询检索两个数据集在给定约束区域中的 K 最接近对。在空间数据库中,对采用 R 树类型索引存储的数据集给出了三个查询处理算法。其中两阶段的 RJ 和 JR 算法采用了变换范围查询和最接近对查询执行顺序的策略。单阶段基于堆的 SPH 算法采用了最好优先的策略,并利用给出的裁减规则、更新规则和访问顺序规则来提高查询处理效率。实验表明 SPH 具有较好的适用性和性能。
