Explore graph-based algorithms for approximate nearest neighbor search in this 59-minute workshop led by HNSW author Yury Malkov and Pinecone's James Briggs. Gain a comprehensive understanding of vector search techniques, from exhaustive to approximate methods, with a focus on graph algorithms and their advantages. Delve into Delaunay graphs, Voronoi diagrams, and relative neighborhood graphs before examining HNSW construction and its extensions. Learn about memory-constrained scenarios, coarse quantization, and disk-based approaches. Discover update and deletion strategies, benchmark with SQUAD and MSMARCO datasets, and receive practical advice for implementing these techniques in real-world applications.
Overview
Syllabus
Intro
Vector Search
Exhaustive Search
Approximate Search
Many ANNS Algorithms
Graph algorithms
Advantages of graph algorithm
Delaunay graphs and Voronoi diagrams
Problems with Delaunay graphs
Delaunay Graph Subgraphs
Relative neighborhood graph (RNG)
Skip-lists analogy
HNSW construction
Extension to memory-constrained scenarios
Using graphs a coarse quantizer (ivf-hnsw)
DiskANN
SPANN and HNSW-IF
Updates and deletions.
Benchmarking SQUAD
Benchmarking MSMARCO
Practical advice
Taught by
Pinecone
