We present an engineered version of the divide-and-conquer algorithm for finding the closest pair of points, within a given set of points in the XY-plane. For this version of the algorithm we show that only two pairwi...We present an engineered version of the divide-and-conquer algorithm for finding the closest pair of points, within a given set of points in the XY-plane. For this version of the algorithm we show that only two pairwise comparisons are required in the combine step, for each point that lies in the 25-wide vertical slab. The correctness of the algorithm is shown for all Minkowski distances with p ≥ 1. We also show empirically that, although the time complexity of the algorithm is still O（n lgn）, the reduction in the total number of comparisons leads to a significant reduction in the total execution time, for inputs with size sufficiently large.展开更多
定义了满足空间约束的 K 最接近对查询,该查询检索两个数据集在给定约束区域中的 K 最接近对。在空间数据库中,对采用 R 树类型索引存储的数据集给出了三个查询处理算法。其中两阶段的 RJ 和 JR 算法采用了变换范围查询和最接近对查询...定义了满足空间约束的 K 最接近对查询,该查询检索两个数据集在给定约束区域中的 K 最接近对。在空间数据库中,对采用 R 树类型索引存储的数据集给出了三个查询处理算法。其中两阶段的 RJ 和 JR 算法采用了变换范围查询和最接近对查询执行顺序的策略。单阶段基于堆的 SPH 算法采用了最好优先的策略,并利用给出的裁减规则、更新规则和访问顺序规则来提高查询处理效率。实验表明 SPH 具有较好的适用性和性能。展开更多
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.展开更多
文摘We present an engineered version of the divide-and-conquer algorithm for finding the closest pair of points, within a given set of points in the XY-plane. For this version of the algorithm we show that only two pairwise comparisons are required in the combine step, for each point that lies in the 25-wide vertical slab. The correctness of the algorithm is shown for all Minkowski distances with p ≥ 1. We also show empirically that, although the time complexity of the algorithm is still O（n lgn）, the reduction in the total number of comparisons leads to a significant reduction in the total execution time, for inputs with size sufficiently large.
文摘定义了满足空间约束的 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.
