Publication Type:

Conference Paper

Source:

Proceedings of the 13th International Conference on Extending Database Technology, ACM, New York, NY, USA (2010)

ISBN:

9781605589459

URL:

http://doi.acm.org/10.1145/1739041.1739090

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.

Cite this Research Publication

Dr. Vidhya Balasubramanian, Kalashnikov, D. V., Mehrotra, S., and Venkatasubramanian, N., “Efficient and Scalable Multi-geography Route Planning”, in Proceedings of the 13th International Conference on Extending Database Technology, New York, NY, USA, 2010.