Key Papers about Periodic Pattern Mining

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.

AlgorithmAuthor / Date Key idea
PF-GrowthTanbeer 2009– First algorithm for periodic itemset mining in transactions
Uses the maxPer constraint to select periodic patterns.
– Based on FP-Growth
MTKPPAmphawan 2009– First algorithm for top-k periodic itemset mining
– Uses the maxPer constraint to select periodic patterns.
– Based on Eclat
ITL-treeAmphawan 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.
PFPRashid 2012– Find periodic itemsets using the variance of periods.
– The periodic patterns are called regular periodic patterns.
– Based on FP-Growth
PFPMFournier-Viger 2016Generalize 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
PHMFournier-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
MPFPSFournier-Viger 2019
(ppt)
– Find periodic patterns in multiple sequences
– Introduce a measure called “sequence periodic ratio
– Based on PFPM and Eclat
MRCPPSFournier-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
PHUSPMDinh 2018– Proposed to find periodic sequential patterns (subsequences that are periodic)
SPP-GrowthFournier-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
TSPINFournier-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.

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.

This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *