{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:40:00Z","timestamp":1740123600484,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"PHC Tassili","award":["BiGreen no18 MDU 111"],"award-info":[{"award-number":["BiGreen no18 MDU 111"]}]},{"DOI":"10.13039\/501100005307","name":"DGRSDT","doi-asserted-by":"crossref","award":["FNRSDT no 253"],"award-info":[{"award-number":["FNRSDT no 253"]}],"id":[{"id":"10.13039\/501100005307","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s11227-021-03938-7","type":"journal-article","created":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T11:02:39Z","timestamp":1623754959000},"page":"1642-1671","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient parallel edge-centric approach for relaxed graph pattern matching"],"prefix":"10.1007","volume":"78","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1091-3909","authenticated-orcid":false,"given":"Sarra","family":"Bouhenni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sa\u00efd","family":"Yahiaoui","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"Nouali-Taboudjemat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hamamache","family":"Kheddouci","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"3938_CR1","doi-asserted-by":"crossref","unstructured":"Bhattarai B, Liu H, Huang HH (2019) Ceci: compact embedding cluster index for scalable subgraph matching. In: Proceedings of the 2019 International Conference on Management of Data, pp. 1447\u20131462. ACM, Amsterdam, Netherlands","DOI":"10.1145\/3299869.3300086"},{"key":"3938_CR2","doi-asserted-by":"crossref","unstructured":"Bi F, Chang L, Lin X, Qin L, Zhang W (2016) Efficient subgraph matching by postponing cartesian products. In: Proceedings of the 2016 International Conference on Management of Data, pp. 1199\u20131214. ACM, San Francisco, California, USA","DOI":"10.1145\/2882903.2915236"},{"key":"3938_CR3","doi-asserted-by":"publisher","DOI":"10.1145\/3439724","author":"S Bouhenni","year":"2021","unstructured":"Bouhenni S, Yahiaoui S, Nouali-Taboudjemat N, Kheddouci H (2021) A survey on distributed graph pattern matching in massive graphs. ACM Comput Surv. https:\/\/doi.org\/10.1145\/3439724","journal-title":"ACM Comput Surv"},{"key":"3938_CR4","doi-asserted-by":"crossref","unstructured":"Chakrabarti D, Zhan Y, Faloutsos C (2004) R-mat: a recursive model for graph mining. In: Proceedings of the 2004 SIAM International Conference on Data Mining, pp. 442\u2013446. SIAM","DOI":"10.1137\/1.9781611972740.43"},{"key":"3938_CR5","unstructured":"Cordella LP, Foggia P, Sansone C, Vento M (2001) An improved algorithm for matching large graphs. Proceedings of the 3rd IAPR workshop on graph-based representations in pattern recognition 219(2):149\u2013159. https:\/\/doi.org\/10.1.1.101.5342"},{"key":"3938_CR6","doi-asserted-by":"crossref","unstructured":"Csun S, Luo Q (2018) Parallelizing recursive backtracking based subgraph matching on a single machine. 2018 IEEE 24th International Conference on Parallel and Distributed Systems (ICPADS). IEEE, Singapore, Singapore, pp 1\u20139","DOI":"10.1109\/PADSW.2018.8644869"},{"key":"3938_CR7","unstructured":"Dustin WS (2019) Social media statistics 2020: top networks by the numbers. https:\/\/dustinstout.com\/social-media-statistics\/. Accessed: 2021-03-01"},{"key":"3938_CR8","doi-asserted-by":"publisher","unstructured":"Fan W (2012) Graph pattern matching revised for social network analysis. In: Proceedings of the 15th International Conference on Database Theory, ICDT \u201912, p. 8-21. Association for Computing Machinery, New York, NY, USA. https:\/\/doi.org\/10.1145\/2274576.2274578","DOI":"10.1145\/2274576.2274578"},{"issue":"1\u20132","key":"3938_CR9","doi-asserted-by":"publisher","first-page":"264","DOI":"10.14778\/1920841.1920878","volume":"3","author":"W Fan","year":"2010","unstructured":"Fan W, Li J, Ma S, Tang N, Wu Y, Wu Y (2010) 1Graph pattern matching: from intractable to polynomial time. Proc VLDB Endow 3(1\u20132):264\u2013275 (10.14778\/1920841.1920878)","journal-title":"Proc VLDB Endow"},{"issue":"13","key":"3938_CR10","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.14778\/2536258.2536263","volume":"6","author":"W Fan","year":"2013","unstructured":"Fan W, Wang X, Wu Y (2013) Diversified top-k graph pattern matching. Proc VLDB Endow 6(13):1510\u20131521","journal-title":"Proc VLDB Endow"},{"key":"3938_CR11","doi-asserted-by":"publisher","DOI":"10.1145\/2489791","author":"W Fan","year":"2013","unstructured":"Fan W, Wang X, Wu Y (2013) Incremental graph pattern matching. Database Syst ACM Trans. https:\/\/doi.org\/10.1145\/2489791","journal-title":"Database Syst ACM Trans"},{"issue":"12","key":"3938_CR12","doi-asserted-by":"publisher","first-page":"1083","DOI":"10.14778\/2732977.2732983","volume":"7","author":"W Fan","year":"2014","unstructured":"Fan W, Wang X, Wu Y, Deng D (2014) Distributed graph simulation: impossibility and possibility. Proc VLDB Endow 7(12):1083\u20131094 (10.14778\/2732977.2732983)","journal-title":"Proc VLDB Endow"},{"issue":"4","key":"3938_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3282488","volume":"43","author":"W Fan","year":"2018","unstructured":"Fan W, Yu W, Xu J, Zhou J, Luo X, Yin Q, Lu P, Cao Y, Xu R (2018) Parallelizing sequential graph computations. ACM Trans Database Syst (TODS) 43(4):1\u201339","journal-title":"ACM Trans Database Syst (TODS)"},{"key":"3938_CR14","doi-asserted-by":"publisher","unstructured":"Fard A, Nisar MU, Ramaswamy L, Miller JA, Saltz M (2013) A distributed vertex-centric approach for pattern matching in massive graphs. In: 2013 IEEE International Conference on Big Data, pp. 403\u2013411. IEEE, Santa Clara, CA, USA. https:\/\/doi.org\/10.1109\/BigData.2013.6691601","DOI":"10.1109\/BigData.2013.6691601"},{"issue":"6","key":"3938_CR15","doi-asserted-by":"publisher","first-page":"848","DOI":"10.1093\/comjnl\/bxu159","volume":"59","author":"J Gao","year":"2016","unstructured":"Gao J, Liu P, Kang X, Zhang L, Wang J (2016) Prs: parallel relaxation simulation for massive graphs. Comput J 59(6):848\u2013860","journal-title":"Comput J"},{"key":"3938_CR16","doi-asserted-by":"crossref","unstructured":"Gao J, Zhou C, Zhou J, Yu JX (2014) Continuous pattern detection over billion-edge graph using distributed framework. 2014 IEEE 30th International Conference on Data Engineering. IEEE, Chicago, IL, USA, pp 556\u2013567","DOI":"10.1109\/ICDE.2014.6816681"},{"key":"3938_CR17","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to np-completeness"},{"key":"3938_CR18","unstructured":"Gurajada S, Seufert S, Miliaraki I, Theobald M (2014) Triad: a distributed shared-nothing rdf engine based on asynchronous message passing. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp. 289\u2013300. ACM, Utah USA"},{"key":"3938_CR19","doi-asserted-by":"publisher","unstructured":"Han WS, Lee J, Lee JH (2013) Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, SIGMOD \u201913, pp. 337\u2013348. Association for Computing Machinery, New York, New York, USA. https:\/\/doi.org\/10.1145\/2463676.2465300","DOI":"10.1145\/2463676.2465300"},{"key":"3938_CR20","doi-asserted-by":"publisher","unstructured":"He H, Singh AK (2008) Graphs-at-a-time: Query language and access methods for graph databases. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD \u201908, pp. 405\u2013418. Association for Computing Machinery, Vancouver, Canada. https:\/\/doi.org\/10.1145\/1376616.1376660","DOI":"10.1145\/1376616.1376660"},{"key":"3938_CR21","unstructured":"Henzinger MR, Henzinger TA, Kopke PW (1995) Computing simulations on finite and infinite graphs. In: Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 453\u2013462. IEEE, USA"},{"key":"3938_CR22","doi-asserted-by":"publisher","unstructured":"Kao JS, Chou J (2016) Distributed incremental pattern matching on streaming graphs. In: Proceedings of the ACM Workshop on High Performance Graph Processing, HPGP \u201916, p. 43-50. Association for Computing Machinery, Kyoto, Japan. https:\/\/doi.org\/10.1145\/2915516.2915519","DOI":"10.1145\/2915516.2915519"},{"issue":"10","key":"3938_CR23","doi-asserted-by":"publisher","first-page":"974","DOI":"10.14778\/2794367.2794368","volume":"8","author":"L Lai","year":"2015","unstructured":"Lai L, Qin L, Lin X, Chang L (2015) Scalable subgraph enumeration in mapreduce. Proc VLDB Endow 8(10):974\u2013985","journal-title":"Proc VLDB Endow"},{"issue":"3","key":"3938_CR24","doi-asserted-by":"publisher","first-page":"217","DOI":"10.14778\/3021924.3021937","volume":"10","author":"L Lai","year":"2016","unstructured":"Lai L, Qin L, Lin X, Zhang Y, Chang L, Yang S (2016) Scalable distributed subgraph enumeration. Proc VLDB Endow 10(3):217\u2013228","journal-title":"Proc VLDB Endow"},{"issue":"10","key":"3938_CR25","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.14778\/3339490.3339494","volume":"12","author":"L Lai","year":"2019","unstructured":"Lai L, Qing Z, Yang Z, Jin X, Lai Z, Wang R, Hao K, Lin X, Qin L, Zhang W et al (2019) Distributed subgraph matching on timely dataflow. Proc VLDB Endow 12(10):1099\u20131112","journal-title":"Proc VLDB Endow"},{"key":"3938_CR26","unstructured":"Leskovec J, Krevl A (2014) SNAP Datasets: stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"key":"3938_CR27","doi-asserted-by":"crossref","unstructured":"Li J, Cao Y, Ma S (2017) Relaxing graph pattern matching with explanations. In: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp. 1677\u20131686. ACM, Singapore Singapore","DOI":"10.1145\/3132847.3132992"},{"key":"3938_CR28","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/978-981-13-2922-7_16","volume-title":"Big Data","author":"J Li","year":"2018","unstructured":"Li J, Li J, Wang X (2018) A vertex-centric graph simulation algorithm for large graphs. In: Xu Z, Gao X, Miao Q, Zhang Y, Bu J (eds) Big Data. Springer, Singapore, pp 238\u2013254"},{"key":"3938_CR29","doi-asserted-by":"publisher","unstructured":"Liu C, Chen C, Han J, Yu PS (2006) Gplag: detection of software plagiarism by program dependence graph analysis. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD \u201906, pp. 872\u2013881. Association for Computing Machinery, New York, NY, USA. https:\/\/doi.org\/10.1145\/1150402.1150522","DOI":"10.1145\/1150402.1150522"},{"issue":"4","key":"3938_CR30","doi-asserted-by":"publisher","first-page":"310","DOI":"10.14778\/2095686.2095690","volume":"5","author":"S Ma","year":"2011","unstructured":"Ma S, Cao Y, Fan W, Huai J, Wo T (2011) Capturing topology in graph pattern matching. Proc VLDB Endow 5(4):310\u2013321","journal-title":"Proc VLDB Endow"},{"key":"3938_CR31","doi-asserted-by":"publisher","unstructured":"Ma S, Cao Y, Huai J, Wo T (2012) Distributed graph pattern matching. In: Proceedings of the 21st International Conference on World Wide Web, WWW \u201912, pp. 949\u2013958. Association for Computing Machinery, Lyon, France. https:\/\/doi.org\/10.1145\/2187836.2187963","DOI":"10.1145\/2187836.2187963"},{"key":"3938_CR32","doi-asserted-by":"crossref","unstructured":"Malewicz G, Austern MH, Bik AJ, Dehnert JC, Horn I, Leiser N, Czajkowski G (2010) Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pp. 135\u2013146","DOI":"10.1145\/1807167.1807184"},{"key":"3938_CR33","unstructured":"Milner R (1989) Communication and concurrency, vol.\u00a084. Prentice hall Englewood Cliffs"},{"key":"3938_CR34","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-642-37210-0_37","volume-title":"Social computing, behavioral-cultural modeling and prediction","author":"K Ogaard","year":"2013","unstructured":"Ogaard K, Roy H, Kase S, Nagi R, Sambhoos K, Sudit M (2013) Discovering patterns in social networks with graph matching algorithms. In: Greenberg AM, Kennedy WG, Bos ND (eds) Social computing, behavioral-cultural modeling and prediction. Springer, Berlin, Heidelberg, pp 341\u2013349"},{"issue":"2","key":"3938_CR35","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s00778-015-0415-0","volume":"25","author":"P Peng","year":"2016","unstructured":"Peng P, Zou L, \u00d6zsu MT, Chen L, Zhao D (2016) Processing sparql queries over distributed rdf graphs. VLDB J 25(2):243\u2013268","journal-title":"VLDB J"},{"issue":"2","key":"3938_CR36","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 (2017) Subgraph matching: on compression and computation. Proc VLDB Endow 11(2):176\u2013188","journal-title":"Proc VLDB Endow"},{"issue":"5","key":"3938_CR37","doi-asserted-by":"publisher","first-page":"617","DOI":"10.14778\/2735479.2735493","volume":"8","author":"X Ren","year":"2015","unstructured":"Ren X, Wang J (2015) Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs. Proceedings of the VLDB Endowment 8(5):617\u2013628","journal-title":"Proceedings of the VLDB Endowment"},{"key":"3938_CR38","doi-asserted-by":"publisher","unstructured":"Reza T, Ripeanu M, Tripoul N, Sanders G, Pearce R (2018) Prunejuice: pruning trillion-edge graphs to a precise pattern-matching solution. In: SC18: International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 265\u2013281. IEEE, Dallas, Texas, USA. https:\/\/doi.org\/10.1109\/SC.2018.00024","DOI":"10.1109\/SC.2018.00024"},{"key":"3938_CR39","first-page":"155","volume-title":"Biomedical data management and graph online querying","author":"A Sch\u00e4tzle","year":"2016","unstructured":"Sch\u00e4tzle A, Przyjaciel-Zablocki M, Berberich T, Lausen G (2016) S2x: graph-parallel querying of rdf with graphx. In: Wang F, Luo G, Weng C, Khan A, Mitra P, Yu C (eds) Biomedical data management and graph online querying. Springer International Publishing, Cham, pp 155\u2013168"},{"key":"3938_CR40","doi-asserted-by":"crossref","unstructured":"Serafini M, De\u00a0Francisci\u00a0Morales G, Siganos G (2017) Qfrag: distributed graph search via subgraph isomorphism. In: proceedings of the 2017 symposium on cloud computing, pp. 214\u2013228. ACM, Santa Clara, CA","DOI":"10.1145\/3127479.3131625"},{"issue":"1","key":"3938_CR41","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 JX (2008) Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. Proc VLDB Endow 1(1):364\u2013375","journal-title":"Proc VLDB Endow"},{"key":"3938_CR42","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/j.knosys.2016.07.009","volume":"109","author":"A Shemshadi","year":"2016","unstructured":"Shemshadi A, Sheng QZ, Qin Y (2016) Efficient pattern matching for graphs with multi-labeled nodes. Know-Based Syst 109:256\u2013265","journal-title":"Know-Based Syst"},{"issue":"9","key":"3938_CR43","doi-asserted-by":"publisher","first-page":"788","DOI":"10.14778\/2311906.2311907","volume":"5","author":"Z Sun","year":"2012","unstructured":"Sun Z, Wang H, Wang H, Shao B, Li J (2012) Efficient subgraph matching on billion node graphs. Proc VLDB Endow 5(9):788\u2013799","journal-title":"Proc VLDB Endow"},{"issue":"1","key":"3938_CR44","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/321921.321925","volume":"23","author":"JR Ullmann","year":"1976","unstructured":"Ullmann JR (1976) An algorithm for subgraph isomorphism. J ACM 23(1):31\u201342. https:\/\/doi.org\/10.1145\/321921.321925","journal-title":"J ACM"},{"key":"3938_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 XW (2019) Correct filtering for subgraph isomorphism search in compressed vertex-labeled graphs. Inf Sci 482:363\u2013373","journal-title":"Inf Sci"},{"key":"3938_CR46","doi-asserted-by":"crossref","unstructured":"Wang Z, Gu R, Hu W, Yuan C, Huang Y (2019) Benu: Distributed subgraph enumeration with backtracking-based framework. 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, Macao, Macao, pp 136\u2013147","DOI":"10.1109\/ICDE.2019.00021"},{"key":"3938_CR47","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/978-3-030-62005-9_19","volume-title":"Web information systems engineering-WISE 2020","author":"X Wu","year":"2020","unstructured":"Wu X, Theodoratos D, Skoutas D, Lan M (2020) Leveraging double simulation to efficiently evaluate hybrid patterns on data graphs. In: Huang Z, Beek W, Wang H, Zhou R, Zhang Y (eds) Web information systems engineering-WISE 2020. Springer International Publishing, Cham, pp 255\u2013269"},{"key":"3938_CR48","first-page":"1","volume-title":"First international workshop on graph data management experiences and systems","author":"RS Xin","year":"2013","unstructured":"Xin RS, Gonzalez JE, Franklin MJ, Stoica I (2013) Graphx: a resilient distributed graph system on spark. First international workshop on graph data management experiences and systems. ACM, New York, USA, pp 1\u20136"},{"issue":"10","key":"3938_CR49","first-page":"95","volume":"10","author":"M Zaharia","year":"2010","unstructured":"Zaharia M, Chowdhury M, Franklin MJ, Shenker S, Stoica I et al (2010) Spark: cluster computing with working sets. HotCloud 10(10):95","journal-title":"HotCloud"},{"issue":"4","key":"3938_CR50","doi-asserted-by":"publisher","first-page":"265","DOI":"10.14778\/2535570.2488333","volume":"6","author":"K Zeng","year":"2013","unstructured":"Zeng K, Yang J, Wang H, Shao B, Wang Z (2013) A distributed graph engine for web scale rdf data. Proc VLDB Endow 6(4):265\u2013276","journal-title":"Proc VLDB Endow"},{"issue":"1\u20132","key":"3938_CR51","doi-asserted-by":"publisher","first-page":"340","DOI":"10.14778\/1920841.1920887","volume":"3","author":"P Zhao","year":"2010","unstructured":"Zhao P, Han J (2010) On graph query optimization in large networks. Proc VLDB Endow 3(1\u20132):340\u2013351","journal-title":"Proc VLDB Endow"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-021-03938-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-021-03938-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-021-03938-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,1]],"date-time":"2024-09-01T20:56:25Z","timestamp":1725224185000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-021-03938-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["3938"],"URL":"https:\/\/doi.org\/10.1007\/s11227-021-03938-7","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"type":"print","value":"0920-8542"},{"type":"electronic","value":"1573-0484"}],"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"7 June 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 June 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}