论文部分内容阅读
近年来,移动终端和基于位置服务技术的快速发展和广泛应用,使得轨迹数据无处不在,数据规模急剧增加,已成为当前一类重要的大数据。针对这些时空特性显著的大规模轨迹数据,如何对其进行高效索引、查询处理及深度挖掘分析,受到学术界和工业界的广泛研究,并已成为该领域的一个重要研究课题。传统的轨迹数据查询处理技术由于其集中式的处理方式而导致扩展性较差,无法处理这种轨迹大数据,而Hadoop云计算平台由于其高效的并行处理架构已成为当前大数据处理的主流平台。为此本文基于Hadoop平台,针对大规模轨迹数据的查询处理问题进行深入研究,主要做了以下几方面的工作:首先,在深入分析了轨迹数据时空序列特性的基础上,提出了一种轨迹数据压缩算法,该算法运用空间向量思想,将平面数据压缩算法与轨迹数据特征相结合,能够大大降低轨迹数据的存储开销、减轻索引构建代价。在此基础之上,基于MV3R-tree时空索引结构,提出了一种叶子结点分裂处理优化算法,该算法能够保证分裂后的叶子结点内的数据具有较高的相似度,同时降低叶子结点间数据对象的相似度,使索引结构更加紧凑,能有效提高查询处理效率。其次,基于Map-Reduce并行处理框架,设计并实现了两种轨迹数据查询处理算法,主要包括时空范围查询和时空点查询处理算法,在此基础之上提出了一种基于Dijkstra最短路径的路径推荐算法,该算法能够充分利用历史轨迹信息找到两点之间可达且距离短的推荐路径,为进一步扩展轨迹数据分析处理和应用提供了有益的尝试。最后,通过大量实验对本文所提出的轨迹数据压缩、索引优化、查询处理及路径推荐等算法的性能和正确性进行了验证。结果表明,轨迹数据压缩算法能有效地降低索引创建和查询处理代价:优化后的索引结构具有更好的并行查询处理性能,其性能明显优于集中式索引;路径推荐算法在处理小范围查询时响应速度快捷、具有较好的可达性。