In this blog post, I will list the key algorithms for periodic itemset mining (according to me) with comments about their contributions. Of course, this list is subjective. I did not list all the papers of all authors but I have listed the key papers that I have read and found interesting, as they introduced some innovative ideas. I did not list papers that were mostly incremental in their contributions. I also did not list papers that had very few references unless I found them interesting.
| Algorithm | Author / Date | Key idea |
| PF-Growth | Tanbeer 2009 | – First algorithm for periodic itemset mining in transactions Uses the maxPer constraint to select periodic patterns. – Based on FP-Growth |
| MTKPP | Amphawan 2009 | – First algorithm for top-k periodic itemset mining – Uses the maxPer constraint to select periodic patterns. – Based on Eclat |
| ITL-tree | Amphawan 2010 | – Performs an approximate calculation of the periods of patterns – Based on FP-Growth |
| MIS-PF-tree | Kiran 2009 | – Mining periodic patterns with a maxPer threshold for each item – Based on FP-Growth |
| Lahiri 2010 | – Proposed to study periodic patterns as subgraphs in a sequence of graphs. | |
| PFP | Rashid 2012 | – Find periodic itemsets using the variance of periods. – The periodic patterns are called regular periodic patterns. – Based on FP-Growth |
| PFPM | Fournier-Viger 2016 | – Generalize the problem of periodic itemset mining to provide more flexibility using three measures: the average periodicity, minimum periodicity and maximum periodicity – It is shown that average periodicity is inversely related to the support measure. – Based on Eclat |
| PHM | Fournier-Viger 2015 | – An extension of the PFPM algorithm to mine high utility itemsets (itemsets that are periodic but also important such as yield a high profit) – Based on PFPM, Eclat and FHM |
| MPFPS | Fournier-Viger 2019 (ppt) | – Find periodic patterns in multiple sequences – Introduce a measure called “sequence periodic ratio“ – Based on PFPM and Eclat |
| MRCPPS | Fournier-Viger 2019 | – Find periodic patterns in multiple sequences that are rare and correlated. – Use the sequence periodic ratio, bond measure and maximum periodicity to select patterns – Based on PFPM and Eclat |
| PPFP | Nofong 2016 | – Find periodic itemsets using the standard deviation of periods as measure to select patterns. – Apply a statistical test to select periodic patterns that are significant. – Vertical algorithm based on Eclat and inspired by OPUS-Miner for the statistical test |
| PPFP+, PFP+… | Nofong 2018 | – Find periodic itemsets using the standard deviation and variance of periods as measure to select patterns. – The measures are integrated in existing algorithms such as PPFP and PFP |
| PHUSPM | Dinh 2018 | – Proposed to find periodic sequential patterns (subsequences that are periodic) |
| SPP-Growth | Fournier-Viger 2019 (ppt) | – Find the stable periodic patterns using a novel measure called lability. – The goal is to find patterns that are generally stable rather than enforcing a very strict maxPer constraint as many algorithms do. – Based on FPGrowth |
| TSPIN | Fournier-Viger 2020 | – Algorithm for mining the top-k stable periodic patterns. – Based on SPP-Growth |
| LPP-Growth LPP-Miner | Fournier-Viger 2020 (ppt) | – Find locally periodic patterns (periodic in some time intervals rather than the whole database). That is, unlike most algorithms, it is not assumed that a pattern must be always periodic. – LPP-Growth is based on FPGrowth – LPP-Miner is based on PFPM, which is inspired by Eclat and Apriori-TID |
Implementations
Several algorithms above are implemented in the SPMF data mining software in Java as open-source code.
Some survey papers
I have also written two chapters recently that give some overview of some topics on periodic pattern mining. You may read them if you want to have a quick and easy-to-understand overview of some topics in periodic pattern mining.
- Fournier-Viger, P., Wu. Y., Dinh, D.-T., Song, W., Lin, J.C.W. (2021). Discovering Periodic High Utility Itemsets in a Discrete Sequence. In the book “Periodic Pattern Mining: Theory, Algorithms and Application”, Springer, to appear.
- Fournier-Viger, P., Chi, T. T., Wu, Y., Qu, J.-F., Lin, J. C.W., Li, Z. (2021). Finding Periodic Patterns in Multiple Discrete Sequences. In the book “Periodic Pattern Mining: Theory, Algorithms and Application”, Springer, to appear.
Conclusion
In this blog post, I have listed some key references in periodic pattern mining. Of course, I did not list all the references of all authors. I mainly listed the key papers that I have read and found interesting. This is obviously subjective.
Philippe Fournier-Viger is a full professor working in China and founder of the SPMF open source data mining software.
