Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
The VLDB Journal
Erschienen in: The VLDB Journal 3/2017

14.02.2017 | Regular Paper

Distributed shortest path query processing on dynamic road networks

verfasst von: Dongxiang Zhang, Dingyu Yang, Yuan Wang, Kian-Lee Tan, Jian Cao, Heng Tao Shen

Erschienen in: The VLDB Journal | Ausgabe 3/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Shortest path query processing on dynamic road networks is a fundamental component for real-time navigation systems. In the face of an enormous volume of customer demand from Uber and similar apps, it is desirable to study distributed shortest path query processing that can be deployed on elastic and fault-tolerant cloud platforms. In this paper, we combine the merits of distributed streaming computing systems and lightweight indexing to build an efficient shortest path query processing engine on top of Yahoo S4. We propose two types of asynchronous communication algorithms for early termination. One is first-in-first-out message propagation with certain optimizations, and the other is prioritized message propagation with the help of navigational intelligence. Extensive experiments were conducted on large-scale real road networks, and the results show that the query efficiency of our methods can meet the real-time requirement and is superior to Pregel and Pregel+. The source code of our system is publicly available at https://​github.​com/​yangdingyu/​cands.
Vorheriger Artikel Finding lowest-cost paths in settings with safe and preferred zones
Nächster Artikel Scalable subgraph enumeration in MapReduce: a cost-oriented approach

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
7
Other edge-balanced graph partitioning methods can also be applied.
 
Literatur
1.
Abraham, I., Fiat, A., Goldberg, AV., Werneck, RF.: Highway dimension, shortest paths, and provably efficient algorithms. In: SODA, pp. 782–793 (2010)
2.
Akiba, T., Iwata, Y., Yoshida, Y.: Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: SIGMOD, pp. 349–360 (2013)
3.
Bast, H., Funke, S., Sanders, P., Schultes, D.: Fast routing in road networks with transit nodes. Science 316(5824), 566–566 (2007)MathSciNetCrossRefMATH
4.
Bast, H., Delling, D., Goldberg, AV., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., Werneck, RF.: Route planning in transportation networks. arXiv:​1504.​05140v1 [cs.DS] (2015)
5.
Biem, A., Bouillet, E., Feng, H., Ranganathan, A., Riabov, A., Verscheure, O., Koutsopoulos, H., Moran, C.: Ibm infosphere streams for scalable, real-time, intelligent transportation services. In: SIGMOD, ACM, pp. 1093–1104 (2010)
6.
Cheng, J., Ke, Y., Chu, S., Cheng, C.: Efficient processing of distance queries in large graphs: a vertex cover approach. In: SIGMOD, pp. 457–468 (2012)
7.
Delling, D., Werneck, RF.: Faster customization of road networks. In: Experimental Algorithms, Springer, Berlin, pp. 30–42 (2013)
8.
Delling, D., Goldberg, AV., Pajor, T., Werneck, RF.: Customizable Route Planning. In: Pardalos, PM., Rebennack, S., (Eds.) Proceedings of the 10th International Symposium on Experimental Algorithms (SEA’11), Springer, Lecture Notes in Computer Science, vol. 6630, pp. 376–387 (2011)
9.
10.
Fan, Q., Zhang, D., Wu, H., Tan, K.: A general and parallel platform for mining co-movement patterns over large-scale trajectories. PVLDB 10(4), 313–324 (2016)
11.
Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In: Experimental Algorithms, pp. 319–333. Springer, Berlin (2008)
12.
Goldberg, AV., Harrelson, C.: Computing the shortest path: A search meets graph theory. In: SODA, pp. 156–165 (2005)
13.
Goldberg, A.V., Kaplan, H., Werneck, R.F.: Reach for a*: Efficient point-to-point shortest path algorithms. ALENEX 6, 129–143 (2006)
14.
Gonzalez, H., Han, J., Li, X., Myslinska, M., Sondag, JP.: Adaptive fastest path computation on a road network: a traffic mining approach. In: VLDB, VLDB Endowment, pp. 794–805 (2007)
15.
Gonzalez, JE., Low, Y., Gu, H., Bickson, D., Guestrin, C.: Powergraph: Distributed graph-parallel computation on natural graphs. In: OSDI, pp. 17–30 (2012)
16.
Guerrero-Ibáñez, A., Flores-Cortés, C., Damián-Reyes, P., Andrade-Aréchiga, M., Pulido, J.: Emerging technologies for urban traffic management. Tech. rep. (2012)
17.
Hunter, T., Moldovan, TM., Zaharia, M., Merzgui, S., Ma, J., Franklin, MJ., Abbeel, P., Bayen, AM.: Scaling the mobile millennium system in the cloud. In: SOCC, p. 28 (2011)
18.
Jin, R., Ruan, N., Xiang, Y., Lee, VE.: A highway-centric labeling approach for answering distance queries on large sparse graphs. In: SIGMOD, pp. 445–456 (2012)
19.
Jin, R., Ruan, N., You, B., Wang, H.: Hub-accelerator: Fast and exact shortest path computation in large social networks. arXiv:​1305.​0507v1 [cs.SI] (2013)
20.
Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359–392 (1998)MathSciNetCrossRefMATH
21.
Kieritz, T., Luxen, D., Sanders, P., Vetter, C.: Distributed time-dependent contraction hierarchies. ISEA, LNCS 6049, 83–93 (2010)
22.
Low, Y., Gonzalez, J., Kyrola, A., Bickson, D., Guestrin, C., Hellerstein, J.M.: Distributed graphlab: a framework for machine learning in the cloud. PVLDB 5(8), 716–727 (2012)
23.
Malewicz, G., Austern, MH., Bik, AJ., Dehnert, JC., Horn, I., Leiser, N., Czajkowski, G.: Pregel: a system for large-scale graph processing. In: SIGMOD, ACM, pp. 135–146 (2010)
24.
Maue, J., Sanders, P., Matijevic, D.: Goal directed shortest path queries using precomputed cluster distances. ACM J. Exp. Algorithmics (2007)
25.
Rice, M., Tsotras, V.J.: Graph indexing of road networks for shortest path queries with label restrictions. VLDB 4(2), 69–80 (2010)
26.
Salihoglu, S., Widom, J.: GPS: a graph processing system. In: SSDBM, pp. 22:1–22:12 (2013)
27.
Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In: ESA, pp. 568–579, Springer, Berlin (2005)
28.
Thiagarajan, A., Ravindranath, L., LaCurts, K., Madden, S., Balakrishnan, H., Toledo, S., Eriksson, J.: Vtrack: accurate, energy-aware road traffic delay estimation using mobile phones. In: SenSys, pp. 85–98, ACM (2009)
29.
Thomsen, JR., Yiu, ML., Jensen, CS.: Effective caching of shortest paths for location-based services. In: SIGMOD, pp. 313–324 (2012)
30.
Wang, Y., Zhang, D., Hu, L., Yang, Y., Lee, LH.: A data-driven and optimal bus scheduling model with time-dependent traffic and demand. IEEE Trans. Intell. Transp. Syst. (99):1–10, (2017) doi:10.​1109/​TITS.​2016.​2644725
31.
Wei, H., Wang, Y., Forman, G., Zhu, Y., Guan, H.: Fast Viterbi map matching with tunable weight functions. In: SIGSPATIAL GIS, pp. 613–616, ACM (2012)
32.
Wu, L., Xiao, X., Deng, D., Cong, G., Zhu, A.D., Zhou, S.: Shortest path and distance queries on road networks: an experimental evaluation. PVLDB 5(5), 406–417 (2012)
33.
Yan, D., Cheng, J., Lu, Y., Ng, W.: Blogel: a block-centric framework for distributed computation on real-world graphs. PVLDB 7(14), 1981–1992 (2014)
34.
Yan, D., Cheng, J., Xing, K., Lu, Y., Ng, W., Bu, Y.: Pregel algorithms for graph connectivity problems with performance guarantees. PVLDB 7(14), 1821–1832 (2014)
35.
Yan, D., Cheng, J., Lu, Y., Ng, W.: Effective techniques for message reduction and load balancing in distributed graph computation. In: WWW, pp. 1307–1317 (2015)
36.
Yan, D., Cheng, J., Özsu, MT., Yang, F., Lu, Y., Lui, JCS., Zhang, Q., Ng, W.: Quegel: A general-purpose query-centric framework for querying big graphs. arXiv:​1601.​06497v1 [cs.DC] (2016)
37.
Yang, D., Zhang, D., Tan, K., Cao, J., Mouël, F.L.: CANDS: continuous optimal navigation via distributed stream processing. PVLDB 8(2), 137–148 (2014)
38.
Yuan, J., Zheng, Y., Zhang, C., Xie, W., Xie, X., Sun, G., Huang, Y.: T-drive: driving directions based on taxi trajectories. In: SIGSPATIAL GIS, pp. 99–108 , ACM (2010)
39.
Zheng, Y., Liu, Y., Yuan, J., Xie, X.: Urban computing with taxicabs. In: Ubicomp, pp. 89–98 (2011)
40.
Zhu, AD., Ma, H., Xiao, X., Luo, S., Tang, Y., Zhou, S.: Shortest path and distance queries on road networks: towards bridging theory and practice. In: SIGMOD, pp. 857–868 (2013)
Metadaten
Titel
Distributed shortest path query processing on dynamic road networks
verfasst von
Dongxiang Zhang
Dingyu Yang
Yuan Wang
Kian-Lee Tan
Jian Cao
Heng Tao Shen
Publikationsdatum
14.02.2017
Verlag
Springer Berlin Heidelberg
Erschienen in
The VLDB Journal / Ausgabe 3/2017
Print ISSN: 1066-8888
Elektronische ISSN: 0949-877X
DOI
https://doi.org/10.1007/s00778-017-0457-6

Weitere Artikel der Ausgabe 3/2017

The VLDB Journal 3/2017 Zur Ausgabe

Regular Paper

Finding lowest-cost paths in settings with safe and preferred zones

Regular Paper

Disjoint interval partitioning

Regular Paper

Top-k spatial-keyword publish/subscribe over sliding window

Regular Paper

Path-based holistic detection plan for multiple patterns in distributed graph frameworks

Regular Paper

Scalable subgraph enumeration in MapReduce: a cost-oriented approach

Regular Paper

AutoG: a visual query autocompletion framework for graph databases