Data Structure for efficient nearest neighbor search using generalized distance?

Question

I have a list of objects that have a defined measure of distance between them and I'm trying to store them in a data structure such that I can easily and quickly query which of the objects is closest to a key which is not necessarily in the list (like nearest-neighbor). The problem is that these objects aren't points and, as far as I'm aware, can't be converted to points, so something like a k-d tree won't work. All I have to compare them is this distance metric (which does obey the triangle inequality), though it is possible to compute the distance between any two of the objects. Is there any data structure that supports efficient nearest neighbor search but works only off of distance? One idea I had would be to try and convert each object to a point such that the distance between them maps to the euclidean distance of the points, but that seems computationally expensive and I think would require as many dimensions as points in the worst case.

Answer 1

You can use a CoverTree. It indexes objects purely by distance. One implementation is available here.

I have my own implementation here (Java) which is based on a more recent publication "Faster Cover Trees" by Mike Izbicki and Christian R. Shelton.

You may have to modify my implementation because it expects points as input.

Answer 2

Have a good day!You can find the correlation coefficient between what you want and every node of a binary search tree , then choose the value with the highest correleation coefficient.