Publication Type
Journal Article
Version
acceptedVersion
Publication Date
9-2021
Abstract
SimRank is a popular link-based similarity measure on graphs. It enables a variety of applications with different modes of querying (e.g., single-pair, single-source and all-pair modes). 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 state-of-the-art baselines, and scales well on larger graphs.
Keywords
SimRank approximation, unification, index-free, scheduled principle, scalability
Discipline
Databases and Information Systems | Theory and Algorithms
Research Areas
Intelligent Systems and Optimization
Publication
IEEE Transactions on Knowledge and Data Engineering
Volume
35
Issue
3
First Page
3195
Last Page
3210
ISSN
1041-4347
Identifier
10.1109/TKDE.2021.3111734
Publisher
Institute of Electrical and Electronics Engineers
Citation
ZHU, Fanwei; FANG, Yuan; ZHANG, Kai; CHANG, Kevin C.-C.; CAO, Hongtai; JIANG, Zhen; and WU, Minghui.
Unified and incremental SimRank: Index-free approximation with scheduled principle. (2021). IEEE Transactions on Knowledge and Data Engineering. 35, (3), 3195-3210.
Available at: https://ink.library.smu.edu.sg/sis_research/8209
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/TKDE.2021.3111734