vlambda博客
学习文章列表

Space-Time Ripley’s K Function（以下简称时空K函数）是时空点过程分析的代表性方法之一，在生态、地理、社会学、经济学、城市交通等领域应用广泛，但由于其点对距离计算、边界校正、显著性检验等步骤时间复杂度较高，在海量POI分析场景下存在显著的可计算性问题。为此，本文提出一种基于分布式计算框架Apache Spark的时空K函数计算方案，采用四种策略优化计算流程并加速分布式计算：1）利用基于STR算法的时空R树索引缩小时空邻近查询范围，避免不必要点对距离计算；2）通过时空边界校正权重的双层Hash缓存与复用机制，减少权重重复计算；3）使用采样点时空KDB-tree分区方案，在顾及时空邻近性的情况均衡分区任务/数据负载，并采用时空立圆柱冗余代替边界缓冲冗余，减少数据冗余；4）设计定制序列化方法精简时空对象和索引编码，降低数据传输成本。实验结果验证了本文方法的高效性（极端场景下加速比甚至可达1000倍）及适用场景。

基于上述方案，本文设计并实现了基于K函数的时空点模式Web可视分析框架，现已集成空间、时空、局部和交叉四种K函数，并通过GitHub开源化供社区免费使用。

Ripley’s K函数是一种多距离点模式分析方法，可用于研究地理点的空间排列及时空分布特征。相比于其他点模式分析方法，K函数具备以下特点：1）基于距离且与尺度无关，可以避免可变面元问题（MAUP）；2）输入参数可由研究范围得到，无需依赖专家经验；3）不仅考虑最近邻点，还考虑到最大距离内的其他邻近点，充分利用点对信息。因此，K函数已广泛应用于众多领域，挖掘隐藏在地理现象或社会事件背后的时空点过程。

K函数计算量随点集规模急剧增加，严重制约其在时空大数据场景下的应用，原因如下：1）点对距离遍历计算的时间复杂度为总点数的二次方；2）校正边缘效应需要计算点对权重，其计算时间复杂度与研究区域边界复杂程度正相关；3）点模式显著性水平的置信度评估依赖大量模拟计算，计算量远大于观测估计。因而桌面版K函数时常出现内存溢出等问题，极大影响了用户体验及可计算性。

目前已有研究基于OpenMP、MPI、CUDA等并行计算技术加速K函数并取得了较好的效果，但尚未将优化从空间维扩展到时空维。在缺乏有效时空查询和分区机制的情况下，时空计算将面临巨额的计算开销。同时，由于并行框架的限制和相对昂贵的编程成本，这些方法的可伸缩性和功能扩展性受限，制约了K函数在超大规模数据集的应用。而Apache Spark得益于内存架构、统一查询/计算API、完善的生态系统，近些年在地理空间分析得到广泛应用。

针对上述问题并考虑到Spark的技术优势，本文基于Spark设计并实现了索引、缓存、分区与定制序列化四种优化/加速策略组合的时空K函数并行化方案，并通过性能分析实验验证了本文方法的有效性。

时空K函数的计算流程包括观测点和模拟点K函数值测算（以下简称估计与模拟），都可视为双层嵌套遍历过程，融合了四种优化/加速策略的时空K函数并行计算流程如图1所示。

图1. 融合多种策略的并行算法流程图

四种策略的简要设计思路如下：

1）基于时空R树索引的点对过滤

时空K函数默认计算流程需要比较中心点与其他所有点时空距离，以获得时空阈值范围内的点对数量。由于时空阈值的存在，绝大部分点对距离比较实际上可设法避免。考虑到R树的时空索引的查询效率和稳定性，本文将点对过滤视为时空查询任务，采用基于STR算法的R树索引进行加速（图2）。

图2. 时空R树图索引原理图

2）基于双层缓存的权重复用

时空Isotropic Correction边界校正方法（图3）的权重大小仅与中心点的时空坐标及点对空间/时间距离有关，且空间/时间校正权重相互独立。中心点空间坐标和点对空间距离相同时，空间校正权重可复用；中心点时间坐标和点对时间距离相同时，时间校正权重可复用。因此，本文设计面向中心点坐标和点对距离两个索引维度的双层Hash表对权重进行缓存（图4），以满足复用的查询需求。

图3. 边界校正工作原理图

图4. 双层权重缓存与复用示意图

3）基于KDB树的时空分区方案

时空K函数并非是一个易并行计算问题（embarrassingly parallel problem），在以分区为调度基本单位的分布式环境中，需要大量冗余数据来支持时空K函数的计算。Spark默认采用Hash分区器，时空点数据将被随机分配至不同分区。考虑到时空K函数的计算场景，应尽可能地将时空邻近的点划分在一起以降低数据冗余。因此，顾及分区的负载平衡和完整性，本文采用了基于KDB树的时空分区方案，并通过时空点采样降低分区计算成本，过程如图5。同时，本文采用时空圆柱冗余方法代替边界缓冲冗余，避免分区边界数据的过度冗余，即若分区外某点的时空阈值圆柱与分区最小时空包围盒相交，则冗余存储该点到分区。

图5. 基于KDB树的时空分区过程

4）定制序列化

即使进行了分区优化，集群计算时不同节点间依然不可避免地需要传输数据，并涉及数据的序列化与反序列化。Spark默认的序列化器在编码时包含大量多余信息，使传输的字节数组体积较大。设计定制序列化器使传输对象仅包含关键信息，能加快节点间数据传输效率。本文针对时空K函数计算过程中的多种时空对象及索引，设计了定制的序列化与反序列化方法。以时空圆对象为例，其默认序列化与定制序列化的编码方式如图6所示。

图6. 定制序列化与默认序列化对比

（以时空圆对象为例）

实验数据为带有时间戳（1949年至2015年）的湖北省某POI数据，共369,826条。实验在基于Apache CloudStack的私有云平台中开展，计算集群由1台Master虚拟机和8台Worker虚拟机组成。每台虚拟机分配8核2 GHz CPU及16G内存。操作系统为CentOS 7，Hadoop版本为2.7.7，Spark版本为2.3.3。

1）时空索引的性能分析

从数据集中随机采样50000个点作为实验数据，以查询范围作为自变量，对比分析估计和模拟计算时长。实验结果如图7。结果表明时空索引的适用范围受到时空距离阈值的影响。在较短时空距离阈值下的性能提升更为显著，模拟计算效率提升可达9.8倍；随着时空距离阈值升高，基于时空索引的点对遍历将逐渐失去性能优势甚至略弱于不采用索引的全局遍历方案。而不同时空距离阈值下的索引构建时间均小于0.2s（见论文），其成本可以忽略。

图7. 时空索引对比实验结果图

2）双层缓存的性能分析

分析研究区域边界点数不同时，权重缓存策略的估计与模拟计算时长与加速效果，实验数据同上。实验结果（图8）表明双层缓存能够消除研究区域复杂度带来的计算开销。在研究区域较为复杂时发挥显著优势；而当研究区域边界较为简单时（如，矩形），可考虑忽略缓存，直接计算权重。

图8. 双层权重缓存对比实验结果图

 3）时空分区的性能分析

随机采样规模为200,000的时空点数据，以分区数为自变量，比较默认分区与时空分区下的计算时间，实验结果如图9所示。结果表明时空分区能降低不必要的数据冗余，提高时空K函数的执行效率。较少的分区使任务的平均完成时间更长；更多的分区使对应任务划分粒度更细，并行度更高，但同时会增加数据冗余。

图9. 时空分区对比实验结果图

4）定制序列化的性能分析

不同数据量下，比较采用默认序列化与定制序列化的时空K函数在分布式集群中的执行时间。定制序列化的压缩比为23.11倍，编解码时间加速比分别可达10倍及40倍以上（见论文）。实验结果（图10）发现定制序列化在不修改任何时空K函数流程的情况下依然能够带来一定提升。随着数据规模的增大，定制序列化的提升效果也越加显著。

图10. 时空分区对比实验结果图

5）四种策略综合的优化效果分析

以数据规模作为自变量，在相同的计算环境及集群配置下，比较综合采用四项措施的优化计算方法和Spark默认计算方法的执行时间，实验结果如图11。结果表明本文提出的四项优化策略能有效降低时空K函数的时间复杂度，提高时空K函数在分布式环境下的执行效率。

图11. 四项措施综合对比实验结果图

6）可伸缩性分析

伸缩性反映了时空K函数在不同规模的计算资源支持下性能提升幅度的变化。实验选取了规模200,000的点数据，以集群节点数目为自变量，分析执行时间。实验结果（图12）表明分布式时空K函数的加速比随集群节点数目增多而上升，当结点数目达到一定程度时，上升幅度开始下降。对于200,000的数据规模，由4个Worker节点所组成的集群达到最高的并行收益率。

图12. 伸缩性实验结果图

7）整体加速效果分析

整体优加速效果受到点集分布模式和参数设置的影响较大。由于数据分布极端倾斜并呈现显著时空聚集，湖北省近37万POI的时空K函数加速比仅达4倍左右，空间K函数达90倍以上；而针对随机分布的点数据，由于R树深度相对平衡且KDB树分区均衡，在50万点规模下时空K函数和空间K函数加速比分别可达1000倍（见表1）及2000倍以上。同时，分布式计算的集群规模应根据数据规模进行调整，时空距离阈值超出特定范围时可不采用索引策略，研究区域的几何边界过于简单时可关闭双层缓存以避免负面影响，时空分区和定制序列化可默认启用。

表1. 随机分布合成数据集上的总体加速效果

为了有效支撑分布式点模式分析的领域应用，我们将时空K函数的Spark并行化方案拓展至K函数家族其他成员，包括空间K函数、局部K函数及交叉K函数。在此基础上，我们基于主流Web可视化组件，设计并实现了基于K函数的时空点模式Web可视化分析框架（如图13所示），部分实现效果如图14所示。目前系统前后台源代码已在GitHub公开，供社区免费使用，以期推动可复现、可协同的社区氛围。

图13. Web可视化分析系统架构图

图14. Web系统界面截图

本文提出索引、缓存、分区与定制序列化组合的时空Ripley’ K函数并行计算方法，并基于分布式计算框架Apache Spark进行算法实现。验证实验表明，该方法可有效降低大规模点集上时空K函数计算的时间复杂度，使其更好地应用于大数据场景。本文提出的四种优化策略在不同分布式环境下具有一定的通用性，适当调整后可移植到其他计算框架。同时，本文研究为如何降低空间分析方法的计算时间成本及推广用至大规模数据集和分布式计算环境具有一定指导意义，其他空间分析算法可借鉴上述思想实现优化与加速。