EN中文

Journal of Geo-information Science >

2022 , Vol. 24 >Issue 1: 74 - 86

DOI: https://doi.org/10.12082/dqxxkx.2022.210457

Parallel Ripley's K Function based on Hilbert Spatial Partitioning and Geohash Indexing

  • KANG Yangxiao , 1, 2 ,
  • GUI Zhipeng , 1, 3, * ,
  • DING Jinchen 1 ,
  • WU Jinghang 1 ,
  • WU Huayi 3
Expand
  • 1. School of Remote Sensing and Information Engineering, Wuhan University, Wuhan 430079, China
  • 2. Chongqing Geomatics and Remote Sensing Center, Chongqing 401147, China
  • 3. State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China
* GUI Zhipeng, E-mail:

Received date: 2021-08-04

  Revised date: 2021-08-27

  Online published: 2022-03-25

Supported by

National Key Research and Development Program of China(2018YFC0809806)

National Key Research and Development Program of China(2017YFB0503704)

National Natural Science Foundation of China(41971349)

National Natural Science Foundation of China(42090010)

Copyright

Copyright reserved © 2022
Fold

Abstract

As a second-order analysis method of spatial point patterns, Ripley's K function (K function for short) uses distance as an independent variable to detect the distribution patterns of points under different spatial scales, which has been widely used in distinct fields such as ecology, economics, and geography. However, the applications of K function are limited due to the sharply increased computational cost of nested traversals on the point-pair distance measurements in both estimation and simulation phases when the point size getting larger. Therefore, the optimization of algorithm workflow and parallel acceleration have become the key technologies for tackling the performance bottleneck and computability problem of K function. Among these solutions, hash-based partitioning has been widely adopted in parallel computing frameworks for enabling data decomposition, while R-tree indexes have been proposed to reduce the computational cost of point-pair distance measurements by using spatial query instead. However, default hash-based partitioning methods ignore the spatial proximity of data distributions, while R-tree indexes fail to save query time of neighboring points under large spatial distance threshold comparing with pointwise distance calculation. In order to address these issues, this paper proposes an acceleration method for K function based on the space filling curves. Specifically, the Hilbert curve is adopted to achieve spatial partitioning, which reduces the data tilt and communication cost between partitions by better considering the spatial proximity. Upon the partition result, local indexing based on Geohash code is further developed to improve the spatial indexing strategy, which embeds spatial information in codes for achieving quick distance filtering, in turn accelerates the pointwise distance measurements. To verify the effectiveness of the proposed method, it is compared with two optimization methods adopted in previous studies, i.e., default partition without indexing, and KDB-tree partition with R-tree indexing, by analyzing the calculation time of K function for point of interests (POIs) of enterprise registration data in Hubei province, China under different data sizes, spatial distance thresholds, and computing nodes in a computing cluster. Experimental results indicate that the time cost of the proposed method is about 1/4 of that for default partition without indexing under the data scale of 300 000 points. Besides, the speedup ratio is larger than 3.6 times under 9 nodes. Therefore, the proposed method can improve performance of K function effectively in a distributed environment and has a promising scalability and could provide a reference for accelerating other spatial patterns analysis algorithms as well.

Key words： Ripley's K function; distributed computing; Apache Spark; high performance geocomputation; Hilbert curve; Geohash; point pattern analysis; spatial filling curves

Cite this article

KANG Yangxiao , GUI Zhipeng , DING Jinchen , WU Jinghang , WU Huayi . Parallel Ripley's K Function based on Hilbert Spatial Partitioning and Geohash Indexing[J]. Journal of Geo-information Science, 2022 , 24(1) : 74 -86 . DOI: 10.12082/dqxxkx.2022.210457

1 引言

点模式分析通过将观测点分布模式和空间随机分布模式进行对比,探测点事件分布模式的空间分布性质和挖掘点事件所代表的空间分布现象本身及其产生过程[1]。Ripley's K函数（以下简称为 “K函数”）是点模式分析方法的典型代表[2,3],其将尺度作为输入变量研究点数据在不同尺度下的分布模式。由于不会受到可变面元问题（Modifiable Area Unit Problem,MAUP）的影响,K函数在生态学[3]、犯罪学[4]、社会学[5]等诸多领域得到广泛应用。K函数计算的核心步骤是点对间距离计算,具有 O n 2级别的时间复杂度。由于需要在不同距离阈值下对观测数据与多次模拟数据分别逐点计算K函数值,随着数据规模的增大,K函数计算开销变得不可接受,容易产生计算时间过长、单机环境下内存溢出等问题[6]。因此,如何提升海量点事件聚集模式分析挖掘的计算效率,成为降低K函数应用门槛的关键。目前K函数加速的研究主要包括计算流程优化和并行环境下算法改造2个方面[7]。
针对K函数流程优化,现有方案多采用将点对遍历从完整研究区域范围缩小至局部范围的思想,利用预排序或索引避免不必要的点对距离计算[8]。其中,预排序方案将数据集按照x（或y）方向排序并等分为若干个粗“箱子”,然后再按照另一方向排序并等分,将粗“箱子”划分为细“箱子”,在点对距离计算时便通过遍历“箱子”过滤不必要的点[8]。但该方法本质上仍然将空间数据作为一维数据看待,未考虑空间数据分布的异质性,容易出现各“箱子”内点数量不均导致优化效果差的现象,并且使用随机策略选择初始“箱子”加剧了优化效果的不稳定性。基于索引的优化方法将K函数的点对距离计算视为若干个圆形的空间查询任务以缩小遍历范围[9,10]。R树索引使用空间对象间的最小外包矩形（Minimum Bounding Rectangle,MBR）进行空间分割,在空间查询时采用“粗筛-精筛”耦合的思路[11],“粗筛”阶段获得MBR与目标对象MBR相交的候选对象,精筛阶段再逐一遍历计算。然而当K函数距离阈值不断增大时,在“粗筛”阶段R树索引会与过多空间对象的MBR相交而逐渐失去加速效果,甚至会导致时间开销大于逐点遍历的“负优化”现象[12,13]。尽管预排序和R树索引一定程度上提升了K函数计算性能,但存在优化效果不稳定、索引失效等局限性,因此需要改进索引策略以适应距离阈值较大时的点对距离计算。
K函数计算过程中各个事件点的点对距离计算互相独立,因此将K函数计算任务分解给多核CPU、众核GPU并行处理可提升整体计算效率。近些年来涌现出诸多基于OpenMP、MPI、CUDA等并行计算框架的K函数加速方案[13,14,15],但OpenMP和MPI需要人为设置调度、异常处理等策略且对空间数据结构支持有限,加重了开发成本;而CUDA依赖高端专用CPU/GPU的支持,导致计算环境受限。Hadoop、Spark等分布式计算框架是目前大规模并行计算的主流方案,但用于K函数计算等空间分析任务时需解决空间数据分区问题。通常这些原生框架对空间数据支持有限,其默认分区方法（如哈希分区、范围分区等）应用于空间数据时,会因忽视空间邻近性而割裂数据间隐式关联,造成数据倾斜和计算“热点”问题[16],从而降低分布式系统整体计算性能。针对上述问题,有学者提出使用KDB树空间分区、基于STR算法的R树索引、双层Hash权重缓存和自定义二进制序列化等多策略组合的方式综合优化K函数计算流程和加速并行计算[12],并针对时空、空间、局部和交叉K函数等取到较好的优化效果[13]。利用分布式系统并行计算K函数,并引入空间分区缓解数据倾斜和计算“热点”问题,能够有效提升计算效率;但KDB分区易产生条形划分,针对K函数点对计算的圆形范围查询,会增加跨节点数据通讯成本[17,18,19],存在优化空间。
作为一种能够贯穿多维空间的一维连续曲线和有效的降维方法[20],空间填充曲线被应用于各类GIS分析算法,特别是在点数据类型的空间索引及空间划分上表现出色[21,22],具有加速K函数在分布式系统中计算效率的潜力。常用的空间填充曲线主要为Z曲线和Hilbert曲线[23]。Z曲线具有局部保序性,在空间上相邻的点在曲线上也邻近,且拥有诸如Geohash的统一全球编码方案[24],因此在空间索引,尤其是点数据的邻近查询、范围查询等场景的应用较为广泛[22],适用于K函数圆形范围查询。但Z曲线也具有较为严重的空间突变性,即曲线上相邻的点在空间上可能距离较远,导致其在空间划分的表现远差于Hilbert曲线。Hilbert曲线在所有空间填充曲线类型中具有最佳的空间聚集性[23],常应用于空间划分且能够获得接近正方形的划分形态[25],因此适用于K函数并行计算的空间分区,但构造精细的高阶Hilbert曲线时间开销较大,因此在空间索引的应用方面不如编码更为简易的Z曲线。
针对目前K函数优化方案中索引与分区存在的问题,并结合两种空间填充曲线的特点,本文提出一种基于空间填充曲线的分区和索引优化方法。该方法利用Hilbert曲线建立自适应空间分区,缓解数据倾斜和集群计算时的“热点”问题,并在此基础上使用Geohash编码优化索引策略加速点对距离计算。实验结果表明,该方法可有效提升分布式环境下K函数计算效率。本文的贡献在于:① 改进现有基于索引的K函数点对过滤策略和基于空间分区的数据划分方法,实现流程优化和并行加速;② 通过与R树索引、KDB分区优化方案的对比分析,探讨了本文方法的适用场景;③ 基于Spark实现了本文优化方法,并将代码开源化(https://github.com/ZPGuiGroupWhu/Spark-based-Ripley-K-Functions),供社区扩展完善及应用集成。同时,该方法具有较强的平台可移植性,能够与其他主流分布式框架结合,用于面向海量数据的产业集聚分析[26]、公共设施服务空间格局分析[27]等。

2 研究方法

K函数是一种基于距离的二阶点模式分析方法,其同时考虑点的数量及点对距离,通过一定空间距离范围内点的期望总数除以点密度获得对应空间距离下的K函数值（式（1））,并计算多组空间距离对应的K值后可拟合得到最终结果。
K ˆ h = R n 2 ∑ ∑ I h d ij ω ij i , j ∈ 1,2 , … , n
式中: R表示研究区域面积; n为全体点事件数量; d ij表示事件点 s i和事件点 s j之间的欧式距离; ω ij表示边界校正权重; I h d ij表示点对过滤规则（当 d ij ≤ h时记为1,否则为0）。K函数完整的计算流程包括估计和模拟2个部分,两者的计算流程基本相同。其中K函数估计直接利用原始点数据进行计算得到估计值;而K函数模拟需利用一定的点事件生成方法创建模拟点进行计算,以便评估估计值在统计学上的显著性。为了简化表示,本文主要探讨K函数估计值的计算,其算法流程如图1所示。其中关键步骤是双层循环计算,即依次以各个点事件为中心设置半径为 h的圆,计算落入该圆内其他点事件的个数,其时间复杂度为 O n 2[12]。降低该步骤的时间复杂度,并对不同点事件的K函数值开展并行化计算,将有效降低整个算法的计算耗时。
图1 K函数估计阶段计算流程

Fig. 1 Flowchart of the estimation phase of Ripley's K function

为此,本文基于Spark框架设计并实现分布式K函数,整体流程如图2所示。该方法利用Hilbert曲线良好的空间聚集特征,结合K函数计算流程特点构造Hilbert曲线,优化空间分区方法,支撑点事件的并行化处理;同时,在分区基础上,根据K函数距离阈值,构造基于Geohash编码的局部索引,通过加速点对距离计算降低判断落在某点事件为中心、距离阈值为半径的圆内的点事件数量的复杂度,并有效避免K函数距离阈值较大时索引“负优化”现象。
图2 分布式K函数的分区优化与索引加速流程

Fig. 2 Overall workflow of the partitioning optimization and indexing acceleration for parallel Ripley's K function

2.1 基于Hilbert曲线的自适应空间分区

自适应Hilbert动态空间分区流程如图3所示。为避免在计算过程中传输完整数据集带来的高昂I/O开销,首先按照1%的采样率对数据进行采样处理[28],并基于采样数据子集确定Hilbert初始阶数。然后,通过格网化研究区域计算采样点的Hilbert编码,并基于Hilbert初始阶数和局部四分动态构建Hilbert网格。最后,标记需要进行分区分割的网格,即可获得分区号和Hilbert编码对应关系,并应用于完整数据集实现物理分区。
图3 自适应Hilbert动态分区流程

Fig. 3 Workflow of the adaptive Hilbert dynamic partitioning

在基于Hilbert曲线进行空间分区时,通常采用网格化思想将每个网格作为分区的空间范围。由于研究区域内空间分布模式未知,当空间分布不均匀时,可能会存在某个网格内存在大量数据从而导致分区数据倾斜问题,因此Hilbert初始阶数确定是关键。如果Hilbert阶数过高,则分区过程需要更多的时间成本;如果阶数过低,可能会加剧分布不均问题,且较少分区数量无法充分发挥分布式集群计算性能。在K函数计算过程中,距离阈值作为自变量会不断增大,将导致点对距离比较的搜索范围随之扩大。为减少分区间数据传输开销,空间分区应尽量保证以中心点为圆心、距离阈值为半径的过滤圆落在空间分区内（图4(a)）。Hilbert初始阶数如式（2）所示。
L min 2 n > 2 h max
式中: h max为K函数计算最大距离阈值; L min为研究区域外接矩形的较短边, n为Hilbert划分阶数。
图4 确定分区号和Hilbert编码的对应关系

Fig. 4 Determining the relationship between partition ID and Hilbert code

Hilbert曲线递归构造方式和四叉树相同,本文借助四叉树等分思想进行Hilbert网格的动态划分,如图4所示。即当某格网单元内点数据高于设定阈值时,则单独在该网格单元进行四分构造局部更精细的Hilbert网格,以解决点数据空间分布不均问题。记 P max为分区内点数阈值。若加入当前网格后,分区内点数 P > P max,则对当前网格继续剖分,直到满足 P < P max时剖分完毕,并记录此网格的分区标识符。

2.2 基于Geohash编码的K函数流程加速

Geohash具有局部保序性,即Geohash字符串前缀相同位数越多,则其在空间上越邻近。Geohash 编码与<key, value>键值对数据结构结合能够有效实现对点事件的高效检索[29],其中key为空间对象的Geohash编码,value为真实空间对象。本文在空间分区的基础上,利用Spark分布式集群计算每个RDD分区内部所有空间对象的Geohash编码,构建一组局部空间索引。在K函数计算过程中,一个点的Geohash编码会被多次重复利用,因此需要将其存放至内存或HDFS进行持久化处理。同时,本文采用聚簇索引方式,将数据存放的物理位置直接存放在索引中,以加快数据访问。
点对距离计算使用经典的“粗筛-精筛”索引规则,而当距离阈值较大时,R树索引因“粗筛”过程需要与过多空间对象MBR进行相交判断而失效,因此本文对“粗筛”过程进行加速。首先,通过Geohash编码将查询范围从全部研究区域缩小至一个包含9个Geohash网格的局部范围内;然后,在该局部范围内筛选出所有可能的候选对象,完成“粗筛”过程;最后,对所有候选对象进行逐个遍历计算,具体优化方案如图5所示。
图5 点过滤优化步骤

Fig. 5 Optimization procedure of the point filtering

查询范围缩减阶段,根据K函数距离阈值 h确定Geohash子级编码长度,即保证编码长度对应的Geohash格网较小边长大于当前距离阈值 h。如 图5(b)所示,此时满足要求的Geohash编码长度为5位,中心事件点所在网格编码为wx4fb。为保证计算正确性,将查询范围从整个研究区域缩小至该编码的父级尺度网格及其八邻域范围,如图5(c)所示,此时中心父级尺度网格的Geohash编码为wx4f。确定候选对象阶段,由于Geohash每一级之间空间距离跨度较大,查询范围缩减阶段筛选出来的点数据仍然会有大量冗余,可进一步通过K函数过滤圆的外接矩形与上一步得到的9个父级Geohash网格内所有子级网格进行求交判定,剔除所有相离的子级网格,即得到所有候选对象,如图5(d)所示。最后,逐个遍历候选点,计算和中心事件点的距离。

3 实验与结果分析

3.1 实验数据与设计

本文选取来自工商局的369 826条湖北省工商企业注册POI[26]作为原始点数据集、湖北省行政边界作为K函数估计的边界,开展算法性能分析实验,实验数据概况如图6所示。图中每个红点表示一个企业POI,可以看出POI数据整体分布极为不均,呈现出武汉、宜昌和襄阳等区域密集分布的多中心性特征,POI数量分别约占湖北省POI总数的23.02%、12.79%和9.16%。上述异质数据分布易造成分区数据倾斜和节点间通讯成本失衡,并增加R树索引在较大距离阈值下失效的可能性,因此有助于验证本文空间分区及索引的有效性。
图6 实验数据展示

Fig. 6 Illustration of Experimental data

实验中以Spark默认的哈希分区与无索引方案、KDB分区与R树索引组合优化方案[13]作为对照,共设计4组实验验证本文方法的有效性,具体包括基于自适应Hilbert阶数的空间分区优化有效性验证实验、Geohash局部索引有效性验证实验、 分区与索引的组合优化效果对比实验及算法伸缩性实验。为了确保计算时间统计的稳定性,每组 实验的时间开销取10次重复实验的平均值。实验环境为基于Apache CloudStack搭建的分布式 Spark集群,共由1台master、8台worker节点构成,每台虚拟机配置8核2GHz CPU和16G内存。软件版本为CentOS 7、Hadoop 2.7.7、Spark 2.3.3,主要编程语言为Java 8。

3.2 Hilbert分区的有效性验证

空间分区通过将空间上邻近的点划分到一个分区中,减少不同分区间的频繁数据传输,降低集群IO开销,从而提升分布式环境下K函数的计算效率。本实验以Spark默认分区（哈希分区）、KDB分区作为对照方案,验证不同分区数量和不同点数据规模下本文Hilbert分区的有效性及相对KDB分区的优势。进行K函数估计计算时,根据Ripley经验法则,K函数最大距离阈值不超过研究区域外包矩形短边边长的1/4[3]。本实验主要为验证不同分区方法对K函数计算的影响,同时考虑本文实验对象为企业数据（如餐饮、娱乐等）,其空间交互主要体现在街道级别尺度,可以适当减小最大距离阈值。实验设置K函数最大距离阈值为研究区域外包矩形短边1/32（约20 km）,以最大距离阈值的1/20为步长（约1 km）,迭代计算20次获得不同的距离阈值及其对应K值。
3.2.1 不同分区数目的对比实验
本实验从原始数据随机抽样固定数量的点得到作为输入数据,通过对比计算时间开销,分析不同分区数量下各分区方案对分布式K函数的计算性能的影响。实验中输入点数据规模设置为200 000,分区数量取值分别为32、64、128、256和512,但由于分区构造方式原因,KDB分区的指定分区数量与实际分区数量间会存在一定差异。KDB分区的实际分区数量分别为37、69、132、268和533,Hilbert区分数量与指定分区数量对应一致。
如图7所示,不论是KDB分区还是本文Hilbert分区,相比于默认的哈希分区均取得较好的优化效果,说明顾及空间邻近性的分区方案可以有效提高分布式环境下K函数的整体计算效率。同时,从不同分区数量的时间开销可以看出,虽然不同分区数量下Hilbert分区相比默认分区均有良好的优化效果,但并不是分区数量越多时间开销越小。本文提出的自适应Hilbert分区相较KDB分区,在分区数量较小时优化效果较为明显,特别是当分区数量等于64和128时总计算时间开销明显优于KDB分区。而在256、512分区数量下的计算时间反而增加并劣于KDB分区。这是因为本文Hilbert分区顾及分区间点数量均衡,在本文实验数据分布极为不均情况下,随着分区数量的增大,与KDB分区相比Hilbert分区的分区面积呈现出更显著的两级分化现象,即容易出现更多的小面积分区与大面积分区（2种分区策略在不同分区数量下的面积对比如图8(a)所示）。图8(b)展示了不同分区策略下各距离尺度的过滤圆与分区外包矩形的相交次数。可以看出随着分区数量增大,两种分区策略下的总相交次数均显著增加;并且当分区数量较大时（如256和512）,大量的小面积分区使得利用Hilbert分区计算K函数时各分区外包矩形与过滤圆相交总次数显著增多,并大于KDB分区下的相交次数（如图8(b)各分区数量下的Hilbert-KDB列所示,特别是总计行Hilbert-KDB列格子由蓝转红）,即需要更频繁地在分区间进行数据传输,从而增加整体时间开销。这也反映分布式环境下的分区方案需要精细设置,以确保分区粒度与系统调度之间达到最优平衡。
图7 不同分区策略下K函数计算时间随分区规模增大的对比

Fig. 7 Comparison of execution times of Ripley's K functions equipped with different partition methods as the partition size increases

图8 不同分区策略下分区外包矩形面积及其与过滤圆相交次数对比

注:(b)中“总计”表示1~20 km距离阈值下过滤圆与分区外包矩形相交次数总和

Fig.8 Comparison of the areas of partition MBRs and the intersections between partition MBRs and filter circles for different partition methods under different partition sizes

3.2.2 不同点数据规模对比实验
本实验对比本文Hilbert自适应分区和KDB分区方案在不同规模输入数据下的计算性能。实验固定分区数量为128,并从原始数据集中随机采样生成10 000~300 000共6个数据量等级规模。实验结果如图9(a)所示,从整体时间开销来看,除了10 000的数据规模以外,Hilbert分区在大多数情况下计算开销均优于KDB分区。如图9(b)所示,由2种分区方法得到的所有分区外包矩形长宽比可知,Hilbert分区长宽比更接近1,即趋近于正方形,而KDB分区则有更多细长型分区（128分区数量下 2种分区策略分区结果如图10所示）。相比于KDB分区,本文方法更适合于诸如K函数以某观察点事件为中心、距离阈值为半径的圆形空间查询等应用场景。同时,从分区构建时间开销来看,Hilbert分区的构建开销大于KDB分区,特别是在大数据规模下更加明显,反映出Hilbert曲线构造相较KDB树复杂的特点。综上,在分区数量相对较少时（如32至128）,建议采用本文Hilbert分区,而当分区数量较大时可以考虑KDB分区。
图9 不同分区策略下K函数计算时间及分区长宽比对比

Fig. 9 Comparison of execution times of Ripley's K functions and the length-width ratios of partitions for different partition methods

图10 分区个数为128时的KDB分区和Hilbert分区形态展示

Fig. 10 Illustration of the partitioning results of KDB-Tree and Hilbert under partitioning size of 128

3.3 索引加速的有效性验证

本文将无索引与R树索引作为本文Geohash索引的对比方案,分析K函数计算性能随空间距离阈值增大的变化规律。实验从原始数据中随机采样生成50 000个点数据作为输入数据,同样设置20次迭代;采用本文基于自适应Hilbert空间分区策略,并选择研究区域外包矩形最短边1/128至1/4等8种比例作为K函数阈值最大值参数,计算包含空间分区构建的总时间开销,实验结果如图11所示。
图11 不同空间索引方案下K函数计算时间随距离阈值增大的对比

Fig. 11 Comparison of execution times of Ripley's K functions adopted different index methods as the query scope increases

实验结果表明,在距离阈值较小时,R树与本文索引方案均有显著的计算加速效果,即引入空间索引能够有效优化K函数计算流程。随着距离阈值增大,R树在使用索引查询时会因为与过多MBR相交出现“负优化”现象,使得整体时间开销大于无索引方案;但本文的Geohash索引相对于无索引方案仍有一定的优化效果。从两种索引方案横向对比来看,针对当前数据集,当距离阈值取值比例大于研究区域MBR短边的1/64时,Geohash索引计算性能均优于R树索引（即加速比均大于1）。考虑到K函数是一种多尺度点模式分析方法,其距离阈值参数取值范围较广（最大通常取至研究区域MBR短边长度的1/4）,Geohash相较R树更适合作为其索引方案。在实际应用中,也可考虑当距离阈值较小时采用R树索引、距离较大时采用Geohash索引的多索引组合策略,以期达到最佳优化效果。

3.4 综合优化效果的对比验证

为验证本文方法的综合优化效果,将默认分区与无索引的组合方案、KDB分区与R树索引的组合方案[12,13]与本文方法对比,并适当增大最大距离阈值设置与迭代次数,对比分析不同方法在进行更精细、更繁重的K函数计算任务时的时间开销。实验从原始数据集随机采样生成10 000~300 000共6个数据规模作为输入,研究区域的1/16作为最大距离阈值,以最大距离阈值的1/30为步长,迭代计算30次。实验结果如图12所示。
图12 不同K函数综合优化方案计算时间随点数据规模增大的对比

Fig. 12 Overall comparison of execution times of Ripley's K functions using hybrid optimization methods as the number of points increases

实验结果表明,在数据规模较大时,与原始方法相比本文方法具有良好的优化效果,尤其是当数据量大于100 000时本文方法与原始方法相比加速比均大于2且呈现递增趋势,可有效提升分布式环境下K函数的计算效率。通过与KDB分区与R树索引的组合方案对比可知,本文方法取得了更好的优化效果。同时也可以看出,随着数据规模的增加, 2种优化方案下的K函数总时间开销仍然较大,尤其在需要获得具有高可信度的计算结果（如0.01置信水平需要模拟计算99次）时不容小觑。在实际应用中,若对计算时间有更高要求,可考虑尽量在不影响计算结果准确性的情况下,对原数据集进行适当采样、缩小距离阈值最大值或减少迭代计算次数来加速计算。

3.5 集群伸缩性实验

本实验选择3台（1台master和2台worker）至9台（1台master和8台worker）节点作为集群规模开展K函数计算,将默认分区与无索引的原始方案 与本文优化方法对比。数据为随机采样得到的300 000点。K函数计算参数设置同3.2节,即以研究区域外包矩形短边边长的1/32（约20 km）作为最大距离阈值,以最大距离阈值的1/20（约1 km）为步长,迭代20次。实验结果如图13所示。
图13 不同集群规模下K函数计算时间对比

Fig. 13 Comparison of execution times of Ripley's K function, using different number of nodes in cluster

实验结果表明,本文方案具有较好可伸缩性,但考虑实验数据规模及节点间通讯成本,并不能保证计算性能随集群规模增加而持续提升。理论上讲,在不考虑节点间通讯的情况下,集群规模的增大能够为分布式系统提供更高的并行度,从而减少系统计算的时间开销。但实际应用中必须考虑节点间的通讯与数据交换成本。从实验结果可以看出,对比方案在9台节点规模下的时间开销相较8台反而有所增加。这是由于原始分区方法人为割裂了数据之间的邻近关系,较低的分区质量产生了较高的通讯成本,进而抵消了集群规模增大带来的计算优化。而本文的优化方法在分区时顾及数据的空间分布,更高的并行度与较低的通讯成本能够带来更高的优化收益。同时可以看出,当集群规模达到6台节点时,进一步增大集群规模不会带来明显的收益。这也反映出分布式系统中资源调度开销、通讯成本与计算耗时之间的制约关系,单纯依靠增加系统并行规模并不能为集群的计算性能带来质的变化,需要结合数据规模、模型参数设置进行综合取舍。

4 结语

本文针对分布式环境下K函数计算的数据分区倾斜和索引失效的问题,结合空间填充曲线的空间邻近性和编码特点,提出了一种基于Hilbert曲线的自适应空间分区方法和Geohash编码点对过滤策略,综合加速K函数计算。实验表明,本文提出的方法可有效提升分布式环境下K函数的计算性能,减少计算时间开销。在300 000点数据规模下,与基于哈希分区和无空间索引的原始方法、基于KDB分区和R树索引的优化方法相比,加速比分别超过4倍和1.3倍,且随着数据规模增大加速效果将更加显著。此外,本文方法具有良好的可伸缩性,相较原始方法9台节点下的加速比超过3.6倍。该方法能够应用于目前主流的分布式计算框架,并与Apache Sedona（即Geospark）和SpatialHadoop等空间扩展方案集成,降低海量空间数据分析算法并行编程与应用的门槛,同时也可为大数据背景下其他点模式分析方法的优化提供参考。
尽管有研究表明Hilbert曲线相比其他类型曲线具有更好的空间邻近性和聚集性,但其原始构造算法时间开销较大,后续可以利用优化的Hilbert曲线构造算法（如Google提出的S2算法[30]）统 一分区与索引算法,减少重复编码带来的时间开销。此外,本文的优化算法主要针对二维的空间K函数。实际上,空间填充曲线支持高维度数据降维,后续可以尝试改进编码方案,克服编码过程中因时间维和空间维之间量纲和尺度差异带来的死区问题[31],以实现时间维度上的扩展,使其适用于时空K函数。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
周成虎. 点模式分析[J]. 地理科学进展, 1989, 8(2):8-11.

[ Zhou C H. Analysis of point patterns[J]. Progress in Geography, 1989, 8(2):8-11. ] DOI: 10.11820/dlkxjz.1989.02.003

DOI

[2]
Yamada I, Rogerson P. An empirical comparison of edge effect correction methods applied to K-function analysis[J]. Geographical Analysis, 2003, 35(2):97-109. DOI: 10.1111/j.1538-4632.2003.tb01103.x

DOI

[3]
Ripley B D. Modelling spatial patterns[J]. Journal of the Royal Statistical Society: Series B (Methodological), 1977, 39(2):172-212. DOI: 10.1111/j.2517-6161.1977.tb01615.x

DOI

[4]
李智, 李卫红. 点模式条件下的犯罪嫌疑人时空同现模式挖掘与分析[J]. 地球信息科学学报, 2018, 20(6):827-836.

DOI

[ Li Z, Li W H. Mining and analyzing spatiotemporal co-occurrence patterns among criminal suspects under point pattern[J]. Journal of Geo-information Science, 2018, 20(6):827-836. ] DOI: 10.12082/dqxxkx.2018.180009

DOI

[5]
曾璇, 崔海山, 刘毅华. 基于网络空间点模式的餐饮店空间格局分析[J]. 地球信息科学学报, 2018, 20(6):837-843.

DOI

[ Zeng X, Cui H S, Liu Y H. Analysis on spatial distribution characteristics of restaurant based on network spatial point model[J]. Journal of Geo-information Science, 2018, 20(6):837-843. ] DOI: 10.12082/dqxxkx.2018.170596

DOI

[6]
李清泉, 李德仁. 大数据GIS[J]. 武汉大学学报·信息科学版, 2014, 39(6):641-644.

[ Li Q Q, Li D R. Big data GIS[J]. Geomatics and Information Science of Wuhan University, 2014, 39(6):641-644. ] DOI: 10.13203/j.whugis20140150

DOI

[7]
崔邹森. 基于交叉Ripley’s K函数的点模式Web可视化分析系统设计与实现[D]. 武汉:武汉大学, 2020.

[ Cui Z S. Design and implementation of Web-based point pattern visual analytics system upon cross Ripley's K function[D]. Wuhan: Wuhan University, 2020. ]

[8]
Tang W W, Feng W P, Jia M J. Massively parallel spatial point pattern analysis: Ripley's K function accelerated using graphics processing units[J]. International Journal of Geographical Information Science, 2015, 29(3):412-439. DOI: 10.1080/13658816.2014.976569

DOI

[9]
Zhang G M, Huang Q Y, Zhu A, et al. Enabling point pattern analysis on spatial big data using cloud computing: Optimizing and accelerating Ripley's K function[J]. International Journal of Geographical Information Science, 2016, 30(11):2230-2252. DOI: 10.1080/13658816.2016.1170836

DOI

[10]
王源. 面向海量点模式分析的时空Ripley's K函数优化与加速[D]. 武汉:武汉大学, 2019.

[ Wang Y. Optimization and acceleration of spatiotemporal Ripley's K function for enabling massive point pattern analysis[D]. Wuhan: Wuhan University, 2019. ]

[11]
向隆刚, 王德浩, 龚健雅. 大规模轨迹数据的Geohash编码组织及高效范围查询[J]. 武汉大学学报·信息科学版, 2017, 42(1):21-27.

[ Xiang L G, Wang D H, Gong J Y. Organization and efficient range query of large trajectory data based on geohash[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1):21-27. ] DOI: 10.13203/j.whugis20150175

DOI

[12]
Wang Y, Gui Z, Wu H, et al. Optimizing and accelerating space-time Ripley’s K function based on Apache Spark for distributed spatiotemporal point pattern analysis[J]. Future Generation Computer Systems, 2020, 105:96-118. DOI: 10.1016/j.future.2019.11.036

DOI

[13]
Gui Z, Wang Y, Cui Z, et al. Developing apache spark based Ripley’s K functions for accelerating spatiotemporal point pattern analysis[J]. The International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2020, 43:545-552. DOI: 10.5194/isprs-archives-XLIII-B4-2020-545-2020

DOI

[14]
左尧, 王少华, 钟耳顺, 等. 高性能GIS研究进展及评述[J]. 地球信息科学学报, 2017, 19(4):437-446.

DOI

[ Zuo Y, Wang S H, Zhong E S, et al. Research progress and review of high-performance GIS[J]. Journal of Geo-information Science, 2017, 19(4):437-446. ] DOI: 10.3969/j.issn.1560-8999.2017.04.001

DOI

[15]
邱强, 秦承志, 朱效民, 等. 全空间下并行矢量空间分析研究综述与展望[J]. 地球信息科学学报, 2017, 19(9):1217-1227.

DOI

[ Qiu Q A, Qin C Z, Zhu X M, et al. Overview and prospect on spatial analysis of parallel vectors in pan-spatial concept[J]. Journal of Geo-Information Science, 2017, 19(9):1217-1227. ] DOI: 10.3724/SP.J.1047.2017.01217

DOI

[16]
Whitman R T, Park M B, Marsh B G, et al. Spatio-temporal join on Apache Spark[C]. Proceedings of the 25thACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2017:1-10. DOI: 10.1145/3139958.3139963

DOI

[17]
高旭, 桂志鹏, 隆玺, 等. KDSG-DBSCAN:一种基于K-D Tree和Spark GraphX的高性能DBSCAN算法[J]. 地理与地理信息科学, 2017, 33(6):1-7,封3.

[ Gao X, Gui Z P, Long X, et al. KDSG-DBSCAN: A high performance DBSCAN algorithm based on K-D tree and spark GraphX[J]. Geography and Geo-Information Science, 2017, 33(6):1-7,封3. ] DOI: 10.3969/j.issn.1672-0504.2017.06.001

DOI

[18]
Gui Z, Peng D, Wu H, et al. MSGC: Multi-scale grid clustering by fusing analytical granularity and visual cognition for detecting hierarchical spatial patterns[J]. Future Generation Computer Systems, 2020, 112:1038-1056. DOI: 10.1016/j.future.2020.06.053

DOI

[19]
Vo H, Aji A, Wang F S. SATO: A spatial data partitioning framework for scalable query processing[J]. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 2014, 04/5/6/7:545-548. DOI: 10.1145/2666310.2666365

DOI

[20]
李绍俊, 钟耳顺, 王少华, 等. 基于状态转移矩阵的Hilbert码快速生成算法[J]. 地球信息科学学报, 2014, 16(6):846-851.

DOI

[ Li J S, Zhong E S, Wang S H, et al. An algorithm for Hilbert ordering code based on state-transition matrix[J]. Journal of Geo-information Science, 2014, 16(6):846-851.] DOI: 10.3724/SP.J.1047.2014.00846

DOI

[21]
崔登吉. 空间分布模式驱动的空间数据组织与索引研究[D]. 南京:南京师范大学, 2016.

[ Cui D J. Spatial data organization and indexing research driven by spatial distribution pattern[D]. Nanjing: Nanjing Normal University, 2016. ]

[22]
Liu Y Y, Cho W K T. A spatially explicit evolutionary algorithm for the spatial partitioning problem[J]. Applied Soft Computing, 2020, 90:106-129. DOI: 10.1016/j.asoc.2020.106129

DOI

[23]
向隆刚, 高萌, 王德浩, 等. Geohash-Trees:一种用于组织大规模轨迹的自适应索引[J]. 武汉大学学报·信息科学版, 2019, 44(3):436-442.

[ Xiang L G, Gao M, Wang D H, et al. Geohash-trees: An adaptive index which can organize large-scale trajectories[J]. Geomatics and Information Science of Wuhan University, 2019, 44(3):436-442. ] DOI: 10.13203/j.whugis20160523

DOI

[24]
Zhang L, Ren L, Hao X, et al. Query method for nearest region of spatial line segment based on Hilbert curve grid[J]. International Journal of Innovative Computing Information and Control, 2019, 15(4):1287-1307. DOI: 10.24507/ijicic.15.04.1287

DOI

[25]
Yu J, Zhang Z S, Sarwat M. Spatial data management in apache spark: The GeoSpark perspective and beyond[J]. GeoInformatica, 2019, 23(1):37-78. DOI: 10.1007/s10707-018-0330-9

DOI

[26]
Li F, Gui Z, Wu H, et al. Big enterprise registration data imputation: Supporting spatiotemporal analysis of industries in China[J]. Computers, Environment and Urban Systems, 2018, 70:9-23. DOI: 10.1016/j.compenvurbsys.2018.01.010

DOI

[27]
湛东升, 张文忠, 党云晓, 等. 北京市公共服务设施空间集聚特征分析[J]. 经济地理, 2018, 38(12):76-82.

[ Zhan D S, Zhang W Z, Dang Y X, et al. Spatial clustering analysis of public service facilities in Beijing[J]. Economic Geography, 2018, 38(12):76-82. ] DOI: 10.15957/j.cnki.jjdl.2018.12.010

DOI

[28]
Eldawy A, Alarabi L, Mokbel M F. Spatial partitioning techniques in SpatialHadoop[J]. Proceedings of the VLDB Endowment, 2015, 8(12):1602-1605. DOI: 10.14778/2824032.2824057

DOI

[29]
Kui Y, Chang Y Q. Prediction and optimization of sharing bikes queuing model in grid of Geohash coding[J]. Measurement and Control, 2020, 53(7):1250-1266. DOI: 10.1177/0020294019877521

DOI

[30]
Google. S2 Geometry[EB/OL]. http://s2geometry.io/, 2019-12-18.

[31]
Li R, He H, Wang R, et al. JUST: JD urban spatio-temporal data engine[C]. 2020 IEEE 36th International Conference on Data Engineering, 2020:1558-1569. DOI: 10.1109/ICDE48307.2020.00138

DOI

Options
Outlines

/

〈 〉