Fast Computation of Clustered Many-to-many Shortest Paths and Its Application to Map Matching

被引:4
|
作者
Jagadeesh, George R. [1 ]
Srikanthan, Thambipillai [1 ]
机构
[1] Nanyang Technol Univ, Sch Comp Sci & Engn, Singapore 639798, Singapore
关键词
Many-to-many shortest paths; map matching; speed-up technique; INFERENCE;
D O I
10.1145/3329676
中图分类号
TP7 [遥感技术];
学科分类号
081102 ; 0816 ; 081602 ; 083002 ; 1404 ;
摘要
We examine the problem of computing shortest paths in a transportation network from a set of geographically clustered source nodes to a set of target nodes. Such many-to-many shortest path computations are an essential and computationally expensive part of many emerging applications that involve map matching of imprecise trajectories. Existing solutions to this problem mostly conform to the obvious approach of performing a single-source shortest path computation for each source node. We present an algorithm that exploits the clustered nature of the source nodes. Specifically, we rely on the observation that paths originating from a cluster of nodes typically exit the source region's boundary through a small number of nodes. Evaluations on a real road network show that the proposed algorithm provides a speed-up of several times over the conventional approach when the source nodes are densely clustered in a region. We also demonstrate that the presented technique is capable of substantially accelerating map matching of sparse and noisy trajectories.
引用
收藏
页数:20
相关论文
共 50 条
  • [21] Many-to-many disjoint paths in hypercubes with faulty vertices
    Li, Xiang Jun
    Liu, Bin
    Ma, Meijie
    Xu, Jun-Ming
    DISCRETE APPLIED MATHEMATICS, 2017, 217 : 229 - 242
  • [22] Constrained many-to-many point matching in two dimensions
    Caraballo, L. E.
    Castro, R. A.
    Diaz-Banez, J. M.
    Heredia, M. A.
    Urrutia, J.
    Ventura, I.
    Zaragoza, F. J.
    OPTIMIZATION LETTERS, 2024, 18 (08) : 1837 - 1854
  • [23] Unsupervised Many-to-Many Object Matching for Relational Data
    Iwata, Tomoharu
    Lloyd, James Robert
    Ghahramani, Zoubin
    IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2016, 38 (03) : 607 - 617
  • [24] A one-sided many-to-many matching problem
    Okumura, Yasunori
    JOURNAL OF MATHEMATICAL ECONOMICS, 2017, 72 : 104 - 111
  • [25] Efficient many-to-many point matching in one dimension
    Colannino, Justin
    Damian, Mirela
    Hurtado, Ferran
    Langerman, Stefan
    Meijer, Henk
    Ramaswami, Suneeta
    Souvaine, Diane
    Toussaint, Godfried
    GRAPHS AND COMBINATORICS, 2007, 23 (Suppl 1) : 169 - 178
  • [26] Efficient Many-To-Many Point Matching in One Dimension
    Justin Colannino
    Mirela Damian
    Ferran Hurtado
    Stefan Langerman
    Henk Meijer
    Suneeta Ramaswami
    Diane Souvaine
    Godfried Toussaint
    Graphs and Combinatorics, 2007, 23 : 169 - 178
  • [27] Many-to-many graph matching via metric embedding
    Keselman, Y
    Shokoufandeh, A
    Demirci, MF
    Dickinson, S
    2003 IEEE COMPUTER SOCIETY CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION, VOL 1, PROCEEDINGS, 2003, : 850 - 857
  • [28] Many-to-many matching with max-min preferences
    Hatfield, John William
    Kojima, Fuhito
    Narita, Yusuke
    DISCRETE APPLIED MATHEMATICS, 2014, 179 : 235 - 240
  • [29] Credible group stability in many-to-many matching problems
    Konishi, Hideo
    Unver, M. Utku
    JOURNAL OF ECONOMIC THEORY, 2006, 129 (01) : 57 - 80
  • [30] Many-to-Many Graph Matching: A Continuous Relaxation Approach
    Zaslavskiy, Mikhail
    Bach, Francis
    Vert, Jean-Philippe
    MACHINE LEARNING AND KNOWLEDGE DISCOVERY IN DATABASES, PT III, 2010, 6323 : 515 - 530