CANDS: Continuous Optimal Navigation via Distributed Stream Processing

Abstract : Shortest path query over a dynamic road network is a prominent problem for the optimization of real-time traffic systems. Existing solutions rely either on a centralized index system with tremen- dous pre-computation overhead, or on a distributed graph process- ing system such as Pregel that requires much synchronization ef- fort. However, the performance of these systems degenerates with frequent route path updates caused by continuous traffic condition change. In this paper, we build CANDS, a distributed stream processing platform for continuous optimal shortest path queries. It provides an asynchronous solution to answering a large quantity of shortest path queries. It is able to efficiently detect affected paths and adjust their paths in the face of traffic updates. Moreover, the affected paths can be quickly updated to the optimal solutions through- out the whole navigation process. Experimental results demon- strate that the performance for answering shortest path queries by CANDS is two orders of magnitude better than that of GPS, an open-source implementation of Pregel. In addition, CANDS pro- vides fast response to traffic updates to guarantee the optimality of answering shortest path queries.
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01073066
Contributeur : Frédéric Le Mouël <>
Soumis le : jeudi 9 octobre 2014 - 12:58:32
Dernière modification le : mardi 17 novembre 2015 - 17:36:12
Document(s) archivé(s) le : samedi 10 janvier 2015 - 10:10:14

Fichier

cands.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01073066, version 1

Collections

Citation

Dingyu Yang, Dongxiang Zhang, Kian-Lee Tan, Jian Cao, Frédéric Le Mouël. CANDS: Continuous Optimal Navigation via Distributed Stream Processing. Proceedings of the VLDB Endowment (PVLDB), VLDB Endowment, 2014, 8 (2), pp.137-148. 〈http://www.vldb.org/pvldb/vol8.html〉. 〈hal-01073066〉

Partager

Métriques

Consultations de la notice

151

Téléchargements de fichiers

216