王 飞 庞 悦 周向东 陈海波

1(复旦大学计算机科学技术学院 上海 200433) 2(国网上海市电力公司 上海 200122)

一种面向相似查询的轨迹索引方法

王 飞1庞 悦1周向东1陈海波2

1(复旦大学计算机科学技术学院 上海 200433)2(国网上海市电力公司 上海 200122)

轨迹数据具有重要的应用价值，轨迹索引技术得到广泛的研究与关注。传统索引方法存在节点重叠、缺乏动态划分空间能力和丢失大量原始信息等问题，为此提出一种面向相似查询的轨迹索引方法GeoSAX。该方法将原始轨迹分成若干等长子段并采用基于Geohash的空间编码；对编码后的整条轨迹设计了基于HBase存储的索引架构；实现相似轨迹查询。GeoSAX不仅节点间没有重叠，还能依据数据量的大小对空间动态划分，同时保留指定精度的轨迹信息。在真实的航运和出租车数据集上进行的对比实验表明，与传统方法相比GeoSAX具有更好的轨迹查询性能。

轨迹索引 相似查询 Geohash 空间编码 HBase

0 引 言

近年来随着移动设备的普及和GPS定位技术的发展，现实生活中产生了海量移动对象的轨迹数据，如船舶的航运线路，出租车接送乘客的路线等。轨迹是移动对象运动过程中在不同时刻的位置序列，因此轨迹可以看作是一种多元时间序列数据[1]。轨迹数据有着非常重要的应用价值，如可以根据风暴的移动轨迹辅助预报自然灾害[2]；可以根据人们的运动轨迹挖掘出一些行为习惯从而为人们的生活提供智能的个性化服务[3]。移动对象轨迹数据的模式挖掘是当前的研究热点之一。……