关键词:
时空点数据
数据划分
图划分
存储负载均衡
时空范围查询
摘要:
随着物联网和云计算技术的高速发展,GIS已步入大数据时代。智能手机、车载传感器等数据采集设备产生了海量时空数据,这类数据具有数据量大、多源异构、时空分布不均等特点。目前,已有多种方案基于分布式No SQL数据库来管理海量时空数据,然而大多数管理方案没有考虑数据分布对查询效率的影响,对时空数据存储负载均衡支持不足。同时很多学者针对分布式环境下数据的划分和存储均衡进行了深入研究,但时空数据具有其独特性,在进行数据划分时需要保持空间邻近性,在负载均衡时需要考虑到各时段内的数据在节点间的数据量均衡。否则在进行时空查询和分析时,会频繁进行分布式计算节点的交互而大大降低效率。因此,如何对时空分布不均的海量时空数据进行数据划分和存储负载均衡是一个亟需解决的问题。针对上述问题,本文首先提出了顾及时空分布的自适应数据划分方法,在空间上,通过抽样实验来确定针对特定应用场景的网格分裂阈值,设计一种基于空间分布的层级计算模型来确定划分起始层级,从而实现网格的并行分裂和合并,以提高空间自适应划分的效率;在时间上,根据数据的时间潮汐规律来划分时间分段,构建时空分层索引结构。接着,本文研究并提出基于图划分的存储负载均衡方法,在数据分组阶段,通过定义初始分布实现将多个时段的数据用统一的空间分布来表达,将自适应划分结果映射成加权无向图结构后,采用开源Metis图划分算法实现数据均衡分组;在分组调优阶段,设计迭代微调法平衡各时段的数据存储负载,同时有效维护了划分结果的空间邻近性。最后,基于本文提出的索引架构和负载均衡方法,采用HBase数据库设计了相应的存储方案和查询算法,利用协处理器机制和辅助索引表来加速查询处理。以纽约出租车数据为实验对象,本文进行了一系列对比实验。实验结果表明:在数据划分方面,利用抽样实验得到的网格点数阈值具有可靠性,能有效平衡负载均衡效果和查询效率;本文提出的分布式并行划分方法效率高于自顶向下或自底向上划分,索引构建效率提高了20%以上。在存储负载均衡方面,基于图划分的数据分组方法虽然不均衡度略低于基于Z-Order曲线的方法,但维持空间邻近性的能力更强;采用迭代微调法能在不破坏空间邻近性的前提下,将数据集的平均不均衡度降低30%左右,从而实现各时段数据的存储均衡。在查询效率方面,利用辅助索引表结合HBase协处理器机制的查询方法在各种查询场景下相对Geo Mesa的查询效率提升了2.5倍左右。