{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:56Z","timestamp":1750219856364,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["12025104","81930119"],"award-info":[{"award-number":["12025104","81930119"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>SimRank is an important metric to measure the topological similarity between two nodes in a graph. In particular, single-source and top-k SimRank has numerous applications in recommendation systems, network analysis, and web mining, etc. Mathematically, given a vertex, the computation of single-machine and single-source SimRank mainly lies in matrix-matrix operations. However, it is almost impossible to directly compute on large graphs. Thus, existing works yield to two main operations: a series of random walks, and sparse matrix and dense vector multiplication operations. This brings about high computation cost for SimRank on large graphs. In real-world applications, there is always the query time and accuracy trade-off, which hinders the computation of high-precision SimRank on large-scale graphs.<\/jats:p>\n          <jats:p>To handle this problem, this paper proposesClipSim, the first GPU-friendly parallel framework that accelerates the single-source SimRank on GPU with accuracy guarantee. We design a novel data structure and GPU-friendly parallel algorithms for efficient computation of all the operations of SimRank on GPU. Moreover, our theoretical derivation enables ClipSim to largely reduce the number of random walks required for each node, while maintaining the same theoretical accuracy as the state-of-the-art algorithm, ExactSim. We conduct extensive experiments on real-world and synthetic datasets to demonstrate the accuracy and efficiency of ClipSim. The results show that compared with ExactSim, ClipSim obtains single-source SimRank vectors with the same accuracy and up to 160\u00d7 faster computation time.<\/jats:p>","DOI":"10.1145\/3588707","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["ClipSim: A GPU-friendly Parallel Framework for Single-Source SimRank with Accuracy Guarantee"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6141-5512","authenticated-orcid":false,"given":"Tianhao","family":"Wu","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3120-8966","authenticated-orcid":false,"given":"Ji","family":"Cheng","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1530-2584","authenticated-orcid":false,"given":"Chaorui","family":"Zhang","sequence":"additional","affiliation":[{"name":"Theory Lab, 2012 Labs &amp; Huawei Technologies, Co. Ltd, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5221-003X","authenticated-orcid":false,"given":"Jianfeng","family":"Hou","sequence":"additional","affiliation":[{"name":"Theory Lab, 2012 Labs &amp; Huawei Technologies, Co. Ltd, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-3264-0461","authenticated-orcid":false,"given":"Gengjian","family":"Chen","sequence":"additional","affiliation":[{"name":"Wuhan University, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5623-4864","authenticated-orcid":false,"given":"Zhongyi","family":"Huang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-4769-2779","authenticated-orcid":false,"given":"Weixi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Theory Lab, 2012 Labs &amp; Huawei Technologies, Co. Ltd, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0920-1357","authenticated-orcid":false,"given":"Wei","family":"Han","sequence":"additional","affiliation":[{"name":"Theory Lab, 2012 Labs &amp; Huawei Technologies, Co. Ltd, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4796-8249","authenticated-orcid":false,"given":"Bo","family":"Bai","sequence":"additional","affiliation":[{"name":"Theory Lab, 2012 Labs &amp; Huawei Technologies, Co. Ltd, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367714"},{"key":"e_1_2_2_2_1","volume-title":"International Conference on Parallel Processing and Applied Mathematics. Springer","author":"Bialas Piotr","year":"2015","unstructured":"Piotr Bialas and Adam Strzelecki. 2015. Benchmarking the cost of thread divergence in CUDA. In International Conference on Parallel Processing and Applied Mathematics. Springer, Krakow, Poland, 570--579."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536313"},{"key":"e_1_2_2_4_1","unstructured":"Rohit Chandra Leo Dagum David Kohr Ramesh Menon Dror Maydan and Jeff McDonald. 2001. Parallel programming in OpenMP. Morgan kaufmann."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01013465"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060839"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.68"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1208999"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1098\/rstl.1819.0023"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2020.113724"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020561"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610526"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151113.3151115"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436914"},{"key":"e_1_2_2_18_1","volume-title":"Efficient SimRank computation via linearization. arXiv preprint arXiv:1411.7228","author":"Maehara Takanori","year":"2014","unstructured":"Takanori Maehara, Mitsuru Kusumoto, and Ken-ichi Kawarabayashi. 2014. Efficient SimRank computation via linearization. arXiv preprint arXiv:1411.7228 (2014)."},{"key":"e_1_2_2_19_1","unstructured":"Sara Makki Rafiqul Haque Yehia Taher Zainab Assaghir Mohand-Said Hacid and Hassan Zeineddine. 2018. A cost-sensitive cosine similarity K-nearest neighbor for credit card fraud detection. In Big Data and Cyber-Security Intelligence. Hadath Lebanon 1--6."},{"key":"e_1_2_2_20_1","volume-title":"GPU Technology Conference","author":"Naumov Maxim","year":"2010","unstructured":"Maxim Naumov, L Chien, Philippe Vandermersch, and Ujval Kapasi. 2010. Cusparse library. In GPU Technology Conference. San Jose, California, USA, 1--96."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC41405.2020.00060"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2888116.2888372"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384347"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3357377.3357379"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915243"},{"key":"e_1_2_2_27_1","volume-title":"CPU and GPU. In NASA\/ESA Conference on Adaptive Hardware and Systems. IEEE","author":"Tian Xiang","year":"2009","unstructured":"Xiang Tian and Khaled Benkrid. 2009. Mersenne twister random number generation on FPGA, CPU and GPU. In NASA\/ESA Conference on Adaptive Hardware and Systems. IEEE, San Francisco, California, USA, 460--464."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10852-014-9267-7"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00672-7"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389781"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2976988"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851145"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430925"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319873"},{"key":"e_1_2_2_35_1","volume-title":"Scaling axiomatic role-based similarity ranking on large graphs. World Wide Web","author":"Yu Weiren","year":"2021","unstructured":"Weiren Yu, Sima Iranmanesh, Aparajita Haldar, Maoyin Zhang, and Hakan Ferhatosmanoglu. 2021. RoleSim*: Scaling axiomatic role-based similarity ranking on large graphs. World Wide Web (2021), 1--45."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0536-3"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735489"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00579-4"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783267"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588707","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588707","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:14Z","timestamp":1750178834000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588707"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588707"],"URL":"https:\/\/doi.org\/10.1145\/3588707","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}