[ https://issues.apache.org/jira/browse/MAHOUT823?page=com.atlassian.jira.plugin.system.issuetabpanels:commenttabpanel&focusedCommentId=13118049#comment13118049
]
Eugene Kirpichov commented on MAHOUT823:

Ted, since the code change required is so small, I simply included it into the task description.
Is there any particular reason to convert that into a patch (e.g. the necessity to follow
a formal procedure)?
Sean, right, the goal is to avoid doing many lookups; I actually only had in mind the trivial
case of dotting two RandomAccess vectors, but your comment got me thinking on what to do in
the general case.
Randomrandom: Smallest leads (what's proposed)
Seqseq: Merge (what's implemented)
Randomseq:
If random leads, number of operations is O((numnonzeroinr)^2) because there's this many
lookups into the sequential vector, each taking linear time.
If sequential leads (what's implemented), number of operations is O(num nonzero in sequential).
It's difficult to decide which to use, given that we don't know the constant factors, but
at least having the sequential lead will never have quadratic behavior, so I suggest to leave
it as is.

Bottom line:
I would suggest to implement just the proposed change.
> RandomAccessSparseVector.dot with another nonsequential vector can be extremely nonsymmetric
in its performance
> 
>
> Key: MAHOUT823
> URL: https://issues.apache.org/jira/browse/MAHOUT823
> Project: Mahout
> Issue Type: Improvement
> Components: Math
> Affects Versions: 0.5
> Reporter: Eugene Kirpichov
> Assignee: Sean Owen
> Labels: dot, dotproduct, vector
> Fix For: 0.6
>
> Attachments: MAHOUT823.patch
>
>
> 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 KMeans clustering.
> In KMeans for highdimensional points (e.g. those that arise in text retrieval problems),
the centroids often have a huge number of nonzero 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
