Unified and incremental SimRank: Index-free approximation with scheduled principle
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 a...
Saved in:
Main Authors: | , , , , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2021
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/8209 https://ink.library.smu.edu.sg/context/sis_research/article/9212/viewcontent/TKDE21_UISim.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-9212 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-92122023-10-13T09:24:02Z Unified and incremental SimRank: Index-free approximation with scheduled principle ZHU, Fanwei FANG, Yuan ZHANG, Kai CHANG, Kevin C.-C. CAO, Hongtai JIANG, Zhen WU, Minghui 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. 2021-09-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/8209 info:doi/10.1109/TKDE.2021.3111734 https://ink.library.smu.edu.sg/context/sis_research/article/9212/viewcontent/TKDE21_UISim.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University SimRank approximation unification index-free scheduled principle scalability Databases and Information Systems Theory and Algorithms |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
SimRank approximation unification index-free scheduled principle scalability Databases and Information Systems Theory and Algorithms |
spellingShingle |
SimRank approximation unification index-free scheduled principle scalability Databases and Information Systems Theory and Algorithms ZHU, Fanwei FANG, Yuan ZHANG, Kai CHANG, Kevin C.-C. CAO, Hongtai JIANG, Zhen WU, Minghui Unified and incremental SimRank: Index-free approximation with scheduled principle |
description |
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. |
format |
text |
author |
ZHU, Fanwei FANG, Yuan ZHANG, Kai CHANG, Kevin C.-C. CAO, Hongtai JIANG, Zhen WU, Minghui |
author_facet |
ZHU, Fanwei FANG, Yuan ZHANG, Kai CHANG, Kevin C.-C. CAO, Hongtai JIANG, Zhen WU, Minghui |
author_sort |
ZHU, Fanwei |
title |
Unified and incremental SimRank: Index-free approximation with scheduled principle |
title_short |
Unified and incremental SimRank: Index-free approximation with scheduled principle |
title_full |
Unified and incremental SimRank: Index-free approximation with scheduled principle |
title_fullStr |
Unified and incremental SimRank: Index-free approximation with scheduled principle |
title_full_unstemmed |
Unified and incremental SimRank: Index-free approximation with scheduled principle |
title_sort |
unified and incremental simrank: index-free approximation with scheduled principle |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2021 |
url |
https://ink.library.smu.edu.sg/sis_research/8209 https://ink.library.smu.edu.sg/context/sis_research/article/9212/viewcontent/TKDE21_UISim.pdf |
_version_ |
1781793934066843648 |