{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:08:15Z","timestamp":1764688095908},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:p>\n            SimRank-based similarity joins, which mainly include threshold-based and top-\n            <jats:italic>k<\/jats:italic>\n            similarity joins, are important types of all-pair SimRank queries. Although a line of related algorithms have been proposed recently, they still fall short of providing approximation guarantee and suffer from scalability issues on medium and large graphs. Meanwhile, we also lack an extensive analysis of existing techniques in terms of accuracy and efficiency. Motivated by these challenges, we first conduct detailed analysis of state-of-the-art algorithms and provide additional theoretical results. Second, to address the limitations of existing techniques, we propose simple yet effective algorithm frameworks for both queries to theoretically guarantee the approximation bound, and present a more efficient all-pair algorithm inspired by randomized local push of Personalized PageRank. Next, we analyze the algorithmic complexity of threshold-based and top-\n            <jats:italic>k<\/jats:italic>\n            similarity joins by leveraging a reasonable assumption of SimRank distribution. Through extensive experiments, we find that our proposed methods far exceed existing ones with respect to query efficiency, approximation guarantee and practical accuracy, while our theoretical analysis nicely matches the empirical study.\n          <\/jats:p>","DOI":"10.14778\/3636218.3636219","type":"journal-article","created":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T17:04:07Z","timestamp":1709658247000},"page":"617-629","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient and Accurate SimRank-Based Similarity Joins: Experiments, Analysis, and Improvement"],"prefix":"10.14778","volume":"17","author":[{"given":"Qian","family":"Ge","sequence":"first","affiliation":[{"name":"Peking University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu","family":"Liu","sequence":"additional","affiliation":[{"name":"Beijing Jiaotong University, Beijing Key Laboratory of Traffic Data Analysis and Mining, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yinghao","family":"Zhao","sequence":"additional","affiliation":[{"name":"Beijing Jiaotong University, Beijing Key Laboratory of Traffic Data Analysis and Mining, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuetian","family":"Sun","sequence":"additional","affiliation":[{"name":"Beijing Jiaotong University, Beijing Key Laboratory of Traffic Data Analysis and Mining, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Zou","sequence":"additional","affiliation":[{"name":"Peking University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuxing","family":"Chen","sequence":"additional","affiliation":[{"name":"Tencent Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anqun","family":"Pan","sequence":"additional","affiliation":[{"name":"Tencent Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. https:\/\/github.com\/xinghun0525\/R2LP."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554819"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403296"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1306--1325","author":"Brach Pawel","year":"2016","unstructured":"Pawel Brach, Marek Cygan, Jakub Lkacki, and Piotr Sankowski. 2016. Algorithmic complexity of power law networks. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1306--1325."},{"key":"e_1_2_1_7_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Charikar Moses","unstructured":"Moses Charikar, Kevin Chen, and Martin Farach-Colton. 2002. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming. Springer, 693--703."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060839"},{"key":"e_1_2_1_9_1","volume-title":"2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, 589--600","author":"Fujiwara Yasuhiro","year":"2013","unstructured":"Yasuhiro Fujiwara, Makoto Nakatsuji, Hiroaki Shiokawa, and Makoto Onizuka. 2013. Efficient search algorithm for SimRank. In 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, 589--600."},{"key":"e_1_2_1_10_1","volume-title":"Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997","author":"Gasteiger Johannes","year":"2018","unstructured":"Johannes Gasteiger, Aleksandar Bojchevski, and Stephan G\u00fcnnemann. 2018. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997 (2018)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835874"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Glen Jeh and Jennifer Widom. 2002. SimRank: a measure of structural-context similarity. In SIGKDD. 538--543.","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099625"},{"key":"e_1_2_1_14_1","volume-title":"Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907","author":"Kipf Thomas N","year":"2016","unstructured":"Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.109"},{"key":"e_1_2_1_17_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739098"},{"key":"e_1_2_1_19_1","volume-title":"Mapreduce-based SimRank computation and its application in social recommender system. In 2013 IEEE international congress on big data","author":"Li Lina","unstructured":"Lina Li, Cuiping Li, Hong Chen, and Xiaoyong Du. 2013. Mapreduce-based SimRank computation and its application in social recommender system. In 2013 IEEE international congress on big data. IEEE, 133--140."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2016.10.042"},{"key":"e_1_2_1_21_1","volume-title":"SIMGA: A Simple and Effective Heterophilous Graph Neural Network with Efficient Global Aggregation. arXiv preprint arXiv:2305.09958","author":"Liu Haoyu","year":"2023","unstructured":"Haoyu Liu, Ningyi Liao, and Siqiang Luo. 2023. SIMGA: A Simple and Effective Heterophilous Graph Neural Network with Efficient Global Aggregation. arXiv preprint arXiv:2305.09958 (2023)."},{"key":"e_1_2_1_22_1","volume-title":"Probesim: scalable single-source and top-k simrank computations on dynamic graphs. arXiv preprint arXiv:1709.06955","author":"Liu Yu","year":"2017","unstructured":"Yu Liu, Bolong Zheng, Xiaodong He, Zhewei Wei, Xiaokui Xiao, Kai Zheng, and Jiaheng Lu. 2017. Probesim: scalable single-source and top-k simrank computations on dynamic graphs. arXiv preprint arXiv:1709.06955 (2017)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407819"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453904"},{"key":"e_1_2_1_25_1","volume-title":"Personalized pagerank to a target node. arXiv preprint arXiv:1304.4658","author":"Lofgren Peter","year":"2013","unstructured":"Peter Lofgren and Ashish Goel. 2013. Personalized pagerank to a target node. arXiv preprint arXiv:1304.4658 (2013)."},{"key":"e_1_2_1_26_1","volume-title":"A novel and fast simrank algorithm","author":"Lu Juan","year":"2016","unstructured":"Juan Lu, Zhiguo Gong, and Xuemin Lin. 2016. A novel and fast simrank algorithm. IEEE transactions on knowledge and data engineering 29, 3 (2016), 572--585."},{"key":"e_1_2_1_27_1","volume-title":"Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications 390, 6","author":"L\u00fc Linyuan","year":"2011","unstructured":"Linyuan L\u00fc and Tao Zhou. 2011. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications 390, 6 (2011), 1150--1170."},{"key":"e_1_2_1_28_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_1_29_1","volume-title":"2015 IEEE 31st International Conference on Data Engineering. IEEE, 603--614","author":"Maehara Takanori","year":"2015","unstructured":"Takanori Maehara, Mitsuru Kusumoto, and Ken-ichi Kawarabayashi. 2015. Scalable simrank join algorithm. In 2015 IEEE 31st International Conference on Data Engineering. IEEE, 603--614."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2757807.2757809"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384347"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735520"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915243"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186120"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403108"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00672-7"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098072"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0521-x"},{"key":"e_1_2_1_39_1","volume-title":"2018 IEEE 34th international conference on data engineering (ICDE). IEEE, 545--556","author":"Wang Yue","year":"2018","unstructured":"Yue Wang, Xiang Lian, and Lei Chen. 2018. Efficient simrank tracking in dynamic graphs. In 2018 IEEE 34th international conference on data engineering (ICDE). IEEE, 545--556."},{"key":"e_1_2_1_40_1","volume-title":"2013 IEEE 29th international conference on data engineering (ICDE). IEEE, 601--612","author":"Yu Weiren","year":"2013","unstructured":"Weiren Yu, Xuemin Lin, and Wenjie Zhang. 2013. Towards efficient SimRank computation on large networks. In 2013 IEEE 29th international conference on data engineering (ICDE). IEEE, 601--612."},{"key":"e_1_2_1_41_1","volume-title":"Fast incremental simrank on link-evolving graphs. In 2014 ieee 30th international conference on data engineering","author":"Yu Weiren","unstructured":"Weiren Yu, Xuemin Lin, and Wenjie Zhang. 2014. Fast incremental simrank on link-evolving graphs. In 2014 ieee 30th international conference on data engineering. IEEE, 304--315."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732221"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735489"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-010-0100-6"},{"key":"e_1_2_1_45_1","volume-title":"Hierarchical All-Pairs SimRank Calculation. In International Conference on Database Systems for Advanced Applications. Springer, 252--268","author":"Zhang Liangfu","year":"2023","unstructured":"Liangfu Zhang, Cuiping Li, Xue Zhang, and Hong Chen. 2023. Hierarchical All-Pairs SimRank Calculation. In International Conference on Database Systems for Advanced Applications. Springer, 252--268."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3083899"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536349.2536350"},{"key":"e_1_2_1_48_1","volume-title":"Unified and Incremental SimRank: Index-free Approximation with Scheduled Principle","author":"Zhu Fanwei","year":"2021","unstructured":"Fanwei Zhu, Yuan Fang, Kai Zhang, Kevin Chang, Hongtai Cao, Zhen Jiang, and Minghui Wu. 2021. Unified and Incremental SimRank: Index-free Approximation with Scheduled Principle. IEEE Transactions on Knowledge and Data Engineering (2021)."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3636218.3636219","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T17:10:14Z","timestamp":1709658614000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3636218.3636219"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["10.14778\/3636218.3636219"],"URL":"https:\/\/doi.org\/10.14778\/3636218.3636219","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,12]]},"assertion":[{"value":"2024-03-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}