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
id sg-smu-ink.sis_research-8500
record_format dspace
spelling sg-smu-ink.sis_research-85002022-11-21T05:44:22Z Unified and incremental SimRank: Index-free approximation with scheduled principle (extended abstract) ZHU, Fanwei FANG, Yuan ZHANG, Kai CHANG, Kevin Chen-Chuan 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. 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. 2022-05-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/7497 info:doi/10.1109/ICDE53745.2022.00161 https://ink.library.smu.edu.sg/context/sis_research/article/8500/viewcontent/ICDE22_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
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
spellingShingle SimRank approximation
unification
index-free
scheduled principle
scalability
Databases and Information Systems
ZHU, Fanwei
FANG, Yuan
ZHANG, Kai
CHANG, Kevin Chen-Chuan
CAO, Hongtai
JIANG, Zhen
WU, Minghui
Unified and incremental SimRank: Index-free approximation with scheduled principle (extended abstract)
description 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.
format text
author ZHU, Fanwei
FANG, Yuan
ZHANG, Kai
CHANG, Kevin Chen-Chuan
CAO, Hongtai
JIANG, Zhen
WU, Minghui
author_facet ZHU, Fanwei
FANG, Yuan
ZHANG, Kai
CHANG, Kevin Chen-Chuan
CAO, Hongtai
JIANG, Zhen
WU, Minghui
author_sort ZHU, Fanwei
title Unified and incremental SimRank: Index-free approximation with scheduled principle (extended abstract)
title_short Unified and incremental SimRank: Index-free approximation with scheduled principle (extended abstract)
title_full Unified and incremental SimRank: Index-free approximation with scheduled principle (extended abstract)
title_fullStr Unified and incremental SimRank: Index-free approximation with scheduled principle (extended abstract)
title_full_unstemmed Unified and incremental SimRank: Index-free approximation with scheduled principle (extended abstract)
title_sort unified and incremental simrank: index-free approximation with scheduled principle (extended abstract)
publisher Institutional Knowledge at Singapore Management University
publishDate 2022
url https://ink.library.smu.edu.sg/sis_research/7497
https://ink.library.smu.edu.sg/context/sis_research/article/8500/viewcontent/ICDE22_UISim.pdf
_version_ 1770576358144999424