Vector Databases and ANN Indexes (HNSW, IVF-PQ) TODO
Concept
Vector search means finding items close to a query vector in embedding space; in high dimensions, exact nearest-neighbor search effectively degrades into brute-force comparison, so approximate nearest neighbor (ANN) search is used instead. An ANN index's quality is judged on the tradeoff curve between recall (accuracy) and latency/memory, and no index escapes that curve for free. HNSW builds a hierarchical proximity graph, greedily jumping far via sparse links at the top layers and refining the search at lower layers, with a search-width parameter that trades off recall against speed. IVF-PQ first partitions the vector space into clusters so a query only scans a handful of nearby lists, then compresses vectors into per-subspace codebook indices to cut memory sharply while comparing with approximate distances. Broadly, HNSW uses more memory and gives lower latency, while IVF-PQ is more memory-efficient at large scale.
The perceived quality of RAG or similar-item recommendations is usually decided by the retriever's recall, not the generation model, so if you don't understand how index parameters affect accuracy, you'll end up looking for the cause in the wrong place.
Code & Formula
# 벡터 DB와 ANN 인덱스 — 소규모 벡터 집합에 대한 브루트포스 최근접 탐색을 베이스라인으로 구현.
# 실제 HNSW/IVF-PQ 는 이 exact 결과를 근사(recall<1.0)로 더 빠르게 흉내내는 것이 목표다.
import numpy as np
rng = np.random.default_rng(42)
DIM, N = 8, 200
vectors = rng.normal(size=(N, DIM)).astype("float32")
ids = [f"doc-{i}" for i in range(N)]
def cosine_distance(a, b):
a_n = a / np.linalg.norm(a)
b_n = b / (np.linalg.norm(b, axis=1, keepdims=True) + 1e-9)
return 1.0 - b_n @ a_n
def brute_force_knn(query, k=5):
dists = cosine_distance(query, vectors) # 전수 비교: O(N*DIM)
top_k = np.argsort(dists)[:k]
return [(ids[i], float(dists[i])) for i in top_k]
query = vectors[7] + rng.normal(scale=0.05, size=DIM).astype("float32") # doc-7 근처 질의
result = brute_force_knn(query, k=5)
print("query is a noisy copy of doc-7")
print("brute-force top-5 nearest neighbors (id, cosine distance):")
for doc_id, dist in result:
print(f" {doc_id}: {dist:.4f}")
print("exact search cost: O(N * DIM) per query — ANN indexes trade this for recall < 1.0")
docs/code/algorithms/algorithms-78.py
Exercise
Build tens of thousands of embeddings, treat brute-force results as ground truth, then vary HNSW's search-width parameter and plot the recall@10 vs. query-latency tradeoff curve.
Practical Connection
Vector search on on-chain data itself is rare, but it applies directly to text assets at the service layer — deduplicating market descriptions, recommending similar markets, or searching past dispute cases.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.