{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T16:41:55Z","timestamp":1759941715682,"version":"3.41.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,7,31]],"date-time":"2017-07-31T00:00:00Z","timestamp":1501459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSFC Guang Dong","award":["U1301253"],"award-info":[{"award-number":["U1301253"]}]},{"name":"Microsoft Research Asia Collaborative Grant"},{"name":"National Key Research and Development Program of China","award":["2016YFB1000603"],"award-info":[{"award-number":["2016YFB1000603"]}]},{"name":"National Grand Fundamental Research 973 Program of China","award":["2014CB340303, HKUST-SSTSP FP305"],"award-info":[{"award-number":["2014CB340303, HKUST-SSTSP FP305"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61622201, 61532010, 61370055 and 61328202"],"award-info":[{"award-number":["61622201, 61532010, 61370055 and 61328202"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Hong Kong RGC project","award":["16202215"],"award-info":[{"award-number":["16202215"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2017,9,30]]},"abstract":"<jats:p>\n            Graphs have been widely used to model complex data in many real-world applications. Answering vertex join queries over large graphs is meaningful and interesting, which can benefit friend recommendation in social networks and link prediction, and so on. In this article, we adopt \u201cSimRank\u201d [13] to evaluate the similarity between two vertices in a large graph because of its generality. Note that \u201cSimank\u201d is purely structure dependent, and it does not rely on the domain knowledge. Specifically, we define a\n            <jats:italic>S<\/jats:italic>\n            im\n            <jats:italic>R<\/jats:italic>\n            ank-based\n            <jats:italic>j<\/jats:italic>\n            oin (\n            <jats:italic>SRJ<\/jats:italic>\n            ) query to find all vertex pairs satisfying the threshold from two sets of vertices\n            <jats:italic>U<\/jats:italic>\n            and\n            <jats:italic>V<\/jats:italic>\n            . To reduce the search space, we propose a shortest-path-distance-based upper bound for SimRank scores to prune unpromising vertex pairs. In the verification, we propose a novel index, called\n            <jats:italic>h-go cover<\/jats:italic>\n            <jats:sup>+<\/jats:sup>\n            , to efficiently compute the SimRank score of any single vertex pair. Given a graph\n            <jats:italic>G<\/jats:italic>\n            , we only materialize the SimRank scores of a small proportion of vertex pairs (i.e., the\n            <jats:italic>h-go cover<\/jats:italic>\n            <jats:sup>+<\/jats:sup>\n            vertex pairs), based on which the SimRank score of any vertex pair can be computed easily. To find the\n            <jats:italic>h-go cover<\/jats:italic>\n            <jats:sup>+<\/jats:sup>\n            vertex pairs, we propose an efficient method without building the vertex-pair graph. Hence, large graphs can be dealt with easily. Extensive experiments over both real and synthetic datasets confirm the efficiency of our solution.\n          <\/jats:p>","DOI":"10.1145\/3083899","type":"journal-article","created":{"date-parts":[[2017,8,1]],"date-time":"2017-08-01T19:20:44Z","timestamp":1501615244000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Efficient SimRank-Based Similarity Join"],"prefix":"10.1145","volume":"42","author":[{"given":"Weiguo","family":"Zheng","sequence":"first","affiliation":[{"name":"Peking University, The Chinese University of Hong Kong, Shatin, Hong Kong"}]},{"given":"Lei","family":"Zou","sequence":"additional","affiliation":[{"name":"Peking University, Beijing Institute of Big Data Research, Beijing, China"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Kowloon, Hong Kong"}]},{"given":"Dongyan","family":"Zhao","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2017,7,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1348549.1348561"},{"volume-title":"Nichomachean Ethics. Rackman Translator","key":"e_1_2_1_2_1","unstructured":"Aristotle. 1934. Rhetoric . In Nichomachean Ethics. Rackman Translator . Harvard University Press , Cambridge, MA .23. Aristotle. 1934. Rhetoric. In Nichomachean Ethics. Rackman Translator. Harvard University Press, Cambridge, MA.23."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0177-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497500"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_2_1_6_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . Introduction to Algorithms ( 3 rd ed.). The MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd ed.). The MIT Press.","edition":"3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767858"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060839"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544858"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"J. E. Gentle. 1998. Gaussian elimination. In Numerical Linear Algebra for Applications in Statistics. 87--91.  J. E. Gentle. 1998. Gaussian elimination. In Numerical Linear Algebra for Applications in Statistics. 87--91.","DOI":"10.1007\/978-1-4612-0623-1_3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871503"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1033772"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1597036.1597045"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0271(63)90016-0"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989418"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610526"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.109"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739098"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01307-2_36"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.50"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850472"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.20591"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453904"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0168-8"},{"key":"e_1_2_1_28_1","volume-title":"Efficient SimRank computation via linearization. CoRR abs\/1411.7228","author":"Maehara Takanori","year":"2014","unstructured":"Takanori Maehara , Mitsuru Kusumoto , and Ken-ichi Kawarabayashi. 2014. Efficient SimRank computation via linearization. CoRR abs\/1411.7228 ( 2014 ). Takanori Maehara, Mitsuru Kusumoto, and Ken-ichi Kawarabayashi. 2014. Efficient SimRank computation via linearization. CoRR abs\/1411.7228 (2014)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113318"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.soc.27.1.415"},{"volume-title":"Plato in Twelve Volumes. Bury Translator","key":"e_1_2_1_31_1","unstructured":"Plato. 1968. Laws . In Plato in Twelve Volumes. Bury Translator . Harvard Univ. Press , Cambridge, MA . 11. Plato. 1968. Laws. In Plato in Twelve Volumes. Bury Translator. Harvard Univ. Press, Cambridge, MA. 11."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.74.47"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2757807.2757809"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.4630240406"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"714","DOI":"10.14778\/3402707.3402712","article-title":"On link-based similarity join","volume":"4","author":"Sun Liwen","year":"2011","unstructured":"Liwen Sun , Reynold Cheng , Xiang Li , David W. Cheung , and Jiawei Han . 2011 . On link-based similarity join . Proc. VLDB 4 , 11 (2011), 714 -- 725 . Liwen Sun, Reynold Cheng, Xiang Li, David W. Cheung, and Jiawei Han. 2011. On link-based similarity join. Proc. VLDB 4, 11 (2011), 714--725.","journal-title":"Proc. VLDB"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735520"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063834"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247573"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.53"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807181"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE&lsquor;13)","author":"Yu Weiren","year":"2013","unstructured":"Weiren Yu , Xuemin Lin , and Wenjie Zhang . 2013 . Towards efficient SimRank computation on large networks . In Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE&lsquor;13) . 601--612. Weiren Yu, Xuemin Lin, and Wenjie Zhang. 2013. Towards efficient SimRank computation on large networks. In Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE&lsquor;13). 601--612."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816660"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2339828"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735489"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-010-0100-6"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516384"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920988"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536349.2536350"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687727"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3083899","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3083899","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:08Z","timestamp":1750217408000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3083899"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,31]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9,30]]}},"alternative-id":["10.1145\/3083899"],"URL":"https:\/\/doi.org\/10.1145\/3083899","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2017,7,31]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}