NCD as a distance measure can be used for kNN and in this case actually was used for hierarchical clustering in the form of the unrooted binary tree. As for ho

NCD as a distance measure can be used for kNN and in this case actually was used for hierarchical clustering in the form of the unrooted binary tree. As for how NCD compares to euclidian, manhattan distances and so on - it's interesting. One of NCD's strengths is that you can apply it even if your data is not readily representable as a uniformly-long vector of numbers, whereas most other distance measures require this and it's not always convenient to represent input data in that form. For example, in this application games may be of widely-varying lengths. That doesn't matter when computing the NCD, but I'd have had to pad out the "missing" values from shorter runs to the lengths of longer ones, or truncated long ones, or resized them all with some smoothing. None of those seemed like particularly good options for this application. Also, with time series (which this essentially is), most compressors are good at recognizing patterns repeated in items. That means that 0, 0, 4, 7, 9, 4, 0 is very close to 0, 4, 7, 9, 4, 0, 0 under NCD and is comparatively distant under euclidian, manhattan and cosine distances as the elements of each vector are assumed to be independent. In short, your mileage may vary and will depend on the application. I like NCD because it's super easy to throw it at almost any problem and get a quick understanding of how the data is structured. The algorithms in complearn are slow. I'm experimenting with much faster ones that scale better at the moment.