● Stage 02 • High-Dimensional Algorithms
Vector Index (ANN Search)
Implement an Approximate Nearest Neighbor index for floating-point vectors. Benchmark query throughput and recall against an exhaustive brute-force baseline.
First steps
- Store three points: [1, 0], [3, 4], and [10, 10].
- Calculate each point's Euclidean distance from [0, 0]. The nearest must be [1, 0].
- Extend the search to 128 dimensions. Complete the exact scan before clustering.
Project Goal
- Understand the core indexing mechanics behind modern vector databases.
- Implement metric distance kernels (Cosine, Euclidean) for high-dimensional float arrays.
- Build an Inverted File (IVF) index to replace $O(N)$ linear scans with sub-linear centroid lookups.
- Benchmark the fundamental tradeoff between search accuracy (Recall@K) and latency (QPS).
Skills Acquired
Vector Distance Math (L2 & Cosine)
Bounded Priority Heaps
k-Means Centroid Clustering
Inverted File (IVF) Indexing
SIMD / Loop Autovectorization
Recall@10 Evaluation Curves
Technical Specification
- Dataset: $N=50,000$ vectors with dimension $D=128$ (32-bit floating point).
- Index Parameters: $C=256$ centroids, configurable probe depth $n_{probe} \in [1, 32]$.
- Query API: search(query_vector, k=10, n_probe=8) returning top-$k$ nearest vector IDs.
Milestones
02.1
Vector Distance Kernels & Normalization
Implement L2 distance and Cosine similarity for float arrays. Apply unit normalization ($||u||=1$) so cosine calculations simplify to fast dot products.
02.2
Exact Flat Scan Baseline
Implement linear $k$-NN scan using a bounded max-heap of size $k$. Run 1,000 test queries and save the exact top-10 ground-truth IDs for benchmarking.
02.3
k-Means Clustering & Inverted Lists
Partition the dataset into $C=256$ centroids using Lloyd's algorithm. Group vector IDs and raw floats into 256 inverted posting lists.
02.4
IVF Approximate Query Engine
Given a query vector, find the top-$n_{probe}$ nearest centroids. Search only vectors inside those buckets and return top-$k$ candidates.
02.5
Recall vs. Latency Evaluation
Benchmark 1,000 test queries across probe depths ($1, 2, 4, 8, 16, 32$). Generate a CSV table documenting Recall@10 against query latency.
Verification Commands
These are interfaces for tools you will write, not files supplied with this track. Your generator should save vectors.bin and 1,000 separate queries in queries.bin using a fixed random seed so results are repeatable.
# 1. Generate 50,000 synthetic test vectors
python3 generate_data.py --dim 128 --count 50000
# 2. Run benchmark comparing IVF search to flat scan
./vector_index --mode benchmark --data vectors.bin --queries queries.binAcceptance Criteria
At $n_{probe}=8$, the IVF index must achieve $\ge 90\%$ average Recall@10 across 1,000 test queries while delivering at least a $5\times$ speedup over the flat scan baseline.