  Single-source and top-$k$ SimRank queries are two important types of
similarity search in graphs with numerous applications in web mining, social
network analysis, spam detection, etc. A plethora of techniques have been
proposed for these two types of queries, but very few can efficiently support
similarity search over large dynamic graphs, due to either significant
preprocessing time or large space overheads.
  This paper presents ProbeSim, an index-free algorithm for single-source and
top-$k$ SimRank queries that provides a non-trivial theoretical guarantee in
the absolute error of query results. ProbeSim estimates SimRank similarities
without precomputing any indexing structures, and thus can naturally support
real-time SimRank queries on dynamic graphs. Besides the theoretical guarantee,
ProbeSim also offers satisfying practical efficiency and effectiveness due to
several non-trivial optimizations. We conduct extensive experiments on a number
of benchmark datasets, which demonstrate that our solutions significantly
outperform the existing methods in terms of efficiency and effectiveness.
Notably, our experiments include the first empirical study that evaluates the
effectiveness of SimRank algorithms on graphs with billion edges, using the
idea of pooling.
