ScaNN: Efficient Vector Similarity Search
ai.googleblog.com
ai.googleblog.com
Before you start looking at approximate nearest neighbors, ask yourself the following:
1. Do I know all of the vectors ahead of time? (i.e. query vectors are not constructed at runtime, it's a fixed inventory of items being embedded)
2. Do I need to return an unlimited number of neighbors per query? (i.e. do you ever need more than like, a few thousand neighbors)
If the answer to both of these is "no", then you should probably just precompute the neighbors exactly on one or more GPUs. It's feasible for millions of terms, and may actually be faster than the index-building steps for many ANN algorithms. Example code: https://github.com/explosion/sense2vec/blob/master/scripts/0...
A cache of k neighbors for vectors of dimension d will be k/d the size of the original vector data, because one integer and one float both occupy 32-bits of data. So if your vectors are 300 dimensions, you can save 150 neighbors and serve the results with half the space of the original data. The responses are then instant and exact, and you'll never have problems with load management because the runtime is so cheap. Example demo: https://explosion.ai/demos/sense2vec
Again, this doesn't work for queries you have to construct on the fly, for instance it won't work if you need to construct a vector that incorporates information from the user's session or something. It only works if the process of constructing the vectors is already a batch job to e.g. embed the user's history. It also won't work well if you have to page through arbitrary amounts of history, as storing more than a few thousand neighbors per query would get impractical. Generally the similarity accuracy degrades to uselessness long before that point though (especially if you're using an approximation technique).
The principle seems very similar: find a simpler representation that preserves distance.
Example: if you crudely crunch MNIST from a [60000 x 784] matrix down to [60000 x 15] matrix (15 is arbitrary here—anything smaller than the original 784 works) using random projection, the JL lemma tells you how badly you mangled the similarity structure of your dataset in the worst case scenario. It turns out it’s not so bad, so we can use DR to compress our data matrix and then confidently do useful things with the vectors it contains (like search for similar ones).
ScaNN is an approximate nearest neighbor (ANN) search algorithm. There is an entire zoo of them, but they all have the same goal: given a query vector q and a data matrix X (where q has the same number of elements as a row vector in X), find the k vectors in X that are “most similar” to q, without exhaustively checking all the possible matches. Most similar could be any similarity or distance measure, but in this case it’s the simple inner product.
To do this more quickly, the algorithm uses a type of vector quantization (i.e. sort the high-D vectors into buckets), which is similar to k-means. K-means can also be construed as a dimensionality reduction technique, you are just reducing to a single dimension. That way you’re only looking in buckets where there’s hope of finding close matches.
This works great in real life with socks—if you’re trying to find a match for a stray black dress sock, then 1) make sure you presort your socks so that they are approximately binned by similarity and 2) look in the bin that contains socks most similar to your “query sock” (i.e. don’t look in the colorful athletic sock or plain white dad-sock bins). I’m not actually kidding, if you have a billion unmatched socks in a box, try this and you’ll see.
Anyways...as for this particular algorithm, someone else may be able to explain the details better. But my coarse understanding is that the loss function (which measures how good the bucketing is—how purely you pre-binned your socks) was defined in such a way that accounts for the density of the region in question—a neighbor in NYC means something different than a neighbor in Wyoming, so you need more granular buckets for denser regions. However, I thought this was essentially how almost every ANN algorithm worked, so how this one blows all the others out of the water (faster for a given recall value) is mystifying to me.
[PS—someone please correct me if any aspect of my loosey goosey explanation is inaccurate]
It's worth noting that without this additional weighting you end up with the euclidean distance under the assumption that q is distributed symmetrically.
Wait, that’s a very arbitrary and general statement. Is this a bot?
(I know (hope, given I’ve read your comments before... :) you’re not, but still, a sign of the times I guess...)
Edit: Looks like it's already there for some datasets. Interestingly it is primarily strong for the glove-100 dataset. I wonder if there are parts of scann that (accidentally) exploit structure specific to word vectors.
Still, We are very far away from creating reverse video search engine. Also, Most of these techniques are in-memory not on disk.
I am really interested in making reverse video search engine.
What are the bottlenecks besides performance?
A decade ago there was some hobby implementations of these algorithms that got cease and desist letters form Shazam and that was all over HN.
It's currently not as fast as the in-memory alternatives. Though it's not a perfect apples/apples comparison. Data is stored on disk, it's a JVM implementation rather than C/C++, and it's optimized for single queries rather than bulk.
https://github.com/elastic/elasticsearch/issues/42326
A different implementation is already in OpenDistro for Elasticsearch:
https://opendistro.github.io/for-elasticsearch-docs/docs/knn...
The Lucene implementation seems early and slow-moving. Seems they are trying to create new storage formats and use graph-based search methods. OpenDistro wrapped a C++ binary that also uses a graph-based method. It works quite well, but only for L2 similarity and comes with the operational burden of running a rather large sidecar process completely disjoint from the JVM.
The approach I've taken is to support five similarity functions (L1, L2, Angular, Jaccard, Hamming), support sparse and dense vectors, implement everything inside the JVM with no sidecar processes and no changes to Lucene, and to use hashing-based search methods (i.e. LSH). IMO the last point has a clear advantage over using graph-based methods, because the hashes are treated just like regular text tokens which is clearly the optimal access pattern in ES/Lucene. Of course it will likely lose to a C++ implementation in terms of raw speed because it's the JVM, but IMO that matters less than making the plugin trivial to run and scale.
I don't think there's a definitively better approach yet. It's an interesting problem and it'll be interesting to see what ends up working well.
[0] https://github.com/yahoo/lopq
[1] https://github.com/cgtuebingen/Product-Quantization-Tree
If you prioritize the bins you search by distance, you are are more likely to find closer points sooner. If you are finding a set number of closest points, then you will have a minimum distance to be included in the point set sooner. If that minimum distance is shorter than the distance to a bin, you can skip it.
It is not only on those benchmarks but is one of the reasons they exist in the first place, since it instigated a lot of the research into approximate nearest neighbors.