Not irrelevant at all. It is a very good point. It means that the strict triangle optimization cannot be applied with the no-square-root optimization.
There is a stricter bound that you can use with squared distances (r_12^2 - 3 r_x1^2 as opposed to r_12 - r_x1) but using that spoils the generality of the k-means algorithm. We could also push a method into some distances using an additional interface something like HasTriangleBound and allow the distance to compute the bound, but this is getting pretty far out in the weeds. On Fri, Jun 26, 2009 at 6:35 AM, Sean Owen (JIRA) <j...@apache.org> wrote: > > [ > https://issues.apache.org/jira/browse/MAHOUT-121?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12724520#action_12724520] > > Sean Owen commented on MAHOUT-121: > ---------------------------------- > > This may be irrelevant -- haven't thought it through -- since someone > mentioned using the triangle inequality to optimize some stuff earlier, I > wonder if it is a problem that a squared-distance measure no longer > satisfies this inequality? That is, it is not true that the square of one > side is less than the sum of squares of other two sides. > >
