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

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/TKDE.2021.3111734

Share

COinS