  This paper investigates two types of graph queries: {\em single source
distance (SSD)} queries and {\em 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 in $G$, while an SSSP query retrieves the shortest
path from $v$ to any other node. These two types of queries are fundamental
building blocks of numerous graph algorithms, and they 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. The only exceptions are a few 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 {\em
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.
