SCIENCE@home

Scalable Single-Source SimRank Computation for Large Graphs

Xingkun Gao,Nianyuan Bao,Jie Liu,Jie Tang,Gangshan Wu

Published 2016 in International Conference on Parallel and Distributed Systems

ABSTRACT

SimRank is an effective similarity measure between vertices in a graph, which has become a fundamental technique in graph analytics. Despite its popularity, computation of SimRank is often costly in both space and time, especially with the ever growing scale of graph data nowadays. In this paper, we focus on the computation of Single-Source SimRank: given a query vertex, return the similarities between this vertex and any other vertices in the graph. The traditional centralized SimRank algorithms are not efficient for this problem. To fully utilize the computing power of modern distributed systems, we propose sssSimRank, an efficient distributed algorithm based on the random walk model. Our algorithm achieves scalability via minimizing the total number, the space cost, and the matching time of random walks. We implement our approach on the popular distributed processing platform Spark. Experimental results demonstrate the effectiveness, efficiency and scalability of our method.

PUBLICATION RECORD

  • Publication year

    2016

  • Venue

    International Conference on Parallel and Distributed Systems

  • Publication date

    2016-12-01

  • Fields of study

    Computer Science

  • Identifiers
    DOI 10.1109/ICPADS.2016.0143
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-20 of 20 references · Page 1 of 1

CITED BY