{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T03:06:03Z","timestamp":1787022363241,"version":"build-2736575974"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,9]]},"abstract":"<jats:p>\n                    Despite its popularity, SimRank is computationally costly, in both time and space. In particular, its recursive nature poses a great challenge in using modern distributed computing power, and also prevents querying similarities individually. Existing solutions suffer greatly from these practical issues. In this paper, we break such dependency for maximum efficiency possible. Our method consists of offline and online phases. In offline phase, a length-\n                    <jats:italic>n<\/jats:italic>\n                    indexing vector is derived by solving a linear system in parallel. At online query time, the similarities are computed instantly from the index vector. Throughout, the Monte Carlo method is used to maximally reduce time and space. Our algorithm, called CloudWalker, is highly parallelizable, with only linear time and space. Remarkably, it responses to both single-pair and single-source queries in constant time. CloudWalker is orders of magnitude more efficient and scalable than existing solutions for large-scale problems. Implemented on Spark with 10 machines and tested on the web-scale clue-web graph with 1 billion nodes and 43 billion edges, it takes 110 hours for offline indexing, 64 seconds for a single-pair query, and 188 seconds for a single-source query. To the best of our knowledge, our work is the first to report results on clue-web, which is 10x larger than the largest graph ever reported for SimRank computation.\n                  <\/jats:p>","DOI":"10.14778\/2850469.2850472","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T09:10:31Z","timestamp":1454317831000},"page":"24-35","source":"Crossref","is-referenced-by-count":32,"title":["Walking in the cloud"],"prefix":"10.14778","volume":"9","author":[{"given":"Zhenguo","family":"Li","sequence":"first","affiliation":[{"name":"Huawei Noah's Ark Lab, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qin","family":"Liu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiefeng","family":"Cheng","sequence":"additional","affiliation":[{"name":"Huawei Noah's Ark Lab, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John C. S.","family":"Lui","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apache Spark - Lightning-Fast Cluster Computing. http:\/\/spark.apache.org\/.  Apache Spark - Lightning-Fast Cluster Computing. http:\/\/spark.apache.org\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2351316.2351321"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113362"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28396"},{"key":"e_1_2_1_7_1","volume-title":"Introduction to algorithms","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to algorithms . MIT press , 2009 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. MIT press, 2009."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00022-5"},{"key":"e_1_2_1_9_1","first-page":"12","article-title":"Random walks and electric networks","volume":"10","author":"Doyle P. G.","year":"1984","unstructured":"P. G. Doyle and J. L. Snell . Random walks and electric networks . AMC , 10 : 12 , 1984 . P. G. Doyle and J. L. Snell. Random walks and electric networks. AMC, 10:12, 1984.","journal-title":"AMC"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060839"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.46"},{"key":"e_1_2_1_12_1","volume-title":"Matrix computations","author":"Golub G. H.","year":"2012","unstructured":"G. H. Golub and C. F. Van Loan . Matrix computations , volume 3 . JHU Press , 2012 . G. H. Golub and C. F. Van Loan. Matrix computations, volume 3. JHU Press, 2012."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835874"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557067"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610526"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_18_1","unstructured":"J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014.  J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739098"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.Congress.2013.26"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.50"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0168-8"},{"key":"e_1_2_1_23_1","volume-title":"Efficient SimRank computation via linearization. CoRR, abs\/1411.7228","author":"Maehara T.","year":"2014","unstructured":"T. Maehara , M. Kusumoto , and K. Kawarabayashi . Efficient SimRank computation via linearization. CoRR, abs\/1411.7228 , 2014 . T. Maehara, M. Kusumoto, and K. Kawarabayashi. Efficient SimRank computation via linearization. CoRR, abs\/1411.7228, 2014."},{"key":"e_1_2_1_24_1","volume-title":"The PageRank citation ranking: Bringing order to the web. Technical report","author":"Page L.","year":"1999","unstructured":"L. Page , S. Brin , R. Motwani , and T. Winograd . The PageRank citation ranking: Bringing order to the web. Technical report , 1999 . L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, 1999."},{"issue":"11","key":"e_1_2_1_25_1","first-page":"714","article-title":"On link-based similarity join","volume":"4","author":"Sun L.","year":"2011","unstructured":"L. Sun , R. Cheng , X. Li , D. Cheung , and J. Han . On link-based similarity join . VLDB , 4 ( 11 ): 714 -- 725 , 2011 . L. Sun, R. Cheng, X. Li, D. Cheung, and J. Han. On link-based similarity join. VLDB, 4(11):714--725, 2011.","journal-title":"VLDB"},{"key":"e_1_2_1_26_1","volume-title":"CVPR","author":"Wu X.-M.","year":"2012","unstructured":"X.-M. Wu , Z. Li , and S.-F. Chang . New insights into laplacian similarity search . In CVPR , 2012 . X.-M. Wu, Z. Li, and S.-F. Chang. New insights into laplacian similarity search. In CVPR, 2012."},{"key":"e_1_2_1_27_1","volume-title":"NIPS","author":"Wu X.-M.","year":"2012","unstructured":"X.-M. Wu , Z. Li , A. M. So , J. Wright , and S.-F. Chang . Learning with partially absorbing random walks . In NIPS , 2012 . X.-M. Wu, Z. Li, A. M. So, J. Wright, and S.-F. Chang. Learning with partially absorbing random walks. In NIPS, 2012."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735489"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-010-0100-6"},{"key":"e_1_2_1_30_1","volume-title":"NSDI","author":"Zaharia M.","year":"2012","unstructured":"M. Zaharia Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing . In NSDI , 2012 . M. Zaharia et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In NSDI, 2012."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2850469.2850472","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T04:47:38Z","timestamp":1672202858000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2850469.2850472"}},"subtitle":["parallel SimRank at scale"],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["10.14778\/2850469.2850472"],"URL":"https:\/\/doi.org\/10.14778\/2850469.2850472","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,9]]}}}