I/O-Efficient Multi-Criteria Shortest Paths Query Processing on Large Graphs

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 general STOP & SHARE scheme to synchronize the search speeds of all criteria for sharing partition accesses. Two algorithms called OHP and MHP, adopting the one-hop strategy and partition exhaustive strategy, respectively, are proposed for implementing our scheme. Moreover, we develop two optimized algorithms, BMHP and BMHPS, to improve query efficiency by combining MHP with the bidirectional technique and a novel in-partition shortcut optimization. We also investigate partition-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.