Spatio-temporal network databases and routing algorithms: a summary of results

摘要: Spatio-temporal networks are spatial whose topology and parameters change with time. These important due to many critical applications such as emergency traffic planning route finding services there is an immediate need for models that support the design of efficient algorithms computing frequent queries on networks. This problem challenging potentially conflicting requirements model simplicity algorithms. Time expanded which have been used dynamic employ replication network across time instants, resulting in high storage overhead computationally expensive. In contrast, proposed time-aggregated graphs do not replicate nodes edges time; rather they allow properties be modeled a series. Since does entire graph every instant time, it uses less memory common operations (e.g. connectivity, shortest path) more than those One query spatio-temporal computation paths. Shortest paths can computed either given start or find path leads least travel journeys (best journeys). Developing varying because these always display greedy property optimal substructure, making techniques like programming inapplicable. this paper, we propose computations both contexts. We present analytical cost provide experimental comparison performance existing