Disk-based shortest path discovery using distance index over large dynamic graphs

详细信息    查看全文

• 作者：Jihye Hong ^{hjhh@khu.ac.kr} ; Kisung Park ^{kspark224@khu.ac.kr} ; Yongkoo Han ^{ykhan@khu.ac.kr} ; Mostofa Kamal Rasel ^{rasel@khu.ac.kr} ; Dawanga Vonvou ^{dawangav@khu.ac.kr} ; Young-Koo Lee ; ^{yklee@khu.ac.kr}
• 关键词：Dynamic graphs ; Graph searching ; Large graphs ; Shortest path discovery
• 刊名：Information Sciences
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：382-383
• 期：Complete
• 页码：201-215
• 全文大小：1966 K
• 卷排序：382

文摘

The persistent alternation of the internet world is changing networks rapidly. Shortest path discovery, especially over dynamic networks such as web page links, telephone or route networks, and ontologies, has received intense attention because of its importance for services in IoT. For example, when a new road is newly opened or becomes unavailable for any unexpected reason, the shortest paths must be recomputed. The system should respond promptly to its users with the updated recommended paths. In this paper, we propose a disk-based shortest path method that updates the shortest paths in a very large dynamic graph efficiently. The proposed method uses partial shortest paths as indices for efficient shortest path discovery. We classify the changes in the graph into four cases, such as the insertion or deletion of edges and the increase or decrease of edge weights. Our proposed strategy considers updating only the corresponding parts of the indices for each case. Our experiments on real-world dynamic datasets verify that the proposed framework updates the shortest paths 4 to 50 times faster than the existing type of framework.