{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:27:30Z","timestamp":1768109250812,"version":"3.49.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Guangdong Innovative Research Team Program 2011D005"},{"name":"973 Programs 2012CB316200 and 2014CB340302"},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"publisher","award":["61322207"],"award-info":[{"award-number":["61322207"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"EPSRC EP\/J015377\/1, U.K."},{"name":"NGFR 973","award":["2014CB340304"],"award-info":[{"award-number":["2014CB340304"]}]},{"name":"863","award":["2013AA01A213"],"award-info":[{"award-number":["2013AA01A213"]}]},{"name":"Shenzhen Peacock Program 1105100030834361 of China"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>\n            Graph pattern matching is finding all matches in a data graph for a given pattern graph and is often defined in terms of subgraph isomorphism, an\n            <jats:sc>NP<\/jats:sc>\n            -complete problem. To lower its complexity, various extensions of graph simulation have been considered instead. These extensions allow graph pattern matching to be conducted in cubic time. However, they fall short of capturing the topology of data graphs, that is, 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 article 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 graph simulation by providing a cubic-time algorithm for computing strong simulation. (3) We present the locality property of strong simulation which allows us to develop an effective distributed algorithm to conduct graph pattern matching on distributed graphs. (4) We experimentally verify the effectiveness and efficiency of these algorithms using both real-life and synthetic data.\n          <\/jats:p>","DOI":"10.1145\/2528937","type":"journal-article","created":{"date-parts":[[2014,2,4]],"date-time":"2014-02-04T14:16:21Z","timestamp":1391523381000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":92,"title":["Strong simulation"],"prefix":"10.1145","volume":"39","author":[{"given":"Shuai","family":"Ma","sequence":"first","affiliation":[{"name":"Beihang University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Cao","sequence":"additional","affiliation":[{"name":"Beihang University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenfei","family":"Fan","sequence":"additional","affiliation":[{"name":"SKLSDE Lab, Beihang University and University of Edinburgh, Scotland, U.K."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinpeng","family":"Huai","sequence":"additional","affiliation":[{"name":"SKLSDE Lab, Beihang University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tianyu","family":"Wo","sequence":"additional","affiliation":[{"name":"SKLSDE Lab, Beihang University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,1,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/645502.656103"},{"key":"e_1_2_1_2_1","unstructured":"Serge Abiteboul Peter Buneman and Dan Suciu. 1999. Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann.   Serge Abiteboul Peter Buneman and Dan Suciu. 1999. Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann."},{"key":"e_1_2_1_3_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of Databases . Addison-Wesley . Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_4_1","volume-title":"Aggarwal and Haixun Wang","author":"Charu","year":"2010","unstructured":"Charu C. Aggarwal and Haixun Wang . 2010 . Managing and Mining Graph Data. Advances in Database Systems, vol. 40 , Springer . Charu C. Aggarwal and Haixun Wang. 2010. Managing and Mining Graph Data. Advances in Database Systems, vol. 40, Springer."},{"key":"e_1_2_1_5_1","first-page":"23","article-title":"Challenges in searching online communities","volume":"30","author":"Amer-Yahia Sihem","year":"2007","unstructured":"Sihem Amer-Yahia , Michael Benedikt , and Philip Bohannon . 2007 . Challenges in searching online communities . IEEE Data Eng. Bull. 30 , 2, 23 -- 31 . Sihem Amer-Yahia, Michael Benedikt, and Philip Bohannon. 2007. Challenges in searching online communities. IEEE Data Eng. Bull. 30, 2, 23--31.","journal-title":"IEEE Data Eng. Bull."},{"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","volume-title":"Rokne","author":"Chia-Lung Chen Alan","year":"2011","unstructured":"Alan Chia-Lung Chen , Shang Gao , Panagiotis Karampelas , Reda Alhajj , and Jon G . Rokne . 2011 . Finding hidden links in terrorist networks by checking indirect links of different sub-networks. In Counterterrorism and Open Source Intelligence. Lecture Notes in Social Networks, vol. 2 , Springer Vienna , 143--158. Alan Chia-Lung Chen, Shang Gao, Panagiotis Karampelas, Reda Alhajj, and Jon G. Rokne. 2011. Finding hidden links in terrorist networks by checking indirect links of different sub-networks. In Counterterrorism and Open Source Intelligence. Lecture Notes in Social Networks, vol. 2, Springer Vienna, 143--158."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376678"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247537"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_14_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2001. Introduction to Algorithms . The MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001. Introduction to Algorithms. The MIT Press."},{"key":"e_1_2_1_15_1","unstructured":"G. Csardi and T. Nepusz. 2006. The igraph software package for complex network research. Inter. J. Complex Syst. 1695 (2006).  G. Csardi and T. Nepusz. 2006. The igraph software package for complex network research. Inter. J. Complex Syst. 1695 (2006)."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 6th Conference on Operating Systems Designs and Implementations (OSDI).","author":"Dean Jeffrey","year":"2004","unstructured":"Jeffrey Dean and Sanjay Ghemawat . 2004 . MapReduce: Simplified data processing on large clusters . In Proceedings of the 6th Conference on Operating Systems Designs and Implementations (OSDI). Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: Simplified data processing on large clusters. In Proceedings of the 6th Conference on Operating Systems Designs and Implementations (OSDI)."},{"key":"e_1_2_1_17_1","volume-title":"Graph Theory. Graduate Texts in Mathematics","author":"Diestel R.","unstructured":"R. Diestel . 2005. Graph Theory. Graduate Texts in Mathematics , vol. 173 , Springer . R. Diestel. 2005. Graph Theory. Graduate Texts in Mathematics, vol. 173, Springer."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1209024"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1331904.1331908"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767858"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920878"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920986"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213855"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350248"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536263"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2489791"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 8th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom).","author":"Fard Arash","unstructured":"Arash Fard , Amir Abdolrashidi , Lakshmish Ramaswamy , and John A. Miller . 2012. Towards efficient query processing on massive time-evolving graphs . In Proceedings of the 8th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom). Arash Fard, Amir Abdolrashidi, Lakshmish Ramaswamy, and John A. Miller. 2012. Towards efficient query processing on massive time-evolving graphs. In Proceedings of the 8th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom)."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the AAAI Fall Symposium Series.","author":"Gallagher Brian","year":"2006","unstructured":"Brian Gallagher . 2006 . Matching structure and semantics: A survey on graph-based pattern matching . In Proceedings of the AAAI Fall Symposium Series. Brian Gallagher. 2006. Matching structure and semantics: A survey on graph-based pattern matching. In Proceedings of the AAAI Fall Symposium Series."},{"key":"e_1_2_1_29_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey Michael","unstructured":"Michael Garey and David Johnson . 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman and Company . Michael Garey and David Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company."},{"key":"e_1_2_1_30_1","first-page":"19","article-title":"Massive graph management for the Web and Web 2.0. In New Directions in Web Data Management 1","volume":"331","author":"Giatsoglou Maria","year":"2011","unstructured":"Maria Giatsoglou , Symeon Papadopoulos , and Athena Vakali . 2011 . Massive graph management for the Web and Web 2.0. In New Directions in Web Data Management 1 . Studies in Computational Intelligence , vol. 331 , Spring er, 19 -- 58 . Maria Giatsoglou, Symeon Papadopoulos, and Athena Vakali. 2011. Massive graph management for the Web and Web 2.0. In New Directions in Web Data Management 1. Studies in Computational Intelligence, vol. 331, Springer, 19--58.","journal-title":"Studies in Computational Intelligence"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB).","author":"Goldman Roy","year":"1997","unstructured":"Roy Goldman and Jennifer Widom . 1997 . DataGuides: Enabling query formulation and optimization in semistructured databases . In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB). Roy Goldman and Jennifer Widom. 1997. DataGuides: Enabling query formulation and optimization in semistructured databases. In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804672"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100054"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 36th Annual Symposium on Foundation of Computer Science (FOCS).","author":"Henzinger M. R.","unstructured":"M. R. Henzinger , T. A. Henzinger , and P. W. Kopke . 1995. Computing simulations on finite and infinite graphs . In Proceedings of the 36th Annual Symposium on Foundation of Computer Science (FOCS). M. R. Henzinger, T. A. Henzinger, and P. W. Kopke. 1995. Computing simulations on finite and infinite graphs. In Proceedings of the 36th Annual Symposium on Foundation of Computer Science (FOCS)."},{"key":"e_1_2_1_35_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Kann Viggo","unstructured":"Viggo Kann . 1992. On the approximability of the maximum common subgraph problem . In Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS) . Lecture Notes in Computer Science , vol. 577 , Springer-Verlag , Berlin Heidelberg , 375--388. Viggo Kann. 1992. On the approximability of the maximum common subgraph problem. In Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 577, Springer-Verlag, Berlin Heidelberg, 375--388."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2021017.2021025"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448952"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/371578.371598"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376706"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956972"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150522"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 26th Conference on Uncertainity in AI (UAI).","author":"Low Yucheng","unstructured":"Yucheng Low , Joseph Gonzalez , Aapo Kyrola , Danny Bickson , Carlos Guestrin , and Joseph M. Hellerstein . 2010. GraphLab: A new parallel framework for machine learning . In Proceedings of the 26th Conference on Uncertainity in AI (UAI). Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos Guestrin, and Joseph M. Hellerstein. 2010. GraphLab: A new parallel framework for machine learning. In Proceedings of the 26th Conference on Uncertainity in AI (UAI)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2095686.2095690"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187963"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_48_1","volume-title":"Communication and Concurrency","author":"Milner Robin","unstructured":"Robin Milner . 1989. Communication and Concurrency . Prentice Hall . Robin Milner. 1989. Communication and Concurrency. Prentice Hall."},{"key":"e_1_2_1_49_1","volume-title":"Computational Complexity","author":"Papadimitriou Christos H","unstructured":"Christos H Papadimitriou . 1994. Computational Complexity . Addison-Wesley . Christos H Papadimitriou. 1994. Computational Complexity. Addison-Wesley."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.67"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(03)00239-0"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1096737.1096740"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497505"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281271"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213895"},{"key":"e_1_2_1_57_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\/2528937","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2528937","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:45Z","timestamp":1750231725000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2528937"}},"subtitle":["Capturing topology in graph pattern matching"],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2528937"],"URL":"https:\/\/doi.org\/10.1145\/2528937","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2012-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}