Computing shortest path distances based on cluster-pairs

Abstract

In this thesis we present a new lookup based shortest path distance computation scheme. Like many other lookup based schemes, this new approach consists of two stages, a preprocessing and a query stage. After the properties, which need to be met by the results of the preprocessing, are formally defined, we propose different preprocessing procedures as well as procedures which are able to use those results to calculate shortest path distances. The proposed new query procedure is able to decide whether a given query can be answered when the preprocessed data is incomplete. This makes it possible to prune the preprocessed data according to arbitrary memory constraints, while a speed up of orders of magnitude in comparison to conventional techniques can be achieved.