Managing Spatial Graph Dependencies in Large Volumes of Traffic Data for Travel-Time Prediction
The exploration of the potential correlations of traffic conditions between roads in large urban networks, which is of pro-found importance for achieving accurate traffic prediction, often implies high computational complexity due to the implicated network topology. Hence, focal methods are required for dealing with the urban network complexity, reducing the performance requirements that are associated to the classical network search techniques (e.g. Breadth First Search). This paper introduces a graph theory-based technique for managing spatial dependencies between roads of the same network. In particular, after representing the traffic network as a graph, the local neighbors of each road are extracted using Breadth First Search graph traversal algorithm, and also a lower com-plexity variant of it. A Pearson product-moment correlation coefficient based metric is applied on the selected graph nodes for a pre-scribed number of level sets of neighbors. In order to evaluate the impact of the new method to the traffic prediction accuracy achieved, the most correlated roads are used to build a STARIMA model taking also into account the possible time delays of traffic conditions between the inter-related roads. The proposed technique is benchmarked using traffic data from two different cities: Berlin (Germany) and Thessaloniki (Greece). Benchmark results indicate not only significant improvement on the computational time re-quired for calculating traffic correlation metric values, but also reveal that a different variant works better in different network topol-ogies, after comparison to third party approaches.