{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T16:49:52Z","timestamp":1774716592966,"version":"3.50.1"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T00:00:00Z","timestamp":1654560000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T00:00:00Z","timestamp":1654560000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Institute of Information communications Technology Planning Evaluation","award":["2018-0-01398"],"award-info":[{"award-number":["2018-0-01398"]}]},{"name":"Institute of Information communications Technology Planning Evaluation","award":["2020-0-01373"],"award-info":[{"award-number":["2020-0-01373"]}]},{"DOI":"10.13039\/501100010418","name":"Institute for Information and Communications Technology Promotion","doi-asserted-by":"publisher","award":["2018-0-00551"],"award-info":[{"award-number":["2018-0-00551"]}],"id":[{"id":"10.13039\/501100010418","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2021R1A2B5B03001551"],"award-info":[{"award-number":["NRF-2021R1A2B5B03001551"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002380","name":"Hanyang University","doi-asserted-by":"publisher","award":["HY-202100000003161"],"award-info":[{"award-number":["HY-202100000003161"]}],"id":[{"id":"10.13039\/501100002380","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2023,3]]},"DOI":"10.1007\/s00778-022-00749-x","type":"journal-article","created":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T07:02:43Z","timestamp":1654585363000},"page":"343-368","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["Fast subgraph query processing and subgraph matching via static and dynamic equivalences"],"prefix":"10.1007","volume":"32","author":[{"given":"Hyunjoon","family":"Kim","sequence":"first","affiliation":[]},{"given":"Yunyoung","family":"Choi","sequence":"additional","affiliation":[]},{"given":"Kunsoo","family":"Park","sequence":"additional","affiliation":[]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[]},{"given":"Seok-Hee","family":"Hong","sequence":"additional","affiliation":[]},{"given":"Wook-Shin","family":"Han","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,7]]},"reference":[{"issue":"4","key":"749_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3129246","volume":"42","author":"CR Aberger","year":"2017","unstructured":"Aberger, C.R., Lamb, A., Tu, S., N\u00f6tzli, A., Olukotun, K., R\u00e9, C.: Emptyheaded: A relational engine for graph processing. ACM Trans. Datab. Syst. (TODS) 42(4), 1\u201344 (2017)","journal-title":"ACM Trans. Datab. Syst. (TODS)"},{"key":"749_CR2","doi-asserted-by":"crossref","unstructured":"Bhattarai, B., Liu, H., Huang, H.H.: Ceci: compact embedding cluster index for scalable subgraph matching. In: Proceedings of the 2019 International Conference on Management of Data, pp. 1447\u20131462 (2019)","DOI":"10.1145\/3299869.3300086"},{"key":"749_CR3","doi-asserted-by":"crossref","unstructured":"Bi, F., Chang, L., Lin, X., Qin, L., Zhang, W.: Efficient subgraph matching by postponing cartesian products. In: Proceedings of ACM SIGMOD, pp. 1199\u20131214 (2016)","DOI":"10.1145\/2882903.2915236"},{"key":"749_CR4","doi-asserted-by":"crossref","unstructured":"Bonnici, V., Ferro, A., Giugno, R., Pulvirenti, A., Shasha, D.: Enhancing graph database indexing by suffix tree structure. In: IAPR International Conference on Pattern Recognition in Bioinformatics, pp. 195\u2013203. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-16001-1_17"},{"issue":"7","key":"749_CR5","first-page":"1","volume":"14","author":"V Bonnici","year":"2013","unstructured":"Bonnici, V., Giugno, R., Pulvirenti, A., Shasha, D., Ferro, A.: A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinf. 14(7), 1\u201313 (2013)","journal-title":"BMC Bioinf."},{"key":"749_CR6","volume-title":"Data Management of Protein Interaction Networks","author":"M Cannataro","year":"2012","unstructured":"Cannataro, M., Guzzi, P.H.: Data Management of Protein Interaction Networks, vol. 17. John Wiley and Sons, New Jersey (2012)"},{"issue":"4","key":"749_CR7","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1109\/TPAMI.2017.2696940","volume":"40","author":"V Carletti","year":"2017","unstructured":"Carletti, V., Foggia, P., Saggese, A., Vento, M.: Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with vf3. IEEE Trans. Pattern Anal. Mach. Intell. 40(4), 804\u2013818 (2017)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"10","key":"749_CR8","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","volume":"26","author":"LP Cordella","year":"2004","unstructured":"Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(10), 1367\u20131372 (2004)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"749_CR9","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1186\/1471-2105-11-96","volume":"11","author":"R Di Natale","year":"2010","unstructured":"Di Natale, R., Ferro, A., Giugno, R., Mongiov\u00ec, M., Pulvirenti, A., Shasha, D.: Sing: Subgraph search in non-homogeneous graphs. BMC Bioinf. 11(1), 96 (2010)","journal-title":"BMC Bioinf."},{"key":"749_CR10","doi-asserted-by":"crossref","unstructured":"Fan, W.: Graph pattern matching revised for social network analysis. In: Proceedings of ICDT, pp. 8\u201321 (2012)","DOI":"10.1145\/2274576.2274578"},{"key":"749_CR11","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co. (1979)"},{"issue":"10","key":"749_CR12","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0076911","volume":"8","author":"R Giugno","year":"2013","unstructured":"Giugno, R., Bonnici, V., Bombieri, N., Pulvirenti, A., Ferro, A., Shasha, D.: Grapes: a software for parallel searching on biological graphs targeting multi-core architectures. PLoS ONE 8(10), e76911 (2013)","journal-title":"PLoS ONE"},{"key":"749_CR13","doi-asserted-by":"crossref","unstructured":"Han, M., Kim, H., Gu, G., Park, K., Han, W.S.: Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together. In: Proceedings of ACM SIGMOD, pp. 1429\u20131446 (2019)","DOI":"10.1145\/3299869.3319880"},{"key":"749_CR14","unstructured":"Han, W.S., Lee, J., Lee, J.H.: Turbo iso: Towards Ultrafast and Robust Subgraph Isomorphism Search in Large Graph Databases. In: Proceedings of ACM SIGMOD, pp. 337\u2013348 (2013)"},{"issue":"1\u20132","key":"749_CR15","doi-asserted-by":"publisher","first-page":"449","DOI":"10.14778\/1920841.1920901","volume":"3","author":"WS Han","year":"2010","unstructured":"Han, W.S., Lee, J., Pham, M.D., Yu, J.X.: igraph: a framework for comparisons of disk-based graph indexing techniques. Proc. VLDB Endow. 3(1\u20132), 449\u2013459 (2010)","journal-title":"Proc. VLDB Endow."},{"key":"749_CR16","doi-asserted-by":"crossref","unstructured":"He, H., Singh, A.K.: Graphs-at-a-time: query language and access methods for graph databases. In: Proceedings of ACM SIGMOD, pp. 405\u2013418 (2008)","DOI":"10.1145\/1376616.1376660"},{"key":"749_CR17","doi-asserted-by":"crossref","unstructured":"Kankanamge, C., Sahu, S., Mhedbhi, A., Chen, J., Salihoglu, S.: Graphflow: an active graph database. In: Proceedings of the 2017 ACM International Conference on Management of Data, pp. 1695\u20131698 (2017)","DOI":"10.1145\/3035918.3056445"},{"issue":"12","key":"749_CR18","doi-asserted-by":"publisher","first-page":"1566","DOI":"10.14778\/2824032.2824054","volume":"8","author":"F Katsarou","year":"2015","unstructured":"Katsarou, F., Ntarmos, N., Triantafillou, P.: Performance and scalability of indexed subgraph query processing methods. Proc. VLDB Endow. 8(12), 1566\u20131577 (2015)","journal-title":"Proc. VLDB Endow."},{"key":"749_CR19","doi-asserted-by":"crossref","unstructured":"Kim, H., Choi, Y., Park, K., Lin, X., Hong, S.H., Han, W.S.: Versatile equivalences: Speeding up subgraph query processing and subgraph matching. In: Proceedings of ACM SIGMOD, pp. 925\u2013937 (2021)","DOI":"10.1145\/3448016.3457265"},{"key":"749_CR20","doi-asserted-by":"crossref","unstructured":"Kim, J., Shin, H., Han, W.S., Hong, S., Chafi, H.: Taming subgraph isomorphism for rdf query processing. Proc. VLDB Endow. 8(11) (2015)","DOI":"10.14778\/2809974.2809985"},{"key":"749_CR21","doi-asserted-by":"crossref","unstructured":"Kim, K., Seo, I., Han, W.S., Lee, J.H., Hong, S., Chafi, H., Shin, H., Jeong, G.: Turboflux: A fast continuous subgraph matching system for streaming graph data. In: Proceedings of ACM SIGMOD, pp. 411\u2013426 (2018)","DOI":"10.1145\/3183713.3196917"},{"key":"749_CR22","doi-asserted-by":"crossref","unstructured":"Klein, K., Kriege, N., Mutzel, P.: Ct-index: Fingerprint-based graph indexing combining cycles and trees. In: Proceedings of IEEE ICDE, pp. 1115\u20131126 (2011)","DOI":"10.1109\/ICDE.2011.5767909"},{"issue":"2","key":"749_CR23","doi-asserted-by":"publisher","first-page":"133","DOI":"10.14778\/2535568.2448946","volume":"6","author":"J Lee","year":"2012","unstructured":"Lee, J., Han, W.S., Kasperovics, R., Lee, J.H.: An in-depth comparison of subgraph isomorphism algorithms in graph databases. Proc. VLDB Endow. 6(2), 133\u2013144 (2012)","journal-title":"Proc. VLDB Endow."},{"key":"749_CR24","unstructured":"Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data (2014)"},{"key":"749_CR25","doi-asserted-by":"crossref","unstructured":"Liang, Y., Zhao, P.: Workload-aware subgraph query caching and processing in large graphs. In: Proceedings of IEEE ICDE, pp. 1754\u20131757 (2019)","DOI":"10.1109\/ICDE.2019.00190"},{"key":"749_CR26","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1613\/jair.5768","volume":"61","author":"C McCreesh","year":"2018","unstructured":"McCreesh, C., Prosser, P., Solnon, C., Trimble, J.: When subgraph isomorphism is really hard, and why this matters for graph databases. J. Artif. Intell. Res. 61, 723\u2013759 (2018)","journal-title":"J. Artif. Intell. Res."},{"key":"749_CR27","unstructured":"McCreesh, C., Prosser, P., Trimble, J.: Heuristics and really hard instances for subgraph isomorphism problems. In: IJCAI, pp. 631\u2013638 (2016)"},{"key":"749_CR28","doi-asserted-by":"crossref","unstructured":"McCreesh, C., Prosser, P., Trimble, J.: The glasgow subgraph solver: using constraint programming to tackle hard subgraph isomorphism problem variants. In: International Conference on Graph Transformation, pp. 316\u2013324. Springer (2020)","DOI":"10.1007\/978-3-030-51372-6_19"},{"issue":"11","key":"749_CR29","doi-asserted-by":"publisher","first-page":"1692","DOI":"10.14778\/3342263.3342643","volume":"12","author":"A Mhedhbi","year":"2019","unstructured":"Mhedhbi, A., Salihoglu, S.: Optimizing subgraph queries by combining binary and worst-case optimal joins. Proc. VLDB Endow. 12(11), 1692\u20131704 (2019)","journal-title":"Proc. VLDB Endow."},{"key":"749_CR30","doi-asserted-by":"crossref","unstructured":"Park, H., Kim, M.S.: Evograph: an effective and efficient graph upscaling method for preserving graph properties. In: Proceedings of ACM SIGKDD, pp. 2051\u20132059 (2018)","DOI":"10.1145\/3219819.3220123"},{"issue":"8","key":"749_CR31","doi-asserted-by":"publisher","first-page":"974","DOI":"10.1093\/bioinformatics\/btl030","volume":"22","author":"N Pr\u017eulj","year":"2006","unstructured":"Pr\u017eulj, N., Corneil, D.G., Jurisica, I.: Efficient estimation of graphlet frequency distributions in protein-protein interaction networks. Bioinformatics 22(8), 974\u2013980 (2006)","journal-title":"Bioinformatics"},{"issue":"2","key":"749_CR32","doi-asserted-by":"publisher","first-page":"176","DOI":"10.14778\/3149193.3149198","volume":"11","author":"M Qiao","year":"2017","unstructured":"Qiao, M., Zhang, H., Cheng, H.: Subgraph matching: on compression and computation. Proc. VLDB Endow. 11(2), 176\u2013188 (2017)","journal-title":"Proc. VLDB Endow."},{"issue":"5","key":"749_CR33","doi-asserted-by":"publisher","first-page":"617","DOI":"10.14778\/2735479.2735493","volume":"8","author":"X Ren","year":"2015","unstructured":"Ren, X., Wang, J.: Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs. Proc. VLDB Endow. 8(5), 617\u2013628 (2015)","journal-title":"Proc. VLDB Endow."},{"issue":"3","key":"749_CR34","doi-asserted-by":"publisher","first-page":"121","DOI":"10.14778\/3021924.3021929","volume":"10","author":"X Ren","year":"2016","unstructured":"Ren, X., Wang, J.: Multi-query optimization for subgraph isomorphism search. Proc. VLDB Endow. 10(3), 121\u2013132 (2016)","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"749_CR35","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s10115-016-0968-2","volume":"51","author":"CR Rivero","year":"2017","unstructured":"Rivero, C.R., Jamil, H.M.: Efficient and scalable labeled subgraph matching using sgmatch. Knowl. Inf. Syst. 51(1), 61\u201387 (2017)","journal-title":"Knowl. Inf. Syst."},{"issue":"4","key":"749_CR36","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1145\/3186728.3164139","volume":"11","author":"S Sahu","year":"2017","unstructured":"Sahu, S., Mhedhbi, A., Salihoglu, S., Lin, J., \u00d6zsu, M.T.: The ubiquity of large graphs and surprising challenges of graph processing. Proc. VLDB Endow. 11(4), 420\u2013431 (2017)","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"749_CR37","doi-asserted-by":"publisher","first-page":"364","DOI":"10.14778\/1453856.1453899","volume":"1","author":"H Shang","year":"2008","unstructured":"Shang, H., Zhang, Y., Lin, X., Yu, J.X.: Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. Proc. VLDB Endow. 1(1), 364\u2013375 (2008)","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"749_CR38","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1111\/j.1467-9531.2006.00176.x","volume":"36","author":"TA Snijders","year":"2006","unstructured":"Snijders, T.A., Pattison, P.E., Robins, G.L., Handcock, M.S.: New specifications for exponential random graph models. Sociol. Methodol. 36(1), 99\u2013153 (2006)","journal-title":"Sociol. Methodol."},{"key":"749_CR39","doi-asserted-by":"crossref","unstructured":"Sun, S., Luo, Q.: Scaling up subgraph query processing with efficient subgraph matching. In: Proceedings of IEEE ICDE, pp. 220\u2013231 (2019)","DOI":"10.1109\/ICDE.2019.00028"},{"key":"749_CR40","doi-asserted-by":"crossref","unstructured":"Sun, S., Luo, Q.: In-memory subgraph matching: An in-depth study. In: Proceedings of ACM SIGMOD, pp. 1083\u20131098 (2020)","DOI":"10.1145\/3318464.3380581"},{"key":"749_CR41","unstructured":"Sun, S., Luo, Q.: Subgraph matching with effective matching order and indexing. IEEE Transactions on Knowledge and Data Engineering (2020)"},{"issue":"2","key":"749_CR42","doi-asserted-by":"publisher","first-page":"176","DOI":"10.14778\/3425879.3425888","volume":"14","author":"S Sun","year":"2020","unstructured":"Sun, S., Sun, X., Che, Y., Luo, Q., He, B.: Rapidmatch: a holistic approach to subgraph query processing. Proc. VLDB Endow. 14(2), 176\u2013188 (2020)","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"749_CR43","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/321921.321925","volume":"23","author":"JR Ullmann","year":"1976","unstructured":"Ullmann, J.R.: An algorithm for subgraph isomorphism. J. ACM 23(1), 31\u201342 (1976)","journal-title":"J. ACM"},{"key":"749_CR44","unstructured":"Wang, J., Ntarmos, N., Triantafillou, P.: Graphcache: a caching system for graph queries, pp. 13\u201324 (2017)"},{"key":"749_CR45","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/j.ins.2019.01.036","volume":"482","author":"J Wang","year":"2019","unstructured":"Wang, J., Ren, X., Anirban, S., Wu, X.W.: Correct filtering for subgraph isomorphism search in compressed vertex-labeled graphs. Inf. Sci. 482, 363\u2013373 (2019)","journal-title":"Inf. Sci."},{"key":"749_CR46","doi-asserted-by":"crossref","unstructured":"Yan, X., Yu, P.S., Han, J.: Graph indexing: a frequent structure-based approach. In: Proceedings of ACM SIGMOD, pp. 335\u2013346 (2004)","DOI":"10.1145\/1007568.1007607"},{"key":"749_CR47","doi-asserted-by":"crossref","unstructured":"Yanardag, P., Vishwanathan, S.: Deep graph kernels. In: Proceedings of ACM SIGKDD, pp. 1365\u20131374 (2015)","DOI":"10.1145\/2783258.2783417"},{"key":"749_CR48","doi-asserted-by":"crossref","unstructured":"Zhang, S., Li, S., Yang, J.: GADDI: Distance index based subgraph matching in biological networks. In: Proceedings of ACM EDBT, pp. 192\u2013203 (2009)","DOI":"10.1145\/1516360.1516384"},{"issue":"1\u20132","key":"749_CR49","doi-asserted-by":"publisher","first-page":"340","DOI":"10.14778\/1920841.1920887","volume":"3","author":"P Zhao","year":"2010","unstructured":"Zhao, P., Han, J.: On graph query optimization in large networks. Proc. VLDB Endow. 3(1\u20132), 340\u2013351 (2010)","journal-title":"Proc. VLDB Endow."},{"key":"749_CR50","unstructured":"Zhao, P., Yu, J.X., Philip, S.Y.: Graph indexing: Tree+ delta$$>=$$ graph. In: Proceedings of VLDB, pp. 938\u2013949 (2007)"},{"key":"749_CR51","doi-asserted-by":"crossref","unstructured":"Zou, L., Chen, L., Yu, J.X., Lu, Y.: A novel spectral coding in a large graph database. In: Proceedings of EDBT, pp. 181\u2013192 (2008)","DOI":"10.1145\/1353343.1353369"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-022-00749-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-022-00749-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-022-00749-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,25]],"date-time":"2023-02-25T05:06:41Z","timestamp":1677301601000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-022-00749-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,7]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["749"],"URL":"https:\/\/doi.org\/10.1007\/s00778-022-00749-x","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,7]]},"assertion":[{"value":"20 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Seok-Hee Hong works in the same university as Alan Fekete of the editorial board. Wook-Shin Han has a conflict of interest with Kyu-Young Whang in the editorial board.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}