Inferring Spatial Distance Rankings with Partial Knowledge on Routing Networks

Abstract

The most common problem on routing networks is to compute the shortest paths from a source vertex to a set of target vertices. A variation of it, with applications for recommender systems, asks to merely rank the target vertices with respect to the shortest distances from the source. A classic solution is Dijkstra’s algorithm; however, it is too slow for large but meaningful applications. A setting where the target vertices are fixed but the source vertex is only known at query time allows for preprocessing. Following the line of research on preprocessing the routing network to speed up the computation of shortest paths, we study in this article a novel approach tackling the problem of ranking the static set of target vertices on the routing network with regard to the distance from a given source vertex to these target vertices by leveraging preprocessing. Our approach allows us to generate a partial solution by pre-computing the distances between all targets so that a shortest-path algorithm does not have to determine the shortest path from the source to every target in general. Our proposal can be adopted for both static and time-dependent networks, and it can be used in conjunction with a general shortest-path algorithm. We can experimentally observe significant speed-ups when using our proposed techniques.

Keywords

• routing network
• quasimetrics
• time-dependence
• caching