Unified and incremental SimRank: Index-free approximation with scheduled principle (extended abstract)

SimRank is a popular link-based similarity measure on graphs. It enables a variety of applications with different modes of querying. In this paper, we propose UISim, a unified and incremental framework for all SimRank modes based on a scheduled approximation principle. UISim processes queries with i...

Full description

Saved in:
Bibliographic Details
Main Authors: ZHU, Fanwei, FANG, Yuan, ZHANG, Kai, CHANG, Kevin Chen-Chuan, CAO, Hongtai, JIANG, Zhen, WU, Minghui
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2022
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/7497
https://ink.library.smu.edu.sg/context/sis_research/article/8500/viewcontent/ICDE22_UISim.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary:SimRank is a popular link-based similarity measure on graphs. It enables a variety of applications with different modes of querying. In this paper, we propose UISim, a unified and incremental framework for all SimRank modes based on a scheduled approximation principle. UISim processes queries with incremental and prioritized exploration of the entire computation space, and thus allows flexible tradeoff of time and accuracy. On the other hand, it creates and shares common “building blocks” for online computation without relying on indexes, and thus is efficient to handle both static and dynamic graphs. Our experiments on various real-world graphs show that to achieve the same accuracy, UISim runs faster than its respective stateof-the-art baselines, and scales well on larger graphs.