Route Planning on Large Scale Dynamic Networks

摘要

Using indexes to find the shortest path can increase query efficiency thousands of times faster than the search-based methods. However, as the networks keep evolving in both the topology and edge weights, these indexes require time-consuming maintenance / re-construction, which stops them from applicable in practice, especially when the network large. This project aims to adapt the path indexes to large networks in the dynamic environments. Theoretically, this project reveals the relation between the graph partitioning / hierarchical partitioning and the path indexing, identifies the partition index strategies for index correctness guarantee, index maintenance meta-methods for all structures, and finally thoroughly decouple the partitioned dynamic methods into the previous three dimensions. Practically, it can serve as a guideline to form any partitioned path index according to the dynamic environment, application purposes, and network structure. As the evidence of the partitioned index theory, several new index structures are proposed based on it. Finally, this project further improves the system throughput by improving the index availability. In summary, this project is the key to efficiency for pathfinding.