Proximity queries in time-dependent traffic networks using graph embeddings
Hans‐Peter Kriegel, Peer Kröger, Matthias Renz, Fabian D. Winter · 2011
In many GIS applications like location-based services proximity queries in traffic networks usually relate to the time two individuals need to reach each other instead of their "real" geographical distance. In graphs modelling street networks, the travel time needed for a path between two nodes is seldom constant, but rather depends on the traffic conditions and therefore on the time of day. In order to speed up common proximity queries in such a graph with time-dependent edge cost we use an intermediate filter step and propose two variants of a Lipschitz embedding to deal with time dependency and its effects on path finding. While the first one is a simple modification of a static embedding, the second is fully aware of the graphs's time component. Finally, both variants will be evaluated and compared to each other as well as to a simpler baseline.