RNE: computing shortest paths using road network embedding

Computing the shortest paths and shortest path distances between two vertices on road networks is a core operation in many real-world applications, e.g., finding the closest taxi/hotel. However, existing techniques have several limitations. First, traditional Dijkstra-based methods have long latency and cannot meet the high-performance requirement. Second, existing indexing-based methods either involve huge index sizes or have poor performance. To address these limitations, in this paper we propose a learning-based method RNE which can efficiently compute an approximate shortest-path distance such that (1) the performance is super fast, e.g., taking 60-150 nanoseconds; (2) the error ratio of the approximate results is super small, e.g., below 0.7%; (3) scales well to large road networks, e.g., millions of nodes. The key idea is to first embed the road networks into a low dimensional space for capturing the distance relations between vertices, get an embedded vector for each vertex, and then perform a distance metric (L-1 metric) on the embedded vectors to approximate shortest-path distances. We propose a hierarchical model to represent the embedding, and design an effective method to train the model. We also design a fine-tuning method to judiciously select high-quality training data. In order to identify the shortest path between two vertices (not just the distance), we extend the vertex embedding from RNE and design the RNE+ model, which can output the approximate shortest path with low error and high efficiency. We also propose effective techniques to accelerate the training process of RNE+, including embedding pre-training, negative sampling and model fine-tuning. Extensive experiments on real-world datasets show that RNE and RNE+ significantly outperform the state-of-the-art methods.

Automated summary

This paper proposes a learning-based method RNE and RNE+ for computing the shortest paths between two vertices on road networks, with features of fast speed, high efficiency, and low error rate, which significantly outperform existing methods in experiments.