I/O-Efficient Multi-Criteria Shortest Paths Query Processing on Large Graphs
Xinjie Zhou, Kai Jian Huang, Lei Li, Mengxuan Zhang, Xiaofang Zhou · IEEE Transactions on Knowledge and Data Engineering · 2024
Shortest path computation is a basic operation for many graph-based applications and has been extensively studied. However, most existing works only consider the optimal path of a single criterion but ignore real-world situations involving multiple criteria. This paper investigates a new Multi-Criteria Shortest Paths (MCSPs) problem, aiming to compute the shortest paths of all criteria between a vertex pair. It is significant for real-world applications such as GPS navigation and social network analysis. Nevertheless, the rapid growth of graph size or memory-limited devices poses a memory-constraint challenge, making the adaptation of existing methods extremely time-consuming. To solve the memory-constraint MCSPs problem, we propose a generalSTOP & SHAREscheme to synchronize the search speeds of all criteria for sharing partition accesses. Two algorithms calledOHPandMHP, adopting the one-hop strategy and partition exhaustive strategy, respectively, are proposed for implementing our scheme. Moreover, we develop two optimized algorithms,BMHPandBMHPS, to improve query efficiency by combiningMHPwith the bidirectional technique and a novelin-partition shortcut optimization. We also investigatepartition-oriented I/O management. Experimental studies on large real-world graphs demonstrate the effectiveness of the proposed methods over the multi-pass adaptations of the existing methods.