# Distance independent approximation of Nearest Neighbor/k-NN.

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.

1. 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.
2. 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'.

Similar things hold for every single (approximated or not) index. The problem is that you can define all kind of stupid distance functions. For example, d(x,y):=hash(x) XOR hash(y). This distance of course will not be metrical, so it won't work with the M-tree. I cannot compute sensible bounds for rectangles, so I cannot use the R-tree either. And so on. You will need to choose the index appropriately for your distance function!