{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T23:58:30Z","timestamp":1771459110038,"version":"3.50.1"},"reference-count":92,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T00:00:00Z","timestamp":1613001600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["III-1763325, III-1909323, and SaTC-1930941"],"award-info":[{"award-number":["III-1763325, III-1909323, and SaTC-1930941"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Manage. Inf. Syst."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>This article introduces a highly efficient pattern mining technique called Clustering-based Pattern Mining (CBPM). This technique discovers relevant patterns by studying the correlation between transactions in the transaction database based on clustering techniques. The set of transactions is first clustered, such that highly correlated transactions are grouped together. Next, we derive the relevant patterns by applying a pattern mining algorithm to each cluster. We present two different pattern mining algorithms, one applying an approximation-based strategy and another based on an exact strategy. The approximation-based strategy takes into account only the clusters, whereas the exact strategy takes into account both clusters and shared items between clusters. To boost the performance of the CBPM, a GPU-based implementation is investigated. To evaluate the CBPM framework, we perform extensive experiments on several pattern mining problems. The results from the experimental evaluation show that the CBPM provides a reduction in both the runtime and memory usage. Also, CBPM based on the approximate strategy provides good accuracy, demonstrating its effectiveness and feasibility. Our GPU implementation achieves significant speedup of up to 552\u00d7 on a single GPU using big transaction databases.<\/jats:p>","DOI":"10.1145\/3439771","type":"journal-article","created":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T17:09:12Z","timestamp":1613063352000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Exploring Decomposition for Solving Pattern Mining Problems"],"prefix":"10.1145","volume":"12","author":[{"given":"Youcef","family":"Djenouri","sequence":"first","affiliation":[{"name":"Dept. of Mathematics and Cybernetics, SINTEF Digital, Oslo, Norway"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8768-9709","authenticated-orcid":false,"given":"Jerry Chun-Wei","family":"Lin","sequence":"additional","affiliation":[{"name":"Dept. of Computing, Mathematics, and Physics, HVL, Bergen, Norway"}]},{"given":"Kjetil","family":"N\u00f8rv\u00e5g","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, NTNU, Trondheim, Norway"}]},{"given":"Heri","family":"Ramampiaro","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, NTNU, Trondheim, Norway"}]},{"given":"Philip S.","family":"Yu","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, University of Illinois, Chicago, IL, United States"}]}],"member":"320","published-online":{"date-parts":[[2021,2,11]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Aggarwal and Jiawei Han","author":"Charu","year":"2014","unstructured":"Charu C. Aggarwal and Jiawei Han. 2014. Frequent Pattern Mining. Springer."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/170036.170072"},{"key":"e_1_2_1_3_1","volume-title":"Gautam Srivastava, Rizwan Yasin, and Youcef Djenouri.","author":"Ahmed Usman","year":"2020","unstructured":"Usman Ahmed, Jerry Chun-Wei Lin, Gautam Srivastava, Rizwan Yasin, and Youcef Djenouri. 2020. An evolutionary model to mine high expected utility patterns from uncertain databases. IEEE Trans. Emerg. Top. Comput. Intell. (2020). In Press."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-55789-8_74"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2018.07.005"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2017.2744322"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/3477.809032"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigDataCongress.2015.14"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2345408"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2014.09.054"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the IEEE\/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGrid\u201919)","author":"Braun Peter","unstructured":"Peter Braun, Alfredo Cuzzocrea, Carson K. Leung, Adam G. M. Pazdor, Joglas Souza, and Syed K. Tanbeer. 2019. Pattern mining from big IoT data with fog computing: Models, issues, and research perspectives. In Proceedings of the IEEE\/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGrid\u201919). 854--891."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2017.10.039"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2003.1250893"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.bdr.2016.07.001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.553158"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151111"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71701-0_8"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01890115"},{"key":"e_1_2_1_19_1","first-page":"58","article-title":"Optimal process mining of timed event logs. Info","volume":"528","author":"Oliveira Hugo De","year":"2020","unstructured":"Hugo De Oliveira, Vincent Augusto, Baptiste Jouaneton, Ludovic Lamarsalle, Martin Prodel, and Xiaolan Xie. 2020. Optimal process mining of timed event logs. Info. Sci. 528 (2020), 58--78.","journal-title":"Sci."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921632.1921635"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.64"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2015.03.004"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319875"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3311950"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2017.10.042"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2017.10.016"},{"key":"e_1_2_1_27_1","volume-title":"Djamel Djenouri, and Alberto Cano.","author":"Djenouri Youcef","year":"2019","unstructured":"Youcef Djenouri, Asma Belhadi, Jerry Chun-Wei Lin, Djamel Djenouri, and Alberto Cano. 2019. A survey on urban traffic anomalies detection algorithms. IEEE Access (2019)."},{"key":"e_1_2_1_28_1","volume-title":"Reducing thread divergence in GPU-based bees swarm optimization applied to association rule mining. Concurr. Comput.: Pract. Exper. 29, 9","author":"Djenouri Youcef","year":"2017","unstructured":"Youcef Djenouri, Ahcene Bendjoudi, Zineb Habbas, Malika Mehdi, and Djamel Djenouri. 2017. Reducing thread divergence in GPU-based bees swarm optimization applied to association rule mining. Concurr. Comput.: Pract. Exper. 29, 9 (2017)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-014-1366-8"},{"key":"e_1_2_1_30_1","first-page":"1","article-title":"Combining Apriori heuristic and bio-inspired algorithms for solving the frequent itemsets mining problem. Info","volume":"420","author":"Djenouri Youcef","year":"2017","unstructured":"Youcef Djenouri and Marco Comuzzi. 2017. Combining Apriori heuristic and bio-inspired algorithms for solving the frequent itemsets mining problem. Info. Sci. 420 (2017), 1--15.","journal-title":"Sci."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57529-2_50"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2017.3121546"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2019.8790127"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00163"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2014.13"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery 8 Data Mining (KDD\u201996)","author":"Ester Martin","year":"1996","unstructured":"Martin Ester, Hans-Peter Kriegel, J\u00f6rg Sander, Xiaowei Xu, et\u00a0al. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery 8 Data Mining (KDD\u201996). 226--231."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.bdr.2015.02.006"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2019.2896267"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281230"},{"key":"e_1_2_1_40_1","first-page":"840","article-title":"Survey on frequent pattern mining","volume":"19","author":"Goethals Bart","year":"2003","unstructured":"Bart Goethals. 2003. Survey on frequent pattern mining. Univ. Helsinki 19 (2003), 840--852.","journal-title":"Univ. Helsinki"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559891"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(89)90048-4"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.846289"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/335191.335372"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382936.2383055"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the IEEE International Conference on Big Data (Big Data). IEEE, 2206--2215","author":"Ibrahim Rami","unstructured":"Rami Ibrahim and M. Omair Shafiq. 2018. Towards a new approach to empower periodic pattern mining for massive data using map-reduce. In Proceedings of the IEEE International Conference on Big Data (Big Data). IEEE, 2206--2215."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:DAPD.0000031634.19130.bd"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-011-0672-7"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.18"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.45"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-019-01622-1"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the International Conference on Database Systems for Advanced Applications. Springer, 440--455","author":"Kai-Sang Leung Carson","year":"2013","unstructured":"Carson Kai-Sang Leung and Yaroslav Hayduk. 2013. Mining frequent patterns from uncertain data with MapReduce for big data analytics. In Proceedings of the International Conference on Database Systems for Advanced Applications. Springer, 440--455."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2018.06.042"},{"key":"e_1_2_1_54_1","volume-title":"A new closed frequent itemset mining algorithm based on GPU and improved vertical structure. Concurr. Comput.: Pract. Exper. 29, 6","author":"Li Yun","year":"2017","unstructured":"Yun Li, Jie Xu, Yun-Hao Yuan, and Ling Chen. 2017. A new closed frequent itemset mining algorithm based on GPU and improved vertical structure. Concurr. Comput.: Pract. Exper. 29, 6 (2017)."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920934"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2010.12.082"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the IEEE International Conference on Data Mining. IEEE, 984--989","author":"Liu Junqiang","unstructured":"Junqiang Liu, Ke Wang, and Benjamin C. M. Fung. 2012. Direct discovery of high-utility itemsets without candidate generation. In Proceedings of the IEEE International Conference on Data Mining. IEEE, 984--989."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2012.05.010"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/11430919_79"},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability","volume":"1","author":"\u00a0al James","year":"1967","unstructured":"James MacQueen et\u00a0al. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1. 281--297."},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 169--178","author":"McCallum Andrew","unstructured":"Andrew McCallum, Kamal Nigam, and Lyle H. Ungar. 2000. Efficient clustering of high-dimensional data sets with application to reference matching. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 169--178."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465285"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2013.6691742"},{"key":"e_1_2_1_64_1","first-page":"214","article-title":"Influence-based approach to market basket analysis. Info","volume":"78","author":"Monteserin Ariel","year":"2018","unstructured":"Ariel Monteserin and Marcelo G. Armentano. 2018. Influence-based approach to market basket analysis. Info. Syst. 78 (2018), 214--224.","journal-title":"Syst."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2019.01.034"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2019.03.022"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011656"},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","first-page":"1424","DOI":"10.1109\/TKDE.2004.77","article-title":"Mining sequential patterns by pattern-growth: The prefixspan approach","volume":"11","author":"Pei Jian","year":"2004","unstructured":"Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Jianyong Wang, Helen Pinto, Qiming Chen, Umeshwar Dayal, and Mei-Chun Hsu. 2004. Mining sequential patterns by pattern-growth: The prefixspan approach. IEEE Trans. Knowl. Data Eng.11 (2004), 1424--1440.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396776"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.5555\/2029759.2029802"},{"key":"e_1_2_1_71_1","volume-title":"Van der Aalst","author":"Song Minseok","year":"2008","unstructured":"Minseok Song, Christian W G\u00fcnther, and Wil M. P. Van der Aalst. 2008. Trace clustering in process mining. In Proceedings of the International Conference on Business Process Management. Springer, 109--120."},{"key":"e_1_2_1_72_1","volume-title":"Alireza Jolfaei, Yuanfa Li, and Youcef Djenouri.","author":"Srivastava Gautam","year":"2020","unstructured":"Gautam Srivastava, Jerry Chun-Wei Lin, Alireza Jolfaei, Yuanfa Li, and Youcef Djenouri. 2020. Uncertain-driven analytics of sequence data in IoCV environments. IEEE Trans. Intell. Transport. Syst. In Press."},{"key":"e_1_2_1_73_1","volume-title":"Proceedings of the KDD Workshop on Text Mining","volume":"400","author":"Steinbach Michael","year":"2000","unstructured":"Michael Steinbach, George Karypis, Vipin Kumar, et\u00a0al. 2000. A comparison of document clustering techniques. In Proceedings of the KDD Workshop on Text Mining, Vol. 400. Boston, 525--526."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2006.11.003"},{"key":"e_1_2_1_75_1","first-page":"105","article-title":"Interest-driven discovery of local process models. Info","volume":"77","author":"Tax Niek","year":"2018","unstructured":"Niek Tax, Benjamin Dalmas, Natalia Sidorova, Wil M. P. van der Aalst, and Sylvie Norre. 2018. Interest-driven discovery of local process models. Info. Syst. 77 (2018), 105--117.","journal-title":"Syst."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2018.08.010"},{"key":"e_1_2_1_77_1","unstructured":"Trang Van Bay Vo and Bac Le. 2018. Mining sequential patterns with itemset constraints. Knowl. Info. Syst. (2018) 1--20."},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.47"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2011.206"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scs.2018.11.021"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13042-014-0252-2"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.109"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.2015.2437327"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2560176"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020462"},{"key":"e_1_2_1_86_1","first-page":"3477","article-title":"Efficient mining of weighted interesting patterns with a strong weight and\/or support affinity. Info","volume":"177","author":"Yun Unil","year":"2007","unstructured":"Unil Yun. 2007. Efficient mining of weighted interesting patterns with a strong weight and\/or support affinity. Info. Sci. 177, 17 (2007), 3477--3499.","journal-title":"Sci."},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.5555\/1551582.1551591"},{"key":"e_1_2_1_88_1","volume-title":"Leggett","author":"Yun Unil","year":"2005","unstructured":"Unil Yun and John J. Leggett. 2005. WFIM: Weighted frequent itemset mining with a weight range and a minimum weight. In Proceedings of the SIAM International Conference on Data Mining. 636--640."},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1109\/4434.806975"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER.2011.61"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2017.2709749"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0986-0"}],"container-title":["ACM Transactions on Management Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3439771","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3439771","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3439771","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:52Z","timestamp":1750197712000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3439771"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,11]]},"references-count":92,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3439771"],"URL":"https:\/\/doi.org\/10.1145\/3439771","relation":{},"ISSN":["2158-656X","2158-6578"],"issn-type":[{"value":"2158-656X","type":"print"},{"value":"2158-6578","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,11]]},"assertion":[{"value":"2020-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}