Published May 3, 2018
| Version v1
Publication
Open
The MapReduce-based approach to improve the shortest path computation in large-scale road networks: the case of A* algorithm
- 1. University of Hassan II Casablanca
Description
This paper deals with an efficient parallel and distributed framework for intensive computation with A* algorithm based on MapReduce concept. The A* algorithm is one of the most popular graph traversal algorithm used in route guidance. It requires exponential time computation and very costly hardware to compute the shortest path on large-scale networks. Thus, it is necessary to reduce the time complexity while exploiting a low cost commodity hardwares. To cope with this situation, we propose a novel approach that reduces the A* algorithm into a set of Map and Reduce tasks for running the path computation on Hadoop MapReduce framework. An application on real road networks illustrates the feasibility and reliability of the proposed framework. The experiments performed on a 6-node Hadoop cluster proves that the proposed approach outperforms A* algorithm and achieves significant gain in terms of computation time.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
تتناول هذه الورقة إطارًا متوازيًا وموزعًا فعالًا للحساب المكثف باستخدام خوارزمية A* بناءً على مفهوم MapReduce. تعد خوارزمية A* واحدة من أكثر خوارزميات اجتياز الرسم البياني شيوعًا المستخدمة في توجيه المسار. يتطلب الأمر حساب وقت أسي وأجهزة مكلفة للغاية لحساب أقصر مسار على الشبكات واسعة النطاق. وبالتالي، من الضروري تقليل تعقيد الوقت مع استغلال الأجهزة السلعية منخفضة التكلفة. للتعامل مع هذا الموقف، نقترح نهجًا جديدًا يقلل من خوارزمية A* إلى مجموعة من مهام Map و Reduce لتشغيل حساب المسار على إطار عمل Hadoop MapReduce. يوضح تطبيق على شبكات الطرق الحقيقية جدوى وموثوقية الإطار المقترح. تثبت التجارب التي أجريت على مجموعة Hadoop المكونة من 6 عقدة أن النهج المقترح يتفوق على خوارزمية A* ويحقق مكاسب كبيرة من حيث وقت الحساب.Translated Description (French)
Cet article traite d'un cadre parallèle et distribué efficace pour le calcul intensif avec un algorithme A* basé sur le concept MapReduce. L'algorithme A* est l'un des algorithmes de parcours de graphe les plus populaires utilisés dans le guidage routier. Il nécessite un calcul de temps exponentiel et un matériel très coûteux pour calculer le chemin le plus court sur les réseaux à grande échelle. Ainsi, il est nécessaire de réduire la complexité temporelle tout en exploitant un matériel de base à faible coût. Pour faire face à cette situation, nous proposons une nouvelle approche qui réduit l'algorithme A* en un ensemble de tâches Map et Reduce pour exécuter le calcul de chemin sur le framework Hadoop MapReduce. Une application sur des réseaux routiers réels illustre la faisabilité et la fiabilité du cadre proposé. Les expériences réalisées sur un cluster Hadoop à 6 nœuds prouvent que l'approche proposée surpasse l'algorithme A* et réalise un gain significatif en termes de temps de calcul.Translated Description (Spanish)
Este documento trata sobre un marco eficiente paralelo y distribuido para el cálculo intensivo con el algoritmo A* basado en el concepto MapReduce. El algoritmo A* es uno de los algoritmos de recorrido de gráficos más populares utilizados en la guía de rutas. Requiere un cálculo exponencial del tiempo y un hardware muy costoso para calcular la ruta más corta en redes a gran escala. Por lo tanto, es necesario reducir la complejidad del tiempo mientras se explota un hardware de productos básicos de bajo costo. Para hacer frente a esta situación, proponemos un enfoque novedoso que reduce el algoritmo A* en un conjunto de tareas Map and Reduce para ejecutar el cálculo de rutas en el marco Hadoop MapReduce. Una aplicación en redes de carreteras reales ilustra la viabilidad y fiabilidad del marco propuesto. Los experimentos realizados en un clúster de Hadoop de 6 nodos demuestran que el enfoque propuesto supera al algoritmo A* y logra una ganancia significativa en términos de tiempo de cálculo.Files
s40537-018-0125-8.pdf
Files
(3.5 MB)
| Name | Size | Download all |
|---|---|---|
|
md5:73bf2cf9f0e8243fa323a9a1e9a24755
|
3.5 MB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- النهج القائم على MapReduce لتحسين أقصر حساب للمسار في شبكات الطرق واسعة النطاق: حالة خوارزمية A*
- Translated title (French)
- L'approche basée sur MapReduce pour améliorer le calcul du plus court chemin dans les réseaux routiers à grande échelle : le cas de l'algorithme A*
- Translated title (Spanish)
- El enfoque basado en MapReduce para mejorar el cálculo de la ruta más corta en redes de carreteras a gran escala: el caso del algoritmo A*
Identifiers
- Other
- https://openalex.org/W2806141066
- DOI
- 10.1186/s40537-018-0125-8
References
- https://openalex.org/W1039385342
- https://openalex.org/W1641749581
- https://openalex.org/W1969483458
- https://openalex.org/W1979957675
- https://openalex.org/W2017694061
- https://openalex.org/W2019724001
- https://openalex.org/W2084224084
- https://openalex.org/W2095941092
- https://openalex.org/W2103610940
- https://openalex.org/W2105947650
- https://openalex.org/W2118382442
- https://openalex.org/W2150437713
- https://openalex.org/W2166837162
- https://openalex.org/W2169528473
- https://openalex.org/W2171053395
- https://openalex.org/W2173213060
- https://openalex.org/W2194873357
- https://openalex.org/W2227557434
- https://openalex.org/W2574663572
- https://openalex.org/W2729421440
- https://openalex.org/W2753693129
- https://openalex.org/W2967057359
- https://openalex.org/W3125867108
- https://openalex.org/W4238584892
- https://openalex.org/W4302771278