基于倒排序索引及前缀树的轨迹索引和查询方法及系统.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN112579921A(43)申请公布日2021.03.30(21)申请号202011489554.4G06F16/2455(2019.01)(22)申请日2020.12.16G06K9/62(2006.01)(71)申请人长安大学地址710064陕西省西安市雁塔区二环南路中段126号(72)发明人康军何昊健段宗涛马浩森李宜修黄山(74)专利代理机构西安恒泰知识产权代理事务所61216代理人王芳(51)Int.Cl.G06F16/9537(2019.01)G06F16/22(2019.01)G06F16/23(2019.01)G06F16/215(2019.01)权利要求书3页说明书10页附图3页(54)发明名称基于倒排序索引及前缀树的轨迹索引和查询方法及系统(57)摘要本发明属于GPS轨迹数据索引技术领域，公开了一种基于倒排序索引及前缀树的轨迹索引和查询方法及系统。通过将原始轨迹数据路网匹配后划分为轨迹段，针对轨迹段倒排序索引并转换为前缀树来进行轨迹索引。本发明可以根据给定的路段和时间范围，查询在该时间范围内经过该路段的所有轨迹段。而传统的轨迹段索引方法面对大量轨迹数据时查询效率不高，或者没有保留车辆轨迹的语义完整性，本发明可以提高轨迹检索的效率、相比传统索引结构节省存储空间，保留轨迹的语义完整性。本发明适用于开发轨迹数据挖掘方法，推断居民的出行特征和模式，发现交通流的时空特征，预测出行时间等情况，在GPS轨迹数据处理技术领域有重要的应用价值。CN112579921ACN112579921A权利要求书1/3页1.一种基于倒排序索引及前缀树的轨迹索引建立方法，其特征在于，包括如下步骤：步骤1：获取车辆所在城市的路网数据和车辆的原始轨迹数据，所述路网数据包括多个路段和每个路段的路段id，所述原始轨迹数据包括多条原始轨迹和每条原始轨迹的原始轨迹id，并对原始轨迹数据进行预处理；步骤2：将路网数据匹配到步骤1进行预处理后得到的原始轨迹数据上，获得原子轨迹数据，所述每条原子轨迹包括路段id、原始轨迹id和属性特征；步骤3：将原始轨迹id相同的原子轨迹作为一组，获得多组原子轨迹；对每组原子轨迹进行判断，若该组中连续三个及以上的原子轨迹的属性特征相同，则将该组原子轨迹作为一个轨迹段，获得轨迹段数据，所述每个轨迹段包含一个原始轨迹id和一个路段id序列，每个轨迹段的路段id序列为该轨迹段所包含的所有原子轨迹对应的路段id的集合；步骤4：根据步骤1得到的每个路段生成一棵前缀树；获取步骤3得到的所有轨迹段的原始轨迹id、所有路段id序列中的路段和所有路段id序列中每个路段在其所在路段id序列中的序号，将每个路段所对应的原始轨迹id和该路段在其所在路段id序列中的序号插入该路段的前缀树中得到有序前缀树，获得每个路段对应的有序前缀树，将全部有序前缀树作为轨迹索引库。2.如权利要求1所述的基于倒排序索引及前缀树的轨迹索引建立方法，其特征在于，步骤2中采用基于HMM模型的地图匹配方法将路网数据匹配到步骤1进行预处理后得到的原始轨迹数据上。3.如权利要求1所述的基于倒排序索引及前缀树的轨迹索引建立方法，其特征在于，步骤4中将每个路段所对应的原始轨迹id和该路段在其所在路段id序列中的序号插入该路段的前缀树中得到有序前缀树，包含如下步骤：步骤a1：取前缀树的根节点为当前节点；步骤a2：获取每个路段所对应的原始轨迹id的年月日、时、秒、车牌号和该路段在其所在路段id序列中的序号分别作为字符P1,P2,P3,P4,P5；步骤a3：获取新节点Pi并令Pi＝P1，将Pi与当前节点的所有子节点进行比较，如果有与Pi相同的子节点则将该子节点设为当前节点并执行步骤a4；如果没有与Pi相同的子节点则将Pi与当前节点的所有子节点一起排序，按序将Pi插入为新子节点，并将Pi设为当前节点并执行步骤a4；步骤a4：如果i＝5，则生成完成，获得有序前缀树；否则Pi＝Pi+1，返回步骤a3。4.如权利要求1所述的基于倒排序索引及前缀树的轨迹索引建立方法，其特征在于，轨迹索引库更新时采用如下方法：步骤b1：获取新产生的轨迹数据，对新产生的轨迹数据执行步骤1至步骤3，最后得到更新轨迹段数据；步骤b2：对更新轨迹段数据经过的路段生成更新前缀树；获取更新轨迹段数据中包含的路段id，从数据库中查询相同路段对应的有序前缀树，将该有序前缀树与生成的更新前缀树做并集运算，得到更新后的有序前缀树，随后将更新后的有序前缀树覆盖掉数据库中与其路段id相同的有序前缀树，索引更新完成。5.一种轨迹查询方法，其特征在于，包括如下步骤：2CN112579921A权利要求书2/3页步骤Ⅰ：获取目标路段集合以及查询时间范围，所述目标路段集合包