于海宁，张宏莉，余翔湛，曲家兴，葛蒙蒙,3

（1.哈尔滨工业大学网络空间安全学院，黑龙江 哈尔滨 150001；2.黑龙江省网络空间研究中心，黑龙江 哈尔滨 150001；3.南洋理工大学计算机科学与工程学院，新加坡 639798）

0 引言

随着无线通信、普适计算、卫星导航技术的不断发展，带有GPS 定位功能的智能设备被应用在许多领域[1]。这些设备能够记录相关实体的运动轨迹，进而形成海量的轨迹数据。这些轨迹数据不但记录了个体对象的运动模式、行为特征与规律，例如，经常活动的路线、生活工作的地点以及兴趣爱好和健康状况等，而且蕴含了群体对象的泛在移动模式与规律，例如，社会群体活动特征、城市交通拥堵规律、路网拓扑与地点坐标等。针对海量的轨迹数据，人们通过轨迹分析、挖掘等技术手段进行知识发现，并将其运用在各种交通和位置服务应用中，包括交通导航、位置服务推荐、交通指挥、物流配送、车辆监控等。轨迹相似度计算是轨迹分析的基础操作之一，其主要分析不同轨迹之间的位置相似性。提取相似轨迹在出行路径预测、兴趣区域发现、轨迹聚类、个性化路径推荐等领域具有广泛的应用。

云计算外包服务[2]的普及使很多轨迹拥有者选择将轨迹上传到云端轨迹服务存储，以降低轨迹存储和计算成本。同时，轨迹查询者可以向轨迹服务发送关于其兴趣轨迹的相似度计算请求，轨迹服务计算该兴趣轨迹与存储轨迹的相似度，并将最相似轨迹返回给查询者。……