Vector Database — References

The index structures behind approximate search, the benchmarks that measure them honestly, and the specific hazard of combining a constraint with a graph traversal.

Index structures

• Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (Malkov & Yashunin, 2016), arXiv:1603.09320 — the graph index behind most production vector search, including the construction and search parameters that set the recall-latency operating point.
• Product Quantization for Nearest Neighbor Search — Hervé Jégou, Matthijs Douze and Cordelia Schmid, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011. The compression scheme behind most memory reduction in vector indexes, and the source of the accuracy loss that has to be re-measured after it is enabled. Cited by name.
• DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node — Suhas Jayaram Subramanya, Fnu Devvrit, Rohan Kadekodi, Ravishankar Krishnaswamy and Harsha Vardhan Simhadri, NeurIPS, 2019. A graph index designed to live on disk, and the basis for most large-corpus, low-memory deployments. Cited by name.
• Billion-scale Similarity Search with GPUs — Jeff Johnson, Matthijs Douze and Hervé Jégou, IEEE Transactions on Big Data, 2021. The FAISS implementation work, and the clearest statement of the trade-offs between exhaustive, partitioned and quantised search. Cited by name.

Measuring approximate search

• ANN-Benchmarks — a standard harness comparing approximate nearest-neighbour implementations on recall against queries-per-second, and the right shape for a recall measurement of your own.
• Big ANN Benchmarks — the billion-scale track, including the filtered-search task that corresponds to constrained retrieval.

Constrained search

• Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters — Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, Amit Singh and Harsha Vardhan Simhadri, The Web Conference, 2023. Why attaching a predicate to a graph search is not a filter applied to its output, and what has to change in the index to make it work. Cited by name.

Implementations worth reading

• FAISS — the reference implementation of most index families, and the practical source for how parameters map onto recall.

No verified reference is recorded for compaction thresholds under delete churn, for alias-based generation swaps, or for selectivity-driven constraint placement. These are operational practice and vary substantially between engines.