Nearest neighbor/k-NN for use with Normalized Compression Distance. I wonder if there exist any approximation of NN/k-NN algorithm which work for all distance measures ? I would like to test Normalized Compression Distance in practice but cost of computation of similarity matrix (compression of concatenation of each two observations/strings) is too high. So mayby there is approximation of NN/k-NN which don't use any direct approximation of distance between observations e.g. without Local Sensitive Hashing and only try to measure those distances which seems to be relevant and bring new informations after random initialization.
- I was thinking about Latent Variables Model based on distance matrix for finding the most relevant pairs of observations, but it seems that distance matrix shouldn't be too sparse for this approach.
- Mayby some heuristics would work, such as : for choosen 'x' find nearest neigbor from set of observations for which distance have been computed - call it 'y', then calculate distance between 'x' and nearest neighbor (or all neighbors or 'n' neighbors) of 'y'.