NGT

https://github.com/yahoojapan/ngt
Admin
NGT provides commands and a library for high-speed approximate nearest neighbor searches against...
Tokens:44,580
Snippets:185
Trust Score:9.5
License:Apache-2.0
Update:1 year ago
Show doc for...
Tokens:
Raw
### NGT Installation

Source: https://github.com/yahoojapan/ngt/wiki/Command-Line-Quick-Start

Steps to download, compile, and install NGT from a zip archive. Includes setting up build directories and running make commands.

```bash
unzip NGT-x.x.x.zip
cd NGT-x.x.x
mkdir build
cd build 
cmake ..
make 
make install
```

--------------------------------

### NGT Index Initialization and Data Registration

Source: https://github.com/yahoojapan/ngt/wiki/Command-Line-Quick-Start

Example of creating and initializing an NGT index with specified dimensions and registering data from a TSV file.

```shell
cd (NGT_TOP_DIR)
ngt create -d 128 anng ./data/sift-dataset-5k.tsv
```

--------------------------------

### Install NGT

Source: https://github.com/yahoojapan/ngt/wiki/Cpp-Quick-Start

Steps to download, compile, and install the NGT library from a zip archive. Includes setting up build directories and environment paths for libraries and executables.

```Shell
unzip NGT-x.x.x.zip
cd NGT-x.x.x
mkdir build
cd build 
cmake ..
make 
make install
```

```Shell
export PATH="$PATH:/opt/local/bin"
export LD_LIBRARY_PATH=/usr/local/lib:/usr/lib
```

--------------------------------

### Data Insertion and Index Construction with NGT

Source: https://github.com/yahoojapan/ngt/wiki/Cpp-Quick-Start

C++ code example demonstrating how to create an NGT index, insert objects from a TSV file, construct the index, and save it. It details property settings, data loading, and index building parameters.

```C++
// construct.cpp
#include        "NGT/Index.h"
using namespace std;
int main(int argc, char **argv)
{
  NGT::Property property;
  property.dimension    = 128;
  property.objectType   = NGT::ObjectSpace::ObjectType::Float;
  property.distanceType = NGT::Index::Property::DistanceType::DistanceTypeL2;
  std::string   path("anng");
  NGT::Index::create(path, property);
  NGT::Index    index(path);
  ifstream      is("./data/sift-dataset-5k.tsv");
  string        line;
  while (getline(is, line)) {
    stringstream        linestream(line);
    vector<float>       object;
    while (!linestream.eof()) {
      float value;
      linestream >> value;
      object.push_back(value);
    }
    object.resize(property.dimension);  // cut off unnecessary data in the file.                                                             
    index.append(object);
  }
  index.createIndex(16);               // 16 is the number of threads to build indexes.                                                      
  index.save();
  return 0;
}
```

--------------------------------

### NGT Command Line Syntax

Source: https://github.com/yahoojapan/ngt/wiki/Command-Line-Quick-Start

Demonstrates the basic syntax for using the NGT command-line tool, including variations based on the POSIXLY_CORRECT environment variable.

```shell
ngt ngt-command options arguments
```

```shell
ngt options ngt-command arguments
```

--------------------------------

### Nearest Neighbor Search with NGT

Source: https://github.com/yahoojapan/ngt/wiki/Cpp-Quick-Start

C++ code example for performing nearest neighbor searches using the NGT library. It shows how to load an index, set up a search query with results and size, and process the search results.

```C++
// search.cpp
#include        "NGT/Index.h"
using namespace std;
int main(int argc, char **argv)
{
  NGT::Index    index("anng", true);    // "true" means read only.                                                                           
  NGT::Property property;
  index.getProperty(property);
  ifstream      is("./data/sift-query-3.tsv");
  string        line;
  int           queryNo = 1;
  while (getline(is, line)) {
    vector<float>       query;
    stringstream        linestream(line);
    while (!linestream.eof()) {
      float value;
      linestream >> value;
      query.push_back(value);
    }
    NGT::SearchQuery            searchQuery(query);
    NGT::ObjectDistances        results;
    searchQuery.setResults(&results);
    searchQuery.setSize(5);
    index.search(searchQuery);
    cout << "Query No." << queryNo++ << endl;
    cout << "Rank\tID\tDistance" << endl;
    for (size_t i = 0; i < results.size(); i++) {
      cout << i + 1 << "\t" << results[i].id << "\t" << results[i].distance << endl;
    }
    cout << endl;
  }
  return 0;
}
```

--------------------------------

### NGT Environment Variables

Source: https://github.com/yahoojapan/ngt/wiki/Command-Line-Quick-Start

Instructions for setting environment variables to include NGT libraries and executables in the system's search paths.

```bash
export PATH="$PATH:/opt/local/bin"
export LD_LIBRARY_PATH=/usr/local/lib:/usr/lib
```

--------------------------------

### NGT Separate Index Initialization and Data Append

Source: https://github.com/yahoojapan/ngt/wiki/Command-Line-Quick-Start

Shows how to separate index creation and data registration into two distinct commands using 'create' and 'append'.

```shell
ngt create -d 128 anng
ngt append anng ./data/sift-dataset-5k.tsv
```

--------------------------------

### NGT Nearest Neighbor Search

Source: https://github.com/yahoojapan/ngt/wiki/Command-Line-Quick-Start

Example of performing a nearest neighbor search using the NGT command, specifying the number of results to retrieve.

```shell
ngt search -n 5 anng ./data/sift-query-3.tsv
```

--------------------------------

### Create NGT Index Example

Source: https://github.com/yahoojapan/ngt/blob/main/bin/ngt/README.md

Example of creating an NGT index for 128-dimensional, 1-byte-integer data using a specified dataset.

```bash
$ cd (NGT_TOP_DIR)
$ ngt create -d 128 -o c index ./data/sift-dataset-5k.tsv
Data loading time=0.160748 (sec) 160.748 (msec)
# of objects=5000
Index creation time=0.379659 (sec) 379.659 (msec)
```

--------------------------------

### Download and Unzip fastText Dataset

Source: https://github.com/yahoojapan/ngt/wiki/Practical-Examples-Using-Python

Downloads the fastText English word vectors dataset and unzips it. This is the initial step for preparing the data for NGT.

```bash
curl -O https://dl.fbaipublicfiles.com/fasttext/vectors-english/wiki-news-300d-1M-subword.vec.zip
unzip wiki-news-300d-1M-subword.vec.zip
```

--------------------------------

### Install NGT Python Binding

Source: https://github.com/yahoojapan/ngt/blob/main/python/README.md

Installs the NGT Python binding (ngtpy) using pip. Ensure the NGT library is built first if installing from source.

```bash
pip3 install ngt
```

```bash
cd NGT_ROOT/python
pip3 install .
```

--------------------------------

### ANNG Quick Optimization: Initial Edges

Source: https://github.com/yahoojapan/ngt/wiki/Optimization-Examples-Using-Ngt-Command

Optimizes the number of initial edges for ANNG by first inserting objects without indexing, then running an optimization command, and finally building the indexes.

```bash
ngt create -d 300 -D c -E 0 fasttext.anng objects.ssv
ngt optimize-#-of-edges fasttext.anng
ngt append fasttext.anng
```

--------------------------------

### Install ngtpy

Source: https://github.com/yahoojapan/ngt/wiki/Python-Quick-Start

Installs the ngtpy Python binding using pip.

```bash
pip3 install ngt
```

--------------------------------

### Install NGT on Ubuntu

Source: https://github.com/yahoojapan/ngt/blob/main/README.md

This snippet provides instructions for installing NGT on an Ubuntu system. It covers installing the required BLAS and LAPACK development libraries, unzipping the NGT archive, configuring the build using CMake, compiling, installing, and updating the dynamic linker cache.

```bash
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
```

--------------------------------

### Download and Unzip fastText Dataset

Source: https://github.com/yahoojapan/ngt/wiki/Practical-Examples-Using-Cpp

This snippet downloads a large-scale fastText dataset (wiki-news-300d-1M-subword.vec.zip) using curl and then unzips it. This dataset is used for generating NGT graphs.

```bash
curl -O https://dl.fbaipublicfiles.com/fasttext/vectors-english/wiki-news-300d-1M-subword.vec.zip
unzip wiki-news-300d-1M-subword.vec.zip
```

--------------------------------

### Install NGT on macOS

Source: https://github.com/yahoojapan/ngt/blob/main/README.md

This snippet outlines the process for installing NGT on macOS using Homebrew. It includes installing Homebrew, CMake, and libomp, unzipping the NGT archive, configuring the build with CMake (setting the OpenMP root), compiling, and installing.

```bash
/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
```

--------------------------------

### Compile Data Insertion Code

Source: https://github.com/yahoojapan/ngt/wiki/Cpp-Quick-Start

Command to compile the C++ source file for data insertion and index construction using g++. It links against the NGT library.

```Shell
g++ -std=c++11 -o construct construct.cpp -lngt
```

--------------------------------

### Install NGT on Linux (without QG/QBG)

Source: https://github.com/yahoojapan/ngt/blob/main/README.md

This snippet shows how to build and install NGT on a Linux system, specifically disabling the Quantized Graph (QG) and Quantized Blob Graph (QBG) features. It requires unzipping the NGT archive, configuring the build with CMake, compiling, and installing.

```bash
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
```

--------------------------------

### Install NGT on CentOS

Source: https://github.com/yahoojapan/ngt/blob/main/README.md

This snippet details the installation of NGT on a CentOS system. It includes installing necessary development libraries (BLAS and LAPACK), unzipping the NGT archive, configuring the build with CMake, compiling, installing, and updating the dynamic linker cache.

```bash
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
```

--------------------------------

### Search ANNG Index and Retrieve Results

Source: https://github.com/yahoojapan/ngt/wiki/Practical-Examples-Using-Cpp

This C++ code demonstrates how to search the constructed ANNG index ('fasttext.anng'). It loads the index, retrieves a query object by its ID, performs a search with specified parameters (size, epsilon), and prints the ranked results along with the corresponding words from 'words.tsv'.

```cpp
// search-fasttext.cpp                                                                                                                       
#include        "NGT/Index.h"
#include        <sstream>
#include        <iomanip>
using namespace std;
int main(int argc, char **argv)
{
  ifstream              is("words.tsv");
  string                word;
  vector<string>        words;
  while (getline(is, word)) {
    words.push_back(word);
  }
  NGT::Index            index("fasttext.anng", true);
  int                   queryID = 10001;
  vector<float>         query;
  index.getObjectSpace().getObject(queryID, query);
  NGT::SearchQuery      searchQuery(query);
  NGT::ObjectDistances  results;
  searchQuery.setResults(&results);
  searchQuery.setSize(10);
  searchQuery.setEpsilon(0.1);
  index.search(searchQuery);
  cout << "Query No." << queryID << endl;
  cout << "Rank\tID\tDistance" << setprecision(6) << fixed << endl;
  for (size_t i = 0; i < results.size(); i++) {
    cout << i + 1 << "\t" << results[i].id << "\t" << results[i].distance << "\t" << words[results[i].id - 1] << endl;
  }
  cout << endl;
  return 0;
}
```

--------------------------------

### Build NGT on Ubuntu

Source: https://github.com/yahoojapan/ngt/blob/main/README-jp.md

Builds the NGT library on Ubuntu. This involves installing BLAS and LAPACK development libraries, unzipping the source, configuring with CMake, compiling, and installing.

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

--------------------------------

### Dataset Generation for NGT

Source: https://github.com/yahoojapan/ngt/wiki/Practical-Examples-Using-Ngt-Command

Generates a dataset in NGT registration format from fastText vectors. It downloads a large English word vector dataset, extracts relevant data, and creates an '_objects.ssv_' file containing 1 million objects. It then extracts three objects from the middle of this file to serve as queries, saving them into '_queries.ssv_'.

```shell
curl -O https://dl.fbaipublicfiles.com/fasttext/vectors-english/wiki-news-300d-1M-subword.vec.zip
zcat wiki-news-300d-1M-subword.vec.zip | tail -n +2 | cut -d " " -f 2- > objects.ssv
head -100000 objects.ssv | tail -3 > queries.ssv
```

--------------------------------

### NGTpy (pybind11) Index Creation and Search

Source: https://github.com/yahoojapan/ngt/blob/main/python/README.md

Demonstrates creating an NGT index, inserting vectors, saving the index, and performing a search using the ngtpy library. This sample uses pybind11 for potentially faster processing.

```Python
import ngtpy
import random


dim = 10
nb = 100
vectors = [[random.random() for _ in range(dim)] for _ in range(nb)]
query = vectors[0]

ngtpy.create(b"tmp", dim)
index = ngtpy.Index(b"tmp")
index.batch_insert(vectors)
index.save()

results = index.search(query, 3)
for i, (id, distance) in enumerate(results) :
    print(str(i) + ": " + str(id) + ", " + str(distance))
    object = index.get_object(id)
    print(object)
```

--------------------------------

### ONNG Construction: ANNG with More Edges

Source: https://github.com/yahoojapan/ngt/wiki/Optimization-Examples-Using-Ngt-Command

Creates an ANNG with a higher number of initial edges (e.g., 100) to serve as a base for ONNG generation. This is a prerequisite for ONNG construction.

```bash
ngt create -d 300 -D c -E 100 -S -2 fasttext.anng-100 objects.ssv
```

--------------------------------

### NGT Python Package

Source: https://github.com/yahoojapan/ngt/wiki/ホーム

Information regarding the Python package for NGT, including installation instructions via PyPI.

```Python
# NGT Python Package
# Available via PyPI
# pip install ngt
```

--------------------------------

### Install NGT on macOS

Source: https://github.com/yahoojapan/ngt/blob/main/README.md

Installs the NGT library on macOS using the Homebrew package manager.

```shell
brew install ngt
```

--------------------------------

### NGT CMake Project Setup

Source: https://github.com/yahoojapan/ngt/blob/main/CMakeLists.txt

Initializes the CMake build system for the NGT project, setting the minimum required version and project name. It also extracts version information and configures the build type.

```cmake
cmake_minimum_required(VERSION 3.5...3.31)

project(ngt)

file(STRINGS "VERSION" ngt_VERSION)
message(STATUS "VERSION: ${ngt_VERSION}")
string(REGEX MATCH "^[0-9]+" ngt_VERSION_MAJOR ${ngt_VERSION})

set(ngt_VERSION ${ngt_VERSION})
set(ngt_SOVERSION ${ngt_VERSION_MAJOR})

if(NOT CMAKE_BUILD_TYPE)
    set(CMAKE_BUILD_TYPE "Release")
endif(NOT CMAKE_BUILD_TYPE)
string(TOLOWER ${CMAKE_BUILD_TYPE} CMAKE_BUILD_TYPE_LOWER)
message(STATUS "CMAKE_BUILD_TYPE: ${CMAKE_BUILD_TYPE}")
message(STATUS "CMAKE_BUILD_TYPE_LOWER: ${CMAKE_BUILD_TYPE_LOWER}")

if(${NGT_SHARED_MEMORY_ALLOCATOR})
    set(NGT_QBG_DISABLED TRUE)
endif(${NGT_SHARED_MEMORY_ALLOCATOR})
```

--------------------------------

### Install NGT on macOS via Homebrew

Source: https://github.com/yahoojapan/ngt/blob/main/README-jp.md

Installs the NGT library on macOS using the Homebrew package manager.

```bash
brew install ngt
```

--------------------------------

### ANNG Quick Optimization: Search Parameters

Source: https://github.com/yahoojapan/ngt/wiki/Optimization-Examples-Using-Ngt-Command

Optimizes search parameters for ANNG, such as explored edges and memory prefetch, without modifying the index data structure. Allows specifying accuracy directly.

```bash
ngt optimize-search-parameters fasttext.anng
ngt search -n 10 -a 0.9 fasttext.anng queries.ssv
```

--------------------------------

### Build NGT on CentOS

Source: https://github.com/yahoojapan/ngt/blob/main/README-jp.md

Builds the NGT library on CentOS. This process involves installing development libraries for BLAS and LAPACK, unzipping the source, configuring with CMake, compiling, and installing.

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

--------------------------------

### Search ANNG Index

Source: https://github.com/yahoojapan/ngt/wiki/Practical-Examples-Using-Python

Searches the constructed ANNG index for approximate nearest neighbors of a given query object. It retrieves results and displays them along with the corresponding words.

```python
# search.py
import ngtpy

with open('words.tsv', 'r') as fin:
    words = list(map(lambda x: x.rstrip('\n'), fin.readlines()))

index = ngtpy.Index('fasttext.anng') # open the index
query_id = 10000
query_object = index.get_object(query_id) # get the object

result = index.search(query_object, epsilon = 0.10) # approximate nearest neighbor search
print('Query={}'.format(words[query_id]))
for rank, object in enumerate(result):
    print('{}	{}	{:.6f}	{}'.format(rank + 1, object[0], object[1], words[object[0]]))
```

--------------------------------

### Build NGT on Linux (Disable QG/QBG)

Source: https://github.com/yahoojapan/ngt/blob/main/README-jp.md

Builds the NGT library on Linux, disabling the Quantized Graph (QG) and Quantized Blob Graph (QBG) features. This requires unzipping the source, creating a build directory, configuring with CMake, compiling, and installing.

```bash
unzip NGT-x.x.x.zip
cd NGT-x.x.x
mkdir build
cd buildcmake -DNGT_QBG_DISABLED=ON ..
make
make install
ldconfig /usr/local/lib
```

--------------------------------

### Convert fastText Vectors to NGT Format

Source: https://github.com/yahoojapan/ngt/wiki/Practical-Examples-Using-Cpp

This Python script converts the downloaded fastText vector file into a format readable by NGT sample scripts. It separates the data into objects (vectors) and words, writing them to 'objects.tsv' and 'words.tsv' respectively.

```python
# dataset.py 
with open('wiki-news-300d-1M-subword.vec', 'r') as fi,
     open('objects.tsv', 'w') as fov, open('words.tsv', 'w') as fow:
    n, dim = map(int, fi.readline().split())
    fov.write('{0}\t{1}\n'.format(n, dim))
    for line in fi:
        tokens = line.rstrip().split(' ')
        fow.write(tokens[0] + '\n')
        fov.write('{0}\n'.format('\t'.join(tokens[1:])))
```

--------------------------------

### Build NGT on macOS

Source: https://github.com/yahoojapan/ngt/blob/main/README-jp.md

Builds the NGT library on macOS using Homebrew for package management. It installs CMake and libomp, then configures and builds NGT with OpenMP support.

```bash
/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
```

--------------------------------

### Search with ONNG

Source: https://github.com/yahoojapan/ngt/wiki/Optimization-Examples-Using-Ngt-Command

Searches using an ONNG in a similar manner to ANNG. ONNGs generally offer higher search accuracy, potentially at a slightly increased search time compared to a basic ANNG, but can outperform ANNGs when higher accuracies are required.

```bash
ngt search -n 10 fasttext.onng queries.ssv
```

--------------------------------

### NGT Index Creation and Usage Example

Source: https://github.com/yahoojapan/ngt/blob/main/python/ngt/README.md

Demonstrates how to create an NGT index, insert objects, save the index, and perform a nearest neighbor search. It also shows how to retrieve objects by their ID.

```Python
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)
# You can also insert objects from a file like this.
# index.insert_from_tsv('list.dat')

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)
```

--------------------------------

### Optional ANNG Refinement (RANNG)

Source: https://github.com/yahoojapan/ngt/wiki/Optimization-Examples-Using-Ngt-Command

Refines the ANNG to improve accuracy by searching with each node, resulting in RANNG. This is an optional step that requires significant processing time and should be executed after building indexes.

```bash
ngt refine-anng fasttext.anng fasttext.ranng
```

--------------------------------

### Construct Optimized ANNG Index

Source: https://github.com/yahoojapan/ngt/wiki/Optimization-Examples-Using-Cpp

Constructs an ANNG index by inserting objects without initial indexing, preparing for edge optimization. It reads objects from 'objects.tsv', sets properties like dimension and distance type, and creates an initial index file.

```C++
#include "NGT/Index.h"
using namespace std;
int main(int argc, char **argv)
{
  ifstream      is("objects.tsv");
  string        line;
  getline(is, line);
  stringstream  linestream(line);
  NGT::Property property;
  size_t n;
  linestream >> n;
  linestream >> property.dimension;
  property.objectType   = NGT::ObjectSpace::ObjectType::Float;
  property.distanceType = NGT::Index::Property::DistanceType::DistanceTypeCosine;
  string path("fasttext.anng");
  NGT::Index::create(path, property);
  NGT::Index    index(path);
  while (getline(is, line)) {
    stringstream        linestream(line);
    vector<float>       object;
    while (!linestream.eof()) {
      float value;
      linestream >> value;
      object.push_back(value);
    }
    index.append(object);
  }
  index.save();
  return 0;
}
```

--------------------------------

### NGT ANNG Index Construction

Source: https://github.com/yahoojapan/ngt/wiki/Practical-Examples-Using-Ngt-Command

Constructs an Approximate Nearest Neighbor Graph (ANNG) index using the 'ngt create' command. The index is built with a dimension of 300, using cosine similarity ('c') as the metric space, and the 'objects.ssv' file as the input data. The output index is named 'fasttext.anng'.

```shell
ngt create -d 300 -D c fasttext.anng objects.ssv
```

--------------------------------

### NGT ANNG Index Search

Source: https://github.com/yahoojapan/ngt/wiki/Practical-Examples-Using-Ngt-Command

Searches the constructed ANNG index ('fasttext.anng') using the provided query data ('queries.ssv'). The command retrieves the top 10 nearest neighbors for each query. The output includes the query number, rank, ID of the neighbor, and the distance. It also reports query time and memory usage.

```shell
ngt search -n 10 fasttext.anng queries.ssv
```

--------------------------------

### NGT ANNG Index Search with Adjusted Accuracy

Source: https://github.com/yahoojapan/ngt/wiki/Practical-Examples-Using-Ngt-Command

Performs a search on the NGT ANNG index ('fasttext.anng') with the query data ('queries.ssv'), specifying a higher accuracy by setting the 'search_range_coefficient' to 0.15. This allows for a trade-off between query time and search accuracy.

```shell
ngt search -n 10 -e 0.15 fasttext.anng queries.ssv
```

--------------------------------

### Construct ANNG Index with Cosine Similarity

Source: https://github.com/yahoojapan/ngt/wiki/Practical-Examples-Using-Cpp

This C++ code constructs an Approximate Nearest Neighbor (ANN) graph of type ANNG using cosine similarity. It reads data from 'objects.tsv', configures the NGT index properties (dimension, object type, distance type), appends objects, creates the index with a specified number of threads, and saves it.

```cpp
// construct-fasttext.cpp                                                                                                                    
#include        "NGT/Index.h"
using namespace std;
int main(int argc, char **argv)
{
  ifstream      is("objects.tsv");
  string        line;
  getline(is, line);
  stringstream  linestream(line);
  NGT::Property property;
  size_t n;
  linestream >> n;
  linestream >> property.dimension;
  property.objectType   = NGT::ObjectSpace::ObjectType::Float;
  property.distanceType = NGT::Index::Property::DistanceType::DistanceTypeCosine;
  string path("fasttext.anng");
  NGT::Index::create(path, property);
  NGT::Index    index(path);
  index.disableLog();
  while (getline(is, line)) {
    stringstream        linestream(line);
    vector<float>       object;
    while (!linestream.eof()) {
      float value;
      linestream >> value;
      object.push_back(value);
    }
    index.append(object);
  }
  index.createIndex(16);        // 16 is the number of threads to construct.                                                                 
  index.save();
  return 0;
}
```

--------------------------------

### NGT Quantized Graph Creation for ONNG

Source: https://github.com/yahoojapan/ngt/blob/main/bin/qbg/README.md

Creates and initializes a quantized graph for an ONNG.

```bash
$ qbg create-qg onng-40
```

--------------------------------

### NGT Quantized Graph Building for ONNG

Source: https://github.com/yahoojapan/ngt/blob/main/bin/qbg/README.md

Builds the quantized graph for an ONNG.

```bash
$ qbg build-qg onng-40
```

--------------------------------

### ngt PREP-PQ Command

Source: https://github.com/yahoojapan/ngt/blob/main/bin/ngt/README.md

Executes preprocessing for product quantization data type on an ngt index. This command builds a QBG data structure for object quantization.

```bash
ngt prep-pq index

Parameters:
  index: Specify the name of the existing index where the data type is set to product quantization and objects are appended. This command builds a QBG data structure to quantize the objects.
```

--------------------------------

### NGT Index Creation with Higher Performance Options

Source: https://github.com/yahoojapan/ngt/blob/main/bin/qbg/README.md

Builds an ANNG index with more edges for potentially higher performance.

```bash
$ ngt create -d 128 -o f -D 2 -E 40 anng-40 sift-128-euclidean.tsv
```

--------------------------------

### NGT Quantized Graph Creation

Source: https://github.com/yahoojapan/ngt/blob/main/bin/qbg/README.md

Creates and initializes a quantized graph from an existing index.

```bash
$ qbg create-qg anng
```

--------------------------------

### NGT Quantized Graph Building

Source: https://github.com/yahoojapan/ngt/blob/main/bin/qbg/README.md

Builds the quantized graph, optimizing and constructing the inverted index.

```bash
$ qbg build-qg anng
```

--------------------------------

### Create Optimized ANNG Index

Source: https://github.com/yahoojapan/ngt/wiki/Optimization-Examples-Using-Python

Creates an ANNG index with default settings and inserts objects from a file. This is the first step before optimizing the number of initial edges.

```Python
# create-optimized-anng.py
import ngtpy

index_path = 'fasttext.anng'
with open('objects.tsv', 'r') as fin:
    n, dim = map(int, fin.readline().split())
    ngtpy.create(index_path, dimension=dim, distance_type='Cosine')               
    index = ngtpy.Index(index_path) # open the index 
    for line in fin:
        object = list(map(float, line.rstrip().split('	')))
        index.insert(object) # insert objects
index.save() # save the index
```

--------------------------------

### QBG Create Command

Source: https://github.com/yahoojapan/ngt/blob/main/bin/qbg/README.md

Creates and initializes a QBG directory for the quantized blob graph. Allows configuration of dimensions, object type, distance function, and cluster data type.

```bash
qbg create [-d number_of_dimension] [-P number_of_extended_dimensions] [-O object_type] [-D distance_function] [-C cluster_data_type] index

*index*: Specify the name of the directory for QBG.
**-d** *number_of_dimensions*: Specify the number of dimensions of registration data.
**-P** *number_of_extended_dimensions*: Specify the number of the extended dimensions. The number should be greater than or equal to the number of the genuine dimensions, and also should be a multiple of 4. When this option is not specified, the smallest multiple of 4 that is greater than the dimension is set to the number of the extended dimensions.
**-O** *object_type*: Specify the data object type.
- __c__: 1 byte unsigned integer
- __f__: 4 byte floating point number (default)
**-D** *distance_function*: Specify the distance function.
- __2__: L2 distance (default)
- __c__: Cosine similarity
**-C** *cluster_data_type*: Specify the cluster data type.
- __pq4__: 4 bit product quantization (default)
- __sq8__: 1 byte scalar quantization
```

--------------------------------

### NGT Project CMake Configuration

Source: https://github.com/yahoojapan/ngt/blob/main/samples/CMakeLists.txt

This snippet shows the main CMake configuration for the NGT project. It sets up include and link directories and conditionally adds subdirectories for various sample applications based on the UNIX environment and a flag for disabling QBG samples.

```cmake
if( ${UNIX} )
	include_directories("${PROJECT_SOURCE_DIR}/lib" "${PROJECT_BINARY_DIR}/lib/")
	link_directories("${PROJECT_BINARY_DIR}/lib/NGT")
	add_subdirectory("${PROJECT_SOURCE_DIR}/samples/hamming-uint8")
	add_subdirectory("${PROJECT_SOURCE_DIR}/samples/l2-uint8")
	add_subdirectory("${PROJECT_SOURCE_DIR}/samples/l2-uint8-range-search")
	add_subdirectory("${PROJECT_SOURCE_DIR}/samples/cosine-float")
	add_subdirectory("${PROJECT_SOURCE_DIR}/samples/jaccard-sparse")
	if(NOT DEFINED NGT_QBG_DISABLED)
		add_subdirectory("${PROJECT_SOURCE_DIR}/samples/qg-l2-float")
		add_subdirectory("${PROJECT_SOURCE_DIR}/samples/qg-capi")
		add_subdirectory("${PROJECT_SOURCE_DIR}/samples/qbg-capi")
	endif()
endif()
```

--------------------------------

### Convert fastText Dataset for NGT

Source: https://github.com/yahoojapan/ngt/wiki/Practical-Examples-Using-Python

Converts the downloaded fastText vector file into a format suitable for NGT scripts. It separates objects (vectors) and words into TSV files.

```python
# dataset.py 
with open('wiki-news-300d-1M-subword.vec', 'r') as fi,
     open('objects.tsv', 'w') as fov, open('words.tsv', 'w') as fow:
    n, dim = map(int, fi.readline().split())
    fov.write('{0}\t{1}\n'.format(n, dim))
    for line in fi:
        tokens = line.rstrip().split(' ')
        fow.write(tokens[0] + '\n')
        fov.write('{0}\n'.format('\t'.join(tokens[1:])))
```

--------------------------------

### Build Quantized Blob Graph

Source: https://github.com/yahoojapan/ngt/blob/main/bin/qbg/README.md

Commands for creating, appending objects to, and building a quantized blob graph index. This process prepares the graph for efficient nearest neighbor searches.

```bash
$ qbg create -d 128 -D 2 -N 128 qbg-index
$ qbg append qbg-index sift-128-euclidean.tsv
$ qbg build qbg-index
```

--------------------------------

### Build Optimized ANNG Index

Source: https://github.com/yahoojapan/ngt/wiki/Optimization-Examples-Using-Cpp

Builds the indexes for an ANNG graph after the number of edges has been optimized. This step constructs the graph structure using a specified number of threads.

```C++
#include "NGT/Index.h"
using namespace std;
int main(int argc, char **argv)
{
  NGT::Index    index("fasttext.anng");
  index.createIndex(16);        // 16 is the number of threads to construct.
  index.save();
  return 0;
}
```

--------------------------------

### NGT Index Object Retrieval and Count

Source: https://github.com/yahoojapan/ngt/blob/main/python/README-ngtpy.md

Provides methods to retrieve specific objects from the index by their ID and to get the total number of objects currently stored in the index.

```python
get_object(self: ngtpy.Index, object_id: int) -> List[float]
  Retrieves an object from the index using its ID.

get_num_of_objects() -> int
  Returns the total number of objects stored in the index.
```

--------------------------------

### QBG Build Command

Source: https://github.com/yahoojapan/ngt/blob/main/bin/qbg/README.md

Quantizes objects and builds a quantized graph into the specified QBG index. Supports optimization through parameters for quantization objects, rotation, trials, and recursive clustering.

```bash
qbg build [-o number_of_objects_for_quantization] [-P rotation] [-M number_of_trials] [-B recursive_clustering_parameters] index

*index*: Specify the name of the directory for the existing index such as ANNG or ONNG to be quantized. The index only with L2 distance and normalized cosine similarity distance can be quantized. You should build the ANNG or ONNG with normalized cosine similarity in order to use cosine similarity for the quantized graph.
**-o** *number_of_objects_for_quantization*: Specify the number of object for quantization and optimization. The number should be less than or equal to the number of the registered objects.
**-P** *rotation*: Specify the transform matrix type for the inserted and query object to optimize the subvector quantization.
- __r__: Rotation matrix.
- __R__: Rotation and repositioning matrix.
- __p__: Repositioning matrix.
- __n__: No matrix.
**-M** *number_of_trials*: Specify the number of trials to optimize the subvector quantization.
**-B** *recursive_clustering_parameters*: Specify the number of clusters and samples for recursive clustering. The parameters are specified as `-B s₁:c₁,s₂:c₂,s₃:c₃`. Here, sₙ and cₙ represent the number of samples used for k-means and the number of clusters, respectively, for the n-th tier of the hierarchy. If sₙ or cₙ is set to 0, an appropriate value will be assigned automatically.
```

--------------------------------

### build-qg Command

Source: https://github.com/yahoojapan/ngt/blob/main/bin/qbg/README.md

Quantizes objects of a specified index and builds a quantized graph within that index. Allows configuration of quantization objects, maximum edges, and optimization trials.

```bash
$ qbg build-qg [-o number_of_objects_for_quantization] [-E max_number_of_edges] [-M number_of_trials] index

*index*
Specify the name of the directory for the existing index such as ANNG or ONNG to be quantized. The index only with L2 distance and normalized cosine similarity distance can be quantized. You should build the ANNG or ONNG with normalized cosine similarity in order to use cosine similarity for the quantized graph.

**-o** *number_of_objects_for_quantization*
Specify the number of object for quantization and optimization. The number should be less than or equal to the number of the registered objects.

**-E** *max_number_of_edges*
Specify the maximum number of edges to build a qunatized graph. Since every 16 objects that are associated with edges of each node are processed, the number should be a multiple of 16.

**-M** *number_of_trials*
Specify the number of trials to optimize the subvector quantization.
```

--------------------------------

### Adjusting Search Accuracy (Epsilon)

Source: https://github.com/yahoojapan/ngt/wiki/Practical-Examples-Using-Python

Demonstrates how to adjust the accuracy of the approximate nearest neighbor search by modifying the epsilon parameter. Higher epsilon increases accuracy but may increase query time.

```python
index.search(query_object, epsilon = 0.15)
```

--------------------------------

### Set Expected Accuracy for Search

Source: https://github.com/yahoojapan/ngt/wiki/Optimization-Examples-Using-Cpp

Demonstrates how to set an expected accuracy value for ANNG search queries after search parameters have been optimized. This replaces the need to specify epsilon values directly.

```C++
  searchQuery.setExpectedAccuracy(0.9);  // instead of setEpsilon()
```

--------------------------------

### NGT Index Creation

Source: https://github.com/yahoojapan/ngt/blob/main/bin/qbg/README.md

Creates an ANNG (Approximate Nearest Neighbor Graph) index. Supports specifying dimensions, output format, and depth.

```bash
$ ngt create -d 128 -o f -D 2 anng sift-128-euclidean.tsv
```

--------------------------------

### NGT Supported Programming Languages

Source: https://github.com/yahoojapan/ngt/wiki/Home

NGT is available for multiple programming languages, allowing integration into various projects. Links to specific language implementations and examples are provided.

```APIDOC
Supported Programming Languages:
  - [Python](../blob/master/python/README.md)
  - [Ruby](https://github.com/ankane/ngt)
  - [Rust](https://crates.io/crates/ngt)
  - [Go](https://github.com/yahoojapan/gongt)
  - C++ ([sample code](../blob/master/samples))
  - C ([C APIs](../blob/master/lib/NGT/Capi.h))
```

--------------------------------

### NGT Project CMake Configuration

Source: https://github.com/yahoojapan/ngt/blob/main/bin/CMakeLists.txt

Configures the NGT project using CMake. It includes directories for libraries, links to the NGT library, and adds subdirectories for the NGT and optionally QBG components based on defined variables.

```cmake
if(${UNIX})
	include_directories("${PROJECT_SOURCE_DIR}/lib" "${PROJECT_BINARY_DIR}/lib/")
	link_directories("${PROJECT_BINARY_DIR}/lib/NGT")
	add_subdirectory("${PROJECT_SOURCE_DIR}/bin/ngt")
	if(NOT DEFINED NGT_QBG_DISABLED OR (NOT ${NGT_QBG_DISABLED}))
		add_subdirectory("${PROJECT_SOURCE_DIR}/bin/qbg")
        endif()
endif()
```

--------------------------------

### QBG Commands for Quantized Blob Graph (QBG)

Source: https://github.com/yahoojapan/ngt/blob/main/bin/qbg/README.md

Commands specific to the Quantized Blob Graph (QBG) data structure. These include creating, appending, building, and searching the QBG index.

```bash
Commands for the quantized blob graph:
- create
- append
- build
- search
```

--------------------------------

### Optimize ANNG Number of Edges

Source: https://github.com/yahoojapan/ngt/wiki/Optimization-Examples-Using-Cpp

Optimizes the number of initial edges for an ANNG index by analyzing inserted objects. This script calculates the optimal edge count and updates the index profile accordingly.

```C++
#include "NGT/Index.h"
#include "NGT/GraphOptimizer.h"

using namespace std;
int main(int argc, char **argv)
{
  NGT::GraphOptimizer::ANNGEdgeOptimizationParameter parameter;
  NGT::GraphOptimizer graphOptimizer(false);
  graphOptimizer.optimizeNumberOfEdgesForANNG("fasttext.anng", parameter);
}
```

--------------------------------

### create-qg Command

Source: https://github.com/yahoojapan/ngt/blob/main/bin/qbg/README.md

Creates and initializes a QG directory for the quantized graph within an NGT index directory. It inserts data from the NGT index into the QG index. Supports specifying extended and subvector dimensions.

```bash
$ qbg create-qg [-P number_of_extended_dimensions] [-Q number_of_subvector_dimensions] index

*index*
Specify the name of the directory for the existing index such as ANNG or ONNG to be quantized. The index only with L2 distance and normalized cosine similarity distance can be quantized. You should build the ANNG or ONNG with normalized cosine similarity in order to use cosine similarity for the quantized graph.

**-P** *number_of_extended_dimensions*
Specify the number of the extended dimensions. The number should be greater than or equal to the number of the genuine dimensions, and also should be a multiple of 4. When this option is not specified, the smallest multiple of 4 that is greater than the dimension is set to the number of the extended dimensions.

**-Q** *number_of_subvector_dimension*
Specify the number of the subvector dimensions. The number should be less than or equal to the the number of the extended dimensions, and also should be a divisor of the number of the extended dimensions. When this option is not specified, one is set to the number of the subvector dimensions.
```

--------------------------------

### NGT Available Commands

Source: https://github.com/yahoojapan/ngt/blob/main/bin/ngt/README.md

The NGT tool supports several commands for managing and querying proximity search indexes. These commands include creating indexes, appending data, preparing for PQ (Product Quantization), performing searches, removing data, pruning the index, reconstructing the graph, and rebuilding the index.

```APIDOC
NGT Commands:

- create: Creates a new NGT index.
- append: Appends data to an existing NGT index.
- prep-pq: Prepares the index for Product Quantization.
- search: Performs a proximity search on the index.
- remove: Removes data from the index.
- prune: Prunes the index (not recommended).
- reconstruct-graph: Reconstructs the graph structure of the index.
- rebuild: Rebuilds the entire index.
```

--------------------------------

### ngt create command

Source: https://github.com/yahoojapan/ngt/blob/main/bin/ngt/README.md

Creates and initializes an NGT index directory, optionally registering vector data. Supports various parameters for configuring index generation, including dimensions, threads, batch processes, index types (graph-only or graph+tree), graph types (ANNG, KNNG, BKNNG), edge reduction, search range, number of edges, object type, and distance function.

```bash
$ ngt create -d no_of_dimensions [-p no_of_threads] [-b no_of_batch_processes] 
    [-i index_type] [-g graph_type] [-t edge_reduction_threshold] 
    [-e search_range_coefficient] [-E no_of_edges] [-S no_of_edges_at_search_time] 
    [-o object_type] [-D distance_function] [-n no_of_registration_data] 
    index [registration_data]
```

--------------------------------

### Disable QG and QBG

Source: https://github.com/yahoojapan/ngt/blob/main/README-jp.md

QG and QBG require BLAS and LAPACK libraries. If you do not wish to install these libraries and do not use QG or QBG, you can disable them using the following CMake command.

```bash
cmake -DNGT_QBG_DISABLED=ON ..
```

--------------------------------

### QBG Commands for Quantized Graph (QG)

Source: https://github.com/yahoojapan/ngt/blob/main/bin/qbg/README.md

Commands specific to the Quantized Graph (QG) data structure. These include creating, building, and searching the QG index.

```bash
Commands for the quantized graph:
- create-qg
- build-qg
- search-qg
```

--------------------------------

### Refine ANNG Index

Source: https://github.com/yahoojapan/ngt/wiki/Optimization-Examples-Using-Cpp

Refines an ANNG index (RANNG) to improve the accuracy of neighboring nodes by performing searches with each node. This is an optional step that requires significant processing time but enhances search performance.

```C++
#include "NGT/Index.h"
#include "NGT/GraphOptimizer.h"
using namespace std;
int main(int argc, char **argv)
{
  NGT::Index    index("fasttext.anng");
  NGT::GraphReconstructor::refineANNG(index, false);
  index.save("fasttext.ranng");
  return 0;
}
```

--------------------------------

### Create PANNG Index

Source: https://github.com/yahoojapan/ngt/blob/main/bin/ngt/README.md

Creates a PANNG (Pruned ANNG) index. Similar to ONNG, but includes parameters for the number of forced and selectively pruned edges.

```Shell
$ ngt create -i g|t -g a -S 0 -e 0.1 -E no_of_edges -d dimensionality_of_data -o data_type -D distatnce_type panng-index vector-data.dat
```

```Shell
$ ngt create -i t -g a -S 0 -e 0.1 -E 10 -d 128 -o c -D 2 panng-index vector-data.dat
```
Tokens:
Raw