Nearest Neighbor Search with Neighborhood Graph and Tree for High-dimensional Data
Neighborhood Graph and Tree for Indexing High-dimensional Data
Home / Installation / Command / License / Publications / About Us / 日本語
NGT provides commands and a library for performing high-speed approximate nearest neighbor searches against a large volume of data in high dimensional vector data space (several ten to several thousand dimensions).
This repository provides the following methods.
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 QB and QBG with this option.
$ 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
$ 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
$ 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
$ /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
$ cmake ..
$ make
$ make install
$ brew install ngt
The following build parameters are available
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.
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 ..
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 ..
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 ..
The followings are the results of ann benchmarks for NGT v2.0.0 where the timeout is 5 hours on an AWS c5.4xlarge instance.
Copyright (C) 2015 Yahoo Japan Corporation
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
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
This project requires contributors to accept the terms in the Contributor License Agreement (CLA).
Please note that contributors to the NGT repository on GitHub (https://github.com/yahoojapan/NGT) shall be deemed to have accepted the CLA without individual written agreements.