Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s00778-021-00705-1 | The VLDB Journal |
Keywords | DocType | Volume |
Shortest path, Graph embedding, Road network | Journal | 31 |
Issue | ISSN | Citations |
3 | 1066-8888 | 0 |
PageRank | References | Authors |
0.34 | 21 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tianyu Zhao | 1 | 17 | 3.06 |
| Shuai Huang | 2 | 0 | 0.34 |
| Yong Wang | 3 | 0 | 0.34 |
| Chengliang Chai | 4 | 124 | 15.45 |
| Guoliang Li | 5 | 3077 | 154.70 |