You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by "Grant Ingersoll (JIRA)" <ji...@apache.org> on 2011/07/19 22:58:59 UTC
[jira] [Created] (MAHOUT-767) Improve RowSimilarityJob performance
for count-based distance measures
Improve RowSimilarityJob performance for count-based distance measures
----------------------------------------------------------------------
Key: MAHOUT-767
URL: https://issues.apache.org/jira/browse/MAHOUT-767
Project: Mahout
Issue Type: Improvement
Reporter: Grant Ingersoll
Fix For: 0.6
(See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
Re: RowSimilarityJob improvements
Posted by Ted Dunning <te...@gmail.com>.
I have heard various arguments that favor retaining the most recent interactions or favor a fair sample or favor taking the earliest interactions. These can even be combined with biased samples. I haven't seen much difference between these approaches. I think at the lack of difference is largely due to the fact that the sampling falls most heavily on items that we care very little about in recommendations since they are the most popular items that are obviously getting plenty of traffic anyway.
Sent from my iPad
On Aug 13, 2011, at 2:31 AM, Sebastian Schelter <ss...@apache.org> wrote:
> One thing I'm currently looking into is how to sample the input. Ted has stated that you usually only need to look at a few hundred or thousand ratings per item as you don't learn anything new from the rest. Would it be sufficient to randomly sample the ratings of an item then? That's what I'm currently doing but I wonder whether there are more clever ways to do this.
Re: RowSimilarityJob improvements
Posted by Grant Ingersoll <gs...@apache.org>.
+1
On Aug 13, 2011, at 3:04 PM, Ted Dunning wrote:
> Frankly you are doing the work. You should take the credit. Ideas without elaboration and testing deserve a little attribution but authorship credit should go to the ones doing the real work.
>
> Sent from my iPad
>
> On Aug 13, 2011, at 3:25 AM, Grant Ingersoll <gs...@apache.org> wrote:
>
>>>
>>> I think about writing a small paper about my works on that (still need to see if I can "sell" it to my professor :) ). I hope everyone who contributed to the discussion here is ok with that, I don't want to "steal" ideas.
>>>
>>
>> Well, you can always be the primary and add others. :-)
--------------------------
Grant Ingersoll
Re: RowSimilarityJob improvements
Posted by Ted Dunning <te...@gmail.com>.
Frankly you are doing the work. You should take the credit. Ideas without elaboration and testing deserve a little attribution but authorship credit should go to the ones doing the real work.
Sent from my iPad
On Aug 13, 2011, at 3:25 AM, Grant Ingersoll <gs...@apache.org> wrote:
>>
>> I think about writing a small paper about my works on that (still need to see if I can "sell" it to my professor :) ). I hope everyone who contributed to the discussion here is ok with that, I don't want to "steal" ideas.
>>
>
> Well, you can always be the primary and add others. :-)
Re: RowSimilarityJob improvements
Posted by Grant Ingersoll <gs...@apache.org>.
Awesome! Some thoughts inline.
On Aug 13, 2011, at 5:31 AM, Sebastian Schelter wrote:
> Hi there,
>
> I invested a lot of work in improving RowSimilarityJob recently and I'm writing to get some feedback on my intermediate results. I also dug out an old mailinglist discussion about the matrix form of itembased recommendation that helped me a lot, I recommend reading this to anyone who wants to dive into the details here:
>
> http://lucene.472066.n3.nabble.com/Re-Taste-GenericItemBasedRecommender-td641062.html
>
> I managed to rework the algorithm as it was proposed in the mailinglist discussion before. The main goal was to drastically reduce the amount of data that needs to be shipped over the network in the cooccurrence computation phase. This is accomplished by making heavy use of a combiner for all supported similarity measures, by not attaching the "norms" of the rows to the cooccurrence pairs anymore and by emitting cooccurrence "stripes" instead of cooccurrence pairs.
>
> A similarity measure must now be expressed by four simple functions that are invoked in different stages of the algorithm
>
> normalize(row) (invoked once at the beginning, can transform the input row vectors)
>
> norm(row) (invoked once at the beginning, maps an input vector a double)
>
> aggregate(nonZeroValueInDimensionXFromRowA,nonZeroValueInDimensionXFromRowB) (invoked for each pair of cooccurring elements of two input vectors, can map them to a double, these doubles are summed then)
>
> similarity(summedAggregations,normOfRowA,normOfRowB,numColumns)
> (invoked at the end with the results of the other functions, should compute the final similarity)
>
> A short list how our commonly used measures can be expressed this way:
>
> cosine:
>
> normalize(...) normalizes the vectors to unit length
> aggregate(...) multiplies valueA and valueB
> similarity(...) just needs to return the summedAggregations (which is the dot-product)
>
> pearson:
>
> same as cosine, but normalize(...) centers the vector elements first (without touching 0s as this would make the input matrix dense)
>
> cooccurrence-count / overlap:
>
> aggregate(...) returns 1 as we only need to count
> similarity(...) returns summedAggregations only
>
> tanimoto/jaccard:
>
> norm(...) returns the l0 norm (number of non-zero elements)
> aggregate(...) returns 1 as we only need to count
> similarity(...) returns summedAggregations / (normOfRowA + normOfRowB - summedDot);
>
> loglikelihood:
>
> same as tanimoto, but we compute LLR in similarity(...) from summedAggregations, normOfRowA,normOfRowB,numColumns
>
>
> cityblock/manhattan:
>
> same as tanimoto, but similarity(...) returns 1.0 / (1.0 + normA + normB - 2 * summedAggregations);
>
> euclidean distance:
>
> norm(...) returns the summed squares of the input vector
> aggregate(...) aggregate(...) multiplies valueA and valueB
> similarity(...) returns 1.0 - 1.0 / (1.0 + Math.sqrt(normA - 2 * dots + normB)
>
> unfortunately we cant use the formula from o.a.m.cf.taste.impl.similarity.EuclideanDistanceSimilarity here which also incorporates the number of "overlapping" dimensions.
>
>
> I'm currently running tests on a small cluster using several rating datasets (18M music ratings from lastfm, 100M movie ratings from netflix, 250M music ratings from yahoo's KDD cup), results are pretty ok so far, but I'm still searching for ways to improve the algorithm.
>
> One thing I'm currently looking into is how to sample the input. Ted has stated that you usually only need to look at a few hundred or thousand ratings per item as you don't learn anything new from the rest. Would it be sufficient to randomly sample the ratings of an item then? That's what I'm currently doing but I wonder whether there are more clever ways to do this.
I assume this will be an option right? Row Similarity obviously goes beyond just recommenders and sampling shouldn't be required.
>
> There is a sampling heuristic in the distributed recommender that caught my attention a long time ago, can anyone give any details on it? I basically understand what it's doing but not exactly why that's a good way to sample. Here's the original implementation:
>
> http://svn.apache.org/viewvc/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/item/UserVectorToCooccurrenceMapper.java?revision=950049&view=co&pathrev=96188
>
> Another issue I'm looking into is whether it would help to specify a similarity threshold. There is some work on "All Pairs Similarity Search" which is closely related to cooccurrence computation that seems to have some nice pruning strategies based on a threshold.
+1
>
> For example imagine your similarity measure is cooccurrence count and you only want to have pairs with a count of 5, than you would not need to consider all pairs where one the vectors has less than 5 non zero entries.
>
> Something like this could be a way to further improve the algorithm's running time, especially as the resulting similarity values seem to follow a heavily tailed distribution. It should be possible to find pruning heuristics for all measures, yet I don't have an idea yet how to find a good a-priori threshold.
I could also see pruning at the very end on the final distance score which would potentially save some IO.
>
> I think about writing a small paper about my works on that (still need to see if I can "sell" it to my professor :) ). I hope everyone who contributed to the discussion here is ok with that, I don't want to "steal" ideas.
>
Well, you can always be the primary and add others. :-)
>
> --sebastian
>
> On 20.07.2011 17:40, Ted Dunning wrote:
>> Not if you are doing Euclidean distance.
>>
>> On Wed, Jul 20, 2011 at 5:41 AM, Grant Ingersoll (JIRA)<ji...@apache.org>wrote:
>>
>>>
>>> [
>>> https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13068331#comment-13068331]
>>>
>>> Grant Ingersoll commented on MAHOUT-767:
>>> ----------------------------------------
>>>
>>> Why do we need the norms? Why can't we assume the user has already
>>> normalized?
>>>
>>>> Improve RowSimilarityJob performance for count-based distance measures
>>>> ----------------------------------------------------------------------
>>>>
>>>> Key: MAHOUT-767
>>>> URL: https://issues.apache.org/jira/browse/MAHOUT-767
>>>> Project: Mahout
>>>> Issue Type: Improvement
>>>> Reporter: Grant Ingersoll
>>>> Fix For: 0.6
>>>>
>>>>
>>>> (See
>>> http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7for background)
>>>> Currently, the RowSimilarityJob defers the calculation of the similarity
>>> metric until the reduce phase, while emitting many Cooccurrence objects.
>>> For similarity metrics that are algebraic (
>>> http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should
>>> be able to do much of the computation during the Mapper part of this phase
>>> and also take advantage of a Combiner.
>>>> We should use a marker interface to know whether a similarity metric is
>>> algebraic and then make use of an appropriate Mapper implementation,
>>> otherwise we can fall back on our existing implementation.
>>>
>>> --
>>> This message is automatically generated by JIRA.
>>> For more information on JIRA, see: http://www.atlassian.com/software/jira
>>>
>>>
>>>
>>
>
--------------------------
Grant Ingersoll
RowSimilarityJob improvements
Posted by Sebastian Schelter <ss...@apache.org>.
Hi there,
I invested a lot of work in improving RowSimilarityJob recently and I'm
writing to get some feedback on my intermediate results. I also dug out
an old mailinglist discussion about the matrix form of itembased
recommendation that helped me a lot, I recommend reading this to anyone
who wants to dive into the details here:
http://lucene.472066.n3.nabble.com/Re-Taste-GenericItemBasedRecommender-td641062.html
I managed to rework the algorithm as it was proposed in the mailinglist
discussion before. The main goal was to drastically reduce the amount of
data that needs to be shipped over the network in the cooccurrence
computation phase. This is accomplished by making heavy use of a
combiner for all supported similarity measures, by not attaching the
"norms" of the rows to the cooccurrence pairs anymore and by emitting
cooccurrence "stripes" instead of cooccurrence pairs.
A similarity measure must now be expressed by four simple functions that
are invoked in different stages of the algorithm
normalize(row) (invoked once at the beginning, can transform the input
row vectors)
norm(row) (invoked once at the beginning, maps an input vector a double)
aggregate(nonZeroValueInDimensionXFromRowA,nonZeroValueInDimensionXFromRowB)
(invoked for each pair of cooccurring elements of two input vectors, can
map them to a double, these doubles are summed then)
similarity(summedAggregations,normOfRowA,normOfRowB,numColumns)
(invoked at the end with the results of the other functions, should
compute the final similarity)
A short list how our commonly used measures can be expressed this way:
cosine:
normalize(...) normalizes the vectors to unit length
aggregate(...) multiplies valueA and valueB
similarity(...) just needs to return the summedAggregations (which is
the dot-product)
pearson:
same as cosine, but normalize(...) centers the vector elements first
(without touching 0s as this would make the input matrix dense)
cooccurrence-count / overlap:
aggregate(...) returns 1 as we only need to count
similarity(...) returns summedAggregations only
tanimoto/jaccard:
norm(...) returns the l0 norm (number of non-zero elements)
aggregate(...) returns 1 as we only need to count
similarity(...) returns summedAggregations / (normOfRowA + normOfRowB -
summedDot);
loglikelihood:
same as tanimoto, but we compute LLR in similarity(...) from
summedAggregations, normOfRowA,normOfRowB,numColumns
cityblock/manhattan:
same as tanimoto, but similarity(...) returns 1.0 / (1.0 + normA + normB
- 2 * summedAggregations);
euclidean distance:
norm(...) returns the summed squares of the input vector
aggregate(...) aggregate(...) multiplies valueA and valueB
similarity(...) returns 1.0 - 1.0 / (1.0 + Math.sqrt(normA - 2 * dots +
normB)
unfortunately we cant use the formula from
o.a.m.cf.taste.impl.similarity.EuclideanDistanceSimilarity here which
also incorporates the number of "overlapping" dimensions.
I'm currently running tests on a small cluster using several rating
datasets (18M music ratings from lastfm, 100M movie ratings from
netflix, 250M music ratings from yahoo's KDD cup), results are pretty ok
so far, but I'm still searching for ways to improve the algorithm.
One thing I'm currently looking into is how to sample the input. Ted has
stated that you usually only need to look at a few hundred or thousand
ratings per item as you don't learn anything new from the rest. Would it
be sufficient to randomly sample the ratings of an item then? That's
what I'm currently doing but I wonder whether there are more clever ways
to do this.
There is a sampling heuristic in the distributed recommender that caught
my attention a long time ago, can anyone give any details on it? I
basically understand what it's doing but not exactly why that's a good
way to sample. Here's the original implementation:
http://svn.apache.org/viewvc/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/item/UserVectorToCooccurrenceMapper.java?revision=950049&view=co&pathrev=96188
Another issue I'm looking into is whether it would help to specify a
similarity threshold. There is some work on "All Pairs Similarity
Search" which is closely related to cooccurrence computation that seems
to have some nice pruning strategies based on a threshold.
For example imagine your similarity measure is cooccurrence count and
you only want to have pairs with a count of 5, than you would not need
to consider all pairs where one the vectors has less than 5 non zero
entries.
Something like this could be a way to further improve the algorithm's
running time, especially as the resulting similarity values seem to
follow a heavily tailed distribution. It should be possible to find
pruning heuristics for all measures, yet I don't have an idea yet how to
find a good a-priori threshold.
I think about writing a small paper about my works on that (still need
to see if I can "sell" it to my professor :) ). I hope everyone who
contributed to the discussion here is ok with that, I don't want to
"steal" ideas.
--sebastian
On 20.07.2011 17:40, Ted Dunning wrote:
> Not if you are doing Euclidean distance.
>
> On Wed, Jul 20, 2011 at 5:41 AM, Grant Ingersoll (JIRA)<ji...@apache.org>wrote:
>
>>
>> [
>> https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13068331#comment-13068331]
>>
>> Grant Ingersoll commented on MAHOUT-767:
>> ----------------------------------------
>>
>> Why do we need the norms? Why can't we assume the user has already
>> normalized?
>>
>>> Improve RowSimilarityJob performance for count-based distance measures
>>> ----------------------------------------------------------------------
>>>
>>> Key: MAHOUT-767
>>> URL: https://issues.apache.org/jira/browse/MAHOUT-767
>>> Project: Mahout
>>> Issue Type: Improvement
>>> Reporter: Grant Ingersoll
>>> Fix For: 0.6
>>>
>>>
>>> (See
>> http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7for background)
>>> Currently, the RowSimilarityJob defers the calculation of the similarity
>> metric until the reduce phase, while emitting many Cooccurrence objects.
>> For similarity metrics that are algebraic (
>> http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should
>> be able to do much of the computation during the Mapper part of this phase
>> and also take advantage of a Combiner.
>>> We should use a marker interface to know whether a similarity metric is
>> algebraic and then make use of an appropriate Mapper implementation,
>> otherwise we can fall back on our existing implementation.
>>
>> --
>> This message is automatically generated by JIRA.
>> For more information on JIRA, see: http://www.atlassian.com/software/jira
>>
>>
>>
>
Re: [jira] [Commented] (MAHOUT-767) Improve RowSimilarityJob
performance for count-based distance measures
Posted by Ted Dunning <te...@gmail.com>.
Not if you are doing Euclidean distance.
On Wed, Jul 20, 2011 at 5:41 AM, Grant Ingersoll (JIRA) <ji...@apache.org>wrote:
>
> [
> https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13068331#comment-13068331]
>
> Grant Ingersoll commented on MAHOUT-767:
> ----------------------------------------
>
> Why do we need the norms? Why can't we assume the user has already
> normalized?
>
> > Improve RowSimilarityJob performance for count-based distance measures
> > ----------------------------------------------------------------------
> >
> > Key: MAHOUT-767
> > URL: https://issues.apache.org/jira/browse/MAHOUT-767
> > Project: Mahout
> > Issue Type: Improvement
> > Reporter: Grant Ingersoll
> > Fix For: 0.6
> >
> >
> > (See
> http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7for background)
> > Currently, the RowSimilarityJob defers the calculation of the similarity
> metric until the reduce phase, while emitting many Cooccurrence objects.
> For similarity metrics that are algebraic (
> http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should
> be able to do much of the computation during the Mapper part of this phase
> and also take advantage of a Combiner.
> > We should use a marker interface to know whether a similarity metric is
> algebraic and then make use of an appropriate Mapper implementation,
> otherwise we can fall back on our existing implementation.
>
> --
> This message is automatically generated by JIRA.
> For more information on JIRA, see: http://www.atlassian.com/software/jira
>
>
>
[jira] [Commented] (MAHOUT-767) Improve RowSimilarityJob
performance
Posted by "Sebastian Schelter (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13100265#comment-13100265 ]
Sebastian Schelter commented on MAHOUT-767:
-------------------------------------------
A summary of my current work so far, a new patch is coming:
We should only support algebraic similarity measures which allows us to use a combiner in the most crucial phase. Furthermore we will use the stripes-pattern for in-mapper combination of cooccurrences to avoid emitting lots of cooccurrence pair objects.
This issue also touches ItemSimilarityJob and RecommenderJob as they use RowSimilarityJob internally. We will introduce a new job responsible for preparing the input data for these jobs.
As the distribution of ratings per user and ratings per item follow power-law distributions usually, appropriate down-sampling is crucial for the performance of these jobs as their runtime is dominated by the user with the largest number of interactions. We should remove the old "maxCooccurrencesPerItem" heuristic as it depends on the number of mappers that are run and the ordering of the input data. A simple random downsampling of users having a number of ratings above a threshold should work better.
> Improve RowSimilarityJob performance
> ------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Grant Ingersoll
> Assignee: Sebastian Schelter
> Fix For: 0.6
>
> Attachments: MAHOUT-767.patch
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-767) Improve RowSimilarityJob
performance
Posted by "Grant Ingersoll (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13101543#comment-13101543 ]
Grant Ingersoll commented on MAHOUT-767:
----------------------------------------
Why the change in types for the prep work? It was VarLongWritable but is now IntWritable?
> Improve RowSimilarityJob performance
> ------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Grant Ingersoll
> Assignee: Sebastian Schelter
> Fix For: 0.6
>
> Attachments: MAHOUT-767-2.patch, MAHOUT-767.patch
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-767) Improve RowSimilarityJob
performance
Posted by "Sebastian Schelter (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13101577#comment-13101577 ]
Sebastian Schelter commented on MAHOUT-767:
-------------------------------------------
itemIDIndex (sequence files of <VarIntWritable,VarLongWritable>) a mapping between the long ids of the input and the internally used int ids
numUsers.bin (binary integer) the number of users
userVectors (sequence files of <VarLongWritable, VectorWritable>) the rating matrix (user-item-matrix)
ratingMatrix (sequence files of <IntWritable,VectorWritable>) the transposed rating matrix (item-user-matrix)
> Improve RowSimilarityJob performance
> ------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Grant Ingersoll
> Assignee: Sebastian Schelter
> Fix For: 0.6
>
> Attachments: MAHOUT-767-2.patch, MAHOUT-767.patch
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-767) Improve RowSimilarityJob
performance
Posted by "Hudson (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13101274#comment-13101274 ]
Hudson commented on MAHOUT-767:
-------------------------------
Integrated in Mahout-Quality #1027 (See [https://builds.apache.org/job/Mahout-Quality/1027/])
MAHOUT-767 Improve RowSimilarityJob performance, threshold integration
ssc : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1167115
Files :
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/item/RecommenderJob.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/similarity/item/ItemSimilarityJob.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/similarity/item/MostSimilarItemPairsMapper.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/similarity/item/MostSimilarItemPairsReducer.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/RowSimilarityJob.java
* /mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/hadoop/similarity/item/ItemSimilarityJobTest.java
> Improve RowSimilarityJob performance
> ------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Grant Ingersoll
> Assignee: Sebastian Schelter
> Fix For: 0.6
>
> Attachments: MAHOUT-767-2.patch, MAHOUT-767.patch
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-767) Improve RowSimilarityJob
performance for count-based distance measures
Posted by "Sebastian Schelter (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13068295#comment-13068295 ]
Sebastian Schelter commented on MAHOUT-767:
-------------------------------------------
I suggest we create a specialized implementation that uses the "stripes" pattern from [1]. As we generalize the approach from that paper we'd need to emit a pair of vectors for each entry, the first holding the partially summed dot-products/counts, the other holding the norms. These vectors should easily be mergeable by a combiner.
With this approach, we should be able to cover all currently existing measures like cooccurrence count, LLR, Tanimoto, Cosine, Euclidean Distance, Manhattan and maybe even Pearson if someone figures out the math :)
I think we should have a shot at this and maybe completely drop the old too generic version (we should ask on the user list before dropping it).
[1] Lin: "Scalable Language Processing Algorithms for the Masses: A Case Study in
Computing Word Co-occurrence Matrices with MapReduce", http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.8326&rep=rep1&type=pdf
> Improve RowSimilarityJob performance for count-based distance measures
> ----------------------------------------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Reporter: Grant Ingersoll
> Fix For: 0.6
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-767) Improve RowSimilarityJob performance
Posted by "Sebastian Schelter (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sebastian Schelter updated MAHOUT-767:
--------------------------------------
Attachment: MAHOUT-767-2.patch
Patch attached with most functionality. Some pruning heuristics still missing
> Improve RowSimilarityJob performance
> ------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Grant Ingersoll
> Assignee: Sebastian Schelter
> Fix For: 0.6
>
> Attachments: MAHOUT-767-2.patch, MAHOUT-767.patch
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-767) Improve RowSimilarityJob
performance for count-based distance measures
Posted by "Grant Ingersoll (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13068331#comment-13068331 ]
Grant Ingersoll commented on MAHOUT-767:
----------------------------------------
Why do we need the norms? Why can't we assume the user has already normalized?
> Improve RowSimilarityJob performance for count-based distance measures
> ----------------------------------------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Reporter: Grant Ingersoll
> Fix For: 0.6
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-767) Improve RowSimilarityJob performance
for count-based distance measures
Posted by "Sebastian Schelter (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sebastian Schelter updated MAHOUT-767:
--------------------------------------
Attachment: MAHOUT-767.patch
Patch with first proof-of-concept code. It introduces AlgebraicRowSimilarityJob.
Instead of emitting (n*(n-1)) pairs from each inverted index entry it emits n "stripes" with each stripe consisting of two vectors with the first one holding the partial dot products/counts and the second holding the norms of cooccurred rows. These stripes can be easily merged by a combiner.
So we emit less objects and hopefully combine a lot of them which should lead to performance increasements.
I attached implementations for LLR, Tanimoto, Cosine and Cooccurrence count. Euclidean distance and Pearson-Correlation are still missing but we should be able to add them later (see AlgebraicVectorSimilarity)
Patch has unit tests, but as I don't have access to a testing cluster currently (this will change in the next weeks), it would be great if someone could verify that this code performs better than the existing approach, seeing some numbers would be awesome.
> Improve RowSimilarityJob performance for count-based distance measures
> ----------------------------------------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Reporter: Grant Ingersoll
> Fix For: 0.6
>
> Attachments: MAHOUT-767.patch
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Issue Comment Edited] (MAHOUT-767) Improve RowSimilarityJob
performance for count-based distance measures
Posted by "Sebastian Schelter (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13070647#comment-13070647 ]
Sebastian Schelter edited comment on MAHOUT-767 at 7/25/11 6:11 PM:
--------------------------------------------------------------------
Patch with first proof-of-concept code. It introduces AlgebraicRowSimilarityJob.
Instead of emitting (n*(n-1))/2 pairs from each inverted index entry it emits n "stripes" with each stripe consisting of two vectors with the first one holding the partial dot products/counts and the second holding the norms of cooccurred rows. These stripes can be easily merged by a combiner.
So we emit less objects and hopefully combine a lot of them which should lead to performance increasements.
I attached implementations for LLR, Tanimoto, Cosine and Cooccurrence count. Euclidean distance and Pearson-Correlation are still missing but we should be able to add them later (see AlgebraicVectorSimilarity)
Patch has unit tests, but as I don't have access to a testing cluster currently (this will change in the next weeks), it would be great if someone could verify that this code performs better than the existing approach, seeing some numbers would be awesome.
was (Author: ssc):
Patch with first proof-of-concept code. It introduces AlgebraicRowSimilarityJob.
Instead of emitting (n*(n-1)) pairs from each inverted index entry it emits n "stripes" with each stripe consisting of two vectors with the first one holding the partial dot products/counts and the second holding the norms of cooccurred rows. These stripes can be easily merged by a combiner.
So we emit less objects and hopefully combine a lot of them which should lead to performance increasements.
I attached implementations for LLR, Tanimoto, Cosine and Cooccurrence count. Euclidean distance and Pearson-Correlation are still missing but we should be able to add them later (see AlgebraicVectorSimilarity)
Patch has unit tests, but as I don't have access to a testing cluster currently (this will change in the next weeks), it would be great if someone could verify that this code performs better than the existing approach, seeing some numbers would be awesome.
> Improve RowSimilarityJob performance for count-based distance measures
> ----------------------------------------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Reporter: Grant Ingersoll
> Fix For: 0.6
>
> Attachments: MAHOUT-767.patch
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-767) Improve RowSimilarityJob
performance for count-based distance measures
Posted by "Sebastian Schelter (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13068368#comment-13068368 ]
Sebastian Schelter commented on MAHOUT-767:
-------------------------------------------
Correct me if I'm wrong but I thought that this normalization trick only works for cosine as similarity measure.
> Improve RowSimilarityJob performance for count-based distance measures
> ----------------------------------------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Reporter: Grant Ingersoll
> Fix For: 0.6
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-767) Improve RowSimilarityJob
performance
Posted by "Hudson (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13101722#comment-13101722 ]
Hudson commented on MAHOUT-767:
-------------------------------
Integrated in Mahout-Quality #1028 (See [https://builds.apache.org/job/Mahout-Quality/1028/])
MAHOUT-767: update the driver.classes.props for the new location of RowSimJob
gsingers : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1167350
Files :
* /mahout/trunk/src/conf/driver.classes.props
> Improve RowSimilarityJob performance
> ------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Grant Ingersoll
> Assignee: Sebastian Schelter
> Fix For: 0.6
>
> Attachments: MAHOUT-767-2.patch, MAHOUT-767.patch
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-767) Improve RowSimilarityJob
performance
Posted by "Hudson (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13101119#comment-13101119 ]
Hudson commented on MAHOUT-767:
-------------------------------
Integrated in Mahout-Quality #1026 (See [https://builds.apache.org/job/Mahout-Quality/1026/])
MAHOUT-767 Improve RowSimilarityJob performance, fixed typos
MAHOUT-767 Improve RowSimilarityJob performance
ssc : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1167030
Files :
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/CityBlockSimilarity.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/CooccurrenceCountSimilarity.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/CosineSimilarity.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/EuclideanDistanceSimilarity.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/LoglikelihoodSimilarity.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/TanimotoCoefficientSimilarity.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/VectorSimilarityMeasure.java
ssc : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1167027
Files :
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/MaybePruneRowsMapper.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/TasteHadoopUtils.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/ToEntityPrefsMapper.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/item/RecommenderJob.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/item/ToUserVectorReducer.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/item/ToUserVectorsReducer.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/preparation
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/preparation/PreparePreferenceMatrixJob.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/preparation/ToItemVectorsMapper.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/preparation/ToItemVectorsReducer.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/similarity/item/ItemSimilarityJob.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/hadoop/similarity/item/ToItemVectorsReducer.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/common/AbstractJob.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/common/ClassUtils.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/graph/linkanalysis/PageRankJob.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/VectorWritable.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/TransposeJob.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/Cooccurrence.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/RowSimilarityJob.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/SimilarityMatrixEntryKey.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/SimilarityType.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/WeightedOccurrence.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/WeightedOccurrenceArray.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/WeightedRowPair.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/RowSimilarityJob.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/Vectors.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/CityBlockSimilarity.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/CooccurrenceCountSimilarity.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/CosineSimilarity.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/CountbasedMeasure.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/EuclideanDistanceSimilarity.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/LoglikelihoodSimilarity.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/PearsonCorrelationSimilarity.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/TanimotoCoefficientSimilarity.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/VectorSimilarityMeasure.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/VectorSimilarityMeasures.java
* /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/similarity/vector
* /mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/hadoop/MaybePruneRowsMapperTest.java
* /mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/hadoop/als/ParallelALSFactorizationJobTest.java
* /mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/hadoop/als/PredictionJobTest.java
* /mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/hadoop/item/RecommenderJobTest.java
* /mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/hadoop/item/ToUserVectorReducerTest.java
* /mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/hadoop/item/ToUserVectorsReducerTest.java
* /mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/hadoop/similarity/item/ItemSimilarityJobTest.java
* /mahout/trunk/core/src/test/java/org/apache/mahout/graph/linkanalysis/PageRankJobTest.java
* /mahout/trunk/core/src/test/java/org/apache/mahout/math/hadoop/MathHelper.java
* /mahout/trunk/core/src/test/java/org/apache/mahout/math/hadoop/similarity/TestRowSimilarityJob.java
* /mahout/trunk/core/src/test/java/org/apache/mahout/math/hadoop/similarity/cooccurrence
* /mahout/trunk/core/src/test/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/RowSimilarityJobTest.java
* /mahout/trunk/core/src/test/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures
* /mahout/trunk/core/src/test/java/org/apache/mahout/math/hadoop/similarity/cooccurrence/measures/VectorSimilarityMeasuresTest.java
* /mahout/trunk/core/src/test/java/org/apache/mahout/math/hadoop/similarity/vector
* /mahout/trunk/integration/src/test/java/org/apache/mahout/utils/eval/ParallelFactorizationEvaluatorTest.java
* /mahout/trunk/math/src/main/java/org/apache/mahout/math/AbstractVector.java
* /mahout/trunk/pom.xml
> Improve RowSimilarityJob performance
> ------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Grant Ingersoll
> Assignee: Sebastian Schelter
> Fix For: 0.6
>
> Attachments: MAHOUT-767-2.patch, MAHOUT-767.patch
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-767) Improve RowSimilarityJob
performance for count-based distance measures
Posted by "Sebastian Schelter (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13070650#comment-13070650 ]
Sebastian Schelter commented on MAHOUT-767:
-------------------------------------------
This patch does not address whether we should keep the old RowSimilarityJob or not, I think we should decide this after we have a little more detailed picture of the performance of the new approach.
> Improve RowSimilarityJob performance for count-based distance measures
> ----------------------------------------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Reporter: Grant Ingersoll
> Fix For: 0.6
>
> Attachments: MAHOUT-767.patch
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Resolved] (MAHOUT-767) Improve RowSimilarityJob performance
Posted by "Sebastian Schelter (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sebastian Schelter resolved MAHOUT-767.
---------------------------------------
Resolution: Fixed
> Improve RowSimilarityJob performance
> ------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Grant Ingersoll
> Assignee: Sebastian Schelter
> Fix For: 0.6
>
> Attachments: MAHOUT-767-2.patch, MAHOUT-767.patch
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-767) Improve RowSimilarityJob performance
for count-based distance measures
Posted by "Sean Owen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Owen updated MAHOUT-767:
-----------------------------
Component/s: Collaborative Filtering
Affects Version/s: 0.5
Assignee: Sebastian Schelter
> Improve RowSimilarityJob performance for count-based distance measures
> ----------------------------------------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Grant Ingersoll
> Assignee: Sebastian Schelter
> Fix For: 0.6
>
> Attachments: MAHOUT-767.patch
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-767) Improve RowSimilarityJob performance
Posted by "Sebastian Schelter (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-767?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sebastian Schelter updated MAHOUT-767:
--------------------------------------
Summary: Improve RowSimilarityJob performance (was: Improve RowSimilarityJob performance for count-based distance measures)
> Improve RowSimilarityJob performance
> ------------------------------------
>
> Key: MAHOUT-767
> URL: https://issues.apache.org/jira/browse/MAHOUT-767
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Grant Ingersoll
> Assignee: Sebastian Schelter
> Fix For: 0.6
>
> Attachments: MAHOUT-767.patch
>
>
> (See http://www.lucidimagination.com/search/document/40c4f124795c6b5/rowsimilarity_s#42ab816c27c6a9e7 for background)
> Currently, the RowSimilarityJob defers the calculation of the similarity metric until the reduce phase, while emitting many Cooccurrence objects. For similarity metrics that are algebraic (http://pig.apache.org/docs/r0.8.1/udf.html#Aggregate+Functions) we should be able to do much of the computation during the Mapper part of this phase and also take advantage of a Combiner.
> We should use a marker interface to know whether a similarity metric is algebraic and then make use of an appropriate Mapper implementation, otherwise we can fall back on our existing implementation.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira