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.
You may have to modify my implementation because it expects points as input.