{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T15:44:21Z","timestamp":1781019861474,"version":"3.54.1"},"reference-count":82,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62372308"],"award-info":[{"award-number":["62372308"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100021171","name":"GuangDong Basic and Applied Basic Research Foundation","doi-asserted-by":"crossref","award":["2023A1515011619"],"award-info":[{"award-number":["2023A1515011619"]}],"id":[{"id":"10.13039\/501100021171","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,10,1]]},"abstract":"<jats:p>\n                    PageRank is a commonly used measurement in a wide range of applications, including search engines, recommendation systems, and social networks. However, this measurement suffers from huge computational overhead, which cannot be scaled to large graphs. Although many approximate algorithms have been proposed for computing PageRank values, these algorithms are either (i) not efficient or (ii) not accurate. Worse still, some of them cannot provide estimated PageRank values for all the vertices. In this paper, we first propose the CUR-Trans algorithm, which can reduce the time complexity for computing PageRank values and has lower error bound than existing matrix approximation-based PageRank algorithms. Then, we develop the\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    -Approx algorithm to further reduce the time complexity for computing this measurement. Experiment results on three large-scale graphs show that both the CUR-Trans algorithm and the\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    -Approx algorithm achieve the lowest response time for computing PageRank values with the best accuracy (for the CUR-Trans algorithm) or the competitive accuracy (for the\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    -Approx algorithm). Besides, the two proposed algorithms are able to provide estimated PageRank values for all the vertices.\n                  <\/jats:p>","DOI":"10.1145\/3677132","type":"journal-article","created":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T17:41:44Z","timestamp":1727718104000},"page":"1-26","source":"Crossref","is-referenced-by-count":2,"title":["Efficient and Accurate PageRank Approximation on Large Graphs"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-2932-2497","authenticated-orcid":false,"given":"Siyue","family":"Wu","sequence":"first","affiliation":[{"name":"Shenzhen University, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7901-9876","authenticated-orcid":false,"given":"Dingming","family":"Wu","sequence":"additional","affiliation":[{"name":"Shenzhen University, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-2840-444X","authenticated-orcid":false,"given":"Junyi","family":"Quan","sequence":"additional","affiliation":[{"name":"Shenzhen University, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5851-7967","authenticated-orcid":false,"given":"Tsz Nam","family":"Chan","sequence":"additional","affiliation":[{"name":"Shenzhen University, Shenzhen, HK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4617-2882","authenticated-orcid":false,"given":"Kezhong","family":"Lu","sequence":"additional","affiliation":[{"name":"Shenzhen University, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,9,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Ziv Bar-Yossef andLi-Tal Mashiach. 2008. Local approximation of pagerank and reverse pagerank. In CIKM. 279--288.","DOI":"10.1145\/1458082.1458122"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-21534-6_1"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2020.1858297"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643799"},{"key":"e_1_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Bahman Bahmani Kaushik Chakrabarti and Dong Xin. 2011. Fast personalized PageRank on MapReduce. In SIGMOD. 973--984.","DOI":"10.1145\/1989323.1989425"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1201\/b17040"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Andr\u00e1s A. Bencz\u00far K\u00e1roly Csalog\u00e1ny and Tam\u00e1s Sarl\u00f3s. 2005. On the feasibility of low-rank approximation for personalized PageRank. In WWW. 972--973.","DOI":"10.1145\/1062745.1062824"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1052934.1052938"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.587"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/pds.2021.599"},{"key":"e_1_2_2_11_1","unstructured":"L. A. Breyer. 2002. Markovian page ranking distributions: some theory and simulations. Technical Report."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_2_13_1","series-title":"SIAM journal on Matrix Analysis and Applications","volume-title":"On the tensor SVD and the optimal low rank orthogonal approximation of tensors","author":"Chen Jie","year":"2009","unstructured":"Jie Chen and Yousef Saad. 2009. On the tensor SVD and the optimal low rank orthogonal approximation of tensors. SIAM journal on Matrix Analysis and Applications, Vol. 30 (2009), 1709--1734."},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Yen-Yu Chen Qingqing Gan and Torsten Suel. 2004. Local methods for estimating pagerank values. In CIKM. 381--389.","DOI":"10.1145\/1031171.1031248"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Zhen Chen Xingzhi Guo Baojian Zhou Deqing Yang and Steven Skiena. 2023. Accelerating Personalized PageRank Vector Computation. In KDD. 262--273.","DOI":"10.1145\/3580305.3599251"},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Eunjoon Cho Seth A Myers and Jure Leskovec. 2011. Friendship and mobility: user movement in location-based social networks. In SIGKDD. 1082--1090.","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2014.2380315"},{"key":"e_1_2_2_18_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to algorithms. MIT press."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129108"},{"key":"e_1_2_2_20_1","volume-title":"Dhillon","author":"Davis Jason V.","year":"2006","unstructured":"Jason V. Davis and Inderjit S. Dhillon. 2006. Estimating the global pagerank of web communities. In SIGKDD. 116--125."},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Petros Drineas and Ravi Kannan. 2001. Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication. In FOCS. 452--459.","DOI":"10.1109\/SFCS.2001.959921"},{"key":"e_1_2_2_22_1","unstructured":"Petros Drineas and Ravi Kannan. 2003. Pass efficient algorithms for approximating large matrices. In ACM-SIAM. 223--232."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442684"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442696"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442702"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/07070471X"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02288367"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958573.1958588"},{"key":"e_1_2_2_29_1","volume-title":"A generalization of the Eckart-Young-Mirsky matrix approximation theorem. Linear Algebra and its applications","author":"Golub Gene H","year":"1987","unstructured":"Gene H Golub, Alan Hoffman, and Gilbert W Stewart. 1987. A generalization of the Eckart-Young-Mirsky matrix approximation theorem. Linear Algebra and its applications, Vol. 88 (1987), 317--327."},{"key":"e_1_2_2_30_1","volume-title":"Handbook for Automatic Computation: Volume II: Linear Algebra","author":"Golub Gene H","unstructured":"Gene H Golub and Christian Reinsch. 1971. Singular value decomposition and least squares solutions. In Handbook for Automatic Computation: Volume II: Linear Algebra. Springer, 134--151."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2014.09.022"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-020-2649-2"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.micpro.2016.10.002"},{"key":"e_1_2_2_34_1","unstructured":"Taher Haveliwala et al. 1999. Efficient computation of PageRank. Technical Report. Citeseer."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04150-6"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461554"},{"key":"e_1_2_2_37_1","volume-title":"Retrieved July","volume":"25","author":"Jackson J","year":"2013","unstructured":"J Jackson. 2013. Facebook?s graph search puts Apache Giraph on the map. Retrieved July, Vol. 25 (2013), 2015."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/582415.582418"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2003.12.008"},{"key":"e_1_2_2_40_1","unstructured":"Sepandar D Kamvar Taher H Haveliwala Christopher Manning and Gene H Golub. 2003 a. Exploiting the block structure of the web for computing pagerank. Technical Report."},{"key":"e_1_2_2_41_1","doi-asserted-by":"crossref","unstructured":"Sepandar D. Kamvar Taher H. Haveliwala Christopher D. Manning and Gene H. Golub. 2003 b. Extrapolation methods for accelerating PageRank computations. In WWW. 261--270.","DOI":"10.1145\/775152.775190"},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"Seunghwa Kang Joseph Nke and Brad Rees. 2022. Analyzing Multi-trillion Edge Graphs on Large GPU Clusters: A Case Study with PageRank. In HPEC. 1--7.","DOI":"10.1109\/HPEC55821.2022.9926341"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144598334138"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1080\/03081087.2016.1267104"},{"key":"e_1_2_2_45_1","volume-title":"Advances in Computers.","author":"Kotlar Milovs","unstructured":"Milovs Kotlar, Marija Punt, and Veljko Milutinovi\u0107. 2022. Energy efficient implementation of tensor operations using dataflow paradigm for machine learning. In Advances in Computers. Vol. 126. 151--199."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2017.05.001"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129091"},{"key":"e_1_2_2_48_1","volume-title":"James Tin-Yau Kwok, and Baoliang L\u00fc","author":"Li Mu","year":"2010","unstructured":"Mu Li, James Tin-Yau Kwok, and Baoliang L\u00fc. 2010. Making large-scale Nystr\u00f6m approximation possible. In ICML. 631."},{"key":"e_1_2_2_49_1","volume-title":"Tutorial: Complexity analysis of singular value decomposition and its variants. arXiv","author":"Li Xiaocan","year":"2019","unstructured":"Xiaocan Li, Shuo Wang, and Yinghao Cai. 2019. Tutorial: Complexity analysis of singular value decomposition and its variants. arXiv (2019)."},{"key":"e_1_2_2_50_1","doi-asserted-by":"crossref","unstructured":"Meihao Liao Rong-Hua Li Qiangqiang Dai and Guoren Wang. 2022. Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach. In SIGMOD. 2048--2061.","DOI":"10.1145\/3514221.3526140"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0691-1"},{"key":"e_1_2_2_52_1","volume-title":"A rigorous introduction to linear models. arXiv","author":"Jun Lu.","year":"2021","unstructured":"Jun Lu. 2021. A rigorous introduction to linear models. arXiv (2021)."},{"key":"e_1_2_2_53_1","volume-title":"Matrix decomposition and applications. arXiv","author":"Jun Lu.","year":"2022","unstructured":"Jun Lu. 2022. Matrix decomposition and applications. arXiv (2022)."},{"key":"e_1_2_2_54_1","doi-asserted-by":"crossref","unstructured":"Siqiang Luo. 2019. Distributed PageRank Computation: An Improved Theoretical Study. In AAAI. 4496--4503.","DOI":"10.1609\/aaai.v33i01.33014496"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2022.05.108"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0803205106"},{"key":"e_1_2_2_57_1","volume-title":"McAuley and Jure Leskovec","author":"Julian","year":"2012","unstructured":"Julian J. McAuley and Jure Leskovec. 2012. Learning to Discover Social Circles in Ego Networks. In NIPS. 548--556."},{"key":"e_1_2_2_58_1","doi-asserted-by":"crossref","unstructured":"Alan Mislove Massimiliano Marcon P. Krishna Gummadi Peter Druschel and Bobby Bhattacharjee. 2007. Measurement and analysis of online social networks. In SIGCOMM. 29--42.","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3175814"},{"key":"e_1_2_2_60_1","volume-title":"Fast and stable randomized low-rank matrix approximation. arXiv:2009.11392","author":"Nakatsukasa Yuji","year":"2020","unstructured":"Yuji Nakatsukasa. 2020. Fast and stable randomized low-rank matrix approximation. arXiv:2009.11392 (2020)."},{"key":"e_1_2_2_61_1","volume-title":"Pablo Ignacio Fierens, and J. Ignacio Alvarez-Hamelin","author":"Orlicki Jos\u00e9 Ignacio","year":"2008","unstructured":"Jos\u00e9 Ignacio Orlicki, Pablo Ignacio Fierens, and J. Ignacio Alvarez-Hamelin. 2008. Faceted Ranking of Egos in Collaborative Tagging Systems. CoRR, Vol. abs\/0809.4668 (2008)."},{"key":"e_1_2_2_62_1","volume-title":"Pablo Ignacio Fierens, and J. Ignacio Alvarez-Hamelin","author":"Orlicki Jos\u00e9 Ignacio","year":"2009","unstructured":"Jos\u00e9 Ignacio Orlicki, Pablo Ignacio Fierens, and J. Ignacio Alvarez-Hamelin. 2009. Faceted Ranking in Collaborative Tagging Systems - Efficient Algorithms for Ranking Users based on a Set of Tags. In WEBIST. 626--633."},{"key":"e_1_2_2_63_1","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1998. The pagerank citation ranking: Bring order to the web. Technical Report. Technical report stanford University."},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(00)00120-8"},{"key":"e_1_2_2_65_1","volume-title":"Full rank factorization of matrices. Mathematics magazine","author":"Piziak R","year":"1999","unstructured":"R Piziak and PL Odell. 1999. Full rank factorization of matrices. Mathematics magazine, Vol. 72 (1999), 193--201."},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.04.003"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2016.20"},{"key":"e_1_2_2_68_1","doi-asserted-by":"crossref","unstructured":"Min Tao Xinmin Yang Gao Gu and Bohan Li. 2020. Paper recommend based on LDA and PageRank. In ICAIS. 571--584.","DOI":"10.1007\/978-981-15-8101-4_51"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2019.02.066"},{"key":"e_1_2_2_70_1","doi-asserted-by":"crossref","unstructured":"Hanghang Tong Christos Faloutsos and Jia-Yu Pan. 2006. Fast Random Walk with Restart and Its Applications. In ICDM. 613--622.","DOI":"10.1109\/ICDM.2006.70"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523216"},{"key":"e_1_2_2_73_1","doi-asserted-by":"crossref","unstructured":"Sibo Wang and Yufei Tao. 2018. Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks. In SIGMOD. 1113--1127.","DOI":"10.1145\/3183713.3196919"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360902"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-27137-8_8"},{"key":"e_1_2_2_76_1","doi-asserted-by":"crossref","unstructured":"Yao Wu and Louiqa Raschid. 2009. ApproxRank: Estimating Rank for a Subgraph. In ICDE. 54--65.","DOI":"10.1109\/ICDE.2009.108"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.3390\/math11153320"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1007\/s40314-016-0338-4"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484427"},{"key":"e_1_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.110"},{"key":"e_1_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1080\/03081087.2014.933219"},{"key":"e_1_2_2_82_1","volume-title":"Bader","author":"Zhou Shijie","year":"2017","unstructured":"Shijie Zhou, Kartik Lakhotia, Shreyas G. Singapura, Hanqing Zeng, Rajgopal Kannan, Viktor K. Prasanna, James Fox, Euna Kim, Oded Green, and David A. Bader. 2017. Design and implementation of parallel PageRank on multicore platforms. In HPEC. 1--6."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677132","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3677132","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:11:58Z","timestamp":1774977118000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677132"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,30]]},"references-count":82,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,1]]}},"alternative-id":["10.1145\/3677132"],"URL":"https:\/\/doi.org\/10.1145\/3677132","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,30]]}}}