一、空间连接定义
随着全球定位系统和移动互联设备的普及,海量的空间数据也随之产生。空间连接(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 实验数据集
数据集 |
点(Point) |
线(LineString) |
面(Polygon) |
数据量 |
50万条 |
20万条 |
20万条 |
文件大小 |
5.47MB |
62.1MB |
57.5MB |
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近邻连接性能
转载请注明:康瑞部落 » JUST技术:空间连接运算与空间索引