Abstract
This study proposes a new approach for the shortest path query problem on continental-scale road networks. We exploit the inherent geographical information of road networks, and use the quad-tree data structure to partition input graphs. In order to reduce computational load of route planning, the clustering structure is constructed during the preprocessing stage; some fine-tune techniques are also applied to make the structure more effective and efficient for shortest path queries. Moreover, we provide several accelerated skills to speedup our routing algorithm based on the geographical information of the data structure, and the setting of the quad-tree data structure can be adjusted to find a good balance between query time and memory space consumption, which makes the algorithm more flexible for practical use. The empirical studies demonstrate the usefulness of our routing algorithm; in particular, each shortest path query can be answered under a few milliseconds on average in Europe and USA networks with more than ten million nodes.