English | Français

ANN Comparative Method

A side-by-side benchmark of three approximate nearest neighbor methods (HNSW, IVF-PQ and LSH) on the one million vectors of SIFT1M, built with FAISS.

Exact search compares a query with every vector in the base, which gets slow at a million vectors. Approximate methods trade some accuracy for speed and memory. This project measures that trade-off with the same protocol for each method: build the index, run the SIFT1M queries, and score Recall@10 against the exact neighbors, along with latency, build time and memory. A fourth notebook tests what a PCA reduction from 128 to 32 dimensions does to all three.

Results · How it works · Getting started · Project structure

---

Results

Measured on SIFT1M (1,000,000 base vectors, 128 dimensions, K = 10, FAISS on CPU), from the outputs saved in the notebooks.

Method	Setting	Recall@10	Latency (ms/query)	Build time	Memory
HNSW (M=32)	efSearch = 10	0.808	0.065	76 s	747 MB
HNSW (M=32)	efSearch = 50	0.971	0.111
HNSW (M=32)	efSearch = 100	0.992	0.177
HNSW (M=32)	efSearch = 400	0.999	0.537
IVF-PQ (nlist=1024, m=8)	nprobe = 1	0.236	0.002	4.7 s	8.1 MB
IVF-PQ (nlist=1024, m=8)	nprobe = 10	0.366	0.006
IVF-PQ (nlist=1024, m=8)	nprobe = 100	0.376	0.041

• HNSW reaches 0.99 Recall@10 at efSearch = 100. efSearch is set at query time, so the same index serves fast or precise searches without being rebuilt. Raising M from 16 to 64 lifts Recall@10 from 0.967 to 0.993 but almost triples the build time (41 s to 114 s).
• IVF-PQ keeps the whole index in about 8 MB, because product quantization stores each vector in 8 bytes instead of 512. Its recall stops at about 0.376: beyond nprobe = 20, visiting more cells adds latency for almost no recall, since most of the error now comes from the compressed codes.
• LSH has no SIFT1M numbers yet. The committed run of lsh_benchmark.ipynb did not find the data files and fell back to 10,000 random vectors, so its outputs are not reported here. The PCA notebook is committed without outputs.

The HNSW figures use the first 100 queries and the IVF-PQ figures all 10,000. The two notebooks ran on different machines (FAISS 1.13.2 and 1.13.0), and latency is the time of one batched search divided by the number of queries. Compare latencies within a method rather than across methods. Memory is the growth of the process memory for HNSW and an estimate of the index size for IVF-PQ.

---

How it works

flowchart TD
    DL["download_data.py"] --> DS[("SIFT1M: 1M vectors, 10k queries<br/>and their exact neighbors")]
    DS --> NB
    subgraph NB["benchmark/*.ipynb"]
        direction TB
        H["HNSW<br/>M, efSearch"]
        I["IVF-PQ<br/>nprobe, nlist"]
        L["LSH<br/>nbits"]
        P["PCA<br/>128 to 32 dims"]
    end
    NB --> M{{"Recall@10, latency<br/>build time, memory"}}
    M --> R[("benchmark/results/")]

Loading

1. download_data.py fetches sift.tar.gz from the TEXMEX corpus and extracts the four .fvecs / .ivecs files into benchmark/data/.
2. Each method has its own notebook, and the notebooks are independent. They load the data with the same load_fvecs / load_ivecs readers and score results against the ground truth shipped with SIFT1M.
3. Each notebook sweeps its main hyperparameters: M and efSearch for HNSW, nprobe and nlist for IVF-PQ, nbits from 32 to 1024 for LSH.
4. pca_benchmark.ipynb fits a PCA (128 to 32 dimensions) and runs HNSW, LSH and IVF-PQ with and without it at fixed settings.
5. Tables and charts are written to benchmark/results/, which git ignores.

---

Getting started

You need Python 3 and about 1 GB of free disk space for the dataset.

git clone https://github.com/Yvngval/Project-ANN-Comparative-Method.git
cd Project-ANN-Comparative-Method/benchmark
python -m venv .venv && source .venv/bin/activate
pip install faiss-cpu scikit-learn numpy matplotlib seaborn psutil pandas jupyterlab
python download_data.py
jupyter lab

If the FTP download fails, get sift.tar.gz from the TEXMEX corpus page and put sift_base.fvecs, sift_query.fvecs, sift_groundtruth.ivecs and sift_learn.fvecs in benchmark/data/. Then open any notebook and run all cells. The notebooks expect to be started from the benchmark/ folder, since they read ./data/.

---

Project structure

benchmark/
├── data/                    SIFT1M files, filled by download_data.py
├── results/                 CSV and PNG written by the notebooks
├── download_data.py         downloads and extracts SIFT1M
├── hnsw_benchmark.ipynb     HNSW: M and efSearch
├── ivfpq_benchmark.ipynb    IVF-PQ: nprobe and nlist
├── lsh_benchmark.ipynb      LSH: nbits
└── pca_benchmark.ipynb      PCA 128 to 32 applied to the three methods
docs/assets/                 figures used in this README

---

Contributing

Issues and pull requests are welcome. See CONTRIBUTING.md.

License

The code is released under the MIT License. SIFT1M comes from the TEXMEX corpus (Jégou, Douze and Schmid, "Product quantization for nearest neighbor search", IEEE TPAMI, 2011) and is not redistributed here.

Authors

Valentin Ponnoussamy (@Yvngval), @chatodit and @SedikRummenigge, 2026.