{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T22:40:08Z","timestamp":1744152008842,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030739720"},{"type":"electronic","value":"9783030739737"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-73973-7_24","type":"book-chapter","created":{"date-parts":[[2021,4,9]],"date-time":"2021-04-09T14:03:24Z","timestamp":1617977004000},"page":"248-258","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parallel Subgraph Isomorphism on Multi-core Architectures: A Comparison of Four Strategies Based on Tree Search"],"prefix":"10.1007","author":[{"given":"Vincenzo","family":"Carletti","sequence":"first","affiliation":[]},{"given":"Pasquale","family":"Foggia","sequence":"additional","affiliation":[]},{"given":"Antonio","family":"Greco","sequence":"additional","affiliation":[]},{"given":"Mario","family":"Vento","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,10]]},"reference":[{"key":"24_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/978-3-030-19212-9_2","volume-title":"Integration of Constraint Programming, Artificial Intelligence, and Operations Research","author":"B Archibald","year":"2019","unstructured":"Archibald, B., Dunlop, F., Hoffmann, R., McCreesh, C., Prosser, P., Trimble, J.: Sequential and parallel solution-biased search for subgraph algorithms. In: Rousseau, L.-M., Stergiou, K. (eds.) CPAIOR 2019. LNCS, vol. 11494, pp. 20\u201338. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-19212-9_2"},{"key":"24_CR2","doi-asserted-by":"publisher","unstructured":"Bi, F., Chang, L., Lin, X., Qin, L., Zhang, W.: Efficient subgraph matching by postponing Cartesian products. In: Proceedings of the 2016 International Conference on Management of Data. Association for Computing Machinery (2016). https:\/\/doi.org\/10.1145\/2882903.2915236","DOI":"10.1145\/2882903.2915236"},{"key":"24_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-14-S7-S13","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 Bioinform. 14, 1\u201313 (2013)","journal-title":"BMC Bioinform."},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1109\/TPAMI.2017.2696940","volume":"40","author":"V Carletti","year":"2018","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, 804\u2013818 (2018)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"24_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/978-3-319-18224-7_18","volume-title":"Graph-Based Representations in Pattern Recognition","author":"V Carletti","year":"2015","unstructured":"Carletti, V., Foggia, P., Vento, M., Jiang, X.: Report on the first contest on graph matching algorithms for pattern search in biological databases. In: Liu, C.-L., Luo, B., Kropatsch, W.G., Cheng, J. (eds.) GbRPR 2015. LNCS, vol. 9069, pp. 178\u2013187. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-18224-7_18"},{"key":"24_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-319-97785-0_30","volume-title":"Structural, Syntactic, and Statistical Pattern Recognition","author":"V Carletti","year":"2018","unstructured":"Carletti, V., Foggia, P., Greco, A., Saggese, A., Vento, M.: The VF3-light subgraph isomorphism algorithm: when doing less is more effective. In: Bai, X., Hancock, E.R., Ho, T.K., Wilson, R.C., Biggio, B., Robles-Kelly, A. (eds.) S+SSPR 2018. LNCS, vol. 11004, pp. 315\u2013325. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-97785-0_30"},{"key":"24_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/978-3-030-20081-7_14","volume-title":"Graph-Based Representations in Pattern Recognition","author":"V Carletti","year":"2019","unstructured":"Carletti, V., Foggia, P., Ritrovato, P., Vento, M., Vigilante, V.: A parallel algorithm for subgraph isomorphism. In: Conte, D., Ramel, J.-Y., Foggia, P. (eds.) GbRPR 2019. LNCS, vol. 11510, pp. 141\u2013151. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-20081-7_14"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-642-41190-8_44","volume-title":"New Trends in Image Analysis and Processing \u2013 ICIAP 2013","author":"V Carletti","year":"2013","unstructured":"Carletti, V., Foggia, P., Vento, M.: Performance comparison of five exact graph matching algorithms on biological databases. In: Petrosino, A., Maddalena, L., Pala, P. (eds.) ICIAP 2013. LNCS, vol. 8158, pp. 409\u2013417. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-41190-8_44"},{"key":"24_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/978-3-319-18224-7_17","volume-title":"Graph-Based Representations in Pattern Recognition","author":"V Carletti","year":"2015","unstructured":"Carletti, V., Foggia, P., Vento, M.: VF2 plus: an improved version of VF2 for biological graphs. In: Liu, C.-L., Luo, B., Kropatsch, W.G., Cheng, J. (eds.) GbRPR 2015. LNCS, vol. 9069, pp. 168\u2013177. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-18224-7_17"},{"key":"24_CR10","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1142\/S0218001404003228","volume":"18","author":"D Conte","year":"2004","unstructured":"Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. Int. J. Pattern Recogn. Artif. Intell. 18, 265\u2013298 (2004)","journal-title":"Int. J. Pattern Recogn. Artif. Intell."},{"key":"24_CR11","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","volume":"26","author":"L Cordella","year":"2004","unstructured":"Cordella, L., Foggia, P., Sansone, C., Vento, M.: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26, 1367\u20131372 (2004)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"1450001","DOI":"10.1142\/S0218001414500013","volume":"28","author":"P Foggia","year":"2014","unstructured":"Foggia, P., Percannella, G., Vento, M.: Graph matching and learning in pattern recognition in the last ten years. Int. J. Patt. Recogn. Artif. Intell. 28, 1450001 (2014)","journal-title":"Int. J. Patt. Recogn. Artif. Intell."},{"key":"24_CR13","unstructured":"Han, W., Lee, J.h., Lee, J.: TurboISO: towards ultrafast and robust subgraph isomorphism search in large graph databases. In: SIGMOD pp. 337\u2013348 (2013)"},{"key":"24_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/978-3-642-23397-5_42","volume-title":"Euro-Par 2011 Parallel Processing","author":"J Jenkins","year":"2011","unstructured":"Jenkins, J., Arkatkar, I., Owens, J.D., Choudhary, A., Samatova, N.F.: Lessons learned from exploring the backtracking paradigm on the GPU. In: Jeannot, E., Namyst, R., Roman, J. (eds.) Euro-Par 2011. LNCS, vol. 6853, pp. 425\u2013437. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-23397-5_42"},{"key":"24_CR15","doi-asserted-by":"publisher","unstructured":"Jin, X., Lai, L.: MPMatch: a multi-core parallel subgraph matching algorithm (2019). https:\/\/doi.org\/10.1109\/ICDEW.2019.000-6","DOI":"10.1109\/ICDEW.2019.000-6"},{"key":"24_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-319-23219-5_21","volume-title":"Principles and Practice of Constraint Programming","author":"C McCreesh","year":"2015","unstructured":"McCreesh, C., Prosser, P.: A parallel, backjumping subgraph isomorphism algorithm using supplemental graphs. In: Pesant, G. (ed.) CP 2015. LNCS, vol. 9255, pp. 295\u2013312. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-23219-5_21"},{"key":"24_CR17","doi-asserted-by":"crossref","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)","DOI":"10.14778\/1453856.1453899"},{"key":"24_CR18","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1016\/j.artint.2010.05.002","volume":"174","author":"C Solnon","year":"2010","unstructured":"Solnon, C.: AllDifferent-based filtering for subgraph isomorphism. Artif. Intell. 174, 850\u2013864 (2010)","journal-title":"Artif. Intell."},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"Sun, Z., Wang, H., Wang, H., Shao, B., Li, J.: Efficient subgraph matching on billion node graphs. Proc. VLDB Endow. (2012). https:\/\/doi.org\/10.14778\/2311906.2311907","DOI":"10.14778\/2311906.2311907"},{"key":"24_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-319-18120-2_18","volume-title":"Database Systems for Advanced Applications","author":"H-N Tran","year":"2015","unstructured":"Tran, H.-N., Kim, J., He, B.: Fast subgraph matching on large graphs using graphics processors. In: Renz, M., Shahabi, C., Zhou, X., Cheema, M.A. (eds.) DASFAA 2015. LNCS, vol. 9049, pp. 299\u2013315. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-18120-2_18"},{"key":"24_CR21","doi-asserted-by":"publisher","unstructured":"Ullmann, J.R.: Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. ACM J. Exp. Algorithmics 15 (2011). https:\/\/doi.org\/10.1145\/1671970.1921702. Association for Computing Machinery","DOI":"10.1145\/1671970.1921702"},{"key":"24_CR22","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/j.patcog.2014.01.002","volume":"48","author":"M Vento","year":"2014","unstructured":"Vento, M.: A long trip in the charming world of graphs for pattern recognition. Pattern Recogn. 48, 291\u2013301 (2014)","journal-title":"Pattern Recogn."},{"key":"24_CR23","doi-asserted-by":"crossref","unstructured":"Xu, Q., Jeon, H., Annavaram, M.: Graph processing on GPUS: where are the bottlenecks. In: 2014 IEEE International Symposium on Workload Characterization (2014)","DOI":"10.1109\/IISWC.2014.6983053"},{"key":"24_CR24","doi-asserted-by":"crossref","unstructured":"Zeng, L., Zou, L., \u00d6zsu, M.T., Hu, L., Zhang, F.: GSI: GPU-friendly subgraph isomorphism. In: 2020 IEEE 36th International Conference on Data Engineering (ICDE), pp. 1249\u20131260 (2020)","DOI":"10.1109\/ICDE48307.2020.00112"}],"container-title":["Lecture Notes in Computer Science","Structural, Syntactic, and Statistical Pattern Recognition"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-73973-7_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T22:03:14Z","timestamp":1744149794000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-73973-7_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030739720","9783030739737"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-73973-7_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"10 April 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"S+SSPR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR)","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 January 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 January 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sspr2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.dais.unive.it\/sspr2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"81","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}