(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202211269077.X (22)申请日 2022.10.17 (65)同一申请的已公布的文献号 申请公布号 CN 115344795 A (43)申请公布日 2022.11.15 (73)专利权人 云南师范大学 地址 650500 云南省昆明市呈贡区 聚贤街 768号 (72)发明人 熊文　黄万兵　王丽明　 (74)专利代理 机构 昆明明润知识产权代理事务 所(普通合伙) 53215 专利代理师 王鹏飞 (51)Int.Cl. G06F 16/9537(2019.01) G06F 16/22(2019.01) G06F 16/245(2019.01) G06F 16/25(2019.01) G06F 16/29(2019.01)(56)对比文件 CN 114637929 A,2022.06.17 CN 111078634 A,2020.04.28 CN 107766407 A,2018.0 3.06 CN 107798346 A,2018.0 3.13 CN 107766406 A,2018.0 3.06 CN 113886390 A,202 2.01.04 CN 112800152 A,2021.0 5.14 US 2017212894 A1,2017.07.27 CN 110796040 A,2020.02.14 郭旦怀等.面向实时交通信息提取的车辆 轨 迹数据挖掘. 《武汉理工大 学学报(交通科 学与工 程版)》 .2010,(第01期), 王祖超等.轨 迹数据可视分析研究. 《计算机 辅助设计与图形 学学报》 .2015,(第01期), 赵卓峰等.基 于海量车牌识别数据的相似轨 迹查询方法. 《清华大 学学报(自然科 学版)》 .2017,(第02期), 高强等.轨 迹大数据:数据处 理关键技 术研 究综述. 《软件学报》 .2016,(第04期), 审查员 罗伟 (54)发明名称 一种基于多路归并的地铁乘客轨迹相似性 搜索方法 (57)摘要 本发明涉及一种基于多路归并的地铁乘客 轨迹相似性搜索方法， 属于轨迹相似性搜索领域 技术领域。 首先获取乘客进出站时实时产生的所 有票卡记录， 再以多级索引的方式对全部票卡记 录进行存储， 所述全部票卡记录包括历史票卡和 实时票卡记录， 接着初始化查询参数， 调用查询 接口， 对全部票卡记录进行查询， 然后使用多轮 归并， 每轮内以多线程分段并行的方式对票卡集 合进行轨迹相似性搜索。 将输入的一组时空约束 SPCL按一组起止点进行分段， 以分段方式去搜索 相似或相同的轨迹， 每轮搜索的结果是一组候选 轨迹， 最后一轮得到与SPCL高度相似的轨迹集合。 本发明效率高、 成本低、 并且支持实时的查 询。 权利要求书4页 说明书13页 附图1页 CN 115344795 B 2022.12.09 CN 115344795 B 1.一种基于多路归并的地铁乘客轨 迹相似性搜索方法， 其特 征在于： Step1： 获取乘客进出站时实时产生的所有票 卡记录； 所述实时产生的票卡记录是指乘客最新的刷卡记录， 所述票卡记录包含的字段包括但 不限于卡 号、 时间戳、 地铁站、 进出 标识， 金额信息； Step2： 以多级索引的方式对全部票卡记录进行存储， 所述全部票卡记录包括历史票卡 和实时票 卡记录； Step3： 初始化 查询参数， 调用查询接口， 对 全部票卡记录进行查询； Step4： 使用多轮归并， 多 线程分段并行的方式对票 卡集合进行轨 迹相似性搜索； 将SPCL按两个轨迹点为一组进行分段， 以分段方式去搜索与该分段相似或相同的轨 迹， 分段搜索的结果是一组候选 轨迹； 分段搜索的过程通过一组多线程并行执行， 每一组线程结束后， 对候选轨迹进行合并 和过滤， 使用一组过 滤规则对票 卡记录集 合进行过滤， 加速搜索查询过程； 分段搜索的过程经过多轮执行以后， 形成最终的一组乘客的轨迹， 该组乘客的轨迹与 SPCL具有高度相似性； 所述Step4具体为： Step4.1： 输入时空约束列表 SPCL=S1(t1) S2(t2) S3(t3) …Sn‑1(tn‑1) Sn(tn)，n为时空 约束的个数； Step4.2： 根据 n计算多轮归并的次数， 若 n满足2k‑1<n≤2k， 则归并次数为 k； Step4.3： 初始化变量 loop=1， 初始化时空约束 spList=SPCL， 初始化任务列表 TaskList ； 变量loop用于控制循环的结束， spList用于保存归并的中间过程， TaskList 用于保存 待计算的任务； Step4.4： 判断 loop与k的关系， 如果 loop大于k， 跳出循环， 转StepE； 否则， 转Step4.5； Step4.5： 遍历 spList， 步长为2， 将连续两个时空约束形成一个元组 (So(to),Sd(td))作 为任务描述符， 将任务描述符加入 TaskList中； 若spList中元素个数为奇数， 以最后一个元素为基础构建形如 (null,Sn(tn))的元组， 加入到TaskList中； Step4.6： 计算 TaskList元素的个数， 假设为m， 在线程池中选取m个空 闲线程； Step4.7： 遍历 TaskList ， 为每个任务描述符指定一个线程， 并启动线程执行轨迹集合 的交集运算； 计算结果保存在形如式 （4） 的键值映射结构中， 具体为： SubTRSet=(stati on,(SubTR1, SubTR2,…, SubTRn))           （4） 所述公式 （4） 描述的是一个键值映射结构， 是每轮归 并以后的中间结果， 是候选卡号轨 迹集合； 所述公式 （4） 中的 key为station， 即一个地铁站名， 具体取值对应每个任务描述元组的 第二个元 素Sd(td)的地铁站名； Step4.8： 通过珊栏的方式等待Step4.7中的线程全部结束； Step4.9： 根据调用接口中变量 filter的值， 判断是否调用过滤函数， 若调用， 则使用过 滤策略对中间结果进行 过滤；权　利　要　求　书 1/4 页 2 CN 115344795 B 2Step4.10： 清空 spList， 遍历TaskList ， 将每个元组的 Sd(td)加入到spList中， 清空 TaskList； Step4.11：loop=loop+1， 变量loop的值增加1， 转Step4； StepE： 结束。 2.根据权利要求1所述的基于多路归 并的地铁乘客轨迹相似性搜索方法， 其特征在于： 所述多级索引的方式指的是以地铁站、 时间戳、 卡号三个字段的不同取值范围对全部票卡 记录集合进 行划分， 使用地铁站、 时间戳两个字段对票卡集合建立多级索引， 该索引可以加 速查找满足在一定时间和空间范围内的票 卡记录。 3.根据权利要求2所述的基于多路归 并的地铁乘客轨迹相似性搜索方法， 其特征在于， 所述Step2具体为： 以地铁站名称， 时间区间对票 卡记录集 合进行不同维度的划分， 建立多 级索引； 首先将票卡记录按不同地铁站进行分区， 再按时间段进一步将票卡分组； 分组内部的 票卡记录按时间戳由小到大进行排序， 若票 卡记录时间戳相同， 按卡 号由小到大排序； 所述多级索引分为 一级索引和二级索引； 所述一级索引具体为： 保存一组形如<地铁站编号， 地铁站名称， 票卡记录集合>的三元 组， 将三元组按地铁站编号由小达 到进行排序， 具体为： StationMap={(ID1,station1,Set1),( ID2,station2,Set2),…, ( IDN,stationN, SetN)} 式中，IDi表示地铁站的编号， stationi表示地铁站的名称， Seti表示该地铁站产生的所 有票卡记录集 合； 所述二级索引具体为： 保存一组形如<时间段编号， 时间段， 票卡记录数， {<时间戳,卡 号,票卡其他字段>， <时间戳,卡号,票卡其他字段>, …,<时间戳,卡号,票卡其他字段>}>的 嵌套式四元组， 具体为： timeLMap={(I1,tSeg1,n1,sSet1), (I2,tSeg2,n2,sSet2),…, (IM,tSegM,nM,sSetM)} 式中，Ii表示的是时间段编号， tSegi表示时间段名称， n表示该时间段范围内产生的票 卡记录数量， sSeti表示该时间段产生的所有票 卡记录集 合， 是Seti的子集； 所述四元组的外层按时间段编 号由小到大存储， 四元组 的内层分别按时间戳和卡号两 个字段进行排序， 先按时间戳大小排序， 相同时间戳的票 卡记录按卡 号大小进行排序。 4.根据权利要求1所述的基于多路归 并的地铁乘客轨迹相似性搜索方法， 其特征在于， 所述查询接口具体为： resList=Searc h(SPCL,distance,fi lter,N)             （1） 式 （1） 中， SPCL是多个时空约束， 时空约束指的是地铁站名和时间戳的组合， distance 是一个阈值， 描述票卡轨迹与时空约束的距离， filter是一个布尔型变量， 控制在搜索过程 中是否开启过 滤功能，N控制返回结果的个数。 5.根据权利要求4所述的基于多路归 并的地铁乘客轨迹相似性搜索方法， 其特征在于， Step3中所