Efficient SimRank Computation via Linearization

Abstract

SimRank, proposed by Jeh and Widom, provides a good similarity measure that has been successfully used in numerous applications. While there are many algorithms proposed for computing SimRank, their computational costs are very high. In this paper, we propose a new computational technique, "SimRank linearization," for computing SimRank, which converts the SimRank problem to a linear equation problem. By using this technique, we can solve many SimRank problems, such as single-pair compuation, single-source computation, all-pairs computation, top k searching, and similarity join problems, efficiently.

46 pages, journal version of our papers appeared in SIGMOD14 and ICDE15

References in corpus (2)

• Simrank++: Query rewriting through link analysis of the click graph
• Similarity Join Size Estimation using Locality Sensitive Hashing

Cited by in corpus (6)

• Personalized PageRank to a Target Node, Revisited
• PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs
• ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs
• Exact Single-Source SimRank Computation on Large Graphs
• SLING: A Near-Optimal Index Structure for SimRank
• Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs