File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: BATON: Batch One-Hop Personalized PageRanks with Efficiency and Accuracy

TitleBATON: Batch One-Hop Personalized PageRanks with Efficiency and Accuracy
Authors
KeywordsTwitter
Art
Monte Carlo methods
Heuristic algorithms
Pins
Issue Date2019
PublisherInstitute of Electrical and Electronics Engineers . The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp/?punumber=69
Citation
IEEE Transactions on Knowledge and Data Engineering, 2019, Epub How to Cite?
AbstractPersonalized PageRank (PPR) is a classic measure of the relevance among different nodes in a graph, and has been applied in numerous systems, such as Twitter's Who-To-Follow. Existing work on PPR has mainly focused on three general types of queries, namely, single-pair PPR, single-source PPR, and all-pair PPR. However, we observe that there are applications that rely on a new query type (referred to as batch one-hop PPR), which takes as input a set S of source nodes and, for each node s∈S and each of s 'S neighbor v , asks for the PPR value of v with respect to s . None of the existing PPR algorithms is able to efficiently process batch one-hop queries, due to the inherent differences between batch one-hop PPR and the three general query types. To address the limitations of existing algorithms, this paper presents Baton, an algorithm for batch one-hop PPR that offers both strong theoretical guarantees and practical efficiency. Baton leverages the characteristics of one-hop PPR to avoid unnecessary computation, and it incorporates advanced mechanisms to improve the cost-effectiveness of PPR derivations. Extensive experiments on benchmark datasets show that Baton is up to 3 orders of magnitude faster than the state of the art, while offering the same accuracy.
Persistent Identifierhttp://hdl.handle.net/10722/277564
ISSN
2019 Impact Factor: 4.935
2015 SCImago Journal Rankings: 2.087

 

DC FieldValueLanguage
dc.contributor.authorLUO, S-
dc.contributor.authorXiao, X-
dc.contributor.authorLin, W-
dc.contributor.authorKao, B-
dc.date.accessioned2019-09-20T08:53:28Z-
dc.date.available2019-09-20T08:53:28Z-
dc.date.issued2019-
dc.identifier.citationIEEE Transactions on Knowledge and Data Engineering, 2019, Epub-
dc.identifier.issn1041-4347-
dc.identifier.urihttp://hdl.handle.net/10722/277564-
dc.description.abstractPersonalized PageRank (PPR) is a classic measure of the relevance among different nodes in a graph, and has been applied in numerous systems, such as Twitter's Who-To-Follow. Existing work on PPR has mainly focused on three general types of queries, namely, single-pair PPR, single-source PPR, and all-pair PPR. However, we observe that there are applications that rely on a new query type (referred to as batch one-hop PPR), which takes as input a set S of source nodes and, for each node s∈S and each of s 'S neighbor v , asks for the PPR value of v with respect to s . None of the existing PPR algorithms is able to efficiently process batch one-hop queries, due to the inherent differences between batch one-hop PPR and the three general query types. To address the limitations of existing algorithms, this paper presents Baton, an algorithm for batch one-hop PPR that offers both strong theoretical guarantees and practical efficiency. Baton leverages the characteristics of one-hop PPR to avoid unnecessary computation, and it incorporates advanced mechanisms to improve the cost-effectiveness of PPR derivations. Extensive experiments on benchmark datasets show that Baton is up to 3 orders of magnitude faster than the state of the art, while offering the same accuracy.-
dc.languageeng-
dc.publisherInstitute of Electrical and Electronics Engineers . The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp/?punumber=69-
dc.relation.ispartofIEEE Transactions on Knowledge and Data Engineering-
dc.rightsIEEE Transactions on Knowledge and Data Engineering. Copyright © Institute of Electrical and Electronics Engineers .-
dc.rights©20xx IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.-
dc.subjectTwitter-
dc.subjectArt-
dc.subjectMonte Carlo methods-
dc.subjectHeuristic algorithms-
dc.subjectPins-
dc.titleBATON: Batch One-Hop Personalized PageRanks with Efficiency and Accuracy-
dc.typeArticle-
dc.identifier.emailKao, B: kao@cs.hku.hk-
dc.identifier.authorityKao, B=rp00123-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1109/TKDE.2019.2912606-
dc.identifier.scopuseid_2-s2.0-85091236863-
dc.identifier.hkuros305601-
dc.identifier.spage1-
dc.identifier.epage1-
dc.publisher.placeUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats