hnsw - GitLite

KO | EN

gitlite — search

#javascript #react #ai #llm #golang #android #nodejs #awesome #cli #kubernetes #vue #ios #openai #open-source

hnsw

(★ 101)

Heirarchical Navigable Small Worlds

File Explorer

Download Latest Version (.zip)

- settings.json
- - build-and-test.yml
- bench_simd.cpp
- CMakeLists.txt
- - .gitignore
  - CMakeLists.txt
  - pyproject.toml
  - pytest.ini
  - README.md
  - requirements.txt
  - setup.py
  - test_pyhnsw.py
- - hnsw.h
  - simd_distance.h
- - framework.h
  - test_hnsw.h
- - framework.cpp
  - test_hnsw.cpp
- CMakeLists.txt
.gitattributes
.gitignore
CMakeLists.txt
LICENSE
r_build.txt
README.md

# Installation Guide

1. Get the code

git clone https://github.com/dicroce/hnsw

Downloads the entire project code from GitHub to your computer.

cd hnsw

Moves into the project folder you just downloaded.

2. CMake

Medium Recommended

Prerequisites

Git Needed to download the project code from GitHub.
CMake The tool used to generate build configuration.
C/C++ 컴파일러 Windows needs Visual Studio (Community edition, free), macOS needs Xcode Command Line Tools, Linux needs the gcc/g++ package.

mkdir build && cd build

Creates a folder to hold the build output and moves into it.

cmake ..

Analyzes the source code and generates build configuration files (must be run inside the build folder).

make

Compiles the code based on the generated build configuration to produce an executable.

✅ Check that an executable was created inside the build folder, then run it directly (e.g. ./build/app_name).

3. Python

Easy

Prerequisites

Git Needed to download the project code from GitHub.
Python 3 On Windows, be sure to check 'Add Python to PATH' during installation.

⚠️ This is a large repository, so this method may point to an internal sub-package rather than the actual core product. Check the full README as well.

pip install -r bindings/pyhnsw/requirements.txt

Installs the Python libraries listed in requirements.txt (or similar).

python <실행할 파일명>.py # README에서 정확한 실행 파일명을 확인하세요

Runs the Python script (or module).

✅ If it runs without errors and prints output in the terminal, it worked.

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# HNSW - Hierarchical Navigable Small Worlds
## Nearest neighbor search for vector embeddings

+ 2 header files.
+ Dependency-free.
+ Fast: hand-written SIMD distance kernels (AVX2/FMA, SSE2, scalar) selected at
  runtime to match the CPU it runs on. See `include/hnsw/simd_distance.h`.

## What is HNSW?
```
// Level 2           *                    *        *                                        *
// Level 1        *  *              *     *        *        *          **                 * *
// Level 0  *     ** *     * * *    *    **   *  * *  * ** **          **     ** *    *   * *   * * *
```
HNSW is a graph structure that consists of levels that are more sparsely populated at the top and more
densely populated at the bottom. Nodes within a layer have connections to other nodes that are near them
on the same level. When a node is inserted a random level is picked and the node is inserted there. It
is also inserted into all levels beneath that level down to 0.

When searches arrive they start at the top and search that level (following connections) until they find
the closest node in the top level. The search then descends and keeps searching nearby nodes. As the
search progresses the code keeps track of the K nearest nodes it has seen. Eventually it either finds
the value OR it finds the closest value on level 0 and the K nearest nodes seen are returned.

### Example

Vectors are passed as `std::vector<scalar>` (e.g. `std::vector<float>`), which
is aliased as `dicroce::hnsw_types<float>::vector_type`.

```cpp
#include "hnsw/hnsw.h"
#include <random>
#include <cstdio>

int main()
{
    using vector_type = dicroce::hnsw_types<float>::vector_type;

// Create an index for 128-dimensional vectors
    const size_t dim = 128;
    dicroce::hnsw<float> index(dim);

std::mt19937 gen(42);
    std::normal_distribution<float> nd(0.0f, 1.0f);
    auto random_vec = [&]() {
        vector_type v(dim);
        for (size_t i = 0; i < dim; ++i) v[i] = nd(gen);
        return v;
    };

// Build the index
    const size_t num_vectors = 10000;
    for (size_t i = 0; i < num_vectors; ++i)
        index.add_item(random_vec());

// Search for the k nearest neighbors of a query vector
    vector_type query = random_vec();
    const size_t k = 10;
    auto results = index.search(query, k);

for (const auto& result : results)
        printf("label: %lld, distance: %f\n",
               (long long)result.first, result.second);
}
```

### External IDs (labels)

`search` returns `(label, distance)` pairs. By default a vector's label is its
insertion order (0, 1, 2, …), but you can attach your own `int64` label so hits
map straight back to your data (e.g. a frame id, a database row, a nanots
`(timestamp)` key):

```cpp
index.add_item(embedding, /*label=*/frame_id);   // your id
...
auto hits = index.search(query, 10);
for (auto& [label, dist] : hits)
    lookup_frame(label);   // label is the frame_id you supplied
```

Labels need not be unique — that's your choice — and they are persisted by
`save()`/`load()`.

### Persistence

The whole graph (vectors *and* connections) is serialized to a flat binary
file, so loading reconstructs a ready-to-search index **without rebuilding** —
construction is the expensive part of HNSW, so you only pay it once.

```cpp
// Save a built index.
index.save("index.bin");

// Load it back later (returns a ready-to-search index; no rebuild).
auto index = dicroce::hnsw<float>::load("index.bin");
auto results = index.search(query, 10);
```

The on-disk format is self-describing (magic + version + byte-order marker) and
records the `sizeof(scalar)`, so loading a file written for `hnsw<double>` into
an `hnsw<float>` — or a file written on a different-endian machine — fails
loudly instead of corrupting silently.

### Compilation
mkdir build && pushd build && cmake .. && make && popd