nach oben

GeoInformatica

Erschienen in:

01.01.2016

SPLZ: An efficient algorithm for single source shortest path problem using compression method

verfasst von: Jingwei Sun, Guangzhong Sun

Erschienen in: GeoInformatica | Ausgabe 1/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Efficient solution of the single source shortest path (SSSP) problem on road networks is an important requirement for numerous real-world applications. This paper introduces an algorithm for the SSSP problem using compression method. Owning to precomputing and storing all-pairs shortest path (APSP), the process of solving SSSP problem is a simple lookup of a little data from precomputed APSP and decompression. APSP without compression needs at least 1TB memory for a road network with one million vertices. Our algorithm can compress such an APSP into several GB, and ensure a good performance of decompression. In our experiment on a dataset about Northwest USA (with 1.2 millions vertices), our method can achieve about three orders of magnitude faster than Dijkstra algorithm based on binary heap.

Nächster Artikel SMe: explicit & implicit constrained-space probabilistic threshold range queries for moving objects

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

https://github.com/asds25810/SPLZ

Abraham I, Delling D, Goldberg AV, Werneck RF (2011) A hub-based labeling algorithm for shortest paths in road networks. In: Experimental Algorithms, Springer, pp 230–241

Abraham I, Delling D, Fiat A, Goldberg AV, Werneck RF (2012) Hldb: Location-based services in databases. In: Proceedings of the 20th International Conference on Advances in Geographic Information Systems, ACM, New York, NY, USA, SIGSPATIAL ’12, pp 339–348, doi:10.1145/2424321.2424365, (to appear in print)

Ahuja RK, Mehlhorn K, Orlin J, Tarjan RE (1990) Faster algorithms for the shortest path problem. J ACM (JACM) 37(2):213–223CrossRef

Arz J, Luxen D, Sanders P (2013) Transit node routing reconsidered. In: Experimental Algorithms, Springer, pp 55–66

Bast H, Funke S, Sanders P, Schultes D (2007) Fast routing in road networks with transit nodes. Science 316(5824):566–566CrossRef

Bell T, Kulp D (1993) Longest-match string searching for ziv-lempel compression. Software: Practice and Experience 23(7):757–771

Bellman R (1956) On a routing problem. Tech rep, DTIC Document

Bertsekas DP (1993) A simple and fast label correcting algorithm for shortest paths. Networks 23(8):703–709CrossRef

Bertsekas DP, Guerriero F, Musmanno R (1996) Parallel asynchronous label-correcting methods for shortest paths. J Optim Theory Appl 88(2):297–320CrossRef

10.

Botea A, Baier JA, Harabor D, Hernández C (2013) Moving target search with compressed path databases. Proceedings of ICAPS-13

11.

Cherkassky BV, Goldberg AV, Radzik T (1996) Shortest paths algorithms: Theory and experimental evaluation. Math Program 73(2):129–174CrossRef

12.

Cherkassky BV, Georgiadis L, Goldberg AV, Tarjan RE, Werneck RF (2009) Shortest-path feasibility algorithms: An experimental evaluation. J Exp Algorithmics (JEA) 14:7

13.

Cormen TH, Leiserson CE, Rivest RL, Stein C, et al. (2001) Introduction to algorithms, vol 2. MIT press, Cambridge

14.

Delling D, Goldberg AV, Nowatzyk A, Werneck RF (2013a) Phast: Hardware-accelerated shortest path trees. J Parallel Distrib Comput 73(7):940–952CrossRef

15.

Delling D, Goldberg AV, Pajor T, Werneck RF (2013b) Customizable route planning in road networks. In: Sixth Annual Symposium on Combinatorial Search

16.

Demetrescu C, Goldberg AV, Johnson DS (2009) The Shortest Path Problem: Ninth DIMACS Implementation Challenge, vol 74. American Mathematical Soc

17.

Dial RB (1969) Algorithm 360: Shortest-path forest with topological ordering [h]. Commun ACM 12(11):632–633CrossRef

18.

Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische mathematik 1(1):269–271CrossRef

19.

Gallo G, Pallottino S (1986) Shortest path methods: A unifying approach. Netflow at Pisa, pp 38–64

20.

Geisberger R, Sanders P, Schultes D, Delling D (2008) Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In: Experimental Algorithms, Springer, pp 319–333

21.

Glover F, Klingman D, Phillips N (1985) A new polynomially bounded shortest path algorithm. Oper Res 33(1):65–73CrossRef

22.

Goldberg AV, Harrelson C (2005) Computing the shortest path: A search meets graph theory. In: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, pp 156–165

23.

Hilger M, Köhler E, Möhring RH, Schilling H (2009) Fast point-to-point shortest path computations with arc-flags. The Shortest Path Problem: Ninth DIMACS Implementation Challenge 74:41–72

24.

Knuth DE, Morris JH Jr, Pratt VR (1977) Fast pattern matching in strings. SIAM J Comput 6(2):323–350CrossRef

25.

Madduri K, Bader DA, Berry JW, Crobak JR (2006) Parallel shortest path algorithms for solving large-scale instances

26.

Maue J, Sanders P, Matijevic D (2010) Goal-directed shortest-path queries using precomputed cluster distances. J Exp Algorithmics 14:2:3.2–2:3.27. doi:10.1145/1498698.1564502

27.

Meyer U, Sanders P (2003) δ-stepping: a parallelizable shortest path algorithm. J Algorithms 49(1):114–152CrossRef

28.

Pallottino S (1984) Shortest-path methods: Complexity, interrelations and new propositions. Networks 14(2):257–267CrossRef

29.

Pape U (1974) Implementation and efficiency of moore-algorithms for the shortest route problem. Math Program 7(1):212–222CrossRef

30.

Sanders P, Schultes D (2005) Highway hierarchies hasten exact shortest path queries. In: Algorithms–Esa 2005, Springer, pp 568–579

31.

Sankaranarayanan J, Alborzi H, Samet H (2005) Efficient query processing on spatial networks. In: Proceedings of the 13th annual ACM international workshop on Geographic information systems, ACM, pp 200–209

32.

Sankaranarayanan J, Samet H, Alborzi H (2009) Path oracles for spatial networks. Proc VLDB Endowment 2(1):1210–1221CrossRef

33.

Ziv J, Lempel A (1977) A universal algorithm for sequential data compression. IEEE Trans Inf Theory 23(3):337–343CrossRef

Titel: SPLZ: An efficient algorithm for single source shortest path problem using compression method
verfasst von: Jingwei Sun
Guangzhong Sun
Publikationsdatum: 01.01.2016
Verlag: Springer US
Erschienen in: GeoInformatica / Ausgabe 1/2016
Print ISSN: 1384-6175
Elektronische ISSN: 1573-7624
DOI: https://doi.org/10.1007/s10707-015-0229-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2016

Spatio-temporal traffic video data archiving and retrieval system

Kernel density estimation based on Ripley’s correction

SMe: explicit & implicit constrained-space probabilistic threshold range queries for moving objects

A domain specific language for spatial simulation scenarios