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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Efficient Routing on Large Road Networks Using Hierarchical Communities


    Contributors:
    Qing Song, (author) / Xiaofan Wang, (author)


    Publication date :

    2011-03-01


    Size :

    403670 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    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