Fast Ad-Hoc Search Algorithm for Personalized PageRank

• FUJIWARA Yasuhiro

  NTT Software Innovation Center

• NAKATSUJI Makoto

  NTT Resonant

• SHIOKAWA Hiroaki

  University of Tsukuba

• MISHIMA Takeshi

  NTT Software Innovation Center

• ONIZUKA Makoto

  Osaka University

Abstract

Personalized PageRank (PPR) is a typical similarity metric between nodes in a graph, and node searches based on PPR are widely used. In many applications, graphs change dynamically, and in such cases, it is desirable to perform ad hoc searches based on PPR. An ad hoc search involves performing searches by varying the search parameters or graphs. However, as the size of a graph increases, the computation cost of performing an ad hoc search can become excessive. In this paper, we propose a method called Castanet that offers fast ad hoc searches of PPR. The proposed method features (1) iterative estimation of the upper and lower bounds of PPR scores, and (2) dynamic pruning of nodes that are not needed to obtain a search result. Experiments confirm that the proposed method does offer faster ad hoc PPR searches than existing methods.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E100.D (4), 610-620, 2017

  The Institute of Electronics, Information and Communication Engineers

Keywords

• Personalized PageRank
• ad-hoc
• fast
• algorithm

Details

• CRID: 1390282679355636352
• NII Article ID: 130005529913
• NII Book ID: AA10826272
• DOI: 10.1587/transinf.2016awi0002
• ISSN: 17451361
• ISSN: 09168532
• HANDLE: 2241/00146196
• Web Site: https://tsukuba.repo.nii.ac.jp/records/41249
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E100.D/4/E100.D_2016AWI0002/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • IRDB
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed