Efficient and Scalable Multi-Geography Route Planning

Appeared in EDBT 2010

Vidhya Balasubramanian, Dmitri V. Kalashnikov, Sharad Mehrotra, and Nalini Venkatasubramanian

Computer Science Department
University of California, Irvine


This paper considers the problem of Multi-Geography Route Planning (MGRP) where the geographical information may be spread over multiple heterogeneous interconnected maps. We first design a flexible and scalable representation to model individual geographies and their interconnections. Given such a representation, we develop an algorithm that exploits precomputation and caching of geographical data for path planning. A utility-based approach is adopted to decide which paths to precompute and store. To validate the proposed approach we test the algorithm over the workload of a campus level evacuation simulation that plans evacuation routes over multiple geographies: indoor CAD maps, outdoor maps, pedestrian and transportation networks, etc. The empirical results indicate that the MGRP algorithm with the proposed utility based caching strategy significantly outperforms the state of the art solutions when applied to a large university campus data under varying conditions.

Categories and Subject Descriptors

H.2 [Database Management];
H.2.8 [Database Applications]: Spatial databases and GIS;
G.2.2 [Graph Theory];


Multi-Geography Route Planning, MGRP, Caching, A* Algorithm

Downloadable Files

Paper: EDBT10_dvk.pdf
Presentation: EDBT10_dvk.ppt

BibTeX Entry

   author    = {Vidhya Balasubramanian and Dmitri V.\ Kalashnikov and
                Sharad Mehrotra and Nalini Venkatasubramanian},
   title     = {Efficient and Scalable Multi-Geography Route Planning},
   booktitle = {International Conference on Extending Database Technology (EDBT 2010)},
   year      = {2010},
   month     = {March 22--26},
   address   = {Lausanne, Switzerland}

Back to Kalashnikov's homepage

© 2011 Dmitri V. Kalashnikov. All Rights Reserved.