基于分布式字典树索引的大规模时空轨迹相似度搜索

作     者：翁良贵 

作者单位：华中科技大学 

学位级别：硕士

导师姓名：郑渤龙

授予年度：2021年

学科分类：12[管理学] 081603[工学-地图制图学与地理信息工程] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081802[工学-地球探测与信息技术] 07[理学] 08[工学] 070503[理学-地图学与地理信息系统] 0818[工学-地质资源与地质工程] 0705[理学-地理学] 0816[工学-测绘科学与技术] 

主      题：轨迹 相似度搜索 k最近邻查询 分布式 异质性 

摘      要：轨迹数据是对移动对象的运动过程进行采样所获得的地理信息序列。随着GPS设备的普及,轨迹数据规模呈爆发式增长,这使得可以通过分析轨迹数据来方便人们的生活。基于轨迹相似度的k最近邻查询是轨迹数据分析的基本运算之一。然而,海量的轨迹数据使得现有的单机算法无法高效地完成查询任务。分布式方案能够利用多台机器的资源去加速查询过程,但目前最先进的分布式方案存在计算资源浪费和局部索引查询效率低的问题。为了解决上述问题,提出了一个运行于Spark的分布式轨迹相似度搜索框架REPOSE(Reference Point Tries)去处理k最近邻查询。该框架支持多种轨迹相似度度量,包括Hausdorff距离、Frechet距离、DTW距离。REPOSE由全局分区策略和局部索引两部分组成。全局分区策略设计了一种新颖的异质性分区策略,它通过平衡每一个分区的组成来实现负载平衡和改善局部索引的查询效率。局部索引使用Zorder将原始轨迹离散化成参考轨迹,然后使用参考字典树来索引参考轨迹。为了进一步改善查询效率,该框架使用了一个基于顺序无关的优化方法来改善参考字典树的性能。除此之外,该框架基于参考轨迹的性质提出了三种强有力的剪枝下界(单向下界,双向下界以及中枢轨迹下界)来减少计算次数和使用中间结果来降低计算下界的成本。为了充分展示REPOSE的效果,将它与最先进的分布式轨迹相似度搜索框架在真实数据集上进行性能比较。实验结果表明,REPOSE的性能优于现有的分布式轨迹相似度搜索框架。