关于我们 | 联系我们

AG真人-AG真人官方-网站

荣誉资质
当前位置:主页 > 荣誉资质 >

JUST技术:空间毗连运算与空间索引

本文摘要:一、空间毗连界说随着全球定位系统和移动互联设备的普及,海量的空间数据也随之发生。空间毗连(Spatial Join)运算是一类最常用的空间数据分析算子,具有广泛的应用场景。例如统计地铁站周围500米的POI,资助东家合理选择商铺选址;从同一个数据集中分析空间相邻的同伴关系,辅助警方侦察;查询河流周围的住民区和农田,在汛期清除洪水隐患;查找去过疫区的人群,利便疫情防控等。

AG真人官方

一、空间毗连界说随着全球定位系统和移动互联设备的普及,海量的空间数据也随之发生。空间毗连(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)另外,空间工具可分为三种类型:点(Point)、线(LineString)、面(Polygon)。

点是最简朴的空间工具,线和面是庞大空间工具,其空间运算相对耗时。为了简化盘算,一般用空间工具的最小界限矩形MBR(MinimumBounding Rectangle)举行空间运算,获得近似效果,然后对近似效果进一步提纯过滤,获得最终的准确解。

空间毗连运算是基于空间索引实现的,空间索引能够通过快速过滤来提高查询效率,基于空间索引的空间毗连的运算历程如下:1)构建空间索引。对荟萃S中所有空间工具s,使用s.mbr构建空间索引I。

2)循环查询。对荟萃R中的每个空间工具r,用r查询索引I中与其满足空间谓词θ的所有空间工具s,并将二元组(r,s)加入效果集。

空间索引不止一种,选取合理的空间索引对提高空间毗连运算的性能至关重要。为了验证空间索引对空间毗连运算性能的影响,本文首先在第2节中先容几种最常用的空间索引。然后在第3节举行实验对比,划分以空间索引、空间工具类型、空间毗连谓词为变量,分析影响空间毗连运算性能的因素。

二、空间索引空间索引一般是基于数据结构中的树来实现的。在索引树上,一个节点对应一个矩形的空间规模,父节点的空间规模包罗所有子节点的空间规模。空间工具依据其MBR,存储在树的对应节点上。

在查询时,首先依据查询工具的MBR遍历树上与该MBR相交的所有节点,并收集节点上存储的空间工具作为一个候选效果集,最后再凭据空间谓词θ做进一步过滤,保留满足空间谓词的候选工具,组成最终的效果集。下面划分先容三种最常用的空间索引:Quadtree索引、KDtree索引和Rtree索引,且设定用数据集S构建索引,然后用数据集R中的空间工具r查询空间索引。

2.1 Quadtree索引Quadtree[1]索引是一棵四叉树,支持所有空间工具类型。Quadtree将荟萃S的全局空间规模G递归地划分成4子空间,直到子空间内的空间工具数量小于即是设定的阈值α,并对四个子空间划分编号0、1、2、3,如图1(a)所示(α = 1)。然后用四叉树结构组织所有子空间,如图1(b)所示,树的根节点对应空间规模G,一个节点对应一个子空间。对数据集S中的空间工具s,将其存储在包罗s.mbr的最小子空间对应的节点中,当s是空间点时,s与s.mbr空间上等价,所有空间点均存储在叶子节点中,如图1所示。

图1 Quadtree索引在查询时,使用r.mbr近似表现空间工具r,查找Quadtree中与r.mbr相交的节点,然后判断节点中的所有空间工具s是否与r存在空间相交关系。图1中,红色的矩形表现r.mbr,该矩形在Quadtree上遍历的节点标志为红色,然后找到叶子节点233上与其相交的一个空间点s,最后再判断r和s的相交关系。通过空间索引,可以快速过滤掉与查询框r.mbr不相交的节点,加速遍历查询效率。2.2KDtree索引KDtree[2]索引是一棵二叉树,仅支持空间点工具。

在构建索引时,首先使用荟萃S中第一个空间点s1的构建根节点root,根节点包罗空间点s1和标签odd,odd是个布尔值,true表现该节点用s1.x举行空间划分,false表现用s1.y,KDtree中父节点和子节点的odd相反,即交替地使用x和y值举行空间划分。对于后续的空间点si(i>1),以root节点为当前节点,递归地执行以下步骤:1)判断当前节点是否为叶子节点,若是执行步骤2),若不是执行步骤3);2)设当前节点中存储的空间点是s,odd = true时凭据s.x的值将当前节点对应的空间规模一分为二生成两个子节点,反之凭据s.y的值举行划分。然后凭据si.x(或si.y)与s.x(或s.y)的巨细关系,将si生存到对应子节点上,子节点的odd值与当前节点相反;3)使用步骤2)中形貌的判断方法,获得子节点,并将其设为当前节点,然后执行步骤1)。

图2 KDtree索引在构建好的KDtree索引中,每个空间点对应一个节点(叶子或非叶子节点),如图2所示。查询时,用r.mbr遍历树上所有与之相交的节点,然后摘取节点上的空间点s并判断r与s是否空间相交。在图2中,红色矩形表现r.mbr,它在KDtree上遍历的节点用红色标志。

2.3Rtree索引Rtree[3]索引是一棵多叉树,支持所有空间工具。Rtree构建索引的思想是空间聚类,对荟萃S中的所有空间工具聚类,生成n个聚类,然后自底向上递归地对n份聚类进一步执行聚类,直到n = 1。Rtree中一个节点对应一个聚类,与Quadtree和KDtree差别的是,Rtree同一级此外节点之前可以存在重叠,这保证了一个空间工具仅属于一个Rtree的叶子节点,即Rtree中所有空间工具之存储在叶子节点中,如图3所示。

图3Rtree索引下面先容一种JTS[5](JavaTopology Suite)实现的一种Rtree索引——STRtree[4]。该索引的构建步骤如下:1)初始化荟萃C = {c1,c2,c3,..,cn}, ci是仅包罗一个空间工具si的空间聚类,ci.mbr = si.mbr,n是荟萃S中的空间工具数量。2)STRtree有一个阈值m,表现一个非叶子节点所包罗的最大子节点数量。

γ = ⌈n/m⌉表现荟萃C需要被划分成γ个聚类。如果γ = 1,说明n≤ m,则将荟萃C聚类成一个根节点Root,ci是Root的子节点,构建索引完成。如果γ > 1,则执行步骤3)。3)ε = ⌈sqrt(γ)⌉表现每个聚类在x和y偏向上划分的份数。

对荟萃C根据ci.mbr.minx在x偏向递增排序,然后将其在x偏向上平均地划分为ε份聚类,然后对每份效果在y偏向上根据ci.mbr.miny排序并平均地划分成ε份聚类,两次划分生成大于即是γ份的聚类,γ≤ k < n,荟萃C中的聚类是荟萃C’中聚类的子节点。用C’替换C,然后执行步骤2)。在查询时,同样用r.mbr遍历STRtree中与之相交的节点,并收集叶子节点上存储的所有空间工具s,然后判断r和s是否空间相交。

遍历历程如图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最近邻毗连性能四、总结本文先容了空间毗连运算的界说和基于空间索引的空间毗连运算方法。同时,本文先容了3种常用的树结构的空间索引和各自的特点。最后,本文做了对比分析实验,以验证差别空间索引对差别空间工具的支持情况和性能差异,以便在差别的空间毗连运算场景下,选择适当的空间索引,实现高效的查询和盘算。

参考文献[1] Finkel RA, Bentley J L. Quad trees a data structure for retrieval on composite keys[J].Acta informatica, 1974, 4(1): 1-9.[2] R.Agrawal, C. Faloutsos, and A. Swami. 1993. Efficient similarity search insequence databases. Springer, 69-84.[3] Guttman,A., 1984. R-trees: a dynamic index structure for spatial searching (Vol. 14,No. 2, pp. 47-57). ACM.[4] S. T.Leutenegger, M. Lopez, J. Edgington, et al. STR: A simple and efficientalgorithm for R-tree packing. In ICDE, 1997.[5] https://github.com/locationtech/jts。


本文关键词:AG真人,JUST,技术,空间,毗连,运算,与,索引,一,、,空间

本文来源:AG真人-www.qingxiuyuan.com

Copyright © 2007-2021 www.qingxiuyuan.com. AG真人科技 版权所有 备案号:ICP备90038471号-5