DOCSEARCHbyAlgolia
Submit Docs

NGT (Neighborhood Graph and Tree)

repository·main·Indexed 23 days ago

https://github.com/ngt-labs/ngt

A high-speed approximate nearest neighbor search engine for high-dimensional vector data. It supports indexing methods including graph-based, quantized graph (QG), and quantized blob graph (QBG) approaches to handle datasets from millions to billions of objects. The toolset includes the `ngt` CLI for index creation, data appending, and proximity search, as well as the `qbg` CLI for managing quantized indices.

Tokens
22.5K
Snippets
29
Records
120
Agent score
79%

What's inside NGT

  1. Use the NGT CLI for high-dimensional vector search

    main

    ngt is a command-line tool for high-speed nearest neighbor search in high-dimensional vector data (millions to tens of millions of vectors with dozens to thousands of dimensions).

    Command Syntax:

    $ ngt command [option] index [data]

    Note: In environments where POSIXLY_CORRECT is set (like CygWin), options must be specified before the command: $ ngt [option] command index [data].

    Available Commands:

    • create: Generate a new index and register data.
    • append: Add new data to an existing index.
    • prep-pq: Pre-process Product Quantization (PQ) data types.
    • search: Perform nearest neighbor search using query data.
    • remove: Delete specific objects from an index.
    • prune (deprecated): Reduce long edges in the graph.
    • reconstruct-graph: Reconstruct the graph from an existing index.
    • rebuild: Re-initialize and regenerate the graph and tree indices.
    • rebuild: Re-initialize and regenerate the graph and tree indices.
    $ ngt command [option] index [data]

  2. Supported Programming Languages for NGT

    main

    NGT provides bindings and support for a wide variety of languages:

    • Python: Full support (including search for QG/QBG).
    • C / C++: Full support.
    • Rust: Via crates/ngt.
    • Go: Via gongt.
    • Ruby: Via ankane/ngt.
    • PHP: Via ankane/ngt-php.
    • JavaScript/NodeJS: Via ngt-tool and spatial-db-ngt.

    For distributed server capabilities, look into ngtd and vald.

  3. Overview of QBG (Quantized Blob Graph) and QG (Quantized Graph)

    main

    The qbg CLI tool provides proximity search for high-dimensional data using two distinct quantization methods:

    1. Quantized Graph (QG): Operates on existing NGT indices (like ANNG or ONNG). It requires an existing index built with L2 distance or normalized cosine similarity. Commands include create-qg, build-qg, and search-qg.
    2. Quantized Blob Graph (QBG): A standalone quantized graph implementation. Commands include create, append, build, and search.

    Note on Command Syntax: On some platforms (e.g., Cygwin), if the POSIXLY_CORRECT environment variable is set, you must specify options before the command: $ qbg [option] command index [data] Otherwise, the standard syntax is: $ qbg command [option] index [data]

  4. Compare NGT, QG, and QBG methods

    main

    NGT provides three distinct indexing methods depending on your scale and performance requirements:

    1. NGT (Graph and tree-based method)

    • Best for: General purpose high-dimensional vector search.
    • Features: Supports data addition/deletion, shared memory (mmap), and various distance functions (L1, L2, Cosine, Hamming, Jaccard, etc.).
    • Supported Languages: Python, Ruby, PHP, Rust, Go, C, C++.

    2. QG (Quantized graph-based method)

    • Best for: Higher performance than standard NGT.
    • Features: Supports L2 and Cosine similarity.
    • Supported Languages: C++, C, Python (search only).

    3. QBG (Quantized blob graph-based method)

    • Best for: Extremely large scale (up to 1 billion objects).
    • Features: Supports L2 distance.
    • Supported Languages: C++, C, Python (search only).

  5. Quickstart: Approximate Nearest Neighbor Search with NGT

    main

    NGT (Neighborhood Graph and Tree) is used for searching approximate nearest neighbors in high-dimensional data. To use it, you create an index with a specific dimension, insert your data objects, build the index, and then perform searches.

    Basic workflow:

    1. Create an index using ngt.base.Index.create(path, dimension, ...).
    2. Insert data using insert(), insert_object(), or insert_from_tsv().
    3. Build the index (required if using insert_object).
    4. Search using search(query, k, epsilon) to find the $k$ nearest neighbors.
    from ngt import base as ngt
import random

dim = 10
objects = []
for i in range(0, 100) :
    vector = random.sample(range(100), dim)
    objects.append(vector)

query = objects[0]
index = ngt.Index.create("tmp", dim)
index.insert(objects)

index.save()

result = index.search(query, 3)

for i, o in enumerate(result) :
    print(str(i) + ": " + str(o.id) + ", " + str(o.distance))
    object = index.get_object(o.id)
    print(object)

  6. Install NGT Python bindings from source

    main

    To install the Python bindings from the source code, you must first install the NGT library following the build instructions in the main README. Once the NGT library is installed, navigate to the python directory in your NGT root and install using pip.

    Prerequisite: The NGT library must be installed before attempting to install the Python bindings.

    cd NGT_ROOT/python
pip3 install .

  7. Install NGT Python bindings via pip

    main

    You can install the ngtpy (pybind11) Python bindings directly from PyPI using pip.

    Note: The PyPI version of ngtpy may perform slower in searches compared to a version built locally on your specific machine, as the local build is optimized for your CPU architecture.

    pip3 install ngt

  8. Use the NGT CLI for proximity search

    main

    The ngt command-line tool provides high-speed nearest neighbor searches for high-dimensional vector data (millions of items, dozens to thousands of dimensions).

    Basic Syntax:

    $ ngt command [options] index [additional arguments]

    Note for macOS/Cygwin users: If the POSIXLY_CORRECT environment variable is set, you must specify options before the command:

    $ ngt [options] command index [additional arguments]

    Available Commands:

    • create: Initialize a new index and insert data.
    • append: Add data to an existing index.
    • prep-pq: Preprocess product quantization data.
    • search: Perform nearest neighbor search.
    • remove: Remove objects from an index.
    • prune: Prune long edges (not recommended).
    • reconstruct-graph: Reconstruct the index graph.
    • rebuild: Clear and rebuild graph/tree indexes.
    $ ngt command [options] index [additional arguments]

  9. Install NGT via Build

    main

    You can build NGT from source on various operating systems. Note that the methods available depend on whether you require QG (Quantized Graph) or QBG (Quantized Blob Graph), which require BLAS and LAPACK libraries.

    Linux (without QG and QBG)

    Use this if you only need the standard Graph and tree-based method and want to avoid installing BLAS/LAPACK.

    $ unzip NGT-x.x.x.zip
$ cd NGT-x.x.x
$ mkdir build
$ cd build
$ cmake -DNGT_QBG_DISABLED=ON ..
$ make
$ make install
$ ldconfig /usr/local/lib

    CentOS

    $ yum install blas-devel lapack-devel
$ unzip NGT-x.x.x.zip
$ cd NGT-x.x.x
$ mkdir build
$ cd build
$ cmake ..
$ make
$ make install
$ ldconfig /usr/local/lib

    Ubuntu

    $ apt install libblas-dev liblapack-dev
$ unzip NGT-x.x.x.zip
$ cd NGT-x.x.x
$ mkdir build
$ cd build
$ cmake ..
$ make
$ make install
$ ldconfig /usr/local/lib

    macOS (using Homebrew)

    $ /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"
$ brew install cmake
$ brew install libomp
$ unzip NGT-x.x.x.zip
$ cd NGT-x.x.x
$ mkdir build
$ cd build
$ export OpenMP_ROOT=$(brew --prefix)/opt/libomp
$ cmake ..
$ make
$ make install

  11. Install NGT via build from source

    main

    You can build NGT from source on various operating systems. Note that the QG and QBG methods require BLAS and LAPACK libraries. If you only need the standard NGT (Graph and tree-based method), you can disable QG/QBG during the CMake configuration step.

    ### Linux (Disabling QG/QBG)
$ unzip NGT-x.x.x.zip
$ cd NGT-x.x.x
$ mkdir build
$ cd build
$ cmake -DNGT_QBG_DISABLED=ON ..
$ make
$ make install
$ ldconfig /usr/local/lib

### CentOS
$ yum install blas-devel lapack-devel
$ unzip NGT-x.x.x.zip
$ cd NGT-x.x.x
$ mkdir build
$ cd build
$ cmake ..
$ make
$ make install
$ ldconfig /usr/local/lib

### Ubuntu
$ apt install libblas-dev liblapack-dev
$ unzip NGT-x.x.x.zip
$ cd NGT-x.x.x
$ mkdir build
$ cd build
$ cmake ..
$ make
$ make install
$ ldconfig /usr/local/lib

### macOS
$ /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"
$ brew install cmake
$ brew install libomp
$ unzip NGT-x.x.x.zip
$ cd NGT-x.x.x
$ mkdir build
$ cd build
$ export OpenMP_ROOT=$(brew --prefix)/opt/libomp
$ cmake ..
$ make
$ make install

  12. Install the NGT Python bindings

    main

    You can install the NGT Python bindings (ngtpy) via PyPI using pip.

    Note on Performance: Packages installed from PyPI are optimized for compatibility with older CPUs and may have slower search speeds compared to a version built from source on your local machine.

    To install from source, you MUST first install the NGT library following the build instructions in the main repository README. Once the library is installed, navigate to the python directory in the source tree and install locally:

    # Install from PyPI
pip3 install ngt

# Install from source (requires NGT library to be built first)
cd NGT_ROOT/python
pip3 install .