HNSW
HNSW
Hierarchical Navigable Small World (HNSW) is a graph-based data structure for Approximate Nearest Neighbor (ANN) search. It builds a multi-layered hierarchy of proximity graphs. The top layer has long-range links for fast global routing, while the bottom layer has short-range links for local accuracy.
Complexity Profile
| Case | Complexity |
|---|---|
| Best Case | O(log N) |
| Average Case | O(log N) |
| Worst Case | O(N) |
| Space Complexity | O(N * D + M * N) |
Code Implementation
# Conceptual traversal of HNSW layers
def search_hnsw(query, index, k):
enter_point = index.enter_node
# Traverse from top layer down to bottom layer
for layer in reversed(range(index.num_layers)):
enter_point = search_layer(query, enter_point, ef=1, layer=layer)
# Get top-k nearest neighbors on bottom layer
nearest_neighbors = search_layer(query, enter_point, ef=index.ef_search, layer=0)
return nearest_neighbors[:k]Real-World Applications
- High-performance vector databases (Milvus, Pinecone, Qdrant).
- Million-scale semantic search systems requiring sub-50ms latencies.
- Large-scale recommendation system index engines.
BM25
BM25 (Best Matching 25) is a ranking function used by search engines to estimate the relevance of documents to a search query. It enhances basic TF-IDF by incorporating document length normalization ($b$) and term frequency saturation ($k_1$), preventing document lengths from biasing similarity scores.
Hybrid Search
Hybrid Search combines sparse lexical retrieval (BM25) and dense semantic retrieval (Vector Search) to provide optimal query relevance. It executes both keyword matching and vector similarity lookups in parallel, and merges the resulting rank lists using Reciprocal Rank Fusion (RRF) to leverage the strengths of both retrieval styles.