You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@mahout.apache.org by Shashikant Kore <sh...@gmail.com> on 2009/05/22 12:52:38 UTC
Performance gains with changes in distance calculation
Hi,
I am working on clustering a dataset which has thousands of sparse
vectors. The complete dataset has few tens of thousands of feature
items but each vector has only couple of hundred feature items. For
this, there is an optimization in distance calculation, a link to
which I found the archives of Mahout mailing list.
http://lingpipe-blog.com/2009/03/12/speeding-up-k-means-clustering-algebra-sparse-vectors/
I tried out this optimization. The test setup had 2000 document
vectors with few hundred items. I ran canopy generation with
Euclidean distance and t1, t2 values as 250 and 200.
Current Canopy Generation: 28 min 15 sec.
Canopy Generation with distance optimization: 1 min 38 sec.
I know by experience that using Integer, Double objects instead of
primitives is computationally expensive. I changed the sparse vector
implementation to used primitive collections by Trove [
http://trove4j.sourceforge.net/ ].
Distance optimization with Trove: 59 sec
Current canopy generation with Trove: 21 min 55 sec
To sum, these two optimizations reduced cluster generation time by a 97%.
Currently, I have made the changes for Euclidean Distance, Canopy and
KMeans. How do we go about pushing these changes to Mahout?
--shashi
Re: Performance gains with changes in distance calculation
Posted by Sean Owen <sr...@gmail.com>.
I guess because you can't really re-use it if you specifically want a
Map that stores primitives, since the current implementations operates
on Objects. And we specifically need to avoid boxing. Somehow
accommodating both in one class would be quite a bit of code an impact
performance -- this is why the Trove guys had to rewrite their own
classes.
I'm all for moving it up to a higher-level common directory if it makes sense.
On Fri, May 22, 2009 at 5:34 PM, Jeff Eastman
<jd...@windwardsolutions.com> wrote:
> Why copy/paste something that's already in Mahout? If it can fill the bill
> as well as Trove then why not use it directly? And, consider moving it into
> the Matrix package if you want to simplify the dependencies.
Re: Performance gains with changes in distance calculation
Posted by Jeff Eastman <jd...@windwardsolutions.com>.
Why copy/paste something that's already in Mahout? If it can fill the
bill as well as Trove then why not use it directly? And, consider moving
it into the Matrix package if you want to simplify the dependencies.
Jeff
Sean Owen wrote:
> Dang you're right. And I can't find it in Commons Collections either.
> I wonder what I was thinking of.
>
> I like the idea of using Trove but not redistributing it, by means of
> Maven if possible.
>
> If not, seriously, just try a copy-and-paste job on
> org.apache.mahout.cf.taste.impl.common.FastMap.
>
> On Fri, May 22, 2009 at 4:51 PM, Shashikant Kore <sh...@gmail.com> wrote:
>
>> I have checked Apache Commons Primitives and Google collections. But
>> none of them offer primitive Hashes.
>>
>
>
>
Re: Performance gains with changes in distance calculation
Posted by Sean Owen <sr...@gmail.com>.
Dang you're right. And I can't find it in Commons Collections either.
I wonder what I was thinking of.
I like the idea of using Trove but not redistributing it, by means of
Maven if possible.
If not, seriously, just try a copy-and-paste job on
org.apache.mahout.cf.taste.impl.common.FastMap.
On Fri, May 22, 2009 at 4:51 PM, Shashikant Kore <sh...@gmail.com> wrote:
> I have checked Apache Commons Primitives and Google collections. But
> none of them offer primitive Hashes.
Re: Performance gains with changes in distance calculation
Posted by Shashikant Kore <sh...@gmail.com>.
I have checked Apache Commons Primitives and Google collections. But
none of them offer primitive Hashes.
--shashi
On Fri, May 22, 2009 at 4:45 PM, Grant Ingersoll <gs...@apache.org> wrote:
>
> It's a bit complicated by Trove, b/c that is LGPL. What that means,
> unfortunately, is that we can't check it into our code or distribute it.
> However, if it is in a Maven repo somewhere (I see an old version) than it
> is easier to include. I haven't looked at the code, but is it possible that
> http://commons.apache.org/primitives/ fills the same role or some other
> library out there that has a more friendly license?
>
> Regardless of these, feel free to submit a patch, so we can at least look at
> it and have something concrete to discuss in JIRA.
>
Re: Performance gains with changes in distance calculation
Posted by Dan Hatfield <da...@gmail.com>.
http://commons.apache.org/primitives/
On Fri, May 22, 2009 at 11:17 AM, Sean Owen <sr...@gmail.com> wrote:
> I'll add that I am not surprised that is significant overhead, and imagine
> most of the use of Objects in the code in Maps and such will need to be
> optimized before 1.0.
>
> Doesn't the Apache or Google collections lib also have primitive-value
> collections in addition to Trove? I swear one of them does. And they are
> Apache licensed.
> Having run up hard against performance and memory issues with java.util, I
> long since wrote custom implementations whose goal is more to use fewer
> memory by using fewer Objects, but that also contributes to speed. Making a
> primitivized version of those could prove exceptionally quick. That is in
> ou
>
> But I favor reusing existing code first.
>
> On May 22, 2009 12:15 PM, "Grant Ingersoll" <gs...@apache.org> wrote:
>
> On May 22, 2009, at 6:52 AM, Shashikant Kore wrote: > Hi, > > I am working
> on clustering a dataset...
> Very cool.
>
> > I know by experience that using Integer, Double objects instead of >
> primitives is computational...
> http://cwiki.apache.org/MAHOUT/howtocontribute.html
>
> It's a bit complicated by Trove, b/c that is LGPL. What that means,
> unfortunately, is that we can't check it into our code or distribute it.
> However, if it is in a Maven repo somewhere (I see an old version) than it
> is easier to include. I haven't looked at the code, but is it possible
> that
> http://commons.apache.org/primitives/ fills the same role or some other
> library out there that has a more friendly license?
>
> Regardless of these, feel free to submit a patch, so we can at least look
> at
> it and have something concrete to discuss in JIRA.
>
> Thanks,
> Grant
>
> --------------------------
> Grant Ingersoll
> http://www.lucidimagination.com/
>
> Search the Lucene ecosystem (Lucene/Solr/Nutch/Mahout/Tika/Droids) using
> Solr/Lucene:
> http://www.lucidimagination.com/search
>
Re: Performance gains with changes in distance calculation
Posted by Sean Owen <sr...@gmail.com>.
I'll add that I am not surprised that is significant overhead, and imagine
most of the use of Objects in the code in Maps and such will need to be
optimized before 1.0.
Doesn't the Apache or Google collections lib also have primitive-value
collections in addition to Trove? I swear one of them does. And they are
Apache licensed.
Having run up hard against performance and memory issues with java.util, I
long since wrote custom implementations whose goal is more to use fewer
memory by using fewer Objects, but that also contributes to speed. Making a
primitivized version of those could prove exceptionally quick. That is in ou
But I favor reusing existing code first.
On May 22, 2009 12:15 PM, "Grant Ingersoll" <gs...@apache.org> wrote:
On May 22, 2009, at 6:52 AM, Shashikant Kore wrote: > Hi, > > I am working
on clustering a dataset...
Very cool.
> I know by experience that using Integer, Double objects instead of >
primitives is computational...
http://cwiki.apache.org/MAHOUT/howtocontribute.html
It's a bit complicated by Trove, b/c that is LGPL. What that means,
unfortunately, is that we can't check it into our code or distribute it.
However, if it is in a Maven repo somewhere (I see an old version) than it
is easier to include. I haven't looked at the code, but is it possible that
http://commons.apache.org/primitives/ fills the same role or some other
library out there that has a more friendly license?
Regardless of these, feel free to submit a patch, so we can at least look at
it and have something concrete to discuss in JIRA.
Thanks,
Grant
--------------------------
Grant Ingersoll
http://www.lucidimagination.com/
Search the Lucene ecosystem (Lucene/Solr/Nutch/Mahout/Tika/Droids) using
Solr/Lucene:
http://www.lucidimagination.com/search
Re: Performance gains with changes in distance calculation
Posted by Grant Ingersoll <gs...@apache.org>.
On May 22, 2009, at 6:52 AM, Shashikant Kore wrote:
> Hi,
>
> I am working on clustering a dataset which has thousands of sparse
> vectors. The complete dataset has few tens of thousands of feature
> items but each vector has only couple of hundred feature items. For
> this, there is an optimization in distance calculation, a link to
> which I found the archives of Mahout mailing list.
>
> http://lingpipe-blog.com/2009/03/12/speeding-up-k-means-clustering-algebra-sparse-vectors/
>
> I tried out this optimization. The test setup had 2000 document
> vectors with few hundred items. I ran canopy generation with
> Euclidean distance and t1, t2 values as 250 and 200.
>
> Current Canopy Generation: 28 min 15 sec.
> Canopy Generation with distance optimization: 1 min 38 sec.
>
Very cool.
> I know by experience that using Integer, Double objects instead of
> primitives is computationally expensive. I changed the sparse vector
> implementation to used primitive collections by Trove [
> http://trove4j.sourceforge.net/ ].
>
> Distance optimization with Trove: 59 sec
> Current canopy generation with Trove: 21 min 55 sec
>
> To sum, these two optimizations reduced cluster generation time by a
> 97%.
>
> Currently, I have made the changes for Euclidean Distance, Canopy and
> KMeans. How do we go about pushing these changes to Mahout?
http://cwiki.apache.org/MAHOUT/howtocontribute.html
It's a bit complicated by Trove, b/c that is LGPL. What that means,
unfortunately, is that we can't check it into our code or distribute
it. However, if it is in a Maven repo somewhere (I see an old
version) than it is easier to include. I haven't looked at the code,
but is it possible that http://commons.apache.org/primitives/ fills
the same role or some other library out there that has a more friendly
license?
Regardless of these, feel free to submit a patch, so we can at least
look at it and have something concrete to discuss in JIRA.
Thanks,
Grant
--------------------------
Grant Ingersoll
http://www.lucidimagination.com/
Search the Lucene ecosystem (Lucene/Solr/Nutch/Mahout/Tika/Droids)
using Solr/Lucene:
http://www.lucidimagination.com/search
Re: Performance gains with changes in distance calculation
Posted by Jeff Eastman <jd...@windwardsolutions.com>.
Shashi,
I'm glad to see you have demonstrated the improvement made possible by
that optimization. It is really astounding. I will look over your
patches immediately.
Jeff
Shashikant Kore wrote:
> Hi,
>
> I am working on clustering a dataset which has thousands of sparse
> vectors. The complete dataset has few tens of thousands of feature
> items but each vector has only couple of hundred feature items. For
> this, there is an optimization in distance calculation, a link to
> which I found the archives of Mahout mailing list.
>
> http://lingpipe-blog.com/2009/03/12/speeding-up-k-means-clustering-algebra-sparse-vectors/
>
> I tried out this optimization. The test setup had 2000 document
> vectors with few hundred items. I ran canopy generation with
> Euclidean distance and t1, t2 values as 250 and 200.
>
> Current Canopy Generation: 28 min 15 sec.
> Canopy Generation with distance optimization: 1 min 38 sec.
>
> I know by experience that using Integer, Double objects instead of
> primitives is computationally expensive. I changed the sparse vector
> implementation to used primitive collections by Trove [
> http://trove4j.sourceforge.net/ ].
>
> Distance optimization with Trove: 59 sec
> Current canopy generation with Trove: 21 min 55 sec
>
> To sum, these two optimizations reduced cluster generation time by a 97%.
>
> Currently, I have made the changes for Euclidean Distance, Canopy and
> KMeans. How do we go about pushing these changes to Mahout?
>
> --shashi
>
>
>