Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs

Understand

Given a graph G and a node u in G, a single source SimRank query evaluates the similarity between u and every node v in G.

• Existing approaches to single source SimRank computation incur either long query response time, or expensive pre-computation, which needs to be performed again whenever the graph G changes.
• Consequently, to our knowledge none of them is ideal for scenarios in which (i) query processing must be done in realtime, and (ii) the underlying graph G is massive, with frequent updates.
• Motivated by this, we propose SimPush, a novel algorithm that answers single source SimRank queries without any pre-computation, and at the same time achieves significantly higher query processing speed than even the fastest known index-based solutions.