Re:FANN: Vector Search in 200 Lines of Rust
by nikhilgarg28 on Thursday June 15, 2023 @11:47PM
(#36350918)
One of the authors of the post here. I've never heard of this approach but it sounds really cool. Will definitely try it out someday!
does that scale to high-dimensions? IIUC the photon mapping procedure typically uses a kd-tree to find closer/farther candidates, and if you consider something like ada embeddings (1536 dim), that would be very computationally intense. photon mapping feels like a 3D problem
The classic approach is to keep your k candidates in a max heap ordered by distance (replacing the farthest candidates whenever the heap is full and you find nearer items in the leaves), and visit the far side of the hyperplane after visiting the near side if either the distance to the hyperplane is less than the distance to the farthest item in the heap or you don't yet have k candidates.
A way to visualize it is that your k candidates define a ball (with radius defined by the worst candidate) around the search point that shrinks as you find better candidates. Then you recursively visit all the nodes in the tree that the ball still touches. Any nodes outside the ball can't possibly improve on the candidates within it and so can be excluded.
In graphics rendering, this sort of thing was the approach used by photon mapping [0] to find the closest photons for density estimation.
[0] https://en.wikipedia.org/wiki/Photon_mapping