基于E2LSH的轨迹KNN查询算法

邱 磊，吴志兵

(江南计算技术研究所，江苏 无锡 214083)

0 引 言

随着传感器技术和定位技术的发展，基于位置的服务应用越来越广泛。人类活动通过智能手机APP应用软件进行位置分享、签到等；车辆安装GPS或北斗定位系统，周期性地上报位置信息；动物学家记录动物的迁徙路径等等。在这些活动中产生了一系列轨迹数据，随着时间的推移，数据规模愈加庞大。

对于海量轨迹数据的挖掘，可以获得大量有价值信息。例如，对车辆轨迹数据分析研究获取驾驶行为与交通路网之间的相关性[1]；对智能手机定位轨迹数据分析得到用户的移动特点和生活规律[2]；对旅行轨迹数据分析向用户推荐满足不同需求的路径[3]。轨迹数据挖掘常常依赖于大量的轨迹查询行为。轨迹查询分为KNN(k-nearest neighbor)查询和范围查询，而KNN查询又分为轨迹点查询和整条轨迹的查询。查询的第一步是定义两条轨迹的距离，也就是轨迹之间的相似度[4]。

传统的海量轨迹数据查询基于树结构进行索引，当轨迹较短，即维度较少时性能良好，但是随着维度的增加(比如20维以上)，检索效率会急剧下降，在性能上甚至还不如对整个数据集合进行顺序检索，这就是高维空间数据处理都会遇到的“维数灾难”[5]问题，从而导致难以实现轨迹的快速查询。局部敏感哈希技术[6](locality sensitive hashing，LSH)是解决高维数据近邻查询的有效方法。传统的LSH采用汉明距离来实现近邻数据的快速查询，所以在实际应用中需要首先将数据嵌入到汉明空间，大大增加了计算的复杂度。目前在大规模数据高维近邻索引中，一般采用LSH在欧氏空间中的一种随机化方法，被称为精确局部敏感哈希(exact Euclidean locality sensitive hashing，E2LSH)[7]。LSH技术在很多领域获得了成功应用，例如大规模网页的去重、海量图片搜索以及相似音视频的检索等等。

综上，文中提出了一种支持海量轨迹数据的KNN查询算法(trajectory E2LSH-based KNN query，TRA-EKNN)。首先研究轨迹大数据的向量空间建模问题，并结合特定领域的兴趣点(point of interest，POI)进行了初步降维，进而采用E2LSH算法实现轨迹数据的索引构建，并在合成数据以及实际数据集上进行KNN查询，最后对实验结果进行了分析和总结，并展望了后续工作。

1 相关工作

对于轨迹数据的KNN查询算法，根据查询结果的可靠性，可以分为两类：基于时空数据库索引的穷举算法和基于哈希的近似算法。

目前，对于轨迹数据的查询研究多基于穷举算法。时空数据库[8](spatio-temporal databases，STDB)将时间和空间有机结合，实现对时空对象的有效管理。由于R树以及改进树[9]在空间索引的巨大优势，被大多时空索引结构所采用。近似算法在允许一定误差的前提下，可以大大提高检索性能。在海量数据日益增多的情况下，近似算法受到研究者的广泛关注。在近似算法中，应用最为广泛的是基于哈希的检索技术。Athitsos等[10]定义并实现了一种全新的基于距离的哈希算法(distance-based hashing，DBH)。Sanchez等[11]提出了一种基于LSH算法的轨迹聚类算法。这两种算法都将轨迹视为连续的轨迹点，即一条曲线，因此计算过程中均没有考虑时间因素，不适应于严格定义的轨迹数据。

国内学者对LSH技术在轨迹数据分析中的应用也做了大量相关研究。赵家石等[12]采用局部敏感哈希技术寻找在一定时间内都相似的移动对象，从而避免传统方法的交集运算过程，实现轨迹相似度的快速估计。廖律超等[13]利用谱哈希实现对交通路网的快速聚类，挖掘出交通轨迹大数据的潜在特性，为交通规划提供了科学依据。印桂生等[14]将文本相似领域比较广泛应用的相似哈希(simhash)[15]技术应用到用户轨迹的相似性比较中，取得了较好效果。

2 TRA-EKNN算法

2.1 相关定义

文中所研究的问题是在海量的轨迹大数据中，根据一条轨迹数据查询找出距离最近，也就是最相似的k条轨迹。

定义1：轨迹是由移动对象在增量时间的一系列轨迹点组成，记为：

TR={P1,P2,…,Pn}

其中Pi是移动对象在t时刻的位置(用经纬度表示)，即pi=(lat,lng,t)。

定义2：网格空间是指对参与计算的地理空间进行划分编码形成的网格集合，记为：

G={gid1,gid2,…,gidm}

其中gidi表示编号为i的网格。地理空间可以是一个国家、一个城市，也可以是结合特定领域知识和含义进行筛选之后区域范围。

定义3：网格序列[16-17]是指一条轨迹将经过的网格顺序排列之后的集合，记为：

GS={g1,g2,…,gm}

其中gi=(gid,t)，即在网格gid停留时间为t。

2.2 算法思想

TRA-EKNN算法主要包括网格索引建立、轨迹向量建模和KNN查询实现等过程，具体流程如图1所示。

2.2.1 网格建立

网格索引建立是针对特定领域的POI集合计算每个地理位置的网格编号，然后合并形成一个网格空间G。

文中采用GeoHash技术实现网格的编码。GeoHash通过使用一个字符串同时表示经度和纬度两个坐标，是一种通用的地址编码方案，具有如下特点：将二维空间的经纬度编码成一个字符串，在传统的数据库中做到一维的高效索引；每一个GeoHash表示的不是一个点，而是一个矩形的区域；GeoHash编码的前缀可以用来表示更大范围的区域。

GeoHash的计算方法主要分为三步：

(1)经纬度转换为二进制。首先将全部的纬度范围(-90,90)平均分为区间(-90,0)和(0,90)，如果目标维度位于第一个区间，则编码为0，否则为1，例如39.923 24属于(0,90)，取编码为1。然后再将(0,90)分为区间(0,45)和(45,90)，而39.923 24位于(0,45)，编码为0。以此类推，直到精度符合要求为止，最终得到纬度的编码1011 1000 1100 0111 1001。经度也采用同样算法得到编码。

图1 TRA-EKNN算法框架

(2)按照经纬度的二进制合并。按照纬度在奇数位，经度在偶数位的规则进行合并。

(3)进行Base32编码。编码字符使用0-9和b-z(其中去掉a,i,l,o四个字母)。

由以上的GeoHash计算过程，可以知道精度取决于编码长度，根据实际需求采用不同长度的编码，二者的对应关系如表1所示。

表1 GeoHash编码长度与精度

通过将地理位置编码，实现了对地理空间的网格索引。在此过程中，根据不同的应用场景采用不同的编码长度，实现效率与精度的统一。将所有特定领域的POI数据经过GeoHash编码，可以得到网格空间G，相比于直接将所有的空间都进行编码，此方法利用了数据融合的思想，从而大大减少了网格数量，实现初步降维，在后续的计算过程中也更具实际意义。

2.2.2 轨迹向量建模

借鉴文本分类中向量空间模型(VSM)[18]的思想，将网格空间G视为n维向量的维度，本小节基于此，将轨迹向量化，然后再进行轨迹的距离计算。

轨迹网格序列化算法是向量建模的关键。将原始轨迹数据转换为网格序列，可以在保证一定精度的前提下，简化轨迹的处理过程。

算法1：轨迹网格化。

输入：轨迹TR={P1,P2,…,Pn}

网格空间G={gid1,gid2,…,gidm}

输出：网格序列GS={g1,g2,…,gm}

其中gi=(gid,t)

详细过程：

1.foreachPiin TR

2.if(i==1)

3.last_time=Pi.t

4.last_geo=geohash(pi.lat,pi.lng)

5.continue

6.g.gid=geohash(Pi.lat,Pi.lng)

7.t_interval=Pi.t-last_time //时间差

8.if(g.gid inG)//只处理位于网格空间的数据

9.if(g.gid==last_geo)

10.t_stay=t_stay+t_interval

11.else//进入另一网格

12.if(g.gid in GS)

13.Break// 截断处理

14.g.t=t_stay+t_interval/2

15.GS.append(g) //当前点加入序列

16.t_stay=t_interval/2

17.OUTPUT(GS)

算法1描述了轨迹转换为网格序列的全过程。最终的输出包含轨迹所经过的网格编码和相应的停留时间。由于采样时间的差异，导致在同一个区域可能出现多个轨迹点。停留时间的计算需要考虑两种情况：(1)两个轨迹点位于同一个网格时，间隔时间直接累加；(2)前后两个轨迹点位于不同网格，则停留时间按时间间隔的一半累加。从后续工作中可以看到，轨迹的向量化意味着轨迹网格不允许出现重复，所以算法1进行了简单处理即轨迹截断，另外一种方法是将后续轨迹点当作另一条轨迹继续处理。

经过算法1的处理，轨迹转换为在选定领域(网格空间)的网格序列。基于此，可以构建轨迹的向量矩阵[13]，其中矩阵的行对应于全部的网格空间，列对应于每条轨迹。假设轨迹数据经过算法1的计算，提取出了r条轨迹，相应的网格空间大小为n，则构成一个n×r的“网格-轨迹”矩阵T，每个元素的值定义为轨迹点在对应网格停留时间。

将轨迹进行以上处理之后，可以据此定义两条轨迹向量的距离：

(1)

轨迹的网格空间可以理解为针对特定领域所关心的所有位置，也就是在轨迹的距离(相似)公式中参与计算的位置，其他非必要的位置不参与计算。相比于通过聚类方法提取POI(兴趣点)的方法，大大降低了数据预处理过程的难度和时间消耗。

2.2.3 E2LSH算法索引构建

E2LSH是LSH在欧氏空间的一种随机化实现方案。基本的思路是：采用基于p稳定分布的局部敏感函数对原始的高维数据进行降维映射。可以看出，E2LSH继承了LSH的特点，即在原始空间相邻的数据，经过哈希之后，在新的空间上存在很大的概率也相近，具体哈希函数如下：

(2)

其中，a是独立随机选择的d维向量，b为范围[0,w]的一个随机数。函数h将一个d维向量映射到一个整数集，然后以w为宽度进行等距离划分。E2LSH将k个哈希函数联合使用，称之为函数族：

(3)

函数族g对应于L个哈希表，随机独立选取的k个h函数又构成了每个g函数，函数的值对应具体的哈希桶。

从算法思想的本质上看，LSH是不确定的，概率性的，可以归结为近似算法。随着数据规模越来越大，数据处理的时效性要求面临很大挑战，这时通过牺牲一定精度以获得更快的处理速度，在一些领域是可行而有效的。本节将此算法应用于轨迹数据索引的构建，具体过程如下：

(1)对于数据库中的轨迹，经过算法1得到一条包含停留时间的网格序列；

(2)对于每条网格序列，由式(3)得到长度为k的哈希桶，计算L次，组成L个哈希表；

(3)对哈希表中的每个桶生成一个索引文件。

2.2.4 KNN查询实现

KNN查询的目标是在轨迹数据中找到与查询轨迹TR距离最近的k条轨迹。传统的线性算法通过计算待查询TR与所有的轨迹的距离，然后从中选出最近的k条轨迹，显然在这过程中计算量十分的巨大。虽然可以采用R-Tree、KD-Tree等树结构进行优化，但是“维数灾难”的问题，使得轨迹点数较多时，存在着大量的回溯计算，导致树结构不能发挥作用，这时退化成线性运算。

本算法在上一节构建好轨迹数据的E2LSH索引的基础上进行查询，具体流程如下：

(1)运用算法1得到所要查询的轨迹对应的网格序列；

(2)计算待查询网格序列的L个哈希表索引；

(3)遍历哈希表，找到对应的哈希桶，对桶内的轨迹，利用式(1)计算对应的距离，返回最近的k条轨迹。

本算法使用E2LSH技术，首先将所有的轨迹数据按照距离划分到不同的哈希桶，同一个哈希桶的轨迹距离较近，所以KNN查询只需要根据不同哈希值比较同一个或者相近桶内的轨迹，从而极大地减少了需要计算比较的轨迹数量，使得海量轨迹的KNN查询效率得到有效提升。

3 实验结果与分析

实验采用两个数据集：合成数据用来检测算法的时间效率，并与传统查询算法进行对比；上海出租车轨迹数据用来证明算法在实际应用中的有效性。实验环境为单机，处理器为Intel(R) Core(TM) i3 M 380 @ 2.53 GHz，内存6 G，操作系统为Windows7 64位 SP1，采用python语言编程实现。

3.1 合成数据实验

本实验的合成轨迹数据，根据网格数量和轨迹停留时间随机生成。假设网格数量为m，轨迹数量为n，根据m和n的不同取值，查询某条轨迹的最近10条轨迹，消耗时间如图2所示。

其中10 000*10 000表示10 000条轨迹对应于10 000个网格空间。可以看出时间消耗与二者的乘积大致是一个线性关系，随着网格空间的增大和轨迹数量的增多，计算所消耗的时间成线性增长。

图2 穷举消耗时间对比

采用TRA-EKNN算法对上述数据进行KNN查询，根据文献[6]中的建议值，算法中w取值为4，k取80，L取10，此时获得的准确率大于95%，时间消耗如图3所示。

图3 TRA-EKNN消耗时间对比

从图3可知，TRA-EKNN算法中，时间消耗主要分索引建立和轨迹查询两部分，而且索引的建立时间远大于查询时间，而且当网格空间固定即轨迹的维度相同时，轨迹的数量只影响索引的建立时间，而查询时间基本相同。

在实际的应用中，一般要先将海量的轨迹建立索引，图1所示的查询算法框架也体现了这一点。在后续的KNN查询时间一般指的就是图3中的查询时间，也就是说在进行轨迹查询之前索引已经建立完毕，查询过程中无需关心E2LSH索引的建立时间。对比图2可以看出，本算法的查询时间消耗明显小于穷举算法。

3.2 上海出租车轨迹数据实验

上海市出租车数据集，采集了2007年2月20日当天4 316台出租车的GPS记录信息，包括出租车标识、时间戳、经纬度、瞬时速度、顺时针角度以及载客情况等。本实验只取标识、时间戳和经纬度三个信息。

根据采集到的上海市交通相关的POI数据共计242 556条，考虑到实验数据是出租车GPS轨迹结合表1的GeoHash长度与精度关系，哈希长度设定为7，误差约为76米，将POI数据中的经纬度计算GeoHash，去重后，共计有71 495个网格。上海面积约为6 340平方公里，如果全部进行7位的GeoHash编码，大约一百万个网格(由于行政区划的不规则，数据不准确，在此仅进行估算)。可以看出由于结合了交通领域的POI数据，使得网格空间大幅压缩。

对出租车轨迹采用算法1进行处理，共提取有效轨迹对应的网格序列1 896条，由于出租车行驶过程中会出现司机休息和等待乘客等情况，停留时间会比较长，为了体现轨迹比较的实际意义，将停留时间大于二十分钟的轨迹截断，然后将其余轨迹的停留时间作归一化处理。

采用TRA-EKNN算法，对所有的轨迹数据建立E2LSH索引，经过多次试验，此算法可以在较短的时间内查询出KNN结果，并有较高的准确率。

3.3 算法分析

正如前文所述，时空轨迹数据的KNN算法主要是基于传统的穷举算法，即采用一一匹配的暴力搜索的方式进行，此时时间复杂度是线性的，即○(N)。随着数据规模越来越大，这种方式会消耗大量的时间。

文中提出的TRA-EKNN算法，首先建立了LSH索引，虽然带来了空间消耗增加的问题，但检索的时间复杂度降为了○(logN)，这对于一些时效性要求较高的场景是完全适用的。

4 结束语

将在海量文本、音频、视频数据处理广泛应用的E2LSH算法引入到轨迹数据的KNN查询中。首先针对不同的应用场景，结合特定领域POI数据建立网格空间；然后对轨迹数据进行预处理，构造出轨迹的网格向量，利用E2LSH算法实现索引。从图1算法的实现框架来看，对于增量的轨迹只需要计算哈希值，然后插入索引即可，计算简单。实验结果表明，在保证一定的准确率的情况下，该算法有效降低了轨迹KNN查询时间。下一步将继续对轨迹的特征提取方法进行探索，找出更适合轨迹数据处理的向量空间构建方案，使此方法能够在海量的轨迹数据挖掘中得到更广泛的应用。