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**
```python
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.