The Data Mining Forum                             open-source data mining software open-source data mining software data science journal data mining conferences
This forum is about data mining, data science and big data: algorithms, source code, datasets, implementations, optimizations, etc. You are welcome to post call for papers, data mining job ads, link to source code of data mining algorithms or anything else related to data mining. The forum is hosted by P. Fournier-Viger. No registration is required to use this forum!.  
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

Options: ReplyQuote
Re: Pattern growth-based algorithms using vertical representation
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.

Options: ReplyQuote
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

Options: ReplyQuote


This forum is powered by Phorum and provided by P. Fournier-Viger (© 2012).
Terms of use.