Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/81350
Full metadata record
DC FieldValueLanguage
dc.contributor.authorWang, Siboen
dc.contributor.authorTang, Youzeen
dc.contributor.authorXiao, Xiaokuien
dc.contributor.authorYang, Yinen
dc.contributor.authorLi, Zengxiangen
dc.date.accessioned2017-07-27T02:34:23Zen
dc.date.accessioned2019-12-06T14:29:00Z-
dc.date.available2017-07-27T02:34:23Zen
dc.date.available2019-12-06T14:29:00Z-
dc.date.issued2016en
dc.identifier.citationWang, S., Tang, Y., Xiao, X., Yang, Y., & Li, Z. (2016). HubPPR: Effective Indexing for Approximate Personalized PageRank. Proceedings of the VLDB Endowment, 10(3), 205-216.en
dc.identifier.issn2150-8097en
dc.identifier.urihttps://hdl.handle.net/10356/81350-
dc.description.abstractPersonalized PageRank (PPR) computation is a fundamental operation in web search, social networks, and graph analysis. Given a graph G, a source s, and a target t, the PPR query Π(s, t) returns the probability that a random walk on G starting from s terminates at t. Unlike global PageRank which can be effectively pre-computed and materialized, the PPR result depends on both the source and the target, rendering results materialization infeasible for large graphs. Existing indexing techniques have rather limited effectiveness; in fact, the current state-of-the-art solution, BiPPR, answers individual PPR queries without pre-computation or indexing, and yet it outperforms all previous index-based solutions. Motivated by this, we propose HubPPR, an effective indexing scheme for PPR computation with controllable tradeoffs for accuracy, query time, and memory consumption. The main idea is to pre-compute and index auxiliary information for selected hub nodes that are often involved in PPR processing. Going one step further, we extend HubPPR to answer top-k PPR queries, which returns the k nodes with the highest PPR values with respect to a source s, among a given set T of target nodes. Extensive experiments demonstrate that compared to the current best solution BiPPR, HubPPR achieves up to 10x and 220x speedup for PPR and top-k PPR processing, respectively, with moderate memory consumption. Notably, with a single commodity server, HubPPR answers a top-k PPR query in seconds on graphs with billions of edges, with high accuracy and strong result quality guarantees.en
dc.description.sponsorshipMOE (Min. of Education, S’pore)en
dc.format.extent12 p.en
dc.language.isoenen
dc.relation.ispartofseriesProceedings of the VLDB Endowmenten
dc.rightsThis work is licensed under the Creative Commons AttributionNonCommercial-NoDerivatives 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org.en
dc.subjectPersonalized PageRanken
dc.subjectIndexing schemeen
dc.titleHubPPR: Effective Indexing for Approximate Personalized PageRanken
dc.typeConference Paperen
dc.contributor.schoolSchool of Computer Science and Engineeringen
dc.contributor.conferenceProceedings of the VLDB Endowmenten
dc.identifier.doi10.14778/3021924.3021936en
dc.description.versionPublished versionen
item.fulltextWith Fulltext-
item.grantfulltextopen-
Appears in Collections:SCSE Conference Papers
Files in This Item:
File Description SizeFormat 
HubPPR _ Effective Indexing for Approximate Personalized PageRank.pdf563.24 kBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 10

41
Updated on Nov 29, 2022

Page view(s) 20

563
Updated on Dec 7, 2022

Download(s) 20

179
Updated on Dec 7, 2022

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.