fast distance metric between a new data entry and available clusters of data Assume we divide a large data set D into m different partitions of data in a distributed learning case, using K-means clustering. We do the training in the clusters and they are local experts. Now, we have some new test points that we want to assign to the partitions and obtain the predictions. An initial guess is we can find the distance between new points the centroids of the clusters which may take time in large data sets. I want to know if there is any faster method that works faster when the number of the new points increases? Also, except distance metrics, it there any similarity-based measures that can be used to make a connection between new entries and available partitions' centroids?
 A: Don't cluster. Classify.
I have expanded on this topic here How to assign new data to an existing clustering but to give some more details why this allows us to have a "fast approximate distance metric".
Especially if we use a classifier $C$ based on trees (e.g. random forests, gradient boosting, etc.) what we would have learned through the training of it will be a recursive partitioning of our sample space (through piece-wise flat functions) such that it aligns as closely as possible with the class/cluster labels. This recursive partitioning is exactly what will allow us now to compute a fast approximate distance from the cluster centres/exemplars in the form of our class/cluster membership probabilities. (where for example, a high probability of being in class $A$ suggest someone "very close" to a typical class/cluster $A$ instance.
To that extent, this "trick" of recursive partitioning our sample space via a tree-based classifier is exactly the "trick" we use when calculating approximate distances between points from a large high-dimensional sample via ball trees.
(Do note though that, unlike ball trees we don't have to use a tree-based classifier, I used it as an example, any classifier with probabilistic outputs will do.)
