Efficient routing is essential in everyday life. Although various hierarchical algorithms exist for computing shortest paths, their heavy precomputation/storage costs and/or query costs hinder their application to large road networks. By detecting a hierarchical community structure in road networks, we develop a community-based hierarchical graph model that supports efficient route computation on large road networks. We then propose a new hierarchical routing algorithm that can significantly reduce the search space over the conventional algorithms with acceptable loss of accuracy. Experimental results on a New York road network demonstrate the performance of the algorithm.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Efficient Routing on Large Road Networks Using Hierarchical Communities


    Beteiligte:
    Qing Song, (Autor:in) / Xiaofan Wang, (Autor:in)


    Erscheinungsdatum :

    2011-03-01


    Format / Umfang :

    403670 byte




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    Heuristic techniques for accelerating hierarchical routing on road networks

    Jagadeesh, G.R. / Srikanthan, T. / Quek, K.H. | IEEE | 2002


    Heuristic Techniques for Accelerating Hierarchical Routing on Road Networks

    Jagadeesh, G. R. / Srikanthan, T. / Quek, K. H. | British Library Online Contents | 2002