基于Hilbert空间分区和Geohash索引的并行Ripley's K函数

摘要/Abstract

摘要： 作为二阶点模式分析方法,Ripley's K函数（简称K函数）以距离为自变量探测不同尺度下点事件的分布模式及演变规律,在生态学、经济学、地理学等诸多领域得到广泛应用。然而,随着点规模的增加,估计与模拟阶段点对距离遍历计算时间开销激增,严重制约了K函数的应用,算法流程优化与并行加速成为应对海量点数据下K函数性能瓶颈及可计算性问题的关键技术手段。针对默认数据分区未考虑点事件空间邻近性导致跨节点通讯成本高昂且K函数距离阈值较大时索引优化失效的现象,本文提出一种基于空间填充曲线的K函数优化加速方法。该方法采用Hilbert 曲线构建空间分区,在顾及数据空间邻近性的前提下减少分区间数据倾斜和通讯开销;在分区基础上,利用Geohash 编码改进各分区内本地空间索引策略加速点对距离计算。本文以湖北省工商企业注册数据为例,通过对比实验分析了默认分区无索引、KDB分区组合R树索引、本文Hilbert分区组合Geohash 索引算法在不同数据规模、距离阈值、集群规模下的计算耗时。结果表明,300 000 点数据规模下本文方法的时间开销约为默认分区无索引方法的1/4,9 台节点下加速比超过3.6 倍。因此,该方法能有效提升分布式环境下K函数计算性能并具有良好的可伸缩性,可为其他点模式分析方法的优化提供参考。

关键词: Ripley's K函数, 分布式计算, Apache Spark, 高性能地理计算, Hilbert曲线, Geohash 编码, 点模式分析, 空间填充曲线

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, hashbased 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

亢扬箫, 桂志鹏, 丁劲宸, 吴京航, 吴华意. 基于Hilbert空间分区和Geohash索引的并行Ripley's K函数[J]. 地球信息科学学报, , (): 9-10.

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, , (): 9-10.

参考文献

[1] 周成虎. 点模式分析[J].地理科学进展,1989,8(2):8-11.
[Zhou C H.Analysis of point patterns[J]. Progress in Geography, 1989,8(2):8-11.]
[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.
[3] Ripley B D.Modelling spatial patterns[J]. Journal of the Royal Statistical Society: Series B (Methodological), 1977,39(2):172-212.
[4] 李智,李卫红.点模式条件下的犯罪嫌疑人时空同现模式挖掘与分析[J].地球信息科学学报,2018,20(6):827-836.
[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.]
[5] 曾璇,崔海山,刘毅华.基于网络空间点模式的餐饮店空间格局分析[J].地球信息科学学报,2018,20(6):837-843.
[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.]
[6] 李清泉,李德仁.大数据GIS[J].武汉大学学报·信息科学版,2014,39(6):641-644.
[Li Q Q, Li D R.Big data GIS[J]. Geomatics and Information Science ofWuhan University, 2014,39(6):641-644.]
[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.
[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.
[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 ofWuhan University, 2017,42(1):21-27.]
[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.
[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.
[14] 左尧,王少华,钟耳顺,等.高性能GIS研究进展及评述[J].地球信息科学学报,2017,19(4):437-446.
[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.]
[15] 邱强,秦承志,朱效民,等.全空间下并行矢量空间分析研究综述与展望[J].地球信息科学学报,2017,19(9):1217-1227.
[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.]
[16] Whitman R T, Park M B, Marsh B G, et al.Spatio-temporal join on Apache Spark[C]. Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2017:1-10.
[17] 高旭,桂志鹏,隆玺,等. KDSG-DBSCAN:一种基于K-D Tree 和Spark GraphX 的高性能DBSCAN 算法[J].地理与地理信息科学,2017,33(6):1-7,127.
[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,127.]
[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.
[19] Vo H, Aji A, Wang F S.SATO: A spatial data partitioning framework for scalable query processing[C]. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 2014.
[20] 李绍俊,钟耳顺,王少华,等.基于状态转移矩阵的Hilbert 码快速生成算法[J].地球信息科学学报,2014,16(6):846-851.
[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.]
[21] 崔登吉. 空间分布模式驱动的空间数据组织与索引研究 [D].南京:南京师范大学,2016.
[Cui D J.Spatial data organization and indexing research driven by spatial distri-bution 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.
[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 ofWuhan University, 2019,44(3):436-442.]
[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.
[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.
[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.
[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.]
[28] Eldawy A, Alarabi L, Mokbel M F.Spatial partitioning techniques in SpatialHadoop[J]. Proceedings of the VLDB Endowment, 2015,8(12):1602-1605.
[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.
[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 36^th International Conference on Data Engineering, 2020:1558-1569.