论文部分内容阅读
近年来,随着移动应用的普及、地理信息技术的不断发展,时空数据的数量急剧增长。时空数据具有增速快、数量大、结构复杂等特点,即使是性能极佳的单机计算设备也无法解决海量时空数据的查询困难、分析复杂等问题。新出现的Spark分布式计算平台虽然具备处理大数据的能力,但不提供对时空数据处理的直接支持。针对上述问题,本课题以Spark为计算引擎,深入研究时空数据的查询与分析关键技术,设计并实现了ST-Spark时空查询与分析系统。ST-Spark实现了范围查询、kNN查询、预测分析、时空聚类分析等功能。具有快速查询、有效分析的优点。论文的主要工作如下:(1)针对时空数据的非结构化、数量大等特点,以分布式NoSQL数据库Cassandra为存储引擎,设计了契合Spark计算模型的时空数据存储和网格索引模型。该模型实现了索引与数据分离,对同一个时空对象的轨迹记录能按照时间顺序存储在同一个节点中,保证了数据的局部性。(2)基于设计的存储与网格索引模型,提出了Spark上的时空范围查询与K邻近查询方法。通过Cassandra服务端过滤优化,解决了查询时空索引时粗过滤效率低下的问题。提出“网格外扩法”,确定至少包含K个时空对象的网格集合,提高了K邻近查询效率。(3)对时空轨迹数据进行多项式拟合、线性回归预测分析。为提高预测正确性,设计了基于滑动窗的多项式拟合时空轨迹预测分析方法。结合范围查询,研究和实现了基于Spark的预测性时空范围查询方法。(4)基于已有的聚类分析算法,进行三维拓展,创新地提出Spark上“均匀划分,本地聚簇,全局合并”的ST-DBSCAN算法。考虑到最大化并行计算优势,该算法按照数量均匀划分了时空数据,根据算法参数进行分区区域外扩,并行执行分区时空聚类方法,最后依据外扩分区数据点的聚簇属性进行全局合并与重新标记。针对ST-Spark系统,本文搭建了集群环境,基于T-Drive北京出租车轨迹和GDELT事件等数据,本文进行查询性能测试、预测分析准确性评估、时空聚类验证等实验。实验结果表明,在查询性能方面,ST-Spark优于同类系统。在时空分析方面,ST-Spark的预测分析准确率高、误差小,ST-DBSCAN分析快速、有效。