Scann: Scalable Nearest Neighbors
github.com
github.com
(It's also linked in the repository's docs/algorithms.md, to which there's a link at the bottom of the main page.)
- How are the quantized vectors used to do NNS? Do we have to brute force compare against each codeword?
- In thst case, how many codewords are there? How big is k compared to n? How does changing k affect performance?
- What architecture is used to train the embeddings? We are only given the loss function.
- How fast is the preprocessing step? If we need to do Lloyd's algorithm type iterations combined with training neural nets, this is potentially a lot slower than Faiss which just picks random landmark points.
I do sort of wonder if we will reach a point where instead of pure recall per speed, we’ll have a family of algorithms with more trade offs for the use case. Where we begin to look at metrics for that domain for a given ANN approach instead of just its ability to recreate a nearest neighbors set retrieval.
Like one thing I see assumed is that while recall at N is good, does this also mean the “ranking” of that top N is ideal? I don’t want to have to manually compute NN on this top N if I can avoid it, for example.
And are there specific vector spaces where one ANN is preferred? Or will there be some universal approach that just works for everything?
I realize it’s too early to tell, but these questions always percolate in my mind when we hit a new benchmark in recall for speed. Especially since I still see people doing more naive things that seem to work perfectly fine for their use case (like KD trees, random projections, or LSH)
This is a great question for research right now. Basically euclidean (and inner product) search is quite well understood, but for distance measures such as edit distance we still have no idea what the best approach is.
The most general result is https://ieeexplore.ieee.org/abstract/document/8555102 , which works for all normed spaces.
However it is possible that people will try to just map everything to inner products using neural networks.
It seems that the primary idea is that quantization precision is more important where there is a high density of neighbors.
I.e. at the edges the quantized sections (buckets) could be large since there are few items there, but at high density areas, the buckets should be much smaller in order to have an even distribution of objects per bucket as possible.
Therefore, the overall effectiveness of a Quantization loss function should not be evaluated on a sum of squared error (that assumes the vector space has consistent linear value), but should rather consider the densities of the vector space and use that as a weight of the errors at different regions.
To me it seems analogous to a hash set, where the goal would be to have even distribution (same number of items in every bucket).
We want to quantize space so that every position has about the same number of items.
Sounds like the n-dimensional version of an octree
And what is that exactly? I was under the impression result of running nearest-neighbor algorithms are clusters. DBSCAN is a clustering algorithm. kNN is a clustering algorithm.
Is this used to find neighbors for use in a clustering algorithm?
The analogy with classical algorithms would be to apply something like DBSCAN or Spectral clustering to cluster points, then find a way to use the clusters to speed up nn search. In practice no one would do this; I'm mentioning it here only because I think it's a helpful analogy.
[1] https://scikit-learn.org/stable/modules/generated/sklearn.ne...
milvus integrates and wraps libraries like faiss and nmslib, which are alternatives to Scann. (If anything, I expect the milvus developers will soon be looking into integrating and wrapping Scann.)