{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:47:17Z","timestamp":1760708837149},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,4]]},"abstract":"<jats:p>\n            SimRank is an important measure of vertex-pair similarity according to the structure of graphs. The similarity search based on SimRank is an important operation for identifying similar vertices in a graph and has been employed in many data analysis applications. Nowadays, graphs in the real world become much larger and more dynamic. The existing solutions for similarity search are expensive in terms of time and space cost. None of them can efficiently support similarity search over large dynamic graphs. In this paper, we propose a novel two-stage random-walk sampling framework (TSF) for SimRank-based similarity search (e.g., top-\n            <jats:italic>k<\/jats:italic>\n            search). In the preprocessing stage, TSF samples a set of one-way graphs to index raw random walks in a novel manner within\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>NR<\/jats:italic>\n            <jats:sub>\n              <jats:italic>g<\/jats:italic>\n            <\/jats:sub>\n            ) time and space, where\n            <jats:italic>N<\/jats:italic>\n            is the number of vertices and\n            <jats:italic>R<\/jats:italic>\n            <jats:sub>\n              <jats:italic>g<\/jats:italic>\n            <\/jats:sub>\n            is the number of one-way graphs. The one-way graph can be efficiently updated in accordance with the graph modification, thus TSF is well suited to dynamic graphs. During the query stage, TSF can search similar vertices fast by naturally pruning unqualified vertices based on the connectivity of one-way graphs. Furthermore, with additional\n            <jats:italic>R<\/jats:italic>\n            <jats:sub>\n              <jats:italic>q<\/jats:italic>\n            <\/jats:sub>\n            samples, TSF can estimate the SimRank score with probability [EQUATION] if the error of approximation is bounded by 1 -- \u03b5. Finally, to guarantee the scalability of TSF, the one-way graphs can also be compactly stored on the disk when the memory is limited. Extensive experiments have demonstrated that TSF can handle dynamic billion-edge graphs with high performance.\n          <\/jats:p>","DOI":"10.14778\/2757807.2757809","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"838-849","source":"Crossref","is-referenced-by-count":45,"title":["An efficient similarity search framework for SimRank over large dynamic graphs"],"prefix":"10.14778","volume":"8","author":[{"given":"Yingxia","family":"Shao","sequence":"first","affiliation":[{"name":"Peking University"}]},{"given":"Bin","family":"Cui","sequence":"additional","affiliation":[{"name":"Peking University"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"HKUST"}]},{"given":"Mingming","family":"Liu","sequence":"additional","affiliation":[{"name":"Peking University"}]},{"given":"Xing","family":"Xie","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]}],"member":"320","published-online":{"date-parts":[[2015,4]]},"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.5555\/645930.672850"},{"key":"e_1_2_1_3_1","unstructured":"T. I. M. Association. Standard midi-file format spec. 1.1.  T. I. M. Association. Standard midi-file format spec. 1.1."},{"key":"e_1_2_1_4_1","volume-title":"One attempt of a compression algorithm using the bwt","author":"Balkenhol B.","year":"1999","unstructured":"B. Balkenhol and Y. M. Shtarkov . One attempt of a compression algorithm using the bwt , 1999 . B. Balkenhol and Y. M. Shtarkov. One attempt of a compression algorithm using the bwt, 1999."},{"key":"e_1_2_1_5_1","first-page":"9","volume-title":"AIRWEB","author":"Bencz\u00far A. A.","year":"2006","unstructured":"A. A. Bencz\u00far , K. Csalog\u00f3ny , and T. Sarl\u00f3s . Link-based similarity search to fight web spam . In AIRWEB , pages 9 -- 16 , 2006 . A. A. Bencz\u00far, K. Csalog\u00f3ny, and T. Sarl\u00f3s. Link-based similarity search to fight web spam. In AIRWEB, pages 9--16, 2006."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2351316.2351321"},{"key":"e_1_2_1_7_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001","unstructured":"T. H. Cormen , C. Stein , R. L. Rivest , and C. E. Leiserson . Introduction to Algorithms . 2 nd edition, 2001 . T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson. Introduction to Algorithms. 2nd edition, 2001.","edition":"2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/nsr\/nwt020"},{"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","volume-title":"Matrix Algebra From a Statistician's Perspective","author":"Harville D. A.","year":"2000","unstructured":"D. A. Harville . Matrix Algebra From a Statistician's Perspective . Springer , corrected edition, Nov. 2000 . D. A. Harville. Matrix Algebra From a Statistician's Perspective. Springer, corrected edition, Nov. 2000."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835874"},{"key":"e_1_2_1_13_1","volume-title":"Probability inequalities for sums of bounded random variables","author":"Hoeffding W.","year":"1962","unstructured":"W. Hoeffding . Probability inequalities for sums of bounded random variables , 1962 . W. Hoeffding. Probability inequalities for sums of bounded random variables, 1962."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610526"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.109"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739098"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01307-2_36"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.50"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0168-8"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.879024"},{"key":"e_1_2_1_23_1","volume-title":"Numerical recipes","author":"Press W. H.","year":"2007","unstructured":"W. H. Press , S. A. Teukolsky , W. T. Vetterling , and B. P. Flannery . Numerical recipes 3 rd edition: The art of scientific computing. 2007 . W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical recipes 3rd edition: The art of scientific computing. 2007.","edition":"3"},{"key":"e_1_2_1_24_1","volume-title":"Monte carlo statistical methods (springer texts in statistics)","author":"Robert C. P.","year":"2005","unstructured":"C. P. Robert and G. Casella . Monte carlo statistical methods (springer texts in statistics) . 2005 . C. P. Robert and G. Casella. Monte carlo statistical methods (springer texts in statistics). 2005."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1076034.1076059"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/APWeb.2010.42"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1884017.1884054"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544859"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816660"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732221"},{"key":"e_1_2_1_31_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\/2757807.2757809","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:45:42Z","timestamp":1672220742000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2757807.2757809"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4]]},"references-count":31,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["10.14778\/2757807.2757809"],"URL":"https:\/\/doi.org\/10.14778\/2757807.2757809","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,4]]}}}