HNSW (Hierarchical Navigable Small World) is a graph-based approximate nearest neighbor (ANN) index that builds a multi-layer structure—similar to skip lists—enabling logarithmic search complexity (O(log N)). It achieves fast approximate search by trading a small amount of recall for dramatically higher throughput, automatically handling new data without rebuilding.
HNSW (Hierarchical Navigable Small World) is a graph-based ANN algorithm that combines skip list concepts with navigable small world graphs to achieve logarithmic search complexity[reference:47]. It builds a multilayer graph where each layer serves as a "highway" for navigation. Queries traverse from the top layer down to the bottom, where exact nearest neighbors are refined. The m parameter (max connections per node) and ef_construction (candidate list size) trade off build time vs. recall; ef_search (search candidate list) trades query time vs. recall[reference:48].
HNSW: Recommended default, better query performance, handles new data without rebuilding, higher memory usage, longer build time[reference:49]
IVFFlat: Shorter build time, lower memory usage, requires existing data for training, lower speed-recall tradeoff, requires rebuild for best recall after data additions[reference:50]
HNSW builds a multi-layer graph structure; can be created on empty tables and supports dynamic data additions[reference:51]
IVFFlat (Inverted File with Flat Compression) partitions vectors into lists; faster build but lower recall, suitable when build time or memory is constrained
Recall vs. speed: In HNSW,
ef_searchcontrols candidates kept during search; larger values increase recall at query cost[reference:52]