You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by "Jaroslaw Odzga (JIRA)" <ji...@apache.org> on 2011/03/21 11:34:05 UTC
[jira] [Created] (MAHOUT-629) FP Growth performance improvement
FP Growth performance improvement
---------------------------------
Key: MAHOUT-629
URL: https://issues.apache.org/jira/browse/MAHOUT-629
Project: Mahout
Issue Type: Improvement
Components: Frequent Itemset/Association Rule Mining
Affects Versions: 0.4
Reporter: Jaroslaw Odzga
Instead of calculating patterns ending with given attribute multiple times they can be calculated just once. Depending on for how many features patterns are generated, speedup can be huge. More feature included - greater speedup. For test data set (88162 real life 'basket' transactions), if all features were selected (i.e. we want to generate patterns for all items in transactions), patterns generation time dropped from 1h 15min to 8sec. For parallel fpgrowth, where the number of requested features is limited the speedup is not that dramatic, but still noticeable. Basically work done is always smaller than before the patch (as patterns for each item are calculated at most once).
The improvement is a variation of base algorithm in situation where we want to generate patterns for only subset of items (let's call this subset A). Given that items are ordered by descending frequency it is enough to calculate only patterns ending on any item with frequency smaller or equal to the most frequent item in the subset A. The heaps for each item are initialized upfront and merged after processing every item.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-629) FP Growth performance improvement
Posted by "niu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-629?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
niu updated MAHOUT-629:
-----------------------
Attachment: FPGrowth.java
I have test the patch of MAHOUT-629 as the FPGrowth.java I attached ,but I find it become slower than the original implementation in mahout 0.4.
The dataset I use is like this, there are so many items which more than 1000 in one transaction.
> FP Growth performance improvement
> ---------------------------------
>
> Key: MAHOUT-629
> URL: https://issues.apache.org/jira/browse/MAHOUT-629
> Project: Mahout
> Issue Type: Improvement
> Components: Frequent Itemset/Association Rule Mining
> Affects Versions: 0.4, 0.5
> Reporter: Jaroslaw Odzga
> Assignee: Robin Anil
> Fix For: 0.6
>
> Attachments: FPGrowth.java, performance_improvement.txt
>
>
> Instead of calculating patterns ending with given attribute multiple times they can be calculated just once. Depending on for how many features patterns are generated, speedup can be huge. More feature included - greater speedup. For test data set (88162 real life 'basket' transactions), if all features were selected (i.e. we want to generate patterns for all items in transactions), patterns generation time dropped from 1h 15min to 8sec. For parallel fpgrowth, where the number of requested features is limited the speedup is not that dramatic, but still noticeable. Basically work done is always smaller than before the patch (as patterns for each item are calculated at most once).
> The improvement is a variation of base algorithm in situation where we want to generate patterns for only subset of items (let's call this subset A). Given that items are ordered by descending frequency it is enough to calculate only patterns ending on any item with frequency smaller or equal to the most frequent item in the subset A. The heaps for each item are initialized upfront and merged after processing every item.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-629) FP Growth performance improvement
Posted by "Sean Owen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-629?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Owen updated MAHOUT-629:
-----------------------------
Fix Version/s: (was: 0.6)
This still isn't in a position to commit without a patch.
> FP Growth performance improvement
> ---------------------------------
>
> Key: MAHOUT-629
> URL: https://issues.apache.org/jira/browse/MAHOUT-629
> Project: Mahout
> Issue Type: Improvement
> Components: Frequent Itemset/Association Rule Mining
> Affects Versions: 0.4, 0.5
> Reporter: Jaroslaw Odzga
> Assignee: Robin Anil
> Attachments: FPGrowth.java, performance_improvement.txt
>
>
> Instead of calculating patterns ending with given attribute multiple times they can be calculated just once. Depending on for how many features patterns are generated, speedup can be huge. More feature included - greater speedup. For test data set (88162 real life 'basket' transactions), if all features were selected (i.e. we want to generate patterns for all items in transactions), patterns generation time dropped from 1h 15min to 8sec. For parallel fpgrowth, where the number of requested features is limited the speedup is not that dramatic, but still noticeable. Basically work done is always smaller than before the patch (as patterns for each item are calculated at most once).
> The improvement is a variation of base algorithm in situation where we want to generate patterns for only subset of items (let's call this subset A). Given that items are ordered by descending frequency it is enough to calculate only patterns ending on any item with frequency smaller or equal to the most frequent item in the subset A. The heaps for each item are initialized upfront and merged after processing every item.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-629) FP Growth performance improvement
Posted by "Yarco Hayduk (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-629?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Yarco Hayduk updated MAHOUT-629:
--------------------------------
Comment: was deleted
(was: Hi Jaroslaw,
I'm currently beginning to review your patch file. I'm not 100% through with it yet, but it seems that your patch does some redundant work.
CountDescendingPairComparator ensures the first element of the flist is the most frequent singleton item. Thus, this code is not needed:
------
long mostFrequentAttributeToReturn = -1;
for (Integer att : requiredFeatures) {
if (attributeFrequency[att] > mostFrequentAttributeToReturn){
mostFrequentAttributeToReturn = attributeFrequency[att];
}
}
------
Further, you can get "long[] attributeFrequency" from the top-most tree, hence you don't need to pass this attribute around.
Will keep you posted if I find anything else)
> FP Growth performance improvement
> ---------------------------------
>
> Key: MAHOUT-629
> URL: https://issues.apache.org/jira/browse/MAHOUT-629
> Project: Mahout
> Issue Type: Improvement
> Components: Frequent Itemset/Association Rule Mining
> Affects Versions: 0.4, 0.5
> Reporter: Jaroslaw Odzga
> Assignee: Robin Anil
> Fix For: 0.6
>
> Attachments: performance_improvement.txt
>
>
> Instead of calculating patterns ending with given attribute multiple times they can be calculated just once. Depending on for how many features patterns are generated, speedup can be huge. More feature included - greater speedup. For test data set (88162 real life 'basket' transactions), if all features were selected (i.e. we want to generate patterns for all items in transactions), patterns generation time dropped from 1h 15min to 8sec. For parallel fpgrowth, where the number of requested features is limited the speedup is not that dramatic, but still noticeable. Basically work done is always smaller than before the patch (as patterns for each item are calculated at most once).
> The improvement is a variation of base algorithm in situation where we want to generate patterns for only subset of items (let's call this subset A). Given that items are ordered by descending frequency it is enough to calculate only patterns ending on any item with frequency smaller or equal to the most frequent item in the subset A. The heaps for each item are initialized upfront and merged after processing every item.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-629) FP Growth performance improvement
Posted by "Sean Owen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-629?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Owen updated MAHOUT-629:
-----------------------------
Affects Version/s: 0.5
Fix Version/s: 0.6
Assignee: Robin Anil
> FP Growth performance improvement
> ---------------------------------
>
> Key: MAHOUT-629
> URL: https://issues.apache.org/jira/browse/MAHOUT-629
> Project: Mahout
> Issue Type: Improvement
> Components: Frequent Itemset/Association Rule Mining
> Affects Versions: 0.4, 0.5
> Reporter: Jaroslaw Odzga
> Assignee: Robin Anil
> Fix For: 0.6
>
> Attachments: performance_improvement.txt
>
>
> Instead of calculating patterns ending with given attribute multiple times they can be calculated just once. Depending on for how many features patterns are generated, speedup can be huge. More feature included - greater speedup. For test data set (88162 real life 'basket' transactions), if all features were selected (i.e. we want to generate patterns for all items in transactions), patterns generation time dropped from 1h 15min to 8sec. For parallel fpgrowth, where the number of requested features is limited the speedup is not that dramatic, but still noticeable. Basically work done is always smaller than before the patch (as patterns for each item are calculated at most once).
> The improvement is a variation of base algorithm in situation where we want to generate patterns for only subset of items (let's call this subset A). Given that items are ordered by descending frequency it is enough to calculate only patterns ending on any item with frequency smaller or equal to the most frequent item in the subset A. The heaps for each item are initialized upfront and merged after processing every item.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-629) FP Growth performance improvement
Posted by "Sean Owen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-629?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13053133#comment-13053133 ]
Sean Owen commented on MAHOUT-629:
----------------------------------
Could you attach a patch, instead of the file itself? it shows the changes and helps everyone evaluate it. Am I right, however, that you do not think it is yet ready for submissions since it causes a slowdown?
> FP Growth performance improvement
> ---------------------------------
>
> Key: MAHOUT-629
> URL: https://issues.apache.org/jira/browse/MAHOUT-629
> Project: Mahout
> Issue Type: Improvement
> Components: Frequent Itemset/Association Rule Mining
> Affects Versions: 0.4, 0.5
> Reporter: Jaroslaw Odzga
> Assignee: Robin Anil
> Fix For: 0.6
>
> Attachments: FPGrowth.java, performance_improvement.txt
>
>
> Instead of calculating patterns ending with given attribute multiple times they can be calculated just once. Depending on for how many features patterns are generated, speedup can be huge. More feature included - greater speedup. For test data set (88162 real life 'basket' transactions), if all features were selected (i.e. we want to generate patterns for all items in transactions), patterns generation time dropped from 1h 15min to 8sec. For parallel fpgrowth, where the number of requested features is limited the speedup is not that dramatic, but still noticeable. Basically work done is always smaller than before the patch (as patterns for each item are calculated at most once).
> The improvement is a variation of base algorithm in situation where we want to generate patterns for only subset of items (let's call this subset A). Given that items are ordered by descending frequency it is enough to calculate only patterns ending on any item with frequency smaller or equal to the most frequent item in the subset A. The heaps for each item are initialized upfront and merged after processing every item.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-629) FP Growth performance improvement
Posted by "Yarco Hayduk (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-629?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13042462#comment-13042462 ]
Yarco Hayduk commented on MAHOUT-629:
-------------------------------------
Hi Jaroslaw,
I'm currently beginning to review your patch file. I'm not 100% through with it yet, but it seems that your patch does some redundant work.
CountDescendingPairComparator ensures the first element of the flist is the most frequent singleton item. Thus, this code is not needed:
------
long mostFrequentAttributeToReturn = -1;
for (Integer att : requiredFeatures) {
if (attributeFrequency[att] > mostFrequentAttributeToReturn){
mostFrequentAttributeToReturn = attributeFrequency[att];
}
}
------
Further, you can get "long[] attributeFrequency" from the top-most tree, hence you don't need to pass this attribute around.
Will keep you posted if I find anything else
> FP Growth performance improvement
> ---------------------------------
>
> Key: MAHOUT-629
> URL: https://issues.apache.org/jira/browse/MAHOUT-629
> Project: Mahout
> Issue Type: Improvement
> Components: Frequent Itemset/Association Rule Mining
> Affects Versions: 0.4, 0.5
> Reporter: Jaroslaw Odzga
> Assignee: Robin Anil
> Fix For: 0.6
>
> Attachments: performance_improvement.txt
>
>
> Instead of calculating patterns ending with given attribute multiple times they can be calculated just once. Depending on for how many features patterns are generated, speedup can be huge. More feature included - greater speedup. For test data set (88162 real life 'basket' transactions), if all features were selected (i.e. we want to generate patterns for all items in transactions), patterns generation time dropped from 1h 15min to 8sec. For parallel fpgrowth, where the number of requested features is limited the speedup is not that dramatic, but still noticeable. Basically work done is always smaller than before the patch (as patterns for each item are calculated at most once).
> The improvement is a variation of base algorithm in situation where we want to generate patterns for only subset of items (let's call this subset A). Given that items are ordered by descending frequency it is enough to calculate only patterns ending on any item with frequency smaller or equal to the most frequent item in the subset A. The heaps for each item are initialized upfront and merged after processing every item.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-629) FP Growth performance improvement
Posted by "Jaroslaw Odzga (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-629?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jaroslaw Odzga updated MAHOUT-629:
----------------------------------
Attachment: performance_improvement.txt
Attached patch with performance improvement.
> FP Growth performance improvement
> ---------------------------------
>
> Key: MAHOUT-629
> URL: https://issues.apache.org/jira/browse/MAHOUT-629
> Project: Mahout
> Issue Type: Improvement
> Components: Frequent Itemset/Association Rule Mining
> Affects Versions: 0.4
> Reporter: Jaroslaw Odzga
> Attachments: performance_improvement.txt
>
>
> Instead of calculating patterns ending with given attribute multiple times they can be calculated just once. Depending on for how many features patterns are generated, speedup can be huge. More feature included - greater speedup. For test data set (88162 real life 'basket' transactions), if all features were selected (i.e. we want to generate patterns for all items in transactions), patterns generation time dropped from 1h 15min to 8sec. For parallel fpgrowth, where the number of requested features is limited the speedup is not that dramatic, but still noticeable. Basically work done is always smaller than before the patch (as patterns for each item are calculated at most once).
> The improvement is a variation of base algorithm in situation where we want to generate patterns for only subset of items (let's call this subset A). Given that items are ordered by descending frequency it is enough to calculate only patterns ending on any item with frequency smaller or equal to the most frequent item in the subset A. The heaps for each item are initialized upfront and merged after processing every item.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-629) FP Growth performance improvement
Posted by "Yarco Hayduk (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-629?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13042506#comment-13042506 ]
Yarco Hayduk commented on MAHOUT-629:
-------------------------------------
Hi Jaroslaw,
The patch is awesome! This also means than we do not have to maintain the first level tree cache anymore as we are mining the 1-k conditional tree only once.
> FP Growth performance improvement
> ---------------------------------
>
> Key: MAHOUT-629
> URL: https://issues.apache.org/jira/browse/MAHOUT-629
> Project: Mahout
> Issue Type: Improvement
> Components: Frequent Itemset/Association Rule Mining
> Affects Versions: 0.4, 0.5
> Reporter: Jaroslaw Odzga
> Assignee: Robin Anil
> Fix For: 0.6
>
> Attachments: performance_improvement.txt
>
>
> Instead of calculating patterns ending with given attribute multiple times they can be calculated just once. Depending on for how many features patterns are generated, speedup can be huge. More feature included - greater speedup. For test data set (88162 real life 'basket' transactions), if all features were selected (i.e. we want to generate patterns for all items in transactions), patterns generation time dropped from 1h 15min to 8sec. For parallel fpgrowth, where the number of requested features is limited the speedup is not that dramatic, but still noticeable. Basically work done is always smaller than before the patch (as patterns for each item are calculated at most once).
> The improvement is a variation of base algorithm in situation where we want to generate patterns for only subset of items (let's call this subset A). Given that items are ordered by descending frequency it is enough to calculate only patterns ending on any item with frequency smaller or equal to the most frequent item in the subset A. The heaps for each item are initialized upfront and merged after processing every item.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Resolved] (MAHOUT-629) FP Growth performance improvement
Posted by "Sean Owen (Resolved) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-629?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Owen resolved MAHOUT-629.
------------------------------
Resolution: Invalid
Looks interesting, but we can't act on this without a current patch.
> FP Growth performance improvement
> ---------------------------------
>
> Key: MAHOUT-629
> URL: https://issues.apache.org/jira/browse/MAHOUT-629
> Project: Mahout
> Issue Type: Improvement
> Components: Frequent Itemset/Association Rule Mining
> Affects Versions: 0.4, 0.5
> Reporter: Jaroslaw Odzga
> Assignee: Robin Anil
> Attachments: FPGrowth.java, performance_improvement.txt
>
>
> Instead of calculating patterns ending with given attribute multiple times they can be calculated just once. Depending on for how many features patterns are generated, speedup can be huge. More feature included - greater speedup. For test data set (88162 real life 'basket' transactions), if all features were selected (i.e. we want to generate patterns for all items in transactions), patterns generation time dropped from 1h 15min to 8sec. For parallel fpgrowth, where the number of requested features is limited the speedup is not that dramatic, but still noticeable. Basically work done is always smaller than before the patch (as patterns for each item are calculated at most once).
> The improvement is a variation of base algorithm in situation where we want to generate patterns for only subset of items (let's call this subset A). Given that items are ordered by descending frequency it is enough to calculate only patterns ending on any item with frequency smaller or equal to the most frequent item in the subset A. The heaps for each item are initialized upfront and merged after processing every item.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira