Annoy — Approximate Nearest Neighbors by Spotify

Introduction

Annoy (Approximate Nearest Neighbors Oh Yeah) is a C++ library with Python bindings created at Spotify for searching nearest neighbors in high-dimensional vector spaces. It builds a forest of random projection trees that can be memory-mapped from disk, enabling multiple processes to share the same index without duplicating memory.

What Annoy Does

• Builds read-only indexes for approximate nearest neighbor search across millions of vectors
• Supports angular, Euclidean, Manhattan, Hamming, and dot-product distance metrics
• Memory-maps index files so multiple processes share one copy in RAM
• Creates static indexes that can be loaded instantly from disk without rebuilding
• Provides both Python and C++ APIs for integration into production systems

Architecture Overview

Annoy constructs a forest of binary trees using random hyperplane splits. At build time, it recursively partitions the vector space by choosing two random points and splitting along their perpendicular bisector. At query time, it searches multiple trees in parallel and merges candidate lists before ranking by exact distance. More trees improve recall at the cost of memory and build time. The index is stored as a single flat file that can be memory-mapped, making it efficient for serving from disk.

Self-Hosting & Configuration

• Install via pip; pre-built wheels available for major platforms
• Build the index once with build(n_trees) and save to disk with save()
• Load saved indexes with load() using mmap mode for shared memory across processes
• Tune n_trees (build time) and search_k (query time) to balance recall vs speed
• Index files are portable across machines with the same architecture and endianness

Key Features

• Memory-mapped indexes allow multiple processes to share a single index in RAM
• Compact on-disk format with low memory overhead per vector
• Decoupled build and query phases: build once, serve forever
• No external dependencies beyond a C++ compiler for building from source
• Battle-tested at Spotify for music recommendation across hundreds of millions of tracks

Comparison with Similar Tools

• FAISS — more algorithms and GPU support; Annoy is simpler and excels at memory-mapped read-only serving
• Milvus — full vector database with CRUD and filtering; Annoy is a lightweight library without server overhead
• ScaNN — Google's optimized ANN library; Annoy trades peak throughput for simpler deployment
• HNSWlib — higher recall at similar speed; Annoy's memory-mapped indexes are better for multi-process sharing
• Qdrant — managed vector search with rich APIs; Annoy is embedded and needs no separate service

FAQ

Q: Can I add items to an existing Annoy index? A: No. Annoy indexes are immutable after building. To add new items, rebuild the index. For dynamic indexes, consider FAISS or HNSWlib.

Q: How many vectors can Annoy handle? A: Annoy has been used with tens of millions of vectors at Spotify. The main constraint is disk space for the index file and RAM for the memory-mapped pages accessed during queries.

Q: Does Annoy support GPU acceleration? A: No. Annoy is CPU-only. For GPU-accelerated ANN search, use FAISS.

Q: What is the right number of trees? A: More trees improve recall but increase index size and build time. Start with 10-50 trees and benchmark recall on a held-out set to find the right trade-off for your use case.

Sources

• https://github.com/spotify/annoy
• https://erikbern.com/annoy