• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

基于路网层次收缩的快速分布式地图匹配算法

李瑞远, 朱浩文, 王如斌, 陈超, 郑宇

李瑞远, 朱浩文, 王如斌, 陈超, 郑宇. 基于路网层次收缩的快速分布式地图匹配算法[J]. 计算机研究与发展, 2022, 59(2): 342-361. DOI: 10.7544/issn1000-1239.20210904
引用本文: 李瑞远, 朱浩文, 王如斌, 陈超, 郑宇. 基于路网层次收缩的快速分布式地图匹配算法[J]. 计算机研究与发展, 2022, 59(2): 342-361. DOI: 10.7544/issn1000-1239.20210904
shu
Li Ruiyuan, Zhu Haowen, Wang Rubin, Chen Chao, Zheng Yu. Fast and Distributed Map-Matching Based on Contraction Hierarchies[J]. Journal of Computer Research and Development, 2022, 59(2): 342-361. DOI: 10.7544/issn1000-1239.20210904
Citation: Li Ruiyuan, Zhu Haowen, Wang Rubin, Chen Chao, Zheng Yu. Fast and Distributed Map-Matching Based on Contraction Hierarchies[J]. Journal of Computer Research and Development, 2022, 59(2): 342-361. DOI: 10.7544/issn1000-1239.20210904
shu
李瑞远, 朱浩文, 王如斌, 陈超, 郑宇. 基于路网层次收缩的快速分布式地图匹配算法[J]. 计算机研究与发展, 2022, 59(2): 342-361. CSTR: 32373.14.issn1000-1239.20210904
引用本文: 李瑞远, 朱浩文, 王如斌, 陈超, 郑宇. 基于路网层次收缩的快速分布式地图匹配算法[J]. 计算机研究与发展, 2022, 59(2): 342-361. CSTR: 32373.14.issn1000-1239.20210904
shu
Li Ruiyuan, Zhu Haowen, Wang Rubin, Chen Chao, Zheng Yu. Fast and Distributed Map-Matching Based on Contraction Hierarchies[J]. Journal of Computer Research and Development, 2022, 59(2): 342-361. CSTR: 32373.14.issn1000-1239.20210904
Citation: Li Ruiyuan, Zhu Haowen, Wang Rubin, Chen Chao, Zheng Yu. Fast and Distributed Map-Matching Based on Contraction Hierarchies[J]. Journal of Computer Research and Development, 2022, 59(2): 342-361. CSTR: 32373.14.issn1000-1239.20210904
shu

基于路网层次收缩的快速分布式地图匹配算法

  • 1(重庆大学计算机学院 重庆 400044)

  • 2(京东城市(北京)数字科技有限公司 北京 100176)

  • 3(北京京东智能城市大数据研究院 北京 100176) (ruiyuan.li@cqu.edu.cn)

基金项目: 国家重点研发计划项目(2019YFB2101801)；国家自然科学基金项目(61976168,61872050,62172066)
详细信息

  • 中图分类号: TP391

Fast and Distributed Map-Matching Based on Contraction Hierarchies

  • 1(College of Computer Science, Chongqing University, Chongqing 400044)

  • 2(JD iCity, JD Technology, Beijing 100176)

  • 3(JD Intelligent Cities Research, Beijing 100176)

Funds: This work was supported by the National Key Research and Development Program of China (2019YFB2101801) and the National Natural Science Foundation of China (61976168, 61872050, 62172066).

摘要

    摘要
  • 摘要: 地图匹配是轨迹数据挖掘的基本操作，在许多空间数据智能场景中都非常有用.基于隐马尔可夫模型(hidden Markov model, HMM)的地图匹配算法具有较高的准确率，应用最为广泛，但其计算效率较低，难以应对实时性要求较高的大规模轨迹情形.提出了一个基于路网层次收缩的分布式地图匹配框架CHMM，能够对大规模的轨迹数据实现快速地图匹配.具体而言，提出了一个简单但有效的分区方案，能够解决分布式场景下轨迹数据分布不平衡的问题；提出了一个基于路网层次收缩的多对多最短路径查询算法，能够保证结果不变的情况下，显著提升基于HMM的地图匹配算法的效率.采用真实的路网数据和轨迹数据做了充分的实验，实验结果表明：CHMM算法具有更快的计算效率和更强的可扩展性.CHMM算法落回到了真实的产品中，支持了多个项目的落地.我们也开源了核心代码，并提供了一个在线演示系统.
    Abstract: Map-Matching is a basic operation for trajectory data mining, which is very useful for many spatial intelligent applications. Hidden Markov model (i.e., HMM)-based map-matching is the most widely-used algorithm for its high accuracy. However, HMM-based map-matching is very time-consuming, so it can hardly be applied to real-time scenarios with massive trajectory data. In this paper a contraction hierarchy-based and distributed map-matching framework, i.e., CHMM, is proposed, which map-matches massive trajectories efficiently. Specifically, we first propose a simple but effective partitioning strategy to solve the issue of unbalanced trajectory data distribution. Then, we propose a contraction hierarchy-based many-to-many shortest path search method, which significantly improves the efficiency of HMM-based map-matching while keeps the results unchanged. Extensive experiments are conducted using real road network data and big trajectory data, verifying the powerful efficiency and scalability of CHMM. CHMM has been deployed to our product, supporting various real urban applications. We publish the core source code and provide an online demo system.
    • HTML全文
    • 参考文献(0)
    • 相关文章
    • 施引文献(13)

  • 期刊类型引用(10)

    1. 王秀珍，徐鹏，陈美荣，王丹琛，徐扬. 一种车联网V2V认证与密钥交换协议设计与验证. 信息安全研究. 2025(05): 465-472 . 百度学术
    2. 邢琦. 基于ECC算法的安全芯片增强双向匿名认证方法. 电子设计工程. 2024(02): 176-180+186 . 百度学术
    3. 吴忠强，李孟亭. 基于CBAMTL-MobileNet V3的车载网络入侵检测. 计量学报. 2024(09): 1407-1415 . 百度学术
    4. 王凯，董建阔，肖甫，吉欣仪，胡昕. 面向物联网的认证密钥协商协议研究综述. 网络空间安全科学学报. 2024(05): 2-16 . 百度学术
    5. 姚海龙. 一种物联网轻量级匿名认证协议的仿冒攻击. 甘肃高师学报. 2023(02): 12-15 . 百度学术
    6. 况博裕，李雨泽，顾芳铭，苏铓，付安民. 车联网安全研究综述：威胁、对策与未来展望. 计算机研究与发展. 2023(10): 2304-2321 . 本站查看
    7. 蒋玉长，徐洋，李克资，秦庆凯，张思聪. 基于深度学习的轻量级车载网络入侵检测方法. 计算机工程与应用. 2023(22): 284-292 . 百度学术
    8. 谢绒娜，谭莉，武佳卉，史国振，李楚涵，邓烨. 面向天地一体化网络的认证与密钥协商协议. 密码学报. 2023(05): 1035-1051 . 百度学术
    9. 王理冬. 基于生成对抗网络的车载网络入侵检测系统. 安徽电子信息职业技术学院学报. 2023(04): 24-28 . 百度学术
    10. 杨文山，陈骁. 基于V2X的车联网安全互信体系架构分析. 信息安全与通信保密. 2022(07): 133-139 . 百度学术

    其他类型引用(3)

    • 资源附件(0)
计量
  • 文章访问数:  831
  • HTML全文浏览量:  9
  • PDF下载量:  362
  • 被引次数: 13
出版历程
  • 发布日期:  2022-01-31

目录

摘要
HTML全文
    参考文献(0)
    相关文章
    施引文献
    资源附件(0)

    /

    返回文章
    返回
    邮件订阅 RSS
    微信订阅号<br/>（实时资讯）

    微信订阅号
    （实时资讯）

    微信服务号<br/>（同步网站）

    微信服务号
    （同步网站）

    微信视频号<br/>（视频分享）

    微信视频号
    （视频分享）

    CCF<br/>（扫码入会）

    CCF
    （扫码入会）

    版权所有 © 《计算机研究与发展》编辑部

    本系统由北京仁和汇智信息技术有限公司开发  百度统计