Problem
Given a collection of vectors and a query vector, a team has to return the most similar vectors quickly. Exact kNN always finds the true nearest vector, but its cost per query is unacceptable once the collection is large. This is the situation in image search over billions of pictures or music recommendations over millions of tracks, where a query must be compared with everything stored. Approximate algorithms trade a little accuracy for speed, and the choice of algorithm and parameters decides both.
Example from the article: a workshop on the MovieLens dataset, using only the movie title column, where similar movies are found by title with three approaches: Annoy, LSH and Faiss.
Solution in brief
Replace exact search with an approximate index. Annoy splits the space with random hyperplanes into a tree. LSH compresses vectors into short signatures and compares them by bands. Faiss offers LSH, IVF (cluster-first search) and product quantization behind one interface. Check each index against exact search and pick the cheapest one that is accurate enough.
Questions this case answers
- How to retrieve the nearest vectors to a query from a collection too large for exact search while keeping answers fast and acceptably accurate
- How to pick and tune an approximate nearest-neighbor index when build time, memory and recall pull in different directions
- How to find the most similar items to a query vector when exact kNN is too slow on a large collection?
- How to choose between Annoy, LSH and Faiss indexes for similarity search?
Tools and methods
- Annoy (via Gensim) — tree of random hyperplanes; one parameter, the number of trees
- Locality-sensitive hashing (MinHash + banding) — short similarity-preserving signatures and candidate pairs
- Faiss — library with LSH, IVF and product quantization indexes, CPU and GPU builds
- Word2Vec — vectors for movie titles
- NLTK Porter stemmer — title preprocessing
Google or a one-time email code. No password.
