  Previous work has shown the effectiveness of random walk hitting times as a
measure of dissimilarity in a variety of graph-based learning problems such as
collaborative filtering, query suggestion or finding paraphrases. However,
application of hitting times has been limited to small datasets because of
computational restrictions. This paper develops a new approximation algorithm
with which hitting times can be computed on very large, disk-resident graphs,
making their application possible to problems which were previously out of
reach. This will potentially benefit a range of large-scale problems.
