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. 


*

*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'.

 A: Distance functions can be really nasty, and you chose on of the most unstable ones.
Any approximation or index makes some extra assumptions on the data.
For example an R-tree can be queries with any distance function where you can compute a lower bound between a point and a rectangle. An M-tree can be built for any metrical distance function - you need to prove triangle inequality for your metric. An M-tree cannot be queried with a different distance function than the one it was built for. And for LSH, you need hash functions that are consistent for your distance function. The commonly used LSH hash families are good for Euclidean distance.
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!
