This paper investigates two types of graph queries: single source distance (SSD) queries and single source shortest path (SSSP) queries. Given a node v in a graph G, an SSD query from v asks for the distance from v to any other node inG, while an SSSP query retrieves the shortest path from v to any other node. These two types of queries find important applications in graph analysis, especially in the computation of graph measures. Most of the existing solutions for SSD and SSSP queries, however, require that the input graph fits in the main memory, which renders them inapplicable for the massive disk-resident graphs commonly used in web and social applications. There are several techniques that are designed to be I/O efficient, but they all focus on undirected and/or unweighted graphs, and they only offer sub-optimal query efficiency. To address the deficiency of existing work, this paper presents Highways-on-Disk (HoD), a disk-based index that supports both SSD and SSSP queries on directed and weighted graphs. The key idea of HoD is to augment the input graph with a set of auxiliary edges, and exploit them during query processing to reduce I/O and computation costs. We experimentally evaluate HoD on both directed and undirected real-world graphs with up to billions of nodes and edges, and we demonstrate that HoD significantly outperforms alternative solutions in terms of query efficiency.
展开▼
