空间数据库中约束K最接近对查询

Constrained K Closest Pairs Query in Spatial Databases

定义了满足空间约束的 K 最接近对查询,该查询检索两个数据集在给定约束区域中的 K 最接近对。在空间数据库中,对采用 R 树类型索引存储的数据集给出了三个查询处理算法。其中两阶段的 RJ 和 JR 算法采用了变换范围查询和最接近对查询执行顺序的策略。单阶段基于堆的 SPH 算法采用了最好优先的策略,并利用给出的裁减规则、更新规则和访问顺序规则来提高查询处理效率。实验表明 SPH 具有较好的适用性和性能。

In this paper,constrained K closest pairs query is introduced,which 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 RJ and JR algorithms adopt the strategy that changes the execution order of range and closest pairs queries, while single-phase heap-based SPH algorithm adopts best-first strategy and utilizes proposed pruning, updating and visit order heuristics to improve its efficiency. Experimental result shows that SPH has better applicability and performance than RJ and JR.