This forum is about

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

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

On the other hand,

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

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.

Posted by:
**
jbd
**

Date: January 20, 2020 06:30AM

Thank you for this detailed and useful explanation!

Best regards

Best regards