GeoSpark

定义

GeoSpark 是一个在集群上处理大规模空间数据的内存计算框架，它把 Apache Spark 的弹性分布式数据集扩展为可以承载几何与空间对象的空间弹性分布式数据集（Spatial Resilient Distributed Dataset，SRDD）。框架的目标是让使用者能够直接在 Spark 上编写空间分析程序，而不必自行实现空间数据的组织与检索逻辑^[3]。

GeoSpark 的架构分为三层：Apache Spark 层负责常规的数据加载、存储与 RDD 操作；SRDD 层负责空间对象的表达、划分与索引；空间查询处理层则在 SRDD 之上执行空间范围查询、空间连接与 K 近邻查询^[4]。早期短论文给出的初步实验显示，它的运行时间优于基于 Hadoop 的同类系统 SpatialHadoop。

原理

GeoSpark 的核心抽象是 SRDD。它在 Spark RDD 的基础上支持点、多边形、线串、矩形与圆等几何对象，并针对这些对象提供了划分与索引能力；以点对象为例，GeoSpark 采用定制序列化方式，单点占用约 20 字节，少于 Spark 自带 Kryo 序列化所需的约 40 字节与 Java 序列化所需的约 1170 字节^[5]。

在数据划分方面，GeoSpark 会先对 RDD 采样，在样本上构建 KD 树、四叉树或 R 树，把树的叶节点作为全局划分文件，再据此重新划分数据，使空间上邻近的对象落入同一分区；划分文件同时被用作记录各分区包围盒的全局索引^[5]。由于一个跨越多个网格的对象可能被复制到多个分区，查询阶段还需要通过参考点去重或按键分组等方式消除重复结果。

在每个分区内部，框架可以按索引开销与查询选择性的权衡，自适应地决定是否为该分区建立四叉树或 R 树等局部索引，从而在内存与 CPU 占用同运行时间之间取得平衡。空间连接查询会先对两个输入 SRDD 分别划分并建立局部索引，再按网格编号连接两个数据集，对网格编号相同的对象逐一判断空间关系。K 近邻查询则采用基于堆的 top-k 算法，先在各分区内维护候选堆，再合并各分区结果输出距离最近的 k 个对象。

发展历程

该项目最初由亚利桑那州立大学 Data Systems Lab 的研究者 Jia Yu、Jinxuan Wu 与 Mohamed Sarwat 于 2015 年以开源形式发起，当时命名为 GeoSpark^[6]。2015 年 11 月 3 日，团队在 ACM SIGSPATIAL 地理信息系统国际会议上发表了介绍该框架的短论文^[7]。2016 年 5 月，团队又在 IEEE 国际数据工程会议（ICDE）上做了系统演示^[1]。

在此期间，GeoSpark 逐步扩展出可视化子系统 GeoSparkViz 与交通仿真器 GeoSparkSim 等组件，2018 年的 SIGMOD 论文与 2018 年的 PVLDB 基准测试论文都对该框架进行了独立的第三方评估^[1]。项目的开源许可证也在 2019 年由 MIT 变更为 Apache 许可证 2.0^[6]。

2020 年 7 月 19 日，GeoSpark 被 Apache 软件基金会接受进入孵化器，并更名为 Apache Sedona，新名称取自亚利桑那州的一座城市^[8]。经过两年多孵化，项目在 2022 年 12 月发起毕业讨论并完成社区投票^[9]，随后于 2023 年 2 月 8 日被宣布成为 Apache 顶级项目^[2]。

应用

框架支持在分布式规模上执行空间连接、最近邻查询、距离连接与轨迹分析等基本操作，因此被用于多个领域：城市计算中用于交通分析与交通需求预测，气候与环境研究中用于对栅格与矢量数据做分区统计，公共卫生研究中曾用于把匿名移动数据与区域感染率关联^[10]。电信与能源行业也用其分析基站覆盖范围与设施管理^[10]。

在实现层面，GeoSpark 可与 Hadoop 分布式文件系统配合作为底层存储，并以 Apache Maven 构建项目^[6]。除 Scala 与 Java 的 RDD API 外，它还提供 Spatial SQL 接口，可读取 WKT、WKB、GeoJSON、ESRI Shapefile 以及 CSV 等格式的数据^[11]。中文研究文献也提到，该框架以基于 Spark RDD 扩展的 Spatial RDD 表达地理对象，仅支持简单空间要素，不能保留单个对象的属性以及图层属性。

局限

2018 年发表的 PVLDB 基准评估认为，该框架接近一个完整的空间分析系统，在多数情况下性能表现最佳，但仍不支持 K 近邻连接^[12]。有研究指出，无论是最近邻连接还是最近点对查询这类基于距离的连接查询，在 Apache Sedona 中都没有原生支持，需要研究者另行设计分布式算法^[13]。

在数据划分环节，R 树划分通过采样实现，索引范围可能无法覆盖全部几何对象，框架因此需要设置溢出桶来容纳未被覆盖的几何对象；当溢出桶中包含来自整个输入数据集的几何对象时，参考点去重方法便难以发挥作用。此外，通过按键分组来消除重复结果会触发跨集群的大规模数据混洗，开销明显。

在涉及栅格谓词时，距离连接同样受限，需要先完成栅格感知的反序列化与按距离半径扩展包络面等改造^[14]。中文研究文献还指出，该框架只能表达数据的空间距离关系，难以直接用于地理流数据的各类分析场景。

参见

• Apache Spark —— GeoSpark 建立在其 RDD 抽象之上，并对其做了空间方向的扩展。

• 空间索引 —— 框架依赖 R 树、四叉树等索引结构加速空间查询。

• 地理信息系统 —— GeoSpark 所服务的应用领域，用于处理矢量地理数据。

• SpatialHadoop —— 与 GeoSpark 同期的基于 Hadoop 的大规模空间数据处理系统。

• Apache Sedona —— GeoSpark 捐献给 Apache 软件基金会后更名而成的项目。