一、空间连接定义

随着全球定位系统和移动互联设备的普及，海量的空间数据也随之产生。空间连接（Spatial Join）运算是一类最常用的空间数据分析算子，具有广泛的应用场景。例如统计地铁站周围500米的POI，帮助店主合理选择商铺选址；从同一个数据集中分析空间相邻的同伴关系，辅助警方侦察；查询河流周围的居民区和农田，在汛期排除洪水隐患；查找去过疫区的人群，方便疫情防控等。

下面给出空间连接的定义：给定空间对相集合R和S以及空间谓词θ，计算并输出所有空间对象二元组（r, s），满足r∈R，s∈S，且r和s满足空间谓词θ，形式化定义如下。

 (1)

空间谓词θ可以分为三类。

1）空间拓扑：如intersects(相交)、contains（包含）等；

2）空间距离：即distance，表示空间对象s与r的空间距离小于等于设定阈值δ，由定义（1）派生出distance连接的定义如下。

 (2)

3）空间k最近邻：即kNN（k Nearest Neighbors），表示空间对象s是数据集S中与r距离最近的k个空间对象之一，由定义（1）派生出kNN连接的定义如下。

 (3)

三、实验分析

为了验证不同空间索引在空间连接运算中的性能，我们利用真实的空间数据对不同空间索引、不同空间对象类型和不同空间连接运算做了对比实验，总结出了不同空间索引的适用场景。

3.1 实验数据和实验环境

我们使用OSM（Open Street Map）提供的部分全球空间数据作为实验数据，如表1所示。实验环境是8核CPU、16GB内存的个人电脑。

表1 实验数据集

3.2 实验结果

实验的变量有三种：空间索引、空间对象类型、空间连接运算。统计的实验数据有空间索引的构建时长和空间连接的运算时长。另外，实验中调用的空间索引都是JTS^[5]实现的。

图4展示了构建空间索引的耗时情况。取STRtree的阈值m = 10，从图中可看出，不管对于哪种空间对象类型，构建STRtree索引的耗时最短，因为STRtree每个节点的子节点数量最大，所以节点数量最少，树的深度最小，则构建索引时的递归层数也最小。KDtree索引仅支持空间点，由于是二叉树，且每个节点仅存储一个空间点，KDtree的节点个数最多，树的深度最深，因此其构建时间最长。Quadtree是四叉树，其构建索引时间介于KDtree和STRtree之间，且远大于STRtree。

图4 空间索引的构建性能

图5展示了空间拓扑连接的实验性能，谓词θ = intersects。图中x轴下标的格式为S-R，例如Point-LineString表示对Point数据集构建空间索引，然后用LineString数据集中的空间对象查询空间索引。对空间点构建Quadtree索引，用数据集LineString和Polygon去查询时，计算耗时非常长，分别达到了8714毫秒和13424毫秒，说明Quadtree索引并不适用于空间点。为了验证这一点，我们将两个数据集互换位置，做了对比实验，当用LineString或Polygon数据集构建Quadtree索引，用Point数据集查询时，计算耗时缩短1~2个数量级，如图5右边所示。从总体来看，KDtree索引适合为空间点构建索引，Quadtree和STRtree适合为线和面构建索引。Quadtree构建索引时间长，查询耗时短，STRtree构建索引时间短，查询耗时长，若以构建索引时间与查询计算时间之和作为评价指标，Quadtree性能优于STRtree。

图5 空间拓扑连接性能

图6展示了空间距离连接运算（δ = 100米）的性能，在空间距离连接时，将r.mbr向外扩展δ的距离生成扩展最小边界矩形r.embr(δ)，用r.embr(δ)查询空间索引，然后判断空间对象s与r的距离distance(r, s)是否小于等于δ。图6中的实验结果变化趋势与图5中类似。需要注意的是，在空间距离连接中，Quadtree和STRtree的性能差异相较图5中变小了，说明STRtree在空间距离变化过程中性能更加稳定。另外，相同数据集之间的空间距离连接要比图5中的空间拓扑连接的耗时更短。主要原因是，虽然空间拓扑连接的结果要比空间距离连接的结果少，但是判断两个空间对象r和s的空间intersects关系（等价于distance(r, s) = 0）要比判断distance(r, s) ≤ δ更耗时。

图6 空间距离连接性能

图7展示了kNN连接运算的性能（k = 10），只有STRtree索引支持kNN查询。当Point数据集与其它数据集做kNN连接时，计算耗时较低且交换数据集时性能变化不大，因为点是最简单的空间对象，所以点与其它空间对象距离的计算复杂度最低。当LineString和Polygon做kNN连接时，其耗时相对较长且交换数据集时性能相差一倍，可以看出，为LineString构建STRtree索引比为Polygon构建索引性能更好， STRtree索引更适用于空间线。

图7 基于STRtree索引的空间k最近邻连接性能