annoy
**ANNOY (Approximate Nearest Neighbors Oh Yeah)** is a **C++ library with Python bindings for fast approximate nearest neighbor search** — using random projection trees to build a search index that enables sub-linear query time for high-dimensional vector similarity search, commonly used in recommendation systems, RAG applications, and ML feature retrieval.
**What Is ANNOY?**
- **Definition**: Library for approximate nearest neighbor search using random projection trees.
- **Developer**: Erik Bernhardsson (originally at Spotify).
- **Language**: C++ core with Python bindings.
- **Use Case**: Fast similarity search for embeddings and feature vectors.
**Why ANNOY Matters**
- **Speed**: Query millions of vectors in milliseconds.
- **Memory Efficiency**: Memory-maps index from disk, low RAM usage.
- **Simplicity**: Easy API, minimal configuration.
- **Proven at Scale**: Used in Spotify recommendations for years.
- **Production Ready**: Stable, battle-tested in high-traffic systems.
**How ANNOY Works**
**Random Projection Trees**:
- Build multiple binary trees using random hyperplane splits.
- Each tree partitions space differently.
- Query traverses multiple trees, merges candidates.
**Index Building**:
```
1. Choose random hyperplane (splits space in half)
2. Recursively build subtrees for each half
3. Stop when leaf contains ≤K points
4. Build F trees with different random projections
```
**Querying**:
```
1. Traverse each tree to find leaf containing query
2. Collect candidate points from all tree leaves
3. Compute exact distances for candidates
4. Return top-k nearest neighbors
```
**Trade-offs**:
- More trees → Better accuracy, more memory, slower queries.
- Typical: 10-100 trees for good accuracy/speed balance.
**ANNOY API**
**Building Index**:
```python
from annoy import AnnoyIndex
# Create index for 128-dimensional vectors
index = AnnoyIndex(128, 'angular') # or 'euclidean'
# Add items
for i, vector in enumerate(vectors):
index.add_item(i, vector)
# Build with 50 trees
index.build(50)
index.save('my_index.ann')
```
**Querying**:
```python
# Load index (memory-mapped)
index = AnnoyIndex(128, 'angular')
index.load('my_index.ann')
# Find 10 nearest neighbors to query vector
neighbors = index.get_nns_by_vector(query, 10)
# Or by item index
similar = index.get_nns_by_item(item_id, 10)
```
**ANNOY vs. Other Libraries**
```
Library | Algorithm | Memory | Speed | GPU
---------|---------------|------------|---------|-----
ANNOY | Proj Trees | Low (mmap) | Good | No
FAISS | IVF/HNSW/PQ | High | Fastest | Yes
hnswlib | HNSW | High | Fast | No
ScaNN | Hybrid | Medium | Fast | Yes
```
**When to Use ANNOY**:
- Memory-constrained environments.
- Need to share index across processes (mmap).
- Simple setup preferred over maximum performance.
- Read-heavy, infrequent index updates.
**ANNOY Limitations**
- **No Updates**: Can't add items after building index.
- **No GPU**: CPU-only, no GPU acceleration.
- **Approximate**: May miss true nearest neighbors.
- **Fixed Dimensions**: Dimension set at index creation.
**Use Cases**
- **Recommendations**: Find similar items/users (Spotify's original use).
- **RAG Retrieval**: Find relevant document chunks.
- **Image Search**: Similar image retrieval by embedding.
- **Deduplication**: Find near-duplicate content.
- **Feature Matching**: Match ML feature vectors.
**Production Considerations**
- **Index Size**: ~100 bytes per vector per tree.
- **Build Time**: Minutes to hours for millions of vectors.
- **Query Time**: <1ms for millions of vectors (with good recall).
- **Recall Tuning**: Increase search_k parameter for higher recall.
ANNOY is **the go-to library for memory-efficient approximate nearest neighbor search** — its memory-mapped indexes and simple API make it ideal for applications that need fast similarity search without the complexity of larger systems, proven at scale by years of production use at Spotify.