Efficient Routing on Large Road Networks Using Hierarchical Communities
Authors:
- 27 September 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Intelligent Transportation Systems
- Vol. 12 (1) , 132-140
Abstract
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.Keywords
This publication has 31 references indexed in Scilit:
- Community detection in graphsPhysics Reports, 2010
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Hierarchical path computation approach for large graphsIEEE Transactions on Aerospace and Electronic Systems, 2008
- Dynamic Highway-Node Routing2007
- Highway Hierarchies Hasten Exact Shortest Path Queries2005
- Finding and evaluating community structure in networksPhysical Review E, 2004
- Heuristic techniques for accelerating hierarchical routing on road networksIEEE Transactions on Intelligent Transportation Systems, 2002
- Approximating Shortest Paths in Large-Scale Networks with an Application to Intelligent Transportation SystemsINFORMS Journal on Computing, 1998
- Route finding by using knowledge about the road networkIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 1997
- Some Basic Definitions in Graph TheoryReviews of Modern Physics, 1970