Article: Detecting and exploiting symmetries in sequential pattern mining Journal: International Journal of Data Mining, Modelling and Management (IJDMMM) 2022 Vol.14 No.4 pp.309 - 334 Abstract: In this paper, we introduce a new framework for discovering and using symmetries in sequential pattern mining tasks. Symmetries are permutations between items that leave invariant the sequential database. Symmetries present several potential benefits. They can be seen as a new kind of structural patterns expressing regularities and similarities between items. As symmetries induce a partition of the sequential patterns into equivalent classes, exploiting them would allow to improve the pattern enumeration process, while reducing the size of the output. To this end, we first address the problem of symmetry discovery from database of sequences. Then, we first show how Apriori-like algorithms can be enhanced by dynamic integration of the detected symmetries. Secondly, we provide a second symmetry breaking approach allowing to eliminate symmetries in a pre-processing step by reformulating the sequential database of transactions. Our experiments clearly show that several sequential pattern mining datasets contain such symmetry-based regularities. We also experimentally demonstrate that using such symmetries would results in significant reduction of the search space on some datasets. Inderscience Publishers - linking academia, business and industry through research

Title: Detecting and exploiting symmetries in sequential pattern mining

Authors: Ikram Nekkache; Said Jabbour; Nadjet Kamel; Lakhdar Sais

Addresses: CRIL – CNRS UMR 8188, University of Artois, Lens, France; LRSD Laboratory, Department of Computer Science, Faculty of Sciences, University Ferhat Abbas Sétif-1, Sétif, Algeria ' CRIL – CNRS UMR 8188, University of Artois, Lens, France ' LRSD Laboratory, Department of Computer Science, Faculty of Sciences, University Ferhat Abbas Sétif-1, Sétif, Algeria ' CRIL – CNRS UMR 8188, University of Artois, Lens, France

Abstract: In this paper, we introduce a new framework for discovering and using symmetries in sequential pattern mining tasks. Symmetries are permutations between items that leave invariant the sequential database. Symmetries present several potential benefits. They can be seen as a new kind of structural patterns expressing regularities and similarities between items. As symmetries induce a partition of the sequential patterns into equivalent classes, exploiting them would allow to improve the pattern enumeration process, while reducing the size of the output. To this end, we first address the problem of symmetry discovery from database of sequences. Then, we first show how Apriori-like algorithms can be enhanced by dynamic integration of the detected symmetries. Secondly, we provide a second symmetry breaking approach allowing to eliminate symmetries in a pre-processing step by reformulating the sequential database of transactions. Our experiments clearly show that several sequential pattern mining datasets contain such symmetry-based regularities. We also experimentally demonstrate that using such symmetries would results in significant reduction of the search space on some datasets.

Keywords: data mining; sequential pattern mining; symmetries.

DOI: 10.1504/IJDMMM.2022.126663

International Journal of Data Mining, Modelling and Management, 2022 Vol.14 No.4, pp.309 - 334

Received: 20 Jun 2020
Accepted: 22 Mar 2021
Published online: 01 Nov 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: Detecting and exploiting symmetries in sequential pattern mining

Keep up-to-date