Name
Abstract | ||
|---|---|---|
Multimodal path queries over transportation networks are receiving increasing attention due to their widespread applications. A multimodal path query consists of finding multimodal journeys from source to destination in transportation networks, including unrestricted walking, driving, cycling, and schedule-based public transportation. Transportation networks are generally continent-sized. This characteristic highlights the need for parallel computing to accelerate multimodal path queries. Meanwhile, transportation networks are often fragmented and distributively stored on different machines. This situation calls for exploiting parallel computing power for these distributed systems. Therefore, in this paper, we study
<i>distributed multimodal path (DMP) queries</i>
over large transportation networks. We develop algorithms to explore parallel computation. When evaluating a DMP query
<inline-formula><tex-math notation="LaTeX">$Q$</tex-math></inline-formula>
on a distributed multimodal graph
<inline-formula><tex-math notation="LaTeX">$Gmult$</tex-math></inline-formula>
, we show that the algorithms possess the following performance guarantees, irrespective of how
<inline-formula><tex-math notation="LaTeX">$Gmult$</tex-math></inline-formula>
is fragmented and distributed: (1) each machine is visited only once; (2) the total network traffic is determined by the size of
<inline-formula><tex-math notation="LaTeX">$Q$</tex-math></inline-formula>
and the fragmentation of
<inline-formula><tex-math notation="LaTeX">$Gmult$</tex-math></inline-formula>
; (3) the response time is decided by the largest fragment of
<inline-formula><tex-math notation="LaTeX">$Gmult$</tex-math></inline-formula>
; and (4) the algorithm is parallel scalable. Using real-life and synthetic data, we experimentally verify that the algorithms are scalable on large graphs. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1109/TKDE.2020.3020185 | IEEE Transactions on Knowledge and Data Engineering |
Keywords | DocType | Volume |
Multimodal graph,path query,parallel computation | Journal | 34 |
Issue | ISSN | Citations |
7 | 1041-4347 | 0 |
PageRank | References | Authors |
0.34 | 28 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yawen Li | 1 | 11 | 2.85 |
| Ye Yuan | 2 | 117 | 24.40 |
| Yishu Wang | 3 | 12 | 3.92 |
| Xiang Lian | 4 | 35 | 5.25 |
| Yuliang Ma | 5 | 20 | 7.39 |
| Guoren Wang | 6 | 1366 | 159.46 |