  A reachability oracle (or hop labeling) assigns each vertex v two sets of
vertices: Lout(v) and Lin(v), such that u reaches v iff Lout(u) \cap Lin(v)
\neq \emptyset. Despite their simplicity and elegance, reachability oracles
have failed to achieve efficiency in more than ten years since their
introduction: the main problem is high construction cost, which stems from a
set-cover framework and the need to materialize transitive closure. In this
paper, we present two simple and efficient labeling algorithms,
Hierarchical-Labeling and Distribution-Labeling, which can work onmassive
real-world graphs: their construction time is an order of magnitude faster than
the setcover based labeling approach, and transitive closure materialization is
not needed. On large graphs, their index sizes and their query performance can
now beat the state-of-the-art transitive closure compression and online search
approaches.
