{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T11:49:42Z","timestamp":1787744982647,"version":"build-2784847793"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,9]]},"abstract":"<jats:p>\n            Single-source and top-\n            <jats:italic>k<\/jats:italic>\n            SimRank queries are two important types of similarity search in graphs with numerous applications in web mining, social network analysis, spam detection, etc. A plethora of techniques have been proposed for these two types of queries, but very few can efficiently support similarity search over large dynamic graphs, due to either significant preprocessing time or large space overheads.\n          <\/jats:p>\n          <jats:p>\n            This paper presents\n            <jats:italic>ProbeSim<\/jats:italic>\n            , an\n            <jats:italic>index-free<\/jats:italic>\n            algorithm for single-source and top-\n            <jats:italic>k<\/jats:italic>\n            SimRank queries that provides a non-trivial theoretical guarantee in the absolute error of query results.\n            <jats:italic>ProbeSim<\/jats:italic>\n            estimates SimRank similarities without precomputing any indexing structures, and thus can naturally support\n            <jats:italic>real-time<\/jats:italic>\n            SimRank queries on\n            <jats:italic>dynamic<\/jats:italic>\n            graphs. Besides the theoretical guarantee,\n            <jats:italic>ProbeSim<\/jats:italic>\n            also offers satisfying practical efficiency and effectiveness due to non-trivial optimizations. We conduct extensive experiments on a number of benchmark datasets, which demonstrate that our solutions outperform the existing methods in terms of efficiency and effectiveness. Notably, our experiments include the first empirical study that evaluates the effectiveness of SimRank algorithms on graphs with billion edges, using the idea of\n            <jats:italic>pooling.<\/jats:italic>\n          <\/jats:p>","DOI":"10.14778\/3151113.3151115","type":"journal-article","created":{"date-parts":[[2017,10,19]],"date-time":"2017-10-19T12:30:08Z","timestamp":1508416208000},"page":"14-26","source":"Crossref","is-referenced-by-count":30,"title":["Probesim"],"prefix":"10.14778","volume":"11","author":[{"given":"Yu","family":"Liu","sequence":"first","affiliation":[{"name":"Renmin University of China, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bolong","family":"Zheng","sequence":"additional","affiliation":[{"name":"Sun Yat-sen University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaodong","family":"He","sequence":"additional","affiliation":[{"name":"Renmin University of China, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhewei","family":"Wei","sequence":"additional","affiliation":[{"name":"Renmin University of China, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kai","family":"Zheng","sequence":"additional","affiliation":[{"name":"University of Electronic Science and Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiaheng","family":"Lu","sequence":"additional","affiliation":[{"name":"University of Helsinki"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"https:\/\/arxiv.org\/abs\/1709.06955.  https:\/\/arxiv.org\/abs\/1709.06955."},{"key":"e_1_2_1_2_1","unstructured":"http:\/\/snap.stanford.edu\/data\/index.html.  http:\/\/snap.stanford.edu\/data\/index.html."},{"key":"e_1_2_1_3_1","unstructured":"http:\/\/law.di.unimi.it\/datasets.php.  http:\/\/law.di.unimi.it\/datasets.php."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453903"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129115"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060839"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129104"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544858"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835874"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/345508.345545"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020561"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610526"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.109"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739098"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850472"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.v58:7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-011-0427-z"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0168-8"},{"key":"e_1_2_1_20_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_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113318"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511809071","volume-title":"Introduction to information retrieval","author":"Manning C. D.","year":"2008","unstructured":"C. D. Manning , P. Raghavan , H. Sch\u00fctze , Introduction to information retrieval , volume 1 . Cambridge university press Cambridge , 2008 . C. D. Manning, P. Raghavan, H. Sch\u00fctze, et al. Introduction to information retrieval, volume 1. Cambridge university press Cambridge, 2008."},{"key":"e_1_2_1_23_1","first-page":"226","article-title":"Kendall tau metric","volume":"3","author":"Nelsen R.","year":"2001","unstructured":"R. Nelsen . Kendall tau metric . Encyclopaedia of Mathematics , 3 : 226 -- 227 , 2001 . R. Nelsen. Kendall tau metric. Encyclopaedia of Mathematics, 3:226--227, 2001.","journal-title":"Encyclopaedia of Mathematics"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2757807.2757809"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2207243.2207252"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735520"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915243"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816660"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732221"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806610"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735489"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766462.2767720"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-010-0100-6"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055552"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646025"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536349.2536350"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3151113.3151115","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:34:15Z","timestamp":1672223655000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3151113.3151115"}},"subtitle":["scalable single-source and top-\n            <i>k<\/i>\n            simrank computations on dynamic graphs"],"short-title":[],"issued":{"date-parts":[[2017,9]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["10.14778\/3151113.3151115"],"URL":"https:\/\/doi.org\/10.14778\/3151113.3151115","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,9]]}}}