IBM Tokyo Research Laboratory
the Department of Information Science, University of Tokyo
Sumitomo Electric Industries
抄録
In geographical databases for navigation, users raise various types of queries concerning route guidance. The most fundamental query is a shortest-route query, but, as dynamical traffic information newly becomes available and the static geographical database of roads itself has grown up further, more flexible queries are required to realize a user-friendly interface meeting the current settings. One important query among them is a detour query which provides information about detours, say listing several candidates for useful detours. This paper first reviews algorithms for the shortest and k shortest paths, and discusses their extensions to detour queries. Algorithms for finding a realistic detour are given. The efficiency and property of the algorithms are examined through experiments on an actual road network.
Finding Useful Detours in Geographical Databases
Finding Useful Detours in Geographical Databases 1999.pdf
(531.2KB)
