CN110543539B - 一种分布式的路网环境下移动对象轨迹相似性查询方法 - Google Patents

Abstract

本发明公开了一种分布式的路网环境下移动对象轨迹相似性查询方法，该方法针对海量移动对象轨迹的相似性查询需求，提出RMT‑HBase索引框架，解决了分布式集群数据的热点分布问题；通过计算轨迹之间的整体距离，提高了轨迹长度不一致情况下轨迹相似性度量的精确度；设计了面向对象‑时间段、空间‑时间段和时间段的三种兴趣点轨迹查询方法，提高了相似轨迹查询效率。

Description

一种分布式的路网环境下移动对象轨迹相似性查询方法

技术领域

本发明属于分布式轨迹相似性查询领域，具体涉及一种分布式的路网环境下移动对象轨迹相似性查询方法。

背景技术：

目前，有很多针对于路网环境下的轨迹相似性研究方法，但这些方法的侧重点存在差异。例如，分别针对于空间相似性和时间相似性的方法POI(Point of Interest)和TOI(Time of Interest)，通过轨迹是否包含预先设定的所有时间兴趣点来判断是否具有空间或时间相似性，然而该方法在度量空间相似性上，只存考虑相似和不相似，无法表达轨迹的相似性程度。其次，该方法只考虑了轨迹的集合特征，没有考虑序列性特征。除此之外，在进行相似性度量时，只考虑轨迹重叠部分，未考虑轨迹非重叠部分对相似性结果的影响。传统的LCS方法，利用轨迹之间的重叠程度作为相似性评判标准。该方法在计算过程中，可以忽略移动对象的出发时间和速度；适用于采样率不同和长度不同的轨迹比较；解决了噪声对计算结果的干扰。然而该方法在比较长度不一致轨迹间相似性度量结果偏向于较短轨迹，造成轨迹相似性度量的精度较低。同时，针对海量的移动对象轨迹相似性查询需求，缺乏高效的路网时空索引框架。

发明内容

本发明的目的在于提供一种分布式的路网环境下移动对象轨迹相似性查询方法，以解决现有技术中轨迹长度不一致情况下轨迹相似性度量的精确度不高的缺陷。

一种分布式的路网环境下移动对象轨迹相似性查询方法，所述方法包括如下步骤：

将移动对象的查询条件输入构建好的查询模型中；

找出查询模型中符合查询条件的候选记录；

根据候选记录中的轨迹信息得到轨迹数据；

对轨迹数据进行运算得到轨迹间的距离值；

通过轨迹简距离值找出相似的轨迹。

进一步的，所述查询模型的构建方法包括如下步骤：

构建索引框架；

将移动对象的轨迹数据分配到索引框架中存储，并与存储位置进行映射；

对索引进行分级；

将各轨迹的属性存储到重新设计的框架存储空间中。

进一步的，所述候选记录包括面向对象-时间段为查询条件的轨迹查询方法，所述方法步骤如下：

根据输入的时间区间以及框架中的映射关系，将查询请求发送到包含该时间区间的所有存储区块；

通过移动对象索引，判断存储区块中是否包含移动对象的记录；

若存在，确定这些对象的候选记录位置；

若不存在，则跳过该存储区块，进入下一个区块查询。

进一步的，所述候选记录包括面向空间-时间段为查询条件的轨迹查询方法，所述方法步骤如下：

根据输入的空间区域条件，查询框架中包含的所有路段，并返回近似路段集合；

根据近似路段集合以及输入的时间条件，利用框架中的映射关系，将请求发送至路段集合中所有存储区块；

通过移动对象索引，获取存储区块中包含移动对象的记录；

查询结束后，确定移动对象的候选记录位置。

进一步的，所述轨迹数据的计算方法包括如下步骤：

根据输入的查询条件，将查询请求发送到查询区间对应的数据存储的存储区块中；

在存储区块中确定对象的候选记录位置；

对候选记录按照时间顺序排列形成单链表，根据时间区间[t_s，t_e]，筛选出满足该区间的交集；

将每个对象和其对应的移动对象轨迹存储在trajmap中；

利用收集函数对每个对象的兴趣点集合进行排序整合，生成符合查询条件的兴趣点编号序列表示的轨迹数据集。

进一步的，所述轨迹间的距离值的计算方法包括如下步骤：

1)分别获取两条轨迹POIA和POIB中除去公共子序列的序列子集POIA′和POIB′；

2)设定两条兴趣点表示的轨迹重叠部分的距离为0；

3)通过下式计算非重叠部分距离：

w1*f_distance+w2*dmin；

其中w1表示POIB′中兴趣点个数与POIA中兴趣点个数的比值，f_distance表示POIA′和POIB′之间的Fréchet距离；w2表示POIA′与POIB′中兴趣点个数之差与POIA中兴趣点个数的比值；dmin表示路网兴趣点间的距离矩阵中的最小值，用于表示POIA中除去相同子序列后所剩兴趣点之间的网络距离。

进一步的，所述轨迹间距离值找出相似的轨迹的方法包括如下步骤：

任意选定一条轨迹，计算该轨迹与其余轨迹之间的距离值；

将轨迹间距离值大小按照升序排列；

距离值最小的轨迹即与该轨迹相似的轨迹。

进一步的，所述索引分级包括第一级的空间段索引和第二级的时间段索引。

本发明的优点在于：该方法通过计算轨迹之间的整体距离，提高了轨迹长度不一致情况下轨迹相似性度量的精确度；设计了面向对象-时间段、空间-时间段和时间段的三种兴趣点轨迹查询方法，提高了相似轨迹查询效率。

附图说明

图1为本发明方法的流程示意图。

图2为本发明模型框架的示意图。

具体实施方式

为使本发明实现的技术手段、创作特征、达成目的与功效易于明白了解，下面结合具体实施方式，进一步阐述本发明。

如图1至图2所示，一种分布式的路网环境下移动对象轨迹相似性查询方法，所述方法包括如下步骤：

步骤一：建立查询模型：

构建RMT-HBase索引框架；

框架以路段为基本单位，将移动对象的历史轨迹数据按时段划分并分配到HBase中不同的HRegionServer和Region中进行存储；

在HBase的META表中映射关系的逻辑结构，将其分为两个部分：空间段(SS)作为第一级索引，时间段(TS)作为第二级索引；

针对轨迹数据的特点重新设计了RowKey，将各轨迹段的对象标准、收录时序和路段标识存储在RowKey中，即RowKey＝oid+T+rid，分别包含移动对象标识oid，数据录入时间T以及路段标识rid三个属性；

步骤二：找出符合条件的候选记录：

1.1)包括面向对象-时间段的兴趣点轨迹查询方法，具体步骤如下：

根据输入的时间区间条件，利用META表中存储的映射关系，将查询请求发送到所有路段在该时间区间对应的数据所存储的Region中；

1.2)确定候选记录位置：

在Region中进行查询时，通过o-index移动对象索引，判断该Region中是否包含移动对象o的记录；

若存在，则确定该对象的候选记录位置，若不存在，则跳过该Region；

2.1)面向空间-时间段的兴趣点轨迹查询方法，具体步骤如下：

根据输入的空间区域条件，通过RM-HBase中的RN-tree查询该区域内包含的路段，最终返回一个存储所有近似路段的集合RoadSet；

根据RoadSet路段集合以及输入的时间条件，利用META表中存储的映射关系，将查询请求发送到RoadSet集合中所有路段在查询时间区间对应的数据所存储Region中；

2.2)确定候选记录位置：

利用o-index移动对象索引，获取该Region内包含候选移动对象记录，在Region中的第一次查询结束后，确定这些对象的候选记录位置；

步骤三：根据轨迹信息得到轨迹数据：

1)根据输入的查询条件，将查询请求发送到查询区间对应的数据存储的Region中；

2)在Region中通过RM-HBase中的o-index移动对象索引，确定对象的候选记录位置；

3)通过步骤2)中选出的候选记录对应o-index中按照时间顺序排列的单链表，根据时间区间[t_s，t_e]，筛选出满足该区间的交集，并且将移动对象记录加入keylist中，将每个对象和其对应的移动对象轨迹存储在trajmap中；最终再利用MapReduce的收集函数Reduce对每个对象的兴趣点集合进行排序整合，生成符合查询条件的兴趣点编号序列表示的轨迹数据集；

步骤四：计算轨迹间的距离值：

1)分别获取两条轨迹POIA和POIB中除去公共子序列的序列子集POIA′和POIB′；

2)设定两条兴趣点表示的轨迹重叠部分的距离为0；

3)计算非重叠部分距离：w1*f_distance+w2*dmin；

w1表示POIB′中兴趣点个数与POIA中兴趣点个数的比值，f_distance表示POIA′和POIB′之间的Fréchet距离；w2表示POIA′与POIB′中兴趣点个数之差与POIA中兴趣点个数的比值。d_min为路网兴趣点间的距离矩阵中的最小值，用于表示POIA中除去相同子序列后所剩兴趣点之间的网络距离；

4)计算两条轨迹间的距离值，即轨迹之间重叠部分距离与非重叠部分距离之和：value＝w1*f_distance+w2*dmin；

步骤五：通过轨迹间距离值找出相似的轨迹。

任意选定一条轨迹，计算该轨迹与其余轨迹之间的距离值；

将轨迹间距离值大小按照升序排列；

距离值最小的轨迹即与该轨迹相似的轨迹。

由技术常识可知，本发明可以通过其它的不脱离其精神实质或必要特征的实施方案来实现。因此，上述公开的实施方案，就各方面而言，都只是举例说明，并不是仅有的。所有在本发明范围内或在等同于本发明的范围内的改变均被本发明包含。

Claims (6)

1.一种分布式的路网环境下移动对象轨迹相似性查询方法，其特征在于，所述方法包括如下步骤:

将移动对象的查询条件输入构建好的查询模型中；

找出查询模型中符合查询条件的候选记录；

根据候选记录中的轨迹信息得到轨迹数据；

对轨迹数据进行运算得到轨迹间的距离值；

通过轨迹间的距离值找出相似的轨迹；

其中，所述查询模型的构建方法包括如下步骤：

构建索引框架；

将移动对象的轨迹数据分配到索引框架中存储，并与存储位置进行映射；

对索引进行分级；

将各轨迹的属性存储到重新设计的框架存储空间中；

所述轨迹间的距离值的计算方法包括如下步骤：

1）分别获取两条轨迹POIA和POIB中除去公共子序列的序列子集

和

；

2）设定两条兴趣点表示的轨迹重叠部分的距离为0；

3）通过下式计算非重叠部分距离：

w1*f_distance+w2*dmin；

其中w1表示

中兴趣点个数与POIA中兴趣点个数的比值，f_distance表示

和

之间的

距离；w2表示

与

中兴趣点个数之差与POIA中兴趣点个数的比值；dmin表示路网兴趣点间的距离矩阵中的最小值，用于表示POIA中除去相同子序列后所剩兴趣点之间的网络距离；

4）两条轨迹间的距离值为轨迹之间重叠部分距离与非重叠部分距离之和，表示为：value =0+（w1*f_distance+w2*dmin）。

2.根据权利要求1所述的一种分布式的路网环境下移动对象轨迹相似性查询方法，其特征在于：所述候选记录通过以面向对象-时间段为查询条件的轨迹查询方法获得，所述方法步骤如下：

根据输入的时间区间以及框架中的映射关系，将查询请求发送到包含该时间区间的所有存储区块；

通过移动对象索引，判断存储区块中是否包含移动对象的记录；

若存在，确定这些对象的候选记录位置；

若不存在，则跳过该存储区块，进入下一个区块查询。

3.根据权利要求1所述的一种分布式的路网环境下移动对象轨迹相似性查询方法，其特征在于：所述候选记录通过以面向空间-时间段为查询条件的轨迹查询方法获得，所述方法步骤如下：

根据输入的空间区域条件，查询框架中包含的所有路段，并返回近似路段集合；

根据近似路段集合以及输入的时间条件，利用框架中的映射关系，将请求发送至路段集合中所有存储区块；

通过移动对象索引，获取存储区块中包含移动对象的记录；

查询结束后，确定移动对象的候选记录位置。

4.根据权利要求1所述的一种分布式的路网环境下移动对象轨迹相似性查询方法，其特征在于：所述轨迹数据的运算方法包括如下步骤：

根据输入的查询条件，将查询请求发送到查询区间对应的数据存储的存储区块中；

在存储区块中确定对象的候选记录位置；

对候选记录按照时间顺序排列形成单链表，根据时间区间

，筛选出满足该区间的交集；

将每个对象和其对应的移动对象轨迹存储在trajmap中；

利用收集函数对每个对象的兴趣点集合进行排序整合，生成符合查询条件的兴趣点编号序列表示的轨迹数据集。

5.根据权利要求1所述的一种分布式的路网环境下移动对象轨迹相似性查询方法，其特征在于：所述通过轨迹间的距离值找出相似的轨迹的方法包括如下步骤：

任意选定一条轨迹，计算该轨迹与其余轨迹之间的距离值；

将轨迹间距离值大小按照升序排列；

距离值最小的轨迹即与该轨迹相似的轨迹。

6.根据权利要求1所述的一种分布式的路网环境下移动对象轨迹相似性查询方法，其特征在于：索引分级包括第一级的空间段索引和第二级的时间段索引。

Images