search

spotify / annoy

Approximate Nearest Neighbors in C++/Python optimized for memory usage and loading/saving to disk
Apache License 2.0
13.24k stars 1.17k forks source link

other distance functions #102

Closed erikbern closed 8 years ago

erikbern commented 9 years ago

I realized today it's pretty easy to generalize to arbitrary distance functions. If every split is just the midpoint normal of two points then you can split by checking whether d(a, x) < d(b, x) where a and b are the points defining the split.

Interestingly this generalizes to crazy shit like edit distance. Would be cool to do a spell checker using Annoy :)

a1k0n commented 9 years ago

Huh, that's true. A tree is a Voronoi diagram then, effectively. So you could use Hamming distance too.... which I actually have a use for, right now. Neat!

a1k0n commented 9 years ago

And actually, then you don't have to store the split planes at all, only pointers to the left/right tree nodes. Which again breaks your fixed tree node size constraint unless leaves are tiny, but if you had dynamic leaf node sizes then the whole tree would be a lot smaller.

If you do that then it would also make sense to reorder the indices so that the roots and interior tree nodes are first, etc, for memory locality purposes.

Another idea I had was to just store the points in the interior nodes and not in the leaves, and push them onto the priority queue while traversing the tree. But that doesn't really help when you have multiple trees and the same points which are interior in one tree end up in a leaf of another tree.

erikbern commented 9 years ago

But Hamming distance is pretty much the same as Euclidean unless you are saying some leaves could have many items?

Btw did you see https://github.com/houzz/annoy2 ? Will be interesting to see if the LMDB backend works out - then you don't have to worry about the fixed size stuff

On Friday, September 11, 2015, Andy Sloane notifications@github.com wrote:

And actually, then you don't have to store the split planes at all, only pointers to the left/right tree nodes. Which again breaks your fixed tree node size constraint unless leaves are tiny, but if you had dynamic leaf node sizes then the whole tree would be a lot smaller.

If you do that then it would also make sense to reorder the indices so that the roots and interior tree nodes are first, etc, for memory locality purposes.

Another idea I had was to just store the points in the interior nodes and not in the leaves, and push them onto the priority queue while traversing the tree. But that doesn't really help when you have multiple trees and the same points which are interior in one tree end up in a leaf of another tree.

— Reply to this email directly or view it on GitHub https://github.com/spotify/annoy/issues/102#issuecomment-139447487.

a1k0n commented 9 years ago

Oh yeah, I hadn't considered hamming as a special case of euclidean. Still, it would be much more compactly represented as bits rather than 0/0.5/1 floats :)

I did see that, yeah. That could enable all kinds of neat stuff.

erikbern commented 8 years ago

You could implement hamming distance by just having T=int64 and add up the bit distance btw

ANyway, closing this...