首页> 正文

面向海量点模式分析的时空Ripley’s K函数优化与加速

2020-12-08阅读(768)

面向海量点模式分析的时空Ripley’s K函数优化与加速

论文摘要

随着传感器的广泛应用与信息基础设施的日益完善,越来越多的时空点数据被记录和收集下来,成为研究现实世界各类自然现象、社会事件的数据基础。时空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函数及其他点模式分析方法的算法并行化及可视化分析框架研发提供参考。

论文目录

  • 摘要
  • Abstract
  • 1 绪论
  •   1.1 研究背景及意义
  •   1.2 国内外研究现状
  •     1.2.1 面向计算加速的Ripley's K函数算法流程改造与优化
  •     1.2.2 基于分布式计算框架的空间数据处理
  •     1.2.3 Ripley's K函数关键输入参数影响分析
  •   1.3 研究目标与内容
  •     1.3.1 研究目标
  •     1.3.2 研究内容
  •     1.3.3 技术路线
  •   1.4 论文的组织结构
  • 2 时空点模式分析理论
  •   2.1 点模式分析方法概述
  •   2.2 空间Ripley's K函数的估计与模拟
  •   2.3 时空Ripley's K函数的估计与模拟
  •   2.4 时空Ripley's K函数时间复杂度分析
  •   2.5 本章小结
  • 3 时空Ripley's K函数算法流程优化
  •   3.1 时空K函数算法流程性能瓶颈分析
  •     3.1.1 点对过滤的全局遍历问题
  •     3.1.2 时空校正权重的重复计算问题
  •   3.2 基于时空索引的点对过滤方法
  •     3.2.1 主要时空索引方法的对比分析
  •     3.2.2 基于时空索引的点对过滤策略设计
  •   3.3 基于双层缓存的权重复用方法
  •     3.3.1 时空权重缓存设计
  •     3.3.2 时空权重复用流程
  •   3.4 本章小结
  • 4 时空Ripley's K函数分布式加速
  •   4.1 分布式环境下时空K函数性能瓶颈分析
  •     4.1.1 缓存区与数据分块方法的数据冗余问题
  •     4.1.2 默认序列化的编码冗余问题
  •   4.2 顾及时空分布的数据分区方法
  •     4.2.1 数据分区的时空依据
  •     4.2.2 顾及时空分布的数据分区流程
  •   4.3 面向时空对象与索引压缩传输的定制序列化方法
  •     4.3.1 时空对象的定制序列化
  •     4.3.2 时空索引的定制序列化
  •   4.4 本章小结
  • 5 实验与讨论
  •   5.1 实验环境及实验设计
  •     5.1.1 实验数据
  •     5.1.2 实验环境
  •     5.1.3 实验设计
  •   5.2 时空Ripley's K函数流程优化对比实验
  •     5.2.1 基于时空索引的点对过滤对比实验
  •     5.2.2 基于双层缓存的权重复用对比实验
  •   5.3 时空Ripley's K函数分布式加速对比实验
  •     5.3.1 顾及时空分布的数据分区对比实验
  •     5.3.2 面向时空对象及索引的定制序列化对比实验
  •   5.4 综合优化效果对比实验
  •   5.5 伸缩性对比实验
  •   5.6 时空Ripley's K函数输入参数影响分析
  •     5.6.1 点数据规模影响分析
  •     5.6.2 时空距离阈值影响分析
  •     5.6.3 研究区域复杂度影响分析
  •   5.7 应用案例
  •   5.8 本章小结
  • 6 分布式时空Ripley's K函数可视化分析原型系统
  •   6.1 原型系统框架设计
  •   6.2 原型系统界面展示
  • 7 总结与展望
  •   7.1 总结
  •   7.2 展望
  • 参考文献
  • 研究成果
  • 致谢

    • 文章来源

    类型: 硕士论文

    作者: 王源

    导师: 吴华意

    关键词: 点模式分析,大数据,分布式计算,空间索引,数据分区

    来源: 武汉大学

    年度: 2019

    分类: 基础科学,信息科技

    专业: 自然地理学和测绘学,计算机软件及计算机应用

    单位: 武汉大学

    基金: 国家重点研发计划项目(项目编号:2017YFB0503704,项目名称:全球位置信息叠加协议与位置服务网技术),国家重点研发计划项目(项目编号:2018YFC0809806,项目名称:社区风险监测与防范关键技术研究),国家自然科学基金项目(项目编号:41371372,项目名称:支持质量约束的地理信息资源在线搜索关键技术研究),国家自然科学基金项目(项目编号:41501434,项目名称:基于非均衡时空访问模式的网络地图服务计算资源弹性分配方法),武汉大学人才计划-珞珈青年学者项目(项目名称:海量POI高性能空间点模式可视分析关键技术研究)

    分类号: P208

    总页数: 68

    文件大小: 2544K

    下载量: 36

    相关论文文献

    • [1].一种基于信息熵的时空点模式分析方法[J]. 地理与地理信息科学 2016(05)
    • [2].时空点过程:一种新的地学数据模型、分析方法和观察视角[J]. 地球信息科学学报 2013(06)
    • [3].城市入室盗窃时空点模式分析[J]. 测绘与空间地理信息 2014(08)
    • [4].植朵美好的花,迎向2019年[J]. 台声 2018(24)
    • [5].某个时空点上的某种假设[J]. 北方作家 2013(03)
    • [6].汶川地震的时空点格局分析[J]. 地震学报 2009(05)
    • [7].基于点过程模拟的时空级联模式统计挖掘方法[J]. 中南大学学报(自然科学版) 2017(10)
    • [8].什么是人民的立场?[J]. 求知 2016(10)
    • [9].有一种时光[J]. 文苑(经典美文) 2015(05)
    • [10].时空数据发布中的隐式隐私保护[J]. 软件学报 2016(08)
    • [11].谈情说爱录[J]. 文学教育(下) 2017(02)
    • [12].郭蕾 幸福的师者[J]. 今日教育 2009(11)
    • [13].焦虑·叠压·凝视——关于文中言的“城”系列[J]. 美术 2019(01)
    • [14].梦幻日记[J]. 青春 2013(08)
    • [15].时光的锚点 谢铿的写生水彩[J]. 潮商 2013(01)
    • [16].注意7月15日时空点[J]. 股市动态分析 2009(28)
    • [17].预设与生成的完美“邂逅”,凸显精彩的体育课堂[J]. 科技信息 2009(28)
    • [18].数字化时代企业家的“共生”领导力[J]. 企业观察家 2018(12)
    • [19].影像时空建构的审美感知——从中国传统绘画的时空意识谈起[J]. 电影评介 2017(19)
    • [20].微博签到数据的时空热点挖掘——以北京为例[J]. 测绘工程 2018(05)
    • [21].时间文化的互通和渗透——以出土历书为中心[J]. 广西教育学院学报 2017(03)
    • [22].莎菲形象新解:反对自己的现代女性[J]. 长江大学学报(社科版) 2015(05)
    • [23].费师傅[J]. 广西文学 2011(03)
    • [24].MAP-Vis:基于MAP模型的时空点状大数据可视化方案[J]. 中国图象图形学报 2019(05)
    • [25].旋转推铅球技术的时空特征分析——以我国2名铅球运动员推铅球技术动作为例[J]. 湖南工业大学学报 2009(06)
    • [26].基于信息熵抑制的轨迹隐私保护方法[J]. 计算机应用 2018(11)
    • [27].把自己当作自己[J]. 黄河.黄土.黄种人 2019(05)
    • [28].基于中国文化传统的教师角色理解[J]. 中国教师 2016(11)
    • [29].动态认识中医疾病的重要性[J]. 辽宁中医药大学学报 2008(10)

    标签：;  ;  ;  ;  ;  

    面向海量点模式分析的时空Ripley’s K函数优化与加速
    下载Doc文档

    猜你喜欢

    © 2024 毕论降 版权所有 鄂ICP备12018319号-6