Nearest Neighbor Search

Project Overview

This project implements an Approximate Nearest Neighbor (ANN) search algorithm based on a single-layer HNSW-style graph, for quickly finding K nearest neighbors in high-dimensional vector spaces. The core implementations include graph construction, ONNG edge optimization, BFS memory reordering, and SIMD vectorized acceleration, with evaluation support for standard datasets such as GloVe/SIFT.

The main branch focuses on the main program and comparison/evaluation tools:

main.cpp: loads base/query, builds the index and performs searches, and writes results to the selected dataset's output
checker.cpp: reads ground-truth answer files and evaluates/compares against navigable_graph or brute_force

For batch experiments / resume-from-checkpoint workflows, see the documentation on the experiment branch.

Algorithm Implementations

Algorithm	Description	Location
HNSW-style graph	Single-layer navigable neighbor graph construction	`GraphIndex/GraphConstruction.cpp`
ONNG	Optimized Navigable Neighbor Graph edge pruning	`GraphIndex/GraphOptimization.cpp`
BFS reordering	BFS-based node memory layout optimization to improve cache hit rate	`GraphIndex/GraphOptimization.cpp`
SIMD	Vectorized distance computation (SSE/AVX/AVX512 auto-detection)	`Distance/SquaredL2.h`
Adaptive Gamma	Adaptive search strategy that dynamically adjusts the termination threshold	`GraphIndex/GraphSearch.cpp`
Brute Force	Exact brute-force search baseline (O(n))	`BruteForceIndex.h/.cpp`

Implementation Notes

HNSW-style graph: the current implementation keeps only the layer-0 adjacency graph, without the hierarchical skip list
ONNG: prunes edges on top of the single-layer graph to remove redundant edges and improve search efficiency
BFS reordering: reorders graph nodes in BFS order so that nodes accessed adjacently are contiguous in memory
SIMD: supports the SSE, AVX, and AVX-512 instruction sets, automatically enabled on x86/x64 platforms

Algorithm Parameters (`AlgorithmConfig.ini`)

The main experiment parameters are centralized in AlgorithmConfig.ini, which is strictly loaded and validated at startup:

Parameter	Default	Description
`graph_degree`	96	Maximum graph adjacency degree; increasing it usually improves recall at the cost of more memory and computation
`ef_construction`	400	Size of the construction candidate set; increasing it usually improves graph quality but lengthens build time
`random_seed`	114514	Random entry point seed
`onng_max_outdegree`	96	ONNG maximum outdegree
`onng_max_indegree`	144	ONNG maximum indegree
`onng_min_edges`	64	Minimum number of edges kept after ONNG pruning
`search_result_count`	10	Number of neighbors returned per query; also the default maximum K used by checker evaluation
`search_gamma`	0.185	Search expansion range; increasing it usually improves recall at the cost of higher query latency
`entry_point_count`	100	Number of random entry points compared per search
`build_thread_limit`	32	Upper limit on the number of build threads

Parameter changes take effect without recompilation — just re-run main or checker. Graph parameter changes automatically invalidate and rebuild stale graph caches; quantization parameter changes regenerate RaBitQ codes; query parameters apply to the current run directly. Data paths are managed by DatasetConfig.ini.

By default, the program searches upward from the current directory and the executable's directory for a config root containing both AlgorithmConfig.ini and DatasetConfig.ini; alternatively, --config <path> selects another experiment config set. Unknown, duplicate, missing, or invalid parameters cause an immediate error exit.

Datasets

Dataset	#Vectors	Dim	#Queries	Description
GloVe	1,183,514	100	10,000	Word vector dataset, L2 distance
SIFT	1,000,000	128	10,000	Image feature dataset
Test	10	10	-	Small debugging dataset

Note: only .bin binary format files are included in the repository. .txt text files are not included because of their size (~800MB).

Performance Results

GloVe dataset (1.18M vectors, 100 dims, 10K queries)

Method	Search latency (ms/q)	Recall@10	Status
Brute Force	-	100.00%	Baseline
HNSW + ONNG + BFS + SIMD	1.51	≥99%	✓

SIFT dataset (1M vectors, 128 dims, 10K queries)

Method	Search latency (ms/q)	Recall@10	Status
Brute Force	-	100.00%	Baseline
HNSW + ONNG + BFS + SIMD	0.25	≥99%	✓

Test Environment

Item	Configuration
CPU	AMD Ryzen 9 7945HX with Radeon Graphics, 16 cores
Memory	Samsung 16GB DDR5 5200MHz
OS	Windows
Compiler	GCC (C++17)

Compiler Requirements

C++17, with <thread>/<mutex> available (GCC/Clang/MSVC all work)
On Windows with MinGW-w64, use the POSIX threads variant and make sure the compile command includes -pthread

Project Structure (main branch)

.
├── main.cpp            # Main program: build index, run searches, write results
├── checker.cpp         # Comparison/evaluation tool
├── AlgorithmConfig.ini # Actual experiment parameters
├── AlgorithmConfig.h/.cpp # Strongly-typed config, INI parsing and validation
├── DatasetConfig.ini   # Dataset paths and default run selection
├── DatasetConfig.h/.cpp # Dataset config parsing and relative path resolution
├── Distance/           # Metric definitions, DistanceSpace, and squared-L2 SIMD
├── GraphIndex/
│   ├── NavigableGraphIndex.h/.cpp # Public index API, lifecycle, and caching
│   ├── GraphConstruction.cpp      # Graph construction and neighbor connection
│   ├── GraphOptimization.cpp      # ONNG, Vamana, connectivity, and reordering
│   ├── GraphSearch.cpp            # FP32/RaBitQ queries and statistics
│   └── GraphHotPath.inl           # Adjacency access and distance hot path
├── FourAryHeap.h       # Four-ary max heap used by search
├── BruteForceIndex.h/.cpp # Brute-force exact search baseline
├── RaBitQ/             # Self-contained RaBitQ quantization backend
│   ├── RaBitQQuantizer.h/.cpp # Clustering, hot/cold layout, and batched navigation wrapper
│   └── Core/           # Rotation, encoding, querying, estimation, and compact-code kernels
├── IO/
│   ├── BinaryIO.h      # VECBIN1 and IVECS binary read/write
│   ├── GroundTruthIO.h # Headerless answer text and IVECS cache
│   └── TextVectorIO.h  # Strict floating-point text vector reading
├── tests/              # Small-data regression tests
└── CMakeLists.txt      # CMake build entry

File	Description
`main.cpp`	Main program: generate queries, run `navigable_graph`/`brute_force`, write answer files
`checker.cpp`	Comparison/evaluation: read headerless text or IVECS answers, compute top1/recall/latency, etc.
`GraphIndex/`	`NavigableGraphIndex` construction, optimization, querying, and hot-path implementation
`Distance/`	Dataset metric, distance function tables, and squared-L2 SIMD implementation
`FourAryHeap.h`	Four-ary max heap shared by construction and querying
`BruteForceIndex.h/.cpp`	Brute-force exact search baseline
`RaBitQ/`	Self-contained squared-L2 RaBitQ core and ONNG/Vamana backend wrappers
`IO/BinaryIO.h`	Binary read/write for VECBIN1 vectors and standard IVECS answers
`IO/GroundTruthIO.h`	Headerless answer text parsing, IVECS cache selection, and atomic update
`IO/TextVectorIO.h`	Strict parsing of floating-point text for base/query
`DatasetConfig.ini`	Named datasets, base/query/truth/cache/output paths, and default backend
`DatasetConfig.h/.cpp`	Strict dataset config parsing; relative paths resolved against the config file directory

Data and Paths (`DatasetConfig.ini`)

The [run] section of DatasetConfig.ini selects the default dataset, algorithm, backend, and binary mode; each [dataset.NAME] explicitly configures metric/base/query/truth/graph_cache/output. The only legal value is currently metric = squared_l2; a missing or unknown metric fails immediately. Relative paths are resolved against the INI's directory, so moving the project directory requires no changes to absolute paths.

Priority of run values: command-line temporary override > DatasetConfig.ini. When only base is overridden, the graph cache is derived from the overridden base path and does not overwrite the selected dataset's default cache.

Daily runs no longer use 0/1/2. Modify [run].dataset and re-run, or use --dataset NAME to temporarily select another dataset.

`.txt` and `.bin`

The program prefers base.bin in the dataset directory, and a .bin with the same stem as the query text
If the .bin does not exist, the full .txt is read strictly; on success a .bin is auto-written to speed up later runs
--bin forces reading only from .bin (missing or malformed files cause an immediate error exit)
--base <path> reads the specified VECBIN1 base file directly, using the dimension and vector count from its header; on read failure it does not fall back to another base or to synthetic data
The base count comes from the VECBIN1 header or the actual number of text lines; no upper limit is hardcoded in the source; the dimension of case 0 is determined automatically from the file
Empty lines, invalid numbers, NaN, infinity, and dimension mismatches all cause immediate errors; bad lines are not skipped

An existing but corrupt .bin does not fall back to text; missing or corrupt real data is never replaced with synthetic data.

Converting word-first GloVe text

Each line of the raw GloVe text is a word followed by its vector, e.g. word 0.1 0.2 .... The project's original base text reader requires each line to start with a number, so it cannot read such word-first files directly. The conversion script writes the vectors as VECBIN1 and writes the words to a separate vocabulary file at the same line numbers:

# Convert the first 10,000 lines first as a smoke test
python scripts/convert_glove_to_vecbin.py input.txt --limit 10000 --binary subset.bin --vocab subset.vocab.txt

# Convert the full file; defaults to input.bin and input.vocab.txt
python scripts/convert_glove_to_vecbin.py input.txt

# Load the converted result directly
./build/main.exe --base subset.bin --algo=navigable_graph

The script auto-detects the dimension and strictly rejects bad lines, dimension changes, NaN, and infinity; it never overwrites existing output. VECBIN1 uses a 24-byte little-endian header: 8-byte magic VECBIN1\0, uint32 dimension, uint64 vector count, uint32 dtype (1 for float32), followed by vectors stored contiguously row by row.

C++: Main program (`main.cpp`)

Building

CMake is recommended for building and running the regression tests:

cmake -S . -B build
cmake --build build --config Release
ctest --test-dir build -C Release --output-on-failure

You can also invoke the compiler directly:

Windows (PowerShell / MinGW-w64)

g++ -std=c++17 -O2 -Wall -Wextra -pthread -march=native -I. AlgorithmConfig.cpp DatasetConfig.cpp Distance/Metric.cpp Distance/DistanceSpace.cpp GraphCache.cpp main.cpp GraphIndex/NavigableGraphIndex.cpp GraphIndex/GraphConstruction.cpp GraphIndex/GraphSearch.cpp GraphIndex/GraphOptimization.cpp RaBitQ/RaBitQQuantizer.cpp RaBitQ/Core/Estimator.cpp RaBitQ/Core/Quantizer.cpp RaBitQ/Core/Query.cpp RaBitQ/Core/Rotator.cpp RaBitQ/Core/SimdKernels.cpp BruteForceIndex.cpp -o main.exe

Linux / macOS

g++ -std=c++17 -O2 -Wall -Wextra -pthread -march=native -I. AlgorithmConfig.cpp DatasetConfig.cpp Distance/Metric.cpp Distance/DistanceSpace.cpp GraphCache.cpp main.cpp GraphIndex/NavigableGraphIndex.cpp GraphIndex/GraphConstruction.cpp GraphIndex/GraphSearch.cpp GraphIndex/GraphOptimization.cpp RaBitQ/RaBitQQuantizer.cpp RaBitQ/Core/Estimator.cpp RaBitQ/Core/Quantizer.cpp RaBitQ/Core/Query.cpp RaBitQ/Core/Rotator.cpp RaBitQ/Core/SimdKernels.cpp BruteForceIndex.cpp -o main

Parameters (supported on the main branch)

--dataset-config=<path> or --dataset-config <path>: select a dataset config file
--dataset=<name> or --dataset <name>: temporarily override [run].dataset
--config=<path> or --config <path>: select an algorithm config file
--algo=navigable_graph|brute_force or --algo navigable_graph|brute_force
--backend=fp32|rabitq: temporarily override [run].backend
--graph-cache=<path>: temporarily override the selected dataset's graph cache
--rebuild-graph: ignore the existing graph cache and rebuild
--gen-queries: generate queries into the selected dataset's text query path and exit
--gen-test-base[=N]: only applies to datasets with kind=test whose base is a text path
--query=<path> or --query <path>: override the query input path
- Without --bin: read as txt and derive/write a same-named .bin
- With --bin: the path is read as .bin
--bin: force reading base/query only from .bin
--base=<path> or --base <path>: directly read the specified VECBIN1 base file
--output=<path> or --output <path>: temporarily override the result output path
--save-bin-base: legacy-compatible flag; a base.bin is always auto-generated after a text base loads successfully

Output file format (for `checker`)

main writes both the selected dataset's output and a same-stem .ivecs:

The text has no header; one line per query, each line containing a fixed number of space-separated non-negative base IDs
.ivecs consists of lines with a little-endian uint32 k followed by k little-endian int32 IDs
Both outputs are re-read and validated after writing before being published to the target path

checker --ans truth.txt uses the truth.ivecs cache in the same directory. If the cache is missing or older than the text, it is atomically generated from the text; a newer cache is read directly; a corrupt selected cache fails immediately. checker --ans truth.ivecs always reads the specified file directly.

Common commands

# 1) Run with the default dataset from DatasetConfig.ini
./main.exe

# 2) Temporarily select GloVe 100D and brute force
./main.exe --dataset=glove100 --algo=brute_force

# 3) Use another dataset config
./main.exe --dataset-config=experiment-datasets.ini

# 4) Force bin-only reading + a custom query.bin
./main.exe --bin --query=query0.bin --algo=navigable_graph

C++: Comparison/Evaluation (`checker.cpp`)

Building

g++ -std=c++17 -O2 -Wall -Wextra -pthread -march=native -I. AlgorithmConfig.cpp DatasetConfig.cpp Distance/Metric.cpp Distance/DistanceSpace.cpp GraphCache.cpp checker.cpp GraphIndex/NavigableGraphIndex.cpp GraphIndex/GraphConstruction.cpp GraphIndex/GraphSearch.cpp GraphIndex/GraphOptimization.cpp RaBitQ/RaBitQQuantizer.cpp RaBitQ/Core/Estimator.cpp RaBitQ/Core/Quantizer.cpp RaBitQ/Core/Query.cpp RaBitQ/Core/Rotator.cpp RaBitQ/Core/SimdKernels.cpp BruteForceIndex.cpp -o checker.exe

Parameters (supported on the main branch)

--config=<path> or --config <path>: select an algorithm config file
--dataset-config=<path> or --dataset-config <path>: select a dataset config file
--dataset=<name> or --dataset <name>: temporarily select a named dataset
--ans=<path> or --ans <path>: temporarily override the selected dataset's truth
--first=<N> / --first <N> / --firstN: evaluate only the first N queries (0 means all); shorthand forms such as --first10, --first100, --first1000 are supported
--algo=navigable_graph|brute_force: select the algorithm to evaluate (default: navigable_graph)
--backend=fp32|rabitq: temporarily override [run].backend
--graph-cache=<path>: temporarily override the selected dataset's graph cache
--rebuild-graph: ignore the existing graph cache and rebuild
--query=<path>: override the query input path (same semantics as main)
--bin: force reading base/query only from .bin
--base=<path> or --base <path>: directly read the specified VECBIN1 base file
--save-bin-base: legacy-compatible flag; text base is cached as .bin automatically by default

When the ground-truth K is greater than search_result_count, checker computes Recall using the first search_result_count ground truths and reports both the original K and the actually evaluated K.

Common commands

# Evaluate directly per the [run] section of DatasetConfig.ini
./checker.exe

# Temporarily select GloVe 100D and another algorithm parameter set
./checker.exe --dataset=glove100 --config=experiment.ini

# Check only the first 100 (supports --first100 / --first=100 / --first 100)
./checker.exe --first100

# Force bin reading for query with a custom query0.bin
./checker.exe --bin --query=query0.bin --ans=truth.txt --algo=navigable_graph

Multithreading and SIMD Notes

Multithreading relies on the standard library; remember -pthread with GCC/Clang
SIMD defaults to selecting SSE, AVX, or AVX-512 at runtime on x86/x64 platforms; other platforms use the scalar implementation

Quick Start (recommended workflow)

# 1) Build and test
cmake -S . -B build
cmake --build build --config Release
ctest --test-dir build -C Release --output-on-failure

# 2) Run and evaluate with the DatasetConfig.ini defaults
./build/main.exe
./build/checker.exe

Dependencies

This project uses only the C++ standard library — no third-party dependencies:

Dependency	Purpose	Notes
C++ standard library	Containers, multithreading, I/O	`<vector>`, `<thread>`, `<mutex>`, `<fstream>`, etc.
SIMD intrinsics	Vectorized distance computation	`<immintrin.h>` (automatically available on x86/x64)

The RaBitQ squared-L2 core lives in RaBitQ/, so building does not require the adjacent git/RaBitQ-Library repo. The algorithm and parts of the implementation structure reference upstream VectorDB-NTU/RaBitQ-Library v0.1.3; see RaBitQ/UPSTREAM.md for provenance and modification scope.

License

The project core is licensed under the MIT License; see LICENSE. Parts of RaBitQ/ adapted from RaBitQ-Library additionally retain Apache License 2.0 attribution; see RaBitQ/LICENSE.RaBitQ.

MIT License

Copyright (c) 2024

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

Dataset Links

GloVe dataset: Stanford NLP
SIFT dataset: Corpus-Texmex

Navigation Menu

Repository files navigation

Nearest Neighbor Search

Project Overview

Algorithm Implementations

Implementation Notes

Algorithm Parameters (`AlgorithmConfig.ini`)

Datasets

Performance Results

GloVe dataset (1.18M vectors, 100 dims, 10K queries)

SIFT dataset (1M vectors, 128 dims, 10K queries)

Test Environment

Compiler Requirements

Project Structure (main branch)

Data and Paths (`DatasetConfig.ini`)

`.txt` and `.bin`

Converting word-first GloVe text

C++: Main program (`main.cpp`)

Building

Parameters (supported on the main branch)

Output file format (for `checker`)

Common commands

C++: Comparison/Evaluation (`checker.cpp`)

Building

Parameters (supported on the main branch)

Common commands

Multithreading and SIMD Notes

Quick Start (recommended workflow)

Dependencies

License

Dataset Links

About

Releases

Packages

Contributors

Languages

Name		Name	Last commit message	Last commit date
Distance		Distance
GraphIndex		GraphIndex
IO		IO
Platform		Platform
RaBitQ		RaBitQ
.gitignore		.gitignore
AlgorithmConfig.cpp		AlgorithmConfig.cpp
AlgorithmConfig.h		AlgorithmConfig.h
AlgorithmConfig.ini		AlgorithmConfig.ini
BruteForceIndex.cpp		BruteForceIndex.cpp
BruteForceIndex.h		BruteForceIndex.h
CMakeLists.txt		CMakeLists.txt
ConfigExample.h		ConfigExample.h
DatasetConfig.cpp		DatasetConfig.cpp
DatasetConfig.h		DatasetConfig.h
DatasetConfig.ini		DatasetConfig.ini
FourAryHeap.h		FourAryHeap.h
GraphCache.cpp		GraphCache.cpp
GraphCache.h		GraphCache.h
LICENSE		LICENSE
README.md		README.md
README.zh-CN.md		README.zh-CN.md
checker.cpp		checker.cpp
main.cpp		main.cpp

Latest commit

History

Folders and files

Repository files navigation

Nearest Neighbor Search

Project Overview

Algorithm Implementations

Implementation Notes

Algorithm Parameters (AlgorithmConfig.ini)

Datasets

Performance Results

GloVe dataset (1.18M vectors, 100 dims, 10K queries)

SIFT dataset (1M vectors, 128 dims, 10K queries)

Test Environment

Compiler Requirements

Project Structure (main branch)

Data and Paths (DatasetConfig.ini)

.txt and .bin

Converting word-first GloVe text

C++: Main program (main.cpp)

Building

Parameters (supported on the main branch)

Output file format (for checker)

Common commands

C++: Comparison/Evaluation (checker.cpp)

Building

Parameters (supported on the main branch)

Common commands

Multithreading and SIMD Notes

Quick Start (recommended workflow)

Dependencies

License

Dataset Links

About

Resources

Stars

Watchers

Forks

Releases

Packages

Contributors

Languages

Algorithm Parameters (`AlgorithmConfig.ini`)

Data and Paths (`DatasetConfig.ini`)

`.txt` and `.bin`

C++: Main program (`main.cpp`)

Output file format (for `checker`)

C++: Comparison/Evaluation (`checker.cpp`)