{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:55:13Z","timestamp":1777614913969,"version":"3.51.4"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>\n            Graph pattern matching is often defined in terms of subgraph isomorphism, an np-complete problem. To lower its complexity, various extensions of graph simulation have been considered instead. These extensions allow pattern matching to be conducted in cubic-time. However, they fall short of capturing the topology of data graphs,\n            <jats:italic>i.e.<\/jats:italic>\n            , graphs may have a structure drastically different from pattern graphs they match, and the matches found are often too large to understand and analyze. To rectify these problems, this paper proposes a notion of\n            <jats:italic>strong simulation<\/jats:italic>\n            , a revision of graph simulation, for graph pattern matching. (1) We identify a set of criteria for preserving the topology of graphs matched. We show that strong simulation preserves the topology of data graphs and finds a bounded number of matches. (2) We show that strong simulation retains the same complexity as earlier extensions of simulation, by providing a cubic-time algorithm for computing strong simulation. (3) We present the locality property of strong simulation, which allows us to effectively conduct pattern matching on distributed graphs. (4) We experimentally verify the effectiveness and efficiency of these algorithms, using real-life data and synthetic data.\n          <\/jats:p>","DOI":"10.14778\/2095686.2095690","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"310-321","source":"Crossref","is-referenced-by-count":72,"title":["Capturing topology in graph pattern matching"],"prefix":"10.14778","volume":"5","author":[{"given":"Shuai","family":"Ma","sequence":"first","affiliation":[{"name":"Beihang University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Cao","sequence":"additional","affiliation":[{"name":"Beihang University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenfei","family":"Fan","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinpeng","family":"Huai","sequence":"additional","affiliation":[{"name":"Beihang University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tianyu","family":"Wo","sequence":"additional","affiliation":[{"name":"Beihang University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"LinkedIn. www.linkedin.com.  LinkedIn. www.linkedin.com."},{"key":"e_1_2_1_2_1","volume-title":"Morgan Kaufmann","author":"Abiteboul S.","year":"1999","unstructured":"S. Abiteboul , P. Buneman , and D. Suciu . Data on the Web: From Relations to Semistructured Data and XML . Morgan Kaufmann , 1999 . S. Abiteboul, P. Buneman, and D. Suciu. Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann, 1999."},{"key":"e_1_2_1_3_1","volume-title":"Foundations of Databases","author":"Abiteboul S.","year":"1995","unstructured":"S. Abiteboul , R. Hull , and V. Vianu . Foundations of Databases . Addison-Wesley , 1995 . S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1738952"},{"key":"e_1_2_1_5_1","volume-title":"Challenges in searching online communities","author":"Amer-Yahia S.","year":"2007","unstructured":"S. Amer-Yahia , M. Benedikt , and P. Bohannon . Challenges in searching online communities . IEEE Data Eng. Bull ., 30(2), 2007 . S. Amer-Yahia, M. Benedikt, and P. Bohannon. Challenges in searching online communities. IEEE Data Eng. Bull., 30(2), 2007."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2010.52"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jebo.2003.11.005"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/635499.635502"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2008.04.003"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376678"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247537"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_13_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms . The MIT Press , 2001 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2001."},{"issue":"1695","key":"e_1_2_1_14_1","volume":"1695","author":"Csardi G.","year":"2006","unstructured":"G. Csardi and T. Nepusz . The igraph software package for complex network research. InterJournal Complex Systems , 1695 ( 1695 ), 2006 . G. Csardi and T. Nepusz. The igraph software package for complex network research. InterJournal Complex Systems, 1695(1695), 2006.","journal-title":"The igraph software package for complex network research. InterJournal Complex Systems"},{"key":"e_1_2_1_15_1","volume-title":"OSDI","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . Mapreduce: Simplified data processing on large clusters . In OSDI , 2004 . J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. In OSDI, 2004."},{"key":"e_1_2_1_16_1","volume-title":"Graph Theory","author":"Diestel R.","year":"2005","unstructured":"R. Diestel . Graph Theory . Springer , 2005 . R. Diestel. Graph Theory. Springer, 2005."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1209024"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767858"},{"key":"e_1_2_1_19_1","volume-title":"Graph pattern matching: From intractable to polynomial time. PVLDB, 3(1)","author":"Fan W.","year":"2010","unstructured":"W. Fan , J. Li , S. Ma , N. Tang , Y. Wu , and Y. Wu . Graph pattern matching: From intractable to polynomial time. PVLDB, 3(1) , 2010 . W. Fan, J. Li, S. Ma, N. Tang, Y. Wu, and Y. Wu. Graph pattern matching: From intractable to polynomial time. PVLDB, 3(1), 2010."},{"key":"e_1_2_1_20_1","volume-title":"AAAI FS.","author":"Gallagher B.","year":"2006","unstructured":"B. Gallagher . Matching structure and semantics: A survey on graph-based pattern matching . AAAI FS. , 2006 . B. Gallagher. Matching structure and semantics: A survey on graph-based pattern matching. AAAI FS., 2006."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17551-0_2"},{"key":"e_1_2_1_22_1","volume-title":"VLDB","author":"Goldman R.","year":"1997","unstructured":"R. Goldman and J. Widom . Dataguides: Enabling query formulation and optimization in semistructured databases . In VLDB , 1997 . R. Goldman and J. Widom. Dataguides: Enabling query formulation and optimization in semistructured databases. In VLDB, 1997."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804672"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796255"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/646508.694493"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/371578.371598"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150522"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_29_1","volume-title":"Communication and Concurrency","author":"Milner R.","year":"1989","unstructured":"R. Milner . Communication and Concurrency . Prentice Hall , 1989 . R. Milner. Communication and Concurrency. Prentice Hall, 1989."},{"key":"e_1_2_1_30_1","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1994","unstructured":"C. H. Papadimitriou . Computational Complexity . Addison-Wesley , 1994 . C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1096737.1096740"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497505"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281271"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_35_1","volume-title":"\u00d6zsu. Distance-join: Pattern match query in a large graph database. PVLDB, 2(1)","author":"Zou L.","year":"2009","unstructured":"L. Zou , L. Chen , and M. T. \u00d6zsu. Distance-join: Pattern match query in a large graph database. PVLDB, 2(1) , 2009 . L. Zou, L. Chen, and M. T. \u00d6zsu. Distance-join: Pattern match query in a large graph database. PVLDB, 2(1), 2009."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2095686.2095690","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:46:50Z","timestamp":1672220810000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2095686.2095690"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.14778\/2095686.2095690"],"URL":"https:\/\/doi.org\/10.14778\/2095686.2095690","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,12]]}}}