Neighborhood Graph and Tree for Indexing High-dimensional Data

Supported by

Home / Installation / Command / License / Publications / 日本語

NGT provides commands and a library for performing high-speed approximate nearest neighbor searches against a large volume of data in high-dimensional vector spaces (several tens to several thousand dimensions).

News

• 05/26/2025 Product quantization is now available as a data type for graph indices. (v2.4.0)
• 10/29/2024 Scalar quantization is now available as a data type for graph indices and QBG. (v2.3.0)
• 04/10/2024 Inner product (or dot product) is now available. (v2.1.0)
• 08/10/2022 QBG (Quantized Blob Graph) and QG (renewed NGTQG) are now available. The command-line interface ngtq and ngtqg are now obsolete by replacing qbg. (v2.0.0)
• 02/04/2022 FP16 (half-precision floating point) is now available. (v1.14.0)
• 03/12/2021 The results for the quantized graph are added to this README.
• 01/15/2021 NGT v1.13.0 to provide the quantized graph (NGTQG) is released.
• 11/04/2019 NGT tutorial has been released.
• 06/26/2019 Jaccard distance is available. (v1.7.6)
• 06/10/2019 PyPI NGT package v1.7.5 is now available.
• 01/17/2019 Python NGT can be installed via pip from PyPI. (v1.5.1)
• 12/14/2018 NGTQ (NGT with Quantization) is now available. (v1.5.0)
• 08/08/2018 ONNG is now available. (v1.4.0)

Methods

This repository provides the following methods.

• NGT: Graph and tree-based method
• QG: Quantized graph-based method
• QBG: Quantized blob graph-based method

Note: Since QG and QBG require BLAS and LAPACK libraries, if you use only NGT (Graph and tree-based method) without the additional libraries like V1, you can disable QG and QBG with this option.

Installation

Build

Downloads

• Releases

On Linux without QG and 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

On 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
  

On 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

On 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

On Windows

Windows support currently targets MinGW-w64 GCC (via MSYS2 / UCRT64). Native Microsoft Visual C++ (MSVC) is not currently supported and is planned as a future enhancement. -DNGT_QBG_DISABLED=ON is required. The standard in-memory index creation and search workflows are supported. Windows builds currently use static linking for the CLI; DLL export annotations and shared memory (memory-mapped file) allocators are not included yet.

To set up the build environment and build using MSYS2 (UCRT64 environment):

  $ pacman -S mingw-w64-ucrt-x86_64-gcc mingw-w64-ucrt-x86_64-libgomp mingw-w64-ucrt-x86_64-cmake mingw-w64-ucrt-x86_64-ninja
  $ cd NGT
  $ mkdir build
  $ cd build
  $ cmake -DNGT_QBG_DISABLED=ON -G Ninja ..
  $ ninja -j 2

[!NOTE] Compiling with Link-Time Optimization (LTO) and template instantiations is memory-intensive. Using ninja -j 2 (or limiting parallel jobs) avoids compiler out-of-memory errors on machines with less than 16 GB of RAM.

Pre-Built

On macOS

  $ brew install ngt

NGT (Graph and tree-based method)

Key Features

• Supported operating systems: Linux, macOS, and Windows via MinGW-w64/MSYS2
• Object additional registration and removal are available.
• Objects beyond the memory size can be handled using the shared memory (memory mapped file) option.
• Supported distance functions: L1, L2, Cosine similarity, Angular, Hamming, Jaccard, Poincare, Lorentz, and Inner product
• Data Types: 4 byte floating point number, 2 byte floating point number, and 1 byte unsigned integer
• Supported languages: Python, Ruby, PHP, Rust, Go, C, and C++
• Distributed servers: ngtd and vald

Documents

• NGT tutorial

Utilities

• Command : ngt and qbg
• Server : ngtd and vald

Supported Programming Languages

• Python
• Ruby (Thanks Andrew!)
• PHP (Thanks Andrew!)
• Rust (Thanks Romain!)
• JavaScript/NodeJS : ngt-tool and spatial-db-ngt (Thanks stonkpunk!)
• Go
• C
• C++(sample code)

The following build parameters are available

Build parameters

Shared memory use

The index can be placed in shared memory with memory mapped files. Using shared memory can reduce the amount of memory needed when multiple processes are using the same index. In addition, it can not only handle an index with a large number of objects that cannot be loaded into memory, but also reduce time to open it. Since changes become necessary at build time, please add the following parameter when executing "cmake" in order to use shared memory.

  $ cmake -DNGT_SHARED_MEMORY_ALLOCATOR=ON ..

Note: Since there is no lock function, the index should be used only for reference when multiple processes are using the same index.

Large-scale data use

When you insert more than about 5 million objects for the graph-based method, please add the following parameter to improve the search time.

  $ cmake -DNGT_LARGE_DATASET=ON ..

Disable QG and QBG

QG and QBG require BLAS and LAPACK libraries. If you would not like to install these libraries and do not use QG and QBG, you can disable QG and QBG.

  $ cmake -DNGT_QBG_DISABLED=ON ..

QG (Quantized graph-based method)

Key Features

• Higher performance than the graph and tree-based method
• Supported operating systems: Linux and macOS
• Supported distance functions: L2 and Cosine similarity

Documents

• QG tutorial

Utilities

• Command : qbg

Supported Programming Languages

• C++
• C
• Python only for search

Build parameters

For QG, it is recommended to disable rotation of the vector space and residual vectors to improve performance as follows.

  $ cmake -DNGTQG_NO_ROTATION=ON -DNGTQG_ZERO_GLOBAL=ON ..

QBG (Quantized blob graph-based method)

Key Features

• QBG can handle billions of objects.
• Supported operating systems: Linux and macOS
• Supported distance functions: L2

Documents

• QBG tutorial

Utilities

• Command : qbg

Supported Programming Languages

• C++
• C
• Python only for search

Benchmark Results

The following results are for NGT v2.8.0 and were measured on Sakura Cloud, provided by SAKURA internet Inc., using an Intel(R) Xeon(R) Gold 6230R.

glove-100-angular

License

Copyright (C) 2015 Yahoo Japan Corporation
Copyright (C) 2026 SAKURA internet Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this software except in compliance with the License. You may obtain a copy of the License at

https://www.apache.org/licenses/LICENSE-2.0

The holders of patents covering technologies used in this software will not assert those patent rights against users of this software, provided that the software is used in compliance with the Apache License, Version 2.0.

Contributing

Please refer to CONTRIBUTING.md before submitting a pull request.

Contact Person

masajiro

Publications

ONNG

• Iwasaki, M., Miyazaki, D.: Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity. arXiv:1810.07355 [cs] (2018). (pdf)

PANNG

• Iwasaki, M.: Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search. Proc. of SISAP2016 (2016) 20-33. (pdf)
• Sugawara, K., Kobayashi, H. and Iwasaki, M.: On Approximately Searching for Similar Word Embeddings. Proc. of ACL2016 (2016) 2265-2275. (pdf)

ANNGT

• Iwasaki, M.: Applying a Graph-Structured Index to Product Image Search (in Japanese). IIEEJ Journal 42(5) (2013) 633-641. (pdf)
• Iwasaki, M.: Proximity search using approximate k nearest neighbor graph with a tree structured index (in Japanese). IPSJ Journal 52(2) (2011) 817-828. (pdf)

ANNG

• Iwasaki, M.: Proximity search in metric spaces using approximate k nearest neighbor graph (in Japanese). IPSJ Trans. on Database 3(1) (2010) 18-28. (pdf)