What is the taxonomy of ANN methods?
The taxonomy of ANN methods is a map of approximate nearest-neighbor techniques grouped by how they generate candidates – graphs, trees, hashes, partitions, compression-centric codes, flat exact scan, and hybrids – so you can compare algorithms by mechanism instead of by product name.
Why organize ANN algorithms into families at all?
Every serious vector search system eventually faces the same trade: exact brute-force search is correct and slow at scale, so indexes approximate which vectors to score. Those approximations are not interchangeable knobs on one machine; they are different bets about geometry and data structures. A taxonomy makes the bets explicit. When someone says “we use ANN,” the useful follow-up is whether candidates come from neighbor links, spatial partitions, hash collisions, cluster lists, or compressed code tables – because failure modes, update costs, and tuning knobs follow the family. Vector databases such as Weaviate describe several index types with this kind of vocabulary (graph, flat, and related designs) even when one family is the production default.
The major branches of that map are easiest to remember by their candidate generator.
What are the primary branches of the ANN taxonomy?
Graph-based methods (HNSW and related navigable graphs) store explicit neighbor edges and walk them with a beam. Tree-based methods (k-d trees, ball trees, VP-trees, R-trees, random projection forests) recursively partition space and prune regions. Hashing-based ANN (LSH and kin) puts similar points in shared buckets and probes collisions. Partition-based ANN (IVF and cluster-based candidate reduction) opens posting lists of nearby coarse cells. Compression-centric indexes (product-quantization indexes and aggressive code tables) make compact codes the primary stored form, often behind partitions. Flat exact search is the zero-approximation leaf of the taxonomy: every vector is a candidate. Hybrid ANN indexes deliberately stack two or more branches – IVF+PQ, HNSW+quantization, coarse routing into many small graphs – so one stage reduces candidates and another ranks or compresses.
Families still share evaluation language even when their internals differ.
What axes cut across every family when you choose or benchmark?
Recall versus latency is universal: how much of the exact top-k you recover at what delay. Memory footprint separates graph-heavy in-RAM designs from list-and-code designs. Build cost and mutability separate incremental graphs from batch-trained codebooks and immutable forests. Dimensionality sensitivity separates low-dimensional trees from methods that survive embedding-scale dimensions. Filter friendliness and distributed sharding add operational axes on top of pure ANN math. An exact brute-force baseline anchors recall; without it, taxonomy debates become marketing. Two-stage retrieval (approximate candidates, then finer scores) appears inside many families once compression enters.
Knowing the map is not the same as picking a point on it for your workload.
How should you use the taxonomy when selecting an index?
Start from constraints: dataset size, dimension, QPS, p99, RAM, update rate, and whether you need exactness for tiny sets. Prefer graph methods when large dense embeddings need high recall at low latency with ongoing inserts – the reason HNSW dominates much of this site and many production stores. Prefer partitions and PQ-centric stacks when memory per vector dominates and batch reclustering is acceptable. Prefer hashing for threshold-shaped similarities and sketch pipelines. Prefer trees when dimensionality is modest and geometric pruning still works. Prefer flat exact when N is small enough that ANN overhead buys nothing. Prefer hybrids when measurements show a single family failing one axis. Then read the glossary pages for that branch in depth rather than collecting algorithm names.
The taxonomy of ANN methods classifies approximate search by candidate-generation mechanism so comparisons stay structural. From here, composite and two-level index structures zoom into multi-layer designs, the trade-off in choosing an ANN index turns the map into a decision guide, graph-focused chapters elsewhere develop HNSW in depth, and the exact brute-force baseline remains the measuring stick for every branch.