论文部分内容阅读
随着传感器的广泛应用与信息基础设施的日益完善,越来越多的时空点数据被记录和收集下来,成为研究现实世界各类自然现象、社会事件的数据基础。时空Ripley’s K函数作为点模式分析的代表性方法,为研究不同时空尺度下点对象的分布模式提供了有效支撑。然而,全局的点对关系判断以及复杂的边界校正权重计算,使得时空Ripley’s K函数的时间复杂度较高。随着数据规模的增长,计算耗时指数级攀升,阻碍了时空K函数在海量点模式分析中的应用。
随着并行计算技术及高性能地理计算的兴起,基于多核CPU、众核GPU的并行计算技术已被用于空间Ripley’s K函数的优化与加速,相关实验也验证了并行Ripley’s K函数性能提升的可行性与潜力。但多核众核并行Ripley’s K函数的优化方法受制于单机存储能力,无法完全胜任当前大数据分布式存储与处理的潮流。同时,已有的分布式空间数据处理系统对于时空数据对象细粒度管理、操作与编码的支持不够完善,不能满足时空Ripley’s K函数的任务执行需要。
为此,本文基于时空优化原则与Apache Spark分布式计算框架,提出一种分布式时空K函数的计算方法,降低时空Ripley’s K函数在海量点时空模式分析中的应用门槛。该方法包含四项优化策略:(1)利用时空索引缩小点对比较范围,快速获取满足时空阈值的点对;(2)通过双层缓存来复用时空校正权重,避免重复计算;(3)基于时空邻近性优化数据分区流程,减少分布式环境中的数据冗余;(4)面向时空对象与时空索引设计定制序列化方法,精简二进制序列内容,减少数据传输量,降低序列化与反序列化的 CPU 负荷。其中,前两种策略致力于降低时空Ripley’s K函数的时间复杂度,缓解算法本身的计算密集问题;后两种策略注重提升时空Ripley’s K函数在分布式环境下的执行效率,应对数据密集问题。
实验结果表明四项优化与加速策略能够有效为时空Ripley’s K函数带来性能提升以及弹性伸缩能力。同时,本文讨论了时空Ripley’s K函数的输入参数对执行效率与计算结果所产生的影响。基于上述优化策略,本文设计了分布式时空Ripley’s K函数可视化分析框架,并实现原型系统;通过案例数据分析,展示本文方法的技术可行性与潜在应用价值。本文研发的并行算法可用于十万及百万级时空点对象时空聚集模式的挖掘与可视化分析。同时,本文方法可为时空Ripley’s K函数及其他点模式分析方法的算法并行化及可视化分析框架研发提供参考。
随着并行计算技术及高性能地理计算的兴起,基于多核CPU、众核GPU的并行计算技术已被用于空间Ripley’s K函数的优化与加速,相关实验也验证了并行Ripley’s K函数性能提升的可行性与潜力。但多核众核并行Ripley’s K函数的优化方法受制于单机存储能力,无法完全胜任当前大数据分布式存储与处理的潮流。同时,已有的分布式空间数据处理系统对于时空数据对象细粒度管理、操作与编码的支持不够完善,不能满足时空Ripley’s K函数的任务执行需要。
为此,本文基于时空优化原则与Apache Spark分布式计算框架,提出一种分布式时空K函数的计算方法,降低时空Ripley’s K函数在海量点时空模式分析中的应用门槛。该方法包含四项优化策略:(1)利用时空索引缩小点对比较范围,快速获取满足时空阈值的点对;(2)通过双层缓存来复用时空校正权重,避免重复计算;(3)基于时空邻近性优化数据分区流程,减少分布式环境中的数据冗余;(4)面向时空对象与时空索引设计定制序列化方法,精简二进制序列内容,减少数据传输量,降低序列化与反序列化的 CPU 负荷。其中,前两种策略致力于降低时空Ripley’s K函数的时间复杂度,缓解算法本身的计算密集问题;后两种策略注重提升时空Ripley’s K函数在分布式环境下的执行效率,应对数据密集问题。
实验结果表明四项优化与加速策略能够有效为时空Ripley’s K函数带来性能提升以及弹性伸缩能力。同时,本文讨论了时空Ripley’s K函数的输入参数对执行效率与计算结果所产生的影响。基于上述优化策略,本文设计了分布式时空Ripley’s K函数可视化分析框架,并实现原型系统;通过案例数据分析,展示本文方法的技术可行性与潜在应用价值。本文研发的并行算法可用于十万及百万级时空点对象时空聚集模式的挖掘与可视化分析。同时,本文方法可为时空Ripley’s K函数及其他点模式分析方法的算法并行化及可视化分析框架研发提供参考。