一种基于多级索引结构的大规模轨迹数据相似性查询方法

摘要

一种基于多级索引结构的大规模轨迹数据相似性查询方法，属于城市交通大数据处理与应用的领域。本发明分为索引建立阶段和轨迹相似性查询阶段，在索引建立阶段，首先对原始轨迹数据进行数据预处理，并基于空间网格索引思想对预处理后得到的轨迹数据建立网格索引，通过网格索引对轨迹数据集进行网格划分。其次，对于每条轨迹都通过构建特征轨迹来表示该轨迹的特征信息，对空间网格中每条轨迹的起点和终点建立起止索引，再根据每条轨迹的特征轨迹点建立特征点索引，从而将具有轨迹特征信息的轨迹点所组成的特征轨迹应用到多级索引结构上。最后，建立起网格索引‑起止索引‑特征点索引组成的多级索引结构。

说明书

技术领域

本发明属于城市交通大数据处理与应用的领域，具体涉及一种基于多级索引结构的大规模轨迹数据相似性查询方法。

背景技术

近年来，随着卫星定位技术、手机、GPS等移动设备的发展，每天都会产生大量的轨迹数据。轨迹数据里蕴含着巨大的价值，通过对轨迹数据进行挖掘，可以为日常生活中不同类型的应用所服务。由于轨迹存在于我们生活中的各个角落，丰富的轨迹数据资源也带来了对于轨迹数据研究的巨大需求。轨迹数据是属于时空数据的一种，包含了空间信息和时间属性，轨迹的空间位置同时会随着时间而动态地发生变化。轨迹数据具有非结构化、时效性强、规模大的特点。如何高效地对轨迹数据进行处理与分析是当今社会上与大数据技术相关的热点问题。

轨迹的查询操作是轨迹数据管理的关键技术之一，在近年来已逐渐趋于成熟。由于用户需求多种多样，轨迹数据分析与挖掘的应用也是各有不同，针对不同的应用场景也就需要不同类型的查询操作。按照查询类型的不同，轨迹查询可以分为范围查询、K近邻查询、相似性查询等查询操作。

轨迹的相似性查询是指给定查询轨迹，从数据集中查找与给定轨迹满足相似条件的轨迹，主要分为基于阈值的相似性查询和Top-k相似性查询功能。基于阈值的相似性查询操作就是指当用户给定一个相似性阈值，需要在一个轨迹数据集中查找出满足用户要求相似性的轨迹集，并返回给用户；Top-k相似性查询即是对于返回的轨迹集，根据相似度进行排序，选出前k条与查询轨迹最相似的轨迹。近年来对于轨迹相似性查询的研究成为了一个热点问题，相似性轨迹数据可以返回与输入轨迹相似的候选轨迹，从而对频繁轨迹、相似轨迹进行分析，便于挖掘轨迹大数据中潜在的信息与模式。比如在人类移动周期模式挖掘中，采用相似轨迹查询方法可以发现不同时间间隔中相似的人类移动行为，有助于研究城市人群的通勤规律。在位置预测中，已知当前移动对象的位置和历史轨迹，通过轨迹相似性查询，从相似的历史轨迹中发现移动行为的规律和模式，用于预测未来某个时间点的位置，在个性化推荐、交通管理以及天气预报等方面应用广泛。

虽然轨迹相似性查询功能在轨迹挖掘研究中十分重要，但是，由于此类相似性查询的计算复杂度很高，同时又对轨迹数据的质量比较敏感，导致轨迹相似性查询的计算效率比较低，继而影响相关轨迹挖掘算法的挖掘效果和计算效率。另外由于轨迹数据具有非结构化、时效性强、规模庞大等特点，对传统轨迹数据处理系统的实时存储、实时查询的能力提出了挑战。目前现有的对轨迹大数据进行处理的系统比较少，尤其是具有轨迹相似性查询功能并且可以基于内存的分布式轨迹处理系统很少。Xie等人(Xie D,Li F,Yao B,etal.Simba:Efficient in-memory spatial analytics[C].Proceedings of the2016International Conference on Management of Data.ACM,2016:1071-1085.)发明了一种基于Spark的分布式轨迹数据处理系统Simba，可以实现轨迹KNN查询和轨迹相似性查询等功能。Simba使用的是基于豪斯多夫距离和弗雷歇距离的相似性度量函数，并且将轨迹分成了若干个轨迹段，在轨迹段上建立全局索引和局部索引来实现对轨迹数据的管理。虽然相较于早期的单机轨迹数据处理系统，基于Spark大数据平台的Simba可以更加高效地处理轨迹数据，但是Simba在轨迹相似性查询过程中是使用的是传统相似性度量方法，对轨迹中的所有轨迹点进行计算，计算开销大并且花费时间长。Shang等人(Shang Z,Li G,BaoZ.Dita:Distributed in-memory trajectory analytics[C].Proceedings of the2018International Conference on Management of Data.ACM,2018:725-740.)发明了一种集成SparkSQL的分布式系统DITA也是基于Spark大数据平台的，DITA在轨迹相似性查询过程中取出整条轨迹中间距较大的轨迹点作为轴值点来代表轨迹进行计算，并且具有过滤器验证的框架对相似的两条轨迹进行相似性验证。相比于Simba，DITA可以通过选取轨迹中的轴值点代替轨迹计算，通过减少参加轨迹相似性计算的轨迹点个数可以减少计算开销，然而DITA在选取轴值点的过程中，只对轨迹点间的间距大小进行了考虑，选取出来的轴值点并不能有效地代表完整轨迹参加轨迹相似性计算中轨迹点间距离度量与备选轨迹集筛选。所以，如何搭建一个高效的轨迹数据处理系统来对轨迹数据进行分析处理，实现轨迹相似性查询等重要功能是科研领域中值得被关注的热点问题。

发明内容

为了解决上面提出的问题，本发明提出了一种基于多级索引结构的大规模轨迹数据相似性查询方法。通过这一方法，即使在轨迹数据集规模很庞大的情况下也可以对轨迹数据进行相似性计算，高效完成轨迹相似性查询等功能。本方法可以具体实现于Spark平台上，建立起基于内存计算的分布式轨迹数据处理系统来实现轨迹相似性查询等功能。本方法分为索引建立阶段和轨迹相似性查询阶段。索引建立阶段分为两个模块，分别为基于空间网格索引思想的网格索引模块和基于特征轨迹表示法的起止索引-特征点索引二级索引机制模块。第一个模块首先对原始轨迹数据进行预处理，对于预处理操作后得到的轨迹数据集利用地理空间信息进行网格划分，使其划分成大小相同的较大空间网格子集，每个空间网格子集都对应存储一块空间，同时对每个空间网格子集加以编号，生成网格索引；第二个模块通过特征轨迹生成器对空间网格子集中的每条轨迹的轨迹点进行加权计算，排序筛选出更具备轨迹信息的特征轨迹点，并将特征轨迹点组成特征轨迹，利用特征轨迹来建立起止索引-特征点索引二级索引结构，实现对轨迹数据的管理和操作。在轨迹相似性查询阶段，首先输入查询轨迹，利用网格索引与查询轨迹的空间信息计算出相应的轨迹网格签名，通过轨迹网格签名确定查询轨迹所在的空间网格子集，实现对轨迹数据集粗粒度的初步筛选。随后由网格索引确定的空间网格子集上具有对应的起止索引，与查询轨迹的起点和终点进行匹配，返回备选轨迹所在的分区，再通过利用分区中的特征点索引，实现特征轨迹点与查询轨迹进行距离计算，大于给定阈值的特征轨迹点则直接筛选掉，从而达到对轨迹数据更加细粒度筛选的目的。最后，通过网格索引-起止索引-特征点索引的多级索引结构进行粗粒度-细粒度两次筛选所得到的备选特征轨迹，返回备选特征轨迹对应的完整轨迹，并与查询轨迹进行轨迹相似性计算来验证结果，返回符合查询条件的轨迹数据作为轨迹相似性查询的最终结果。通过网格索引-起止索引-特征点索引的多级索引结构可以实现对查询轨迹进行粗粒度-细粒度两次备选轨迹集筛选的操作，可以有效地减少备选轨迹集中轨迹的数量，大大减少轨迹相似性计算带来的时间开销，从而达到提高轨迹相似性查询的效率。图1为本发明的索引筛选方法图。

为了达到上述目的，本发明所采用的技术方案如下：

一种基于多级索引结构的大规模轨迹数据相似性查询方法，步骤如下：

步骤1：对包含GPS信息的大规模轨迹数据集进行轨迹数据预处理，对于预处理操作后得到的轨迹数据集利用地理空间信息进行网格划分，划分成大小相同的空间网格子集，每个空间网格子集都对应存储一块空间，同时对每个空间网格子集加以编号，生成网格索引；

将每一条轨迹经过的空间网格子集标识为1，没有经过的空间网格子集标识为0，依次按照对空间网格子集的编号顺序来标记，则每条轨迹能够通过一串具有二进制信息的数字签名来记录轨迹所经过的空间网格子集；

步骤2：对于每个空间网格子集，使用特征轨迹生成器来计算出空间网格子集中存储的轨迹集中每条轨迹的特征轨迹，利用特征轨迹的起点和终点进行聚类分区，得到基于轨迹起点和终点的起止索引，在每一个空间网格子集都会建立一个起止索引，再使用特征轨迹的3种特征轨迹表示点进行聚类操作来建立特征点索引，建立起止索引-特征点索引的二级索引结构；这样基于网格索引-起止索引-特征点索引的多级索引结构建立完成；

步骤3：在轨迹相似性查询阶段中，输入查询轨迹，利用网格索引对查询轨迹的空间信息计算出相应的轨迹网格签名，通过轨迹网格签名确定查询轨迹所在的空间网格子集，实现对轨迹数据集进行粗粒度的初步筛选；

步骤4：对于网格索引确定的空间网格子集，利用空间网格子集对应的起止索引，与查询轨迹的起点和终点进行匹配，返回备选轨迹所在的分区，再通过对分区中的特征点索引的3种特征轨迹表示点与查询轨迹进行距离计算，大于给定阈值的特征轨迹表示点则直接筛选掉，从而达到对轨迹数据更加细粒度筛选的目的；

步骤5：通过网格索引-起止索引-特征点索引的多级索引结构进行粗粒度-细粒度两次筛选所得到的备选特征轨迹，返回备选特征轨迹对应的完整轨迹，并与查询轨迹进行轨迹相似性计算来验证结果，返回符合查询条件的轨迹数据作为轨迹相似性查询的最终结果。

进一步地，所述特征轨迹的获得方式具体为：

步骤(1)：对于空间网格子集中的每条轨迹，通过特征轨迹生成器取出每条轨迹的起点和终点，并赋予权值；

步骤(2)：对于空间网格子集中的每条轨迹，除去起点和终点后对剩余的轨迹点使用特征轨迹生成器计算各个轨迹点之间的距离，将每两个轨迹点间的距离作为权值赋予给轨迹点对中的排序靠后的轨迹点，并根据权值进行排序，取出权值最大的轨迹点作为特征轨迹表示点之一；

步骤(3)：对于空间网格子集中的轨迹数据，对除去起点和终点的每条轨迹中剩余的轨迹点使用特征轨迹生成器来计算各个轨迹点距离轨迹的起点和终点的距离，取每个轨迹点与轨迹的起点、每个轨迹点与轨迹的终点这两个距离中最大值作为权值赋予给每个轨迹点，并根据权值进行排序，取出权值最大的轨迹点作为特征轨迹表示点之一；

步骤(4)：对于空间网格子集中的轨迹数据，对除去起点和终点的每条轨迹中剩余的轨迹点使用特征轨迹生成器来计算每条轨迹中的拐点，将轨迹中的每个拐点的改变角度作为权值，并根据权值进行排序，取出所有权值最大的拐点作为特征轨迹表示点之一；

其中轨迹中轨迹点拐度的计算加权公式如下：

其中：

A、B、C为一条轨迹中连续的三个轨迹点；

B

A.x为轨迹点A的GPS横坐标；B.x为轨迹点B的GPS横坐标；C.x为轨迹点C的GPS横坐标；

A.y为轨迹点A的GPS纵坐标；B.y为轨迹点B的GPS纵坐标；C.y为轨迹点C的GPS纵坐标；

步骤(5)：特征轨迹生成器将空间网格子集中每条轨迹的起点、终点、步骤2-3得到的特征轨迹表示点组合在一起生成特征轨迹。

进一步地，所述的起止索引和特征点索引的建立方法具体为：

步骤A：对于空间网格子集中的每条轨迹，使用特征轨迹生成器来计算得出相应的特征轨迹，并取出特征轨迹的起点和终点；

步骤B：对空间网格子集中的每条轨迹中的起点和终点进行聚类分区的操作，使具有相同起点和终点的轨迹存储分布在同一个分区中，并对所有分区的起点和终点建立空间R树作为轨迹数据的起止索引；

步骤C：对于每个空间网格子集都具有对应的起止索引，通过特征轨迹生成器来取出每个分区中各个轨迹的3种特征轨迹表示点，对所有轨迹的3种特征轨迹表示点建立索引作为特征轨迹点索引，形成基于特征轨迹的起止-特征点二级索引结构。

基于多级索引结构的大规模轨迹数据相似性查询方法的具体方案为，先建立多级索引结构，后进行轨迹相似性查询。索引建立阶段中，首先对包含GPS信息的大规模轨迹数据集进行轨迹数据预处理，对于预处理操作后得到的轨迹数据集利用地理空间信息进行网格划分，使其划分成大小相同的较大的空间网格子集，每个空间网格子集都对应存储一块空间，同时对每个网格加以编号并生成网格索引，这样轨迹数据集就被网格索引划分成若干个空间网格子集。其次，对空间网格子集中每条轨迹的起点和终点建立起止索引，再根据每条轨迹的特征轨迹点建立特征点索引，从而将具有轨迹特征信息的轨迹点所组成的特征轨迹应用到多级索引上。最后，离线建立起网格索引-起止索引-特征点索引组成的多级索引结构。在轨迹相似性查询阶段，利用多级索引结构实现对备选轨迹集进行筛选。首先，输入查询轨迹后，空间网格索引会根据查询轨迹的空间信息生成轨迹网格签名，根据网格签名信息筛选出其所在的空间网格子集。随后，利用建立在此空间网格子集上的起止索引-特征点索引结合查询轨迹进行二次筛选，得到备选特征轨迹集。最后使用查询轨迹与返回的备选特征轨迹集的完整轨迹进行轨迹相似性计算验证，返回与查询轨迹相似的查询结果。

本发明同时考虑了轨迹数据集中轨迹数据密集与不密集的两种情况，对于轨迹数据比较密集时，空间网格索引和基于特征轨迹表示法的起止索引-特征点索引二级索引可以高效地对轨迹数据进行筛选，大大减少计算量，提高计算效率。而在轨迹数据比较稀疏时，需要考虑通过多次实验来调整网格索引中划分网格的大小，从而更好地利用空间网格索引的粗粒度数据筛选功能。另外，为了考虑全面，对于同时经过多个空间网格子集的轨迹，本发明视为此轨迹包含在每个空间网格子集中进行重复计算。特征轨迹表示法对于轨迹的特征信息提取方案进行了研究，如果两条轨迹是相似的，那么这两条轨迹的起点和终点必定距离很近，因此特征轨迹生成器对于每条轨迹的起点和终点都要赋予权值。特征轨迹生成器中包含多种轨迹点计算函数，分别对轨迹中的轨迹点进行轨迹点间距计算、距轨迹起点和终点距离计算以及轨迹点拐度计算，通过对计算结果的权值进行排序，得到轨迹点间距最大的点、距轨迹起点终点最远的点以及拐度最大的轨迹点，这些特殊的轨迹点包含着轨迹的特征信息，其所组成的特征轨迹能够更好地代表原始轨迹进行轨迹相似性计算。特征轨迹表示法的特征轨迹点个数也较大的影响相似性轨迹查询功能的效率，因为特征轨迹点的个数越多，通过起止索引-特征点索引二级索引机制中计算的特征轨迹点的个数也就越多，增加了计算开销；但是如果特征轨迹点的个数过少，会导致特征轨迹又不能很好的表示出轨迹的特征信息，从而削弱了索引的筛选功能，也同样会增加计算开销，降低轨迹相似性查询功能的效率。通过分析与实验结果，对于轨迹长度较长的轨迹数据集，适当的增加特征轨迹点的个数可以有效地提高轨迹相似性查询的效率。虽然特征轨迹点的个数也会直接影响起止索引和特征点索引存储空间的大小，但是由于基于特征轨迹的起止索引与特征轨迹点索引的存储空间都是比较小的，特征轨迹点个数带来的索引存储空间改变并不会很大。轨迹数据之间的相似度通常通过它们之间的距离来度量，两条轨迹之间的距离越小则越相似，经过多次实验发现，动态时间规整DTW的相似性度量函数可以较好地捕捉到轨迹之间的相似性，是使用最广泛的轨迹相似性度量函数，其能够更好地处理轨迹中的局部时间偏移、查询准确度高的特点，因此本方法最后返回的完整备选轨迹与查询轨迹进行相似性计算时所使用的相似性度量函数采用的就是动态时间规整的方法。虽然传统的相似性度量函数的计算开销比较大，但是通过本方法对备选轨迹的粗粒度-细粒度两次筛选，可以有效地减少备选轨迹的轨迹集大小，继而减少计算开销，提高轨迹数据的处理效率。

本方法区别于已有方法的特色在于：

(1)本发明对轨迹数据进行特征分析，通过计算轨迹中各个轨迹点的权值进行排序，并构建出特征轨迹来对轨迹数据进行表示，特征轨迹法可以有效地表示轨迹，提高轨迹数据处理系统的效率。传统的轨迹数据相似性计算方法的复杂度很高，需要花费大量的时间和空间，并且现有的轨迹相似性计算方法并不能很好地对大规模轨迹进行处理，其他查询操作同理也不能快速地完成。对于大规模轨迹数据集，本发明对数据集中的每条轨迹中的轨迹点进行分析计算，通过计算来找到轨迹中更具有代表意义的轨迹点信息，包括轨迹的起点、终点、轨迹点间距最大点、距起止点最远的轨迹点以及拐点等。通过对这些特殊的轨迹点赋予相应的权值，并通过对权值的排序，得出最终的特征轨迹。本发明得到的特征轨迹可以代表整条轨迹进行轨迹相似性计算，由于传统的轨迹数据的计算方法都是对轨迹中的全部轨迹点进行计算，而整条轨迹的轨迹点的数量一般都很大。而特征轨迹的轨迹点数量都很少，这样使用本发明的特征轨迹来取代整条轨迹进行计算，就会节省大量计算开销。

(2)本发明在特征轨迹表示法的基础上建立了起止索引-特征点索引二级索引机制，可以实现对轨迹数据的高效管理，提高数据的检索效率。由于轨迹数据规模大、具备时空信息，很难对轨迹数据进行管理，传统的轨迹数据分析系统并不能有效地对轨迹数据进行相似性计算等轨迹查询功能，部分分布式轨迹处理系统的索引机制也并不能很好的对处于计算节点上的轨迹数据进行管理。本发明可以在Spark计算平台上建立分布式轨迹数据处理系统，并且利用特征轨迹表示法的策略对整条轨迹进行处理，通过对空间网格中轨迹的起点和终点进行聚类分区得到起止索引，再对每个分区中轨迹的特征轨迹点建立索引形成特征点索引，这样通过二级索引的机制，可以高效地实现在分布式系统上对轨迹数据查询计算等操作。

(3)本发明首次将空间网格索引的思想与特征轨迹法相结合，构建网格索引-起止索引-特征点索引的多级索引结构，经过粗粒度-细粒度两次对轨迹数据集进行备选轨迹结果的筛选，减少备选轨迹数量，有效提高相似性查询的效率。空间网格索引技术一般都是应用于传统的空间对象筛选，而应用到轨迹数据计算的场景较少，本发明提出将基于空间网格索引的思想应用到轨迹网格签名上，通过空间网格索引将轨迹对象经过的空间网格进行标识，生成轨迹的网格签名。这样在轨迹相似性查询阶段，通过轨迹网格签名就可以确定查询轨迹所属的空间网格，随后使用空间网格上建立的起止-特征点二级索引进行筛选，得到备选结果轨迹。通过空间网格索引具备的空间筛选能力可以快速地对轨迹数据实现初步的粗粒度轨迹数据的筛选，减少轨迹数据量，再利用基于特征轨迹法的起止索引-特征点索引二级索引结构，实现对轨迹数据进行更加细粒度的管理与筛选。经过粗粒度-细粒度两次数据筛选，可以大大减少返回的候选轨迹集数量，从而避免由于候选轨迹数量过多而带来的高额计算开销，显著提高系统的轨迹相似性查询的效率。

与当前的轨迹数据处理系统相比，本发明的有益效果为：

(1)使用特征轨迹法来表示整条轨迹，生成的特征轨迹的轨迹点数量少并且具备轨迹的特征信息，可用来替代原始轨迹进行相似性轨迹计算，从而减少计算开销，提高轨迹数据查询的效率。

(2)基于特征轨迹法建立起止索引-轨迹点索引二级索引，可以更好地对分布式系统架构进行数据管理，提高系统对轨迹数据的分析和管理能力。

(3)与基于空间网格索引思想相结合的备选轨迹数据集的筛选策略，通过建立空间网格索引来对轨迹数据实现粗粒度的轨迹数据集筛选，再通过空间网格上的起止索引-特征点索引机制对初筛的轨迹数据集进行细粒度的管理，进一步提高了轨迹数据管理的精确度，这样基于网格索引-起止索引-特征点索引的多级索引结构就可以有效提高基于轨迹点的轨迹计算相关的查询操作的效率。

附图说明

图1为本发明的索引筛选方法图。

具体实施方法

下面对本发明的实施方法进行详细的说明。

一种基于多级索引结构的大规模轨迹数据相似性查询方法，可以具体实施为搭建在基于Spark平台上的轨迹数据处理系统。为更好地完成实施，本系统部署在具有三个节点的微型分布式集群上，使用的实验数据集是北京出租车GPS数据集。利用搭建后的分布式处理系统，完成大规模轨迹数据相似性查询方法。在轨迹相似性查询过程中分为索引建立阶段和轨迹相似性查询阶段。

索引建立阶段为离线阶段，系统根据输入的轨迹数据集离线建立网格索引-起止索引-特征点索引结构的多级索引。具体的索引建立方法如图1，主要分为两部分模块，分别为基于空间网格索引思想的网格索引模块和基于特征轨迹表示法的起止索引-特征点索引二级索引机制模块。空间网格索引模块包括原始轨迹预处理和轨迹网格签名生成方法，二级索引机制模块中包括基于多种轨迹特征点的特征轨迹生成器以及起止索引-特征点索引建立方法。

系统建立索引的具体实施步骤如下：

步骤1：系统中输入包含GPS信息的大规模轨迹数据集，首先对轨迹数据集进行轨迹数据预处理，预处理操作主要是除去轨迹数据集中混入的噪音点以及轨迹长度过短的轨迹。对于预处理操作后得到的轨迹数据集，结合轨迹的地理空间信息进行网格划分。将轨迹数据集划分成大小相同的较大的空间网格子集，每个空间网格子集都对应存储一块空间，同时对每个网格加以编号生成网格索引。

步骤2：系统根据步骤1中返回的网格索引得到所有空间网格子集。利用特征轨迹生成器对空间网格子集中的轨迹生成特征轨迹，生成特征轨迹的具体方法为：

步骤2.1：系统对于空间网格子集中的每条轨迹，会通过特征轨迹生成器取出每条轨迹的起点和终点，并赋予权值；

步骤2.2：对于空间网格子集中的每条轨迹，除去起点和终点后对剩余的轨迹点使用特征轨迹生成器计算各个轨迹点之间的距离，将每两个轨迹点间的距离作为权值赋予给轨迹点对中的排序靠后的轨迹点，并根据权值进行排序，取出权值最大的轨迹点作为特征轨迹表示点之一；

步骤2.3：对于空间网格子集中的轨迹数据，对除去起点和终点的每条轨迹中剩余的轨迹点使用特征轨迹生成器来计算各个轨迹点距离轨迹的起点和终点的距离，取每个轨迹点与轨迹的起点、每个轨迹点与轨迹的终点这两个距离中最大值作为权值赋予给每个轨迹点，并根据权值进行排序，取出权值最大的轨迹点作为特征轨迹表示点之一；

步骤2.4：对于空间网格子集中的轨迹数据，对除去起点和终点的每条轨迹中剩余的轨迹点使用特征轨迹生成器来计算每条轨迹中的拐点，将轨迹中的每个拐点的改变角度作为权值，并根据权值进行排序，取出所有权值最大的拐点作为特征轨迹表示点之一；

其中轨迹中轨迹点拐度的计算加权公式如下：

其中：

A、B、C为一条轨迹中连续的三个轨迹点；

B

A.x为轨迹点A的GPS横坐标；B.x为轨迹点B的GPS横坐标；C.x为轨迹点C的GPS横坐标；

A.y为轨迹点A的GPS纵坐标；B.y为轨迹点B的GPS纵坐标；C.y为轨迹点C的GPS纵坐标；

步骤2.5：特征轨迹生成器将空间网格子集中每条轨迹的起点、终点、步骤2.2-2.4得到的特征轨迹表示点组合在一起生成特征轨迹。

步骤3：系统利用索引构建程序使用特征轨迹来建立起止索引-特征点索引二级索引结构。对于空间网格子集中的每条轨迹中的起点和终点进行聚类分区的操作，使具有相同起点和终点的轨迹存储在同一个分区中，并对所有分区的起点和终点建立空间R树作为起止索引，同时将空间R树的信息存储在内存中。

在轨迹相似性阶段，系统会根据输入的查询轨迹，返回符合条件的相似性查询结果，具体实施步骤如下：

步骤1：向系统输入查询轨迹，查询轨迹的格式为一系列具有GPS点的轨迹数据。通过给定查询轨迹，系统使用离线建立的多级索引结构对轨迹数据集进行筛选。

步骤2：系统使用空间网格索引模块生成查询轨迹对应的轨迹网格签名，通过网格索引和查询轨迹的轨迹网格签名，确定查询轨迹属于的空间网格子集作为粗粒度筛选的结果，并将空间网格子集输出到二级索引机制模块中。

步骤3：系统使用二级索引机制模块对空间网格子集中的轨迹进行筛选，利用起止索引找到与查询轨迹的起点和终点相匹配的备选轨迹，系统会返回备选轨迹所在的分区，再通过分区中的特征点索引，实现索引下的特征轨迹点与查询轨迹间的距离计算，系统会直接排除距离计算结果大于给定阈值的特征轨迹点，达到对轨迹数据更加细粒度筛选的目的。

步骤4：对于步骤3中得到的备选特征轨迹集，系统会返回完整轨迹，与查询轨迹进行轨迹相似性计算来验证结果，返回符合查询条件的轨迹数据。同时系统也会返回整个相似性查询过程的时间，作为性能比较的依据。

通过本发明的实施方案，对百万条轨迹数据进行的轨迹相似性查询操作，系统花费的查询时间为10～20ms，相比于其他现有的相似性查询方法，所用时间更短、效率更高。实验结果表明，通过本方法建立的网格索引-起止索引-特征点索引的多级索引结构实现对轨迹数据粗粒度-细粒度筛选，可以有效地减少备选轨迹集中轨迹的数量，大大减少轨迹相似性计算带来的时间开销，从而达到提高轨迹相似性查询的效率。