References

1. Yu. A. Malkov, D. A. Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE TPAMI, 2018. arXiv:1603.09320. The HNSW paper.

2. Yu. Malkov, A. Ponomarenko, A. Logvinov, V. Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 2014. The flat NSW predecessor HNSW builds on.

3. William Pugh. Skip Lists: A Probabilistic Alternative to Balanced Trees. CACM, 1990. The layered probabilistic structure HNSW borrows for its hierarchy.

4. Jon Kleinberg. Navigation in a small world. Nature, 2000. Why greedy routing succeeds on the right graphs.

5. Y. Koren, R. Bell, C. Volinsky. Matrix Factorization Techniques for Recommender Systems. IEEE Computer, 2009. The user/item embedding model behind the recommendation use case.

Related tools & systems

• FAISS (Meta), IndexHNSWFlat and many other ANN indexes.
• hnswlib: the authors' compact C++/Python HNSW library.
• Apache Lucene / OpenSearch / Elasticsearch: native HNSW vector search.
• Vector databases: Qdrant, Weaviate, Milvus, Pinecone (HNSW-based indexes).

Related ideas

• MIPS (Maximum Inner Product Search): the recommendation ranking problem; reduces to nearest-neighbor search via normalization or an extra coordinate.
• IVF-PQ / product quantization: memory-efficient ANN, often combined with graph indexes.

This book's code

• code/hnsw.py, the full from-scratch index.
• code/demo.py, recall vs. efficiency measurement.
• code/hnsw_search.py, the semantic-search CLI.

All depend only on NumPy and the standard library.