HNSW-Optimized: An Optimized Implementation of HNSW for Approximate Nearest Neighbor Search

This repository contains the source code for the course project of "CS20009h.01" at Fudan University. It presents an optimized implementation of the HNSW (Hierarchical Navigable Small World) algorithm for efficient approximate nearest neighbor search. The project explores various optimization techniques at both the algorithmic and engineering levels, achieving significant performance improvements over the baseline implementation.

This work is detailed in the accompanying research paper: "HNSW 近似最近邻搜索算法的优化与实现".

✨ Core Optimizations & Features

This implementation incorporates several advanced optimization strategies at both algorithmic and engineering levels:

Algorithmic Optimizations

• Single-Layer Graph Structure: Replaces the multi-layer navigation with a single-layer graph combined with multi-entry point initialization (NUM_INIT uniformly sampled points), significantly reducing build time (~50% faster) without compromising search performance.
• "Wide Entry, Early Exit" Search Strategy: Implements a dual-gamma pruning mechanism:
  • gamma_candidate: Broadens candidate admission to explore more paths and avoid local optima.
  • gamma_termination: Enables aggressive early termination to reduce unnecessary computations.
  • Result: 20-30% speedup compared to standard HNSW at similar recall levels.
• Neighbor Visit Limit (MAX_NEIGHBORS_CHECK): Limits the number of neighbors explored per node during search, trading minimal recall for significant speed gains.
• Shortcut Edge Reduction: Post-processing step that removes redundant "shortcut" edges after graph construction, improving graph quality and reducing memory usage.
• Original Heuristic Neighbor Selection: Uses the diversity-aware neighbor selection strategy (with configurable ROBUST_PRUNE_ALPHA) for better graph connectivity.

Engineering Optimizations

• SIMD Acceleration: Utilizes AVX/AVX2/SSE instructions for accelerated distance calculations, with runtime CPU feature detection.
• 16-bit Quantization: Linear quantization of float32 to int16, reducing memory footprint by 50% and improving cache efficiency with <0.5% recall impact.
• Batch-4 Distance Computation (USE_BATCH4): Processes 4 distance calculations at once to maximize instruction-level parallelism and reduce priority queue access overhead.
• Cache-Friendly Memory Layout:
  • RCM Reordering (USE_RCM): Applies Reverse Cuthill-McKee algorithm to reorder nodes such that graph-adjacent nodes are memory-adjacent, improving spatial locality.
  • 64-byte Aligned Memory: Aligns data structures to cache line boundaries.
• Software Prefetching (PREFETCH_WINDOW): Manually inserts _mm_prefetch instructions to preload neighbor data into L1 cache before access.
• Graph Caching (USE_CACHE): Automatically saves/loads constructed graphs to disk to avoid repeated builds with identical parameters.

🚀 Performance Highlights

Our optimizations lead to substantial performance gains. For instance, on the SIFT-1M dataset, our final optimized version (Baseline3) achieves a build time of ~150s while maintaining over 99% recall, compared to the baseline's ~800s.

Below are performance comparisons showing the effect of gamma pruning on recall and search time:

For detailed performance analysis and ablation studies, please refer to the research paper.

🔧 Getting Started

Prerequisites

• A C++ compiler that supports C++17 (e.g., g++ 9 or later).
• A CPU with AVX2 support is highly recommended for best performance.
• CMake (optional, but recommended for easier building).

Build Instructions

You can compile the project directly using the command from the paper:

# Make sure you are in the project root directory
mkdir -p build && cd build
g++ -O3 -Wall -march=native -mavx2 -mfma -std=c++17 -fopenmp ../src/main.cpp ../src/MySolution.cpp -o main -I../include/

Data Preparation

This project's evaluation scripts require a specific directory structure for datasets, which you should create manually:

.
├── data_o/
│   ├── sift/
│   │   ├── base.txt       <- To be generated
│   │   └── query.txt
│   └── glove/
│       ├── base.txt       <- To be generated
│       └── query.txt
└── ground_truth/
    ├── sift_ground_truth.txt
    └── glove_ground_truth.txt

The base.txt files, containing the large vector datasets, are not included in this repository.

To download the original datasets and generate the required base.txt files, simply run the following script from the project's root directory:

bash ./data/prepare_data.sh

This script will automatically:

1. Download the SIFT1M and GloVe datasets.
2. Convert them into the required base.txt format.
3. Place the generated files directly into data_o/sift/ and data_o/glove/.

Note: You must provide your own query.txt and ground_truth.txt files for evaluation. For standard benchmarks, these can be obtained from the same sources as the base datasets.

📁 Project Structure

hnsw-optimized/
├── src/
│   ├── MySolution.cpp       # Main HNSW implementation with all optimizations
│   ├── MySolution.h         # Header file
│   └── main.cpp             # Entry point for benchmarking
├── include/                 # Header files
├── scripts/
│   └── run_experiments.sh   # Automated ablation study runner
├── data/
│   └── prepare_data.sh      # Dataset download and preparation script
├── data_o/                  # Generated dataset directory (created by prepare_data.sh)
│   ├── sift/
│   │   ├── base.txt
│   │   └── query.txt
│   └── glove/
│       ├── base.txt
│       └── query.txt
├── ground_truth/            # Ground truth files for evaluation
│   ├── sift_ground_truth.txt
│   └── glove_ground_truth.txt
├── docs/
│   └── HNSW_Optimization_Report.pdf  # Research paper
├── experiments/             # Experimental results and logs (created by run_experiments.sh)
│   ├── ablation_results_*.csv
│   └── logs_*/
└── README.md

🔬 Running Experiments

The scripts/run_experiments.sh script is provided to automate the process of running tests and ablation studies.

Basic Usage:

# Run the experiment for the SIFT dataset
./scripts/run_experiments.sh sift

The script is highly configurable. You can edit the script to change parameters for ablation studies, such as MAX_NEIGHBORS_CHECK_LIST, ROBUST_PRUNE_ALPHA_LIST, etc.

🎯 Key Parameters Tuning Guide

Based on extensive ablation studies on SIFT-1M and GloVe datasets, here are the recommended parameter settings for different scenarios:

Recommended Settings

For Best Overall Performance (Baseline3)

Achieves ~99% recall with optimal speed on both SIFT and GloVe datasets:

EF_CONSTRUCTION=256
MMAX0=256
USE_QUANTIZATION=1
SELECT_HEURISTIC=0
USE_BIDIR_LINKS=1
USE_SHORTCUTS=1
USE_RCM=1
EF_SEARCH=10
USE_GAMMA=1
GAMMA_TERMINATION=0.19
GAMMA_CANDIDATE=0.19
NUM_INIT=25
MAX_NEIGHBORS_CHECK=256  # or 96 for SIFT, 176 for GloVe
PREFETCH_WINDOW=10
USE_BATCH4=1

For Maximum Recall (>99.5%)

Prioritizes accuracy over speed:

EF_SEARCH=20
GAMMA_TERMINATION=0.25
GAMMA_CANDIDATE=0.25
MAX_NEIGHBORS_CHECK=256
NUM_INIT=50

For Maximum Speed

Fastest search with acceptable recall (~97-98%):

EF_SEARCH=10
GAMMA_TERMINATION=0.10
GAMMA_CANDIDATE=0.10
MAX_NEIGHBORS_CHECK=64
NUM_INIT=10

Parameter Impact Summary

Based on ablation studies (see Section 2.2 of the paper):

Most Impactful Parameters:

1. GAMMA_TERMINATION & GAMMA_CANDIDATE (0.18-0.19 optimal): The "wide entry, early exit" strategy provides 20-30% speedup compared to standard HNSW while maintaining similar recall.
2. EF_SEARCH: Standard parameter; increasing provides diminishing returns compared to gamma tuning.
3. MAX_NEIGHBORS_CHECK: Dataset-dependent; SIFT benefits from ~96, GloVe from ~176.

Build Optimization:

• Single-layer graph (NUM_INIT=25): Reduces build time by ~50% vs multi-layer HNSW with no performance loss.
• Quantization (USE_QUANTIZATION=1): Reduces build time by ~60% with <0.5% recall impact.
• SELECT_HEURISTIC=0 (Original heuristic): Best performance for both datasets at α=1.0.

Engineering Optimizations:

• USE_BATCH4=1: ~10-15% speedup from better instruction pipelining.
• PREFETCH_WINDOW=10: Optimal cache prefetch window size.
• USE_RCM=1 & USE_SHORTCUTS=1: Minimal impact; may help in specific scenarios.

Dataset-Specific Notes

SIFT-1M (128-dim):

• Lower-dimensional; benefits from smaller MAX_NEIGHBORS_CHECK (~96).
• Faster overall; can use more aggressive gamma values for speed.

GloVe-1.2M (100-dim):

• Requires higher MAX_NEIGHBORS_CHECK (~176) for good recall.
• More sensitive to NUM_INIT; keep at 25 or higher.

Environment Variables

The behavior of the algorithm can be controlled via the following environment variables:

Build-time Parameters (Affect Graph Structure)

Variable	Description	Default	Valid Range
EF_CONSTRUCTION	Beam width during graph construction. Higher = better quality but slower.	256	1-1000
MMAX0	Max number of neighbors for a node in layer 0. Higher = more connections.	256	16-512
USE_QUANTIZATION	Enable int16 quantization. 1 = enabled, 0 = float32.	1	0 or 1
SELECT_HEURISTIC	Neighbor selection strategy: 0 = Original heuristic, 1 = Simple greedy, 2 = Robust prune.	0	0, 1, or 2
ROBUST_PRUNE_ALPHA	Alpha parameter for Robust Prune heuristic (only effective when SELECT_HEURISTIC=2).	1.0	0.5-2.0
USE_BIDIR_LINKS	Enable bidirectional linking during construction.	1	0 or 1
USE_SHORTCUTS	Enable shortcut edge reduction post-processing.	1	0 or 1
USE_RCM	Enable RCM (Reverse Cuthill-McKee) memory reordering for cache optimization.	1	0 or 1
USE_CROUTING	Enable CRouting optimization for angle-based pruning.	0	0 or 1
CROUTING_ANGLE	Cosine percentile for CRouting (0-100, where 90 ≈ 90th percentile).	90	0-100
USE_CACHE	Enable graph caching to disk to speed up repeated builds.	1	0 or 1

Search-time Parameters (Do Not Affect Graph Structure)

Variable	Description	Default	Valid Range
EF_SEARCH	Beam width during search. Higher = better recall but slower.	10	1-500
USE_GAMMA	Enable gamma pruning for "wide entry, early exit" strategy.	1	0 or 1
GAMMA_TERMINATION	Gamma for early termination. Allows stopping when dist > (1+γ)*best.	0.19	0.0-0.5
GAMMA_CANDIDATE	Gamma for candidate admission. Allows adding candidates slightly worse than current best.	0.19	0.0-0.5
NUM_INIT	Number of uniformly sampled initial entry points for search (replaces multi-layer navigation).	25	1-100
MAX_NEIGHBORS_CHECK	Maximum number of neighbors to check per node. 256 = no limit.	256	16-256
STABLE_COUNT	Enable early exit when result set is stable for N iterations. 0 = disabled.	0	0-50
SORT_NEIGHBORS	Sort neighbor lists: 0 = no sort, 1 = ascending distance, 2 = descending.	0	0, 1, or 2
PREFETCH_WINDOW	Number of neighbors to prefetch ahead during search.	10	4-20
GAMMA_PHASE2	Gamma value for second phase (if two-phase search is enabled).	0.19	0.0-0.5
PHASE2_THRESHOLD	Distance computation threshold to trigger phase 2. 0 = single-phase only.	0	0-10000
ADAPTIVE_NEIGHBORS	Reduce neighbor checks in phase 2 adaptively.	0	0 or 1
USE_BATCH4	Enable batch-4 distance computation for better instruction pipelining.	1	0 or 1

Usage Examples

Basic Usage

Run with default optimized settings (Baseline3 from the paper):

./build/main sift

Custom Search Parameters

Run a search on SIFT with higher beam width and disabled quantization:

export EF_SEARCH=50
export USE_QUANTIZATION=0
./build/main sift

Tuning for Higher Recall

To achieve higher recall at the cost of search time:

export EF_SEARCH=20
export GAMMA_TERMINATION=0.25
export GAMMA_CANDIDATE=0.25
export NUM_INIT=50
./build/main glove

Tuning for Faster Search

To achieve faster search with slightly lower recall:

export EF_SEARCH=10
export GAMMA_TERMINATION=0.15
export MAX_NEIGHBORS_CHECK=96
export PREFETCH_WINDOW=10
./build/main sift

Building with Different Graph Structure

Change the graph connectivity during build (requires cache rebuild):

export MMAX0=128
export EF_CONSTRUCTION=200
export SELECT_HEURISTIC=2
export ROBUST_PRUNE_ALPHA=1.05
export USE_CACHE=0  # Force rebuild
./build/main sift

Running Ablation Studies

The scripts/run_experiments.sh script supports environment variable overrides:

# Test different MAX_NEIGHBORS_CHECK values
export MAX_NEIGHBORS_CHECK_LIST="64 96 128 160 192 224 256"
./scripts/run_experiments.sh sift

# Test gamma pruning parameters
export GAMMA_TERMINATION_LIST="0.0 0.05 0.10 0.15 0.19 0.25"
export GAMMA_CANDIDATE_LIST="0.0 0.05 0.10 0.15 0.19 0.25"
./scripts/run_experiments.sh sift

📚 Citation

If you use this work in your research, please cite:

@article{hnsw-optimization-2026,
  title={HNSW 近似最近邻搜索算法的优化与实现},
  author={[Your Name]},
  journal={Fudan University Course Project},
  year={2026},
  course={CS20009h.01}
}

📜 License

This project is licensed under the MIT License.

🙏 Acknowledgements

• Yu. A. Malkov and D. A. Yashunin: For the original HNSW algorithm and paper: "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs" (TPAMI 2018).
• nmslib/hnswlib: The official C++ implementation, which served as a foundational reference and inspiration for this work.
• Fudan University CS20009h.01: For the course framework and guidance.
• The SIFT and GloVe dataset creators for providing standard benchmarks for nearest neighbor search evaluation.

📧 Contact

For questions, issues, or suggestions, please open an issue on the GitHub repository or contact the author.

---

Note: This is an academic project completed as part of coursework at Fudan University. The implementation prioritizes educational value and performance optimization exploration over production-ready robustness.