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.