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 Abstract 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]; Keywords Multi-Geography Route Planning, MGRP, Caching, A* Algorithm Downloadable Files Paper: EDBT10_dvk.pdf Presentation: EDBT10_dvk.ppt BibTeX Entry @inproceedings{EDBT10::dvk, 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.