基于Hilbert空间分区和Geohash索引的并行Ripley's K函数 |
| |
引用本文: | 亢扬箫,桂志鹏,丁劲宸,吴京航,吴华意.基于Hilbert空间分区和Geohash索引的并行Ripley's K函数[J].地球信息科学,2022,24(1):74-86. |
| |
作者姓名: | 亢扬箫 桂志鹏 丁劲宸 吴京航 吴华意 |
| |
作者单位: | 1.武汉大学遥感信息工程学院,武汉 4300792.重庆市地理信息与遥感应用中心,重庆 4011473.武汉大学测绘遥感信息工程国家重点实验室,武汉 430079 |
| |
基金项目: | 国家重点研发计划项目(2018YFC0809806,2017YFB0503704);国家自然科学基金项目(41971349,42090010)。 |
| |
摘 要: | 作为二阶点模式分析方法,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编码 点模式分析 空间填充曲线 |
收稿时间: | 2021-08-04 |
本文献已被 维普 等数据库收录! |
| 点击此处可从《地球信息科学》浏览原始摘要信息 |
| 点击此处可从《地球信息科学》下载免费的PDF全文 |
|