ANN indexes

Exact nearest-neighbor search over millions of high-dimensional vectors is too slow; approximate nearest neighbor (ANN) indexes trade perfect recall for sub-linear query time. Popular structures: HNSW (graph navigable small world), IVF (inverted file with coarse clusters), product quantization for compressed vectors.

| Index | Idea | Knob | |-------|------|------| | HNSW | Greedy graph walk | `efConstruction`, `M` | | IVF | Search top clusters only | `nlist`, `nprobe` | | PQ | Compress vectors | recall vs memory |

Higher `ef` or `nprobe` improves recall at higher latency. Indexes are built offline or incrementally; updates may require rebuild or tolerate stale graph edges.

On interviews: articulate the recall–latency–memory triangle; explain why brute force breaks at scale; mention index build time and update semantics for your chosen engine.

Common pitfalls: default ANN params without benchmarking; building index on unnormalized vectors; expecting instant updates on huge HNSW graphs; comparing engines on different recall levels; no periodic rebuild after heavy deletes.

The trade-off is query speed and RAM footprint versus tunable recall loss and operational complexity of index maintenance.

Checklist:

• Define ANN vs exact k-NN.
• Name HNSW and IVF at a high level.
• Explain recall/latency tuning parameters.
• Describe build, update, and rebuild cadence.
• Benchmark with representative query load.