The Data Mining Forum 
IMPORTANT: This is the old Data Mining forum.
I keep it online so that you can read the old messages.
Please post your new messages in the new forum: https://forum2.philippe-fournier-viger.com/index.php
Pattern growth-based algorithms using vertical representation
Posted by:
jbd
Date: January 20, 2020 02:10AM
Hello,
As to your knowledge, is there any pattern growth-based sequential pattern mining algorithm that has a vertical database representation?
Until now I haven't found anyone neither in your survey nor in the literature, so I wonder if such an algorithm exists or can be done.
Thank you
As to your knowledge, is there any pattern growth-based sequential pattern mining algorithm that has a vertical database representation?
Until now I haven't found anyone neither in your survey nor in the literature, so I wonder if such an algorithm exists or can be done.
Thank you
Re: Pattern growth-based algorithms using vertical representation
Posted by:
webmasterphilfv
Date: January 20, 2020 06:26AM
Hi again,
That is a good observation. There would be very few algorithms of this type.
The reason is that pattern-growth scan the database to see which items can extend a pattern. By doing this, pattern-growth algorithms avoid generating patterns that do not exist in the database.
On the other hand, vertical algorithm are designed to avoid scanning the database. They combine two patterns to generate a new pattern and calculate its support by joining some vertical structure. But because such algorithm join the vertical structures of two patterns without looking at the database, there is the possibility of generating a pattern that do not exist in the database and thus waste time...
So, these two types of algorithms have some kind of opposite approach, that is why it seems hard to design a pattern-growth algorithm with a vertical database.
But I would not say that it is impossible.
For example, in one of my papers about periodic pattern pattern mining, we extend the FP-Growth algorithm, which is a pattern-growth algorithm for itemset mining. We extend FP-Growth by storing list of transactions in some tree nodes. These lists of transactions are a vertical structure, while the tree is a horizontal structure. Thus, the tree in that paper combines both. In that paper, we use the vertical structure in the tree to do some calculations with the timestamps of transactions to see whether an itemset is periodic or not, and also calculate the support. And we scan the tree as in FP-Growth to generate itemsets. The resulting algorithm behaves more like a pattern-growth algorithm but it still uses a vertical structure for calculating the support and periodicity of patterns.
There are maybe some other algorithms, but that is an example that comes to my mind!
In any case, it is a good observation. There are few algorithms of this type but I it is not impossible.
Best regards,
Philippe
Edited 3 time(s). Last edit at 01/20/2020 06:29AM by webmasterphilfv.
That is a good observation. There would be very few algorithms of this type.
The reason is that pattern-growth scan the database to see which items can extend a pattern. By doing this, pattern-growth algorithms avoid generating patterns that do not exist in the database.
On the other hand, vertical algorithm are designed to avoid scanning the database. They combine two patterns to generate a new pattern and calculate its support by joining some vertical structure. But because such algorithm join the vertical structures of two patterns without looking at the database, there is the possibility of generating a pattern that do not exist in the database and thus waste time...
So, these two types of algorithms have some kind of opposite approach, that is why it seems hard to design a pattern-growth algorithm with a vertical database.
But I would not say that it is impossible.
For example, in one of my papers about periodic pattern pattern mining, we extend the FP-Growth algorithm, which is a pattern-growth algorithm for itemset mining. We extend FP-Growth by storing list of transactions in some tree nodes. These lists of transactions are a vertical structure, while the tree is a horizontal structure. Thus, the tree in that paper combines both. In that paper, we use the vertical structure in the tree to do some calculations with the timestamps of transactions to see whether an itemset is periodic or not, and also calculate the support. And we scan the tree as in FP-Growth to generate itemsets. The resulting algorithm behaves more like a pattern-growth algorithm but it still uses a vertical structure for calculating the support and periodicity of patterns.
There are maybe some other algorithms, but that is an example that comes to my mind!
In any case, it is a good observation. There are few algorithms of this type but I it is not impossible.
Best regards,
Philippe
Edited 3 time(s). Last edit at 01/20/2020 06:29AM by webmasterphilfv.
Re: Pattern growth-based algorithms using vertical representation
Posted by:
jbd
Date: January 20, 2020 06:30AM
Thank you for this detailed and useful explanation!
Best regards
Best regards