Incremental and accuracy-aware personalized pagerank through scheduled approximation
As Personalized PageRank has been widely leveraged for ranking on a graph, the efficient computation of Personalized PageRank Vector (PPV) becomes a prominent issue. In this paper, we propose FastPPV, an approximate PPV computation algorithm that is incremental and accuracy-aware. Our approach hinge...
Saved in:
Main Authors: | , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2013
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/4071 https://ink.library.smu.edu.sg/context/sis_research/article/5074/viewcontent/p481_zhu.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-5074 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-50742018-07-20T04:57:03Z Incremental and accuracy-aware personalized pagerank through scheduled approximation ZHU, Fanwei FANG, Yuan CHANG, Kevin Chen-Chuan YING, Jing As Personalized PageRank has been widely leveraged for ranking on a graph, the efficient computation of Personalized PageRank Vector (PPV) becomes a prominent issue. In this paper, we propose FastPPV, an approximate PPV computation algorithm that is incremental and accuracy-aware. Our approach hinges on a novel paradigm of scheduled approximation: the computation is partitioned and scheduled for processing in an "organized" way, such that we can gradually improve our PPV estimation in an incremental manner, and quantify the accuracy of our approximation at query time. Guided by this principle, we develop an efficient hub based realization, where we adopt the metric of hub-length to partition and schedule random walk tours so that the approximation error reduces exponentially over iterations. Furthermore, as tours are segmented by hubs, the shared substructures between different tours (around the same hub) can be reused to speed up query processing both within and across iterations. Finally, we evaluate FastPPV over two real-world graphs, and show that it not only significantly outperforms two state-of-the-art baselines in both online and offline phrases, but also scale well on larger graphs. In particular, we are able to achieve near-constant time online query processing irrespective of graph size. 2013-08-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/4071 info:doi/10.14778/2536336.2536348 https://ink.library.smu.edu.sg/context/sis_research/article/5074/viewcontent/p481_zhu.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 Approximation errors Computation algorithm Constant time Efficient computation Graph sizes Personalized PageRank Random Walk Real-world graphs Databases and Information Systems Numerical Analysis and Scientific Computing |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Approximation errors Computation algorithm Constant time Efficient computation Graph sizes Personalized PageRank Random Walk Real-world graphs Databases and Information Systems Numerical Analysis and Scientific Computing |
spellingShingle |
Approximation errors Computation algorithm Constant time Efficient computation Graph sizes Personalized PageRank Random Walk Real-world graphs Databases and Information Systems Numerical Analysis and Scientific Computing ZHU, Fanwei FANG, Yuan CHANG, Kevin Chen-Chuan YING, Jing Incremental and accuracy-aware personalized pagerank through scheduled approximation |
description |
As Personalized PageRank has been widely leveraged for ranking on a graph, the efficient computation of Personalized PageRank Vector (PPV) becomes a prominent issue. In this paper, we propose FastPPV, an approximate PPV computation algorithm that is incremental and accuracy-aware. Our approach hinges on a novel paradigm of scheduled approximation: the computation is partitioned and scheduled for processing in an "organized" way, such that we can gradually improve our PPV estimation in an incremental manner, and quantify the accuracy of our approximation at query time. Guided by this principle, we develop an efficient hub based realization, where we adopt the metric of hub-length to partition and schedule random walk tours so that the approximation error reduces exponentially over iterations. Furthermore, as tours are segmented by hubs, the shared substructures between different tours (around the same hub) can be reused to speed up query processing both within and across iterations. Finally, we evaluate FastPPV over two real-world graphs, and show that it not only significantly outperforms two state-of-the-art baselines in both online and offline phrases, but also scale well on larger graphs. In particular, we are able to achieve near-constant time online query processing irrespective of graph size. |
format |
text |
author |
ZHU, Fanwei FANG, Yuan CHANG, Kevin Chen-Chuan YING, Jing |
author_facet |
ZHU, Fanwei FANG, Yuan CHANG, Kevin Chen-Chuan YING, Jing |
author_sort |
ZHU, Fanwei |
title |
Incremental and accuracy-aware personalized pagerank through scheduled approximation |
title_short |
Incremental and accuracy-aware personalized pagerank through scheduled approximation |
title_full |
Incremental and accuracy-aware personalized pagerank through scheduled approximation |
title_fullStr |
Incremental and accuracy-aware personalized pagerank through scheduled approximation |
title_full_unstemmed |
Incremental and accuracy-aware personalized pagerank through scheduled approximation |
title_sort |
incremental and accuracy-aware personalized pagerank through scheduled approximation |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2013 |
url |
https://ink.library.smu.edu.sg/sis_research/4071 https://ink.library.smu.edu.sg/context/sis_research/article/5074/viewcontent/p481_zhu.pdf |
_version_ |
1770574208582025216 |