论文部分内容阅读
激增的数据量对大数据分析不断提出新的挑战,因而一系列具有快速、易用、可扩展特征的大数据分析新架构不断涌现。分布式内存计算已证明其较MapReduce架构计算性能更优,当被应用在地理信息领域中,为高性能的地理计算提供了新的研究视角。但无论是MapReduce还是分布式内存计算框架本身不支持地理空间数据分析。面对这一现状,很多系统基于这两种计算架构进行了改进以支持空间分析,在特定空间分析领域中表现出了优越的性能。因而,本文基于分布式内存计算架构,着眼于大规模空间矢量数据,考虑对其分析方法进行并行优化。空间大规模矢量数据具有多维、形式多样、结构复杂、分布不均衡的特征,大大增加了分析的难度。本文从考虑空间矢量数据输入系统后的划分、计算、查询这三个层面的特定分析方法,最终实现对空间实时聚集分析应用的支持。(1)提出一种基于随机采样样本和自适应Hilbert排列码的空间矢量数据划分方法,能够快速提供最优的划分方式。数据划分是数据在系统中处理的第一步,通过划分函数将整块空间数据划分到各个计算节点中。因为空间数据包含空间维度信息,所以需要将空间上邻近的数据划分到同一个节点中。因而,本文使用Hilbert空间填充曲线排列码进行数据划分。又因为空间数据的分布不均衡性,需要确定Hilbert空间排列码的层次。本文中先从输入数据中构建一个随机采样样本,通过自适应的迭代求出针对特定数据的排列码层级。此外,介绍了划分分解过程中数据倾斜和边界对象两个问题的处理方法。(2)对矢量数据缓冲区分析这一计算密集型分析算法进行并行优化,采用近似切分、网格累进的任务分解和给定深度的树状合并方法三种策略,较现有的商业流行软件和其他并行策略效率提升了50%以上。矢量缓冲区分析是一类最基本的空间分析方法,其并行化策略对于提升计算效率至关重要。传统的并行优化方法往往基于MPI(Message Pass Interface,消息传递接口),在可扩展性方面受到了限制,而且没有考虑数据的空间邻近特性。所以本文首先按照Hilbert填充曲线编码方式对数据进行划分,对划分过程中存在的边界问题采用切分方法处理。在任务分解时,按照网格累进的方式使每个分解的数据块包含近似相同的对象数量,保证后续单个数据块内的缓冲区计算耗时大致相同。最后,通过给定深度的树状合并方法合并各个数据块的缓冲区计算结果。(3)提出了并行的聚集索引方法,相较于当前分布式内存空间分析系统中支持的索引方式,提升了精确聚集查询的效率。然后,提出了面向空间在线分析的并行近似查询索引方法,快速反馈近似查询结果,以及任意置信度下的置信区间。空间聚集查询是一类应用广泛的查询,本文中主要研究了矩形框聚集查询方法。首先,对聚集R树优化得到Hilbert聚集R树,然后对其并行化构建,结合网格全局索引得到了一种两级索引结构,支持精确聚集结果的并行查询。之后,考虑到随机采样是一种应对大规模数据的有效方法,因而在多层级采样的随机采样样本基础上,构建多层级索引,然后以一种逐层查询的方式反馈近似查询结果,以及该结果对应的任意置信度下的置信区间,为是否终止查询提供参考。(4)面向实时在线分析,设计并实现了大规模轨迹数据在线实时聚集分析原型系统HiStream,支持实时聚集分析,并提供ROI(Range of interest,兴趣区域)和POI(Point of interest,兴趣点)两种尺度下的多种时空分析工具。除了前面提及的并行优化技术,HiStream系统还基于HTML5的数据可视化技术,提供了良好的交互界面。HiStream的基本功能是聚集结果的实时聚集分析,并通过热力分布图的形式展示,实现了亿级轨迹点数据集的秒级响应。此外,原型系统还提供多种交互分析工具,能够实现高效的时空模式发现。本文还提供了城市热点快速发现、城市异常模式快速检测、城市出行模式快速检测分析这三类分析案例。