mahout-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Eugene Kirpichov (Created) (JIRA)" <j...@apache.org>
Subject [jira] [Created] (MAHOUT-823) RandomAccessSparseVector.dot with another non-sequential vector can be extremely non-symmetric in its performance
Date Fri, 30 Sep 2011 11:21:45 GMT
RandomAccessSparseVector.dot with another non-sequential vector can be extremely non-symmetric
in its performance
-----------------------------------------------------------------------------------------------------------------

                 Key: MAHOUT-823
                 URL: https://issues.apache.org/jira/browse/MAHOUT-823
             Project: Mahout
          Issue Type: Improvement
          Components: Math
            Reporter: Eugene Kirpichov


http://codesearch.google.com/#6LK_nEANBKE/math/src/main/java/org/apache/mahout/math/RandomAccessSparseVector.java&l=172

The complexity of the algorithm is O(num nondefault elements in this), while it could clearly
be O(min(num nondefault in this, num nondefault in x)).

This can be fixed by adding this code before line 189.

{code}
if(x.getNumNondefaultElements() < this.getNumNondefaultElements()) {
  return x.dot(this);
}
{code}

An easy case where this asymmetry is very apparent and makes a huge difference in performance
is K-Means clustering.

In K-Means for high-dimensional points (e.g. those that arise in text retrieval problems),
the centroids often have a huge number of non-zero components, whereas points have a small
number of them.

So, if you make a mistake and use centroid.dot(point) in your code for computing the distance,
instead of point.dot(centroid), you end up with orders of magnitude worse performance (which
is what we actually observed - the clustering time was a couple of minutes with this fix and
over an hour without it).

So, perhaps, if you make this fix, quite a few people who had a similar case but didn't notice
it will suddenly have a dramatic performance increase :)

--
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

        

Mime
View raw message