1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 1. Will the key always be one of the objects in the list? Could the key be an object that is not in the list? 2. Do you have distances for all pairs of objects in the list? If not, what is the definition of which object is closest to X, if I don't know the distance between X and every other object? Please edit the question to clarify the problem statement. $\endgroup$
    – D.W.
    Oct 18, 2023 at 19:57

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The only issue with this is O(n) search time. Otherwise, this would be my strategy $\endgroup$
    – Josh Tint
    Oct 19, 2023 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.