{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:18Z","timestamp":1779174798649,"version":"3.51.4"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>\n            The assessment of node-to-node similarities based on graph topology arises in a myriad of applications,\n            <jats:italic>e.g.<\/jats:italic>\n            , web search. SimRank is a notable measure of this type, with the intuition that \"two nodes are similar if their in-neighbors are similar\". While most existing work retrieving SimRank only considers\n            <jats:italic>all-pairs<\/jats:italic>\n            SimRank\n            <jats:italic>s<\/jats:italic>\n            (*, *) and\n            <jats:italic>single-source<\/jats:italic>\n            SimRank\n            <jats:italic>s<\/jats:italic>\n            (*,\n            <jats:italic>j<\/jats:italic>\n            ) (scores between every node and query\n            <jats:italic>j<\/jats:italic>\n            ), there are appealing applications for\n            <jats:italic>partial-pairs<\/jats:italic>\n            SimRank,\n            <jats:italic>e.g.<\/jats:italic>\n            , similarity join. Given two node subsets\n            <jats:italic>A<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            in a graph, partial-pairs SimRank assessment aims to retrieve only {\n            <jats:italic>s<\/jats:italic>\n            (\n            <jats:italic>a<\/jats:italic>\n            ,\n            <jats:italic>b<\/jats:italic>\n            )}\n            <jats:sub>\n              \u2200\n              <jats:italic>a<\/jats:italic>\n              \u03b5\n              <jats:italic>A<\/jats:italic>\n              ,\u2200\n              <jats:italic>b<\/jats:italic>\n              \u03b5\n              <jats:italic>B<\/jats:italic>\n            <\/jats:sub>\n            . However, the best-known solution appears not self-contained since it hinges on the premise that the SimRank scores with node-pairs in an\n            <jats:italic>h<\/jats:italic>\n            -go cover set must be given beforehand.\n          <\/jats:p>\n          <jats:p>\n            This paper focuses on efficient assessment of partial-pairs SimRank in a self-contained manner. (1) We devise a novel \"seed germination\" model that computes partial-pairs SimRank in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            |\n            <jats:italic>E<\/jats:italic>\n            | min{|\n            <jats:italic>A<\/jats:italic>\n            |, |\n            <jats:italic>B<\/jats:italic>\n            |}) time and\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>E<\/jats:italic>\n            | +\n            <jats:italic>k<\/jats:italic>\n            |\n            <jats:italic>V<\/jats:italic>\n            |) memory for\n            <jats:italic>k<\/jats:italic>\n            iterations on a graph of |\n            <jats:italic>V<\/jats:italic>\n            | nodes and |\n            <jats:italic>E<\/jats:italic>\n            | edges. (2) We further eliminate unnecessary edge access to improve the time of partial-pairs SimRank to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            min{|\n            <jats:italic>A<\/jats:italic>\n            |, |\n            <jats:italic>B<\/jats:italic>\n            |}), where\n            <jats:italic>m<\/jats:italic>\n            \u2264 min{\n            <jats:italic>k<\/jats:italic>\n            |\n            <jats:italic>E<\/jats:italic>\n            |, \u0394\n            <jats:sup>\n              2\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            }, and \u0394 is the maximum degree. (3) We show that our partial-pairs SimRank model also can handle the computations of all-pairs and single-source SimRanks. (4) We empirically verify that our algorithms are (a) 38x faster than the best-known competitors, and (b) memory-efficient, allowing scores to be assessed accurately on graphs with tens of millions of links.\n          <\/jats:p>","DOI":"10.14778\/2735479.2735489","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"569-580","source":"Crossref","is-referenced-by-count":46,"title":["Efficient partial-pairs simrank search on large networks"],"prefix":"10.14778","volume":"8","author":[{"given":"Weiren","family":"Yu","sequence":"first","affiliation":[{"name":"Imperial College London"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julie A.","family":"McCann","sequence":"additional","affiliation":[{"name":"Imperial College London"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453903"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129098"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060839"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544858"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835874"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.12.008"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020561"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610526"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.109"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739098"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.50"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0168-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402712"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1884017.1884054"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544859"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816660"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732221"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600428.2609459"},{"key":"e_1_2_1_20_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\/2735479.2735489","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:20:16Z","timestamp":1672226416000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2735479.2735489"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.14778\/2735479.2735489"],"URL":"https:\/\/doi.org\/10.14778\/2735479.2735489","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}