Annoy

Annoy: Approximate Nearest Neighbors Oh Yeah

Overview
Annoy is a C++ library (with Python bindings) developed by Spotify for music recommendations. It performs Approximate Nearest Neighbor (ANN) search.

Use Case at Spotify
"Find 50 songs similar to 'Bohemian Rhapsody' out of 50 million tracks."
Exact search takes too long. Annoy finds "good enough" matches in milliseconds.

How it works (Random Projections)
Annoy builds a forest of trees.
1. Pick two random points.
2. Split the space with a hyperplane between them.
3. Repeat recursively until each leaf node has few points.
4. To search, traverse the trees to find candidate points.

Key Features
- Memory Mapped: The index is stored as a file on disk (`mmap`). This allows multiple processes to share the same memory (crucial for Python multiprocessing).
- Read-Only: Once built, the index cannot be modified. You cannot add new vectors; you must rebuild.

Usage

from annoy import AnnoyIndex

f = 40  # Vector length
t = AnnoyIndex(f, 'angular')
t.add_item(0, [0.1, 0.2, ...])
t.build(10) # 10 trees
t.save('test.ann')

# Search
print(t.get_nns_by_item(0, 5))

Status
Annoy is older tech (2014). Modern libraries like FAISS (HNSW) or ScaNN generally offer better speed/accuracy trade-offs, but Annoy remains popular for its simplicity and low memory usage.