{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T04:42:12Z","timestamp":1773895332845,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Institute for Information & communications Technology Promotion( IITP) grant funded by the Korea government(MSIT) (No. 2018- 0-00551, Framework of Practical Algorithms for NP-hard Graph Problems); Institute of Information communications Technology Planning Evaluation(IITP) grant funded by the Korea government(MSIT) (No. 2018-0-01398, Development of a Conversational, Self-tuning DBMS)"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,9]]},"DOI":"10.1145\/3448016.3457265","type":"proceedings-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T17:22:39Z","timestamp":1624036959000},"page":"925-937","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":56,"title":["Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching"],"prefix":"10.1145","author":[{"given":"Hyunjoon","family":"Kim","sequence":"first","affiliation":[{"name":"Seoul National University & SAP Labs Korea, Seoul, Republic of Korea"}]},{"given":"Yunyoung","family":"Choi","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Republic of Korea"}]},{"given":"Kunsoo","family":"Park","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Republic of Korea"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, NSW, Australia"}]},{"given":"Seok-Hee","family":"Hong","sequence":"additional","affiliation":[{"name":"The University of Sydney, Sydney, NSW, Australia"}]},{"given":"Wook-Shin","family":"Han","sequence":"additional","affiliation":[{"name":"Pohang University of Science and Technology (POSTECH), Pohang, Republic of Korea"}]}],"member":"320","published-online":{"date-parts":[[2021,6,18]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16001-1_17"},{"key":"e_1_3_2_2_4_1","volume-title":"A subgraph isomorphism algorithm and its application to biochemical data. BMC bioinformatics 14, 7","author":"Bonnici Vincenzo","year":"2013","unstructured":"Vincenzo Bonnici , Rosalba Giugno , Alfredo Pulvirenti , Dennis Shasha , and Alfredo Ferro . 2013. A subgraph isomorphism algorithm and its application to biochemical data. BMC bioinformatics 14, 7 ( 2013 ), 1--13. Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, and Alfredo Ferro. 2013. A subgraph isomorphism algorithm and its application to biochemical data. BMC bioinformatics 14, 7 (2013), 1--13."},{"key":"e_1_3_2_2_5_1","volume-title":"Data management of protein interaction networks","author":"Cannataro Mario","unstructured":"Mario Cannataro and PietroHGuzzi. 2012. Data management of protein interaction networks . Vol. 17 . John Wiley & Sons . Mario Cannataro and PietroHGuzzi. 2012. Data management of protein interaction networks. Vol. 17. John Wiley & Sons."},{"key":"e_1_3_2_2_6_1","volume-title":"Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3","author":"Carletti Vincenzo","year":"2017","unstructured":"Vincenzo Carletti , Pasquale Foggia , Alessia Saggese , and Mario Vento . 2017. Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3 . IEEE transactions on pattern analysis and machine intelligence 40, 4 ( 2017 ), 804--818. Vincenzo Carletti, Pasquale Foggia, Alessia Saggese, and Mario Vento. 2017. Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3. IEEE transactions on pattern analysis and machine intelligence 40, 4 (2017), 804--818."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_3_2_2_8_1","volume-title":"Sing: Subgraph search in non-homogeneous graphs. BMC bioinformatics 11, 1","author":"Natale Raffaele Di","year":"2010","unstructured":"Raffaele Di Natale , Alfredo Ferro , Rosalba Giugno , Misael Mongiov\u00ec , Alfredo Pulvirenti , and Dennis Shasha . 2010 . Sing: Subgraph search in non-homogeneous graphs. BMC bioinformatics 11, 1 (2010), 96. Raffaele Di Natale, Alfredo Ferro, Rosalba Giugno, Misael Mongiov\u00ec, Alfredo Pulvirenti, and Dennis Shasha. 2010. Sing: Subgraph search in non-homogeneous graphs. BMC bioinformatics 11, 1 (2010), 96."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274578"},{"key":"e_1_3_2_2_10_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0076911"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920901"},{"key":"e_1_3_2_2_15_1","volume-title":"Singh","author":"He Huahai","year":"2008","unstructured":"Huahai He and Ambuj K . Singh . 2008 . Graphs-at-a-time : Query Language and Access Methods for Graph Databases. In Proceedings of ACM SIGMOD. 405--418. https:\/\/doi.org\/10.1145\/1376616.1376660 10.1145\/1376616.1376660 Huahai He and Ambuj K. Singh. 2008. Graphs-at-a-time: Query Language and Access Methods for Graph Databases. In Proceedings of ACM SIGMOD. 405--418. https:\/\/doi.org\/10.1145\/1376616.1376660"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824054"},{"key":"e_1_3_2_2_17_1","first-page":"11","volume-title":"Taming Subgraph Isomorphism for RDF Query Processing. Proceedings of the VLDB Endowment 8","author":"Kim Jinha","year":"2015","unstructured":"Jinha Kim , Hyungyu Shin , Wook-Shin Han , Sungpack Hong , and Hassan Chafi . 2015 . Taming Subgraph Isomorphism for RDF Query Processing. Proceedings of the VLDB Endowment 8 , 11 (2015). Jinha Kim, Hyungyu Shin, Wook-Shin Han, Sungpack Hong, and Hassan Chafi. 2015. Taming Subgraph Isomorphism for RDF Query Processing. Proceedings of the VLDB Endowment 8, 11 (2015)."},{"key":"e_1_3_2_2_18_1","volume-title":"Seo, Wook-Shin Han, Jeong-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, and Geonhwa Jeong.","author":"Kim Kyoungmin","year":"2018","unstructured":"Kyoungmin Kim , In Seo, Wook-Shin Han, Jeong-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, and Geonhwa Jeong. 2018 . Turboflux : A fast continuous subgraph matching system for streaming graph data. In Proceedings of the 2018 International Conference on Management of Data . 411--426. Kyoungmin Kim, In Seo, Wook-Shin Han, Jeong-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, and Geonhwa Jeong. 2018. Turboflux: A fast continuous subgraph matching system for streaming graph data. In Proceedings of the 2018 International Conference on Management of Data. 411--426."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767909"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448946"},{"key":"e_1_3_2_2_21_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00190"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/3241691.3241707"},{"key":"e_1_3_2_2_24_1","unstructured":"Ciaran McCreesh Patrick Prosser and James Trimble. 2016. Heuristics and Really Hard Instances for Subgraph Isomorphism Problems.. In IJCAI. 631--638.  Ciaran McCreesh Patrick Prosser and James Trimble. 2016. Heuristics and Really Hard Instances for Subgraph Isomorphism Problems.. In IJCAI. 631--638."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-51372-6_19"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220123"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl030"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149198"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735493"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0968-2"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3164135.3164139"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_3_2_2_34_1","volume-title":"New specifications for exponential random graph models. Sociological methodology 36, 1","author":"Snijders Tom AB","year":"2006","unstructured":"Tom AB Snijders , Philippa E Pattison , Garry L Robins , and Mark S Handcock . 2006. New specifications for exponential random graph models. Sociological methodology 36, 1 ( 2006 ), 99--153. Tom AB Snijders, Philippa E Pattison, Garry L Robins, and Mark S Handcock. 2006. New specifications for exponential random graph models. Sociological methodology 36, 1 (2006), 99--153."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00028"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_3_2_2_38_1","unstructured":"Jing Wang Nikos Ntarmos and Peter Triantafillou. 2017. GraphCache: a caching system for graph queries. (2017) 13--24.  Jing Wang Nikos Ntarmos and Peter Triantafillou. 2017. GraphCache: a caching system for graph queries. (2017) 13--24."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.01.036"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783417"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516384"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"},{"key":"e_1_3_2_2_44_1","volume-title":"Proceedings of VLDB. 938--949","author":"Zhao Peixiang","year":"2007","unstructured":"Peixiang Zhao , Jeffrey Xu Yu , and S Yu Philip . 2007 . Graph indexing: Tree+ Delta>= Graph .. In Proceedings of VLDB. 938--949 . Peixiang Zhao, Jeffrey Xu Yu, and S Yu Philip. 2007. Graph indexing: Tree+ Delta>= Graph.. In Proceedings of VLDB. 938--949."},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353369"}],"event":{"name":"SIGMOD\/PODS '21: International Conference on Management of Data","location":"Virtual Event China","acronym":"SIGMOD\/PODS '21","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2021 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3457265","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448016.3457265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:06Z","timestamp":1750195686000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3457265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,9]]},"references-count":45,"alternative-id":["10.1145\/3448016.3457265","10.1145\/3448016"],"URL":"https:\/\/doi.org\/10.1145\/3448016.3457265","relation":{},"subject":[],"published":{"date-parts":[[2021,6,9]]},"assertion":[{"value":"2021-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}