Hum. After reading some code I see your point. I even see that the existing code is fairly sub-optimal for non-euclidean metrics. I will make use of the fact that scipy.spatial.cdist can compute a distance matrix, and apply it on the chunks.