Skip to content

Latest commit

 

History

History
265 lines (187 loc) · 10.4 KB

README-jp.md

File metadata and controls

265 lines (187 loc) · 10.4 KB
Raw

Neighborhood Graph and Tree for Indexing High-dimensional Data

トップ / インストール / コマンド / ライセンス / 関連文献 / About Us / English

大量（数百万から数千万）の高次元ベクトルデータ（数十～数千次元）に対して高速な近似近傍検索を可能とするコマンド及びライブラリを提供します。

ニュース

  • 2024/04/10 内積が利用可能になりました。(v2.1.0)
  • 2022/08/10 QBG(Quantized Blob Graph)およびQG(NGTQGの改良版)が利用可能となりました。ngtqおよびngtqgはqbgで置き換えられました。
  • 2022/02/04 FP16(半精度浮動小数点)が利用可能になりました。(v1.14.0)
  • 2021/03/12 READMEに量子化グラフの結果を追加しました。
  • 2021/01/15 量子化グラフ (NGTQG)を実装した NGT v1.13.0 をリリースしました。
  • 2019/11/04 NGT チュートリアル をリリースしました。
  • 2019/06/26 Jaccard距離が利用可能になりました。(v1.7.6)
  • 2019/06/10 PyPI NGT パッケージ v1.7.5 が利用可能になりました。
  • 2019/01/17 Python NGTはPYPIからpipでインストールが可能になりました。(v1.5.1)
  • 2018/12/14 NGTQ (NGT with Quantization) が利用可能になりました。(v1.5.0)
  • 2018/08/08 ONNGが利用可能になりました。(v1.4.0)

手法

このリポジトリは次の手法を提供します。

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

注：QGおよびQBGはBLASおよびLAPACKライブラリを必要としますので、もし、V1のようにNGT (Graph and tree-based method)のみしか利用しない場合には、QGおよびQBGをこのオプションにより無効化できます。

インストール

ダウンロード

ビルド

Linux （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
  $ cmake ..
  $ make
  $ make install

ビルド済み

macOS

  $ brew install ngt

NGT (Graph and tree-based method)

特徴

  • OS：Linux、macOS
  • データの追加削除が可能
  • 共有メモリ（マップドメモリ）のオプションによるNGTではメモリサイズを超えるデータが利用可能
  • データ型：1バイト整数、4バイト単精度浮動小数点、2バイト半精度浮動小数点
  • 距離関数：L1、L2、コサイン類似度、角度、ハミング、ジャッカード、ポアンカレ、ローレンツ、内積
  • 対応言語：Python、Ruby、PHP、Rust、Go、C、C++
  • 分散サーバ：ngtd, vald

ドキュメント

ユーティリティ

対応言語

ビルドパラメータ

共有メモリの利用

メモリマップドファイルを用いた共有メモリにインデックスを配置することが可能です。共有メモリを利用することにより複数のプロセスが同一のインデックスを利用する場合にメモリ使用量を抑制することが可能です。さらに、メモリにロードできないような大量のオブジェクトを有するインデックスを扱うことが可能なだけでなく、インデックスをオープンする時間を削減することも可能です。共有メモリを利用するにはビルド時の変更が必要となりますので、cmake実行時に以下のパラメータを追加してください。

  $ cmake -DNGT_SHARED_MEMORY_ALLOCATOR=ON ..

注：ロック機能はありませんので、複数プロセスで同一のインデックスを利用する場合には参照のみでご使用ください。

大規模データの利用

約500万以上のオブジェクトをNGTに登録する場合には、検索速度向上のために以下のパラメータを追加してください。

  $ cmake -DNGT_LARGE_DATASET=ON ..

QGおよびQBGの無効化

QGおよびQBGはBLASおよびLAPACKライブラリを必要とします。もし、これらのライブラリをインストールしたくなく、かつ、QGやQBGを利用しない場合には、QGおよびQBGを無効化できます。

  $ cmake -DNGT_QBG_DISABLED=ON ..

QG (Quantized graph-based method)

特徴

  • NGTよりも高性能
  • OS：Linux、macOS
  • 距離関数：L2、コサイン類似度
  • 対応言語：C++, C, Python

ユーティリティ

  • コマンド : qbg

対応言語

  • C++
  • C
  • Python （検索のみ対応）

ビルドパラメータ

QGでは性能向上のためにベクトル空間の回転や残差ベクトルを無効化することを推奨しています。

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

QBG (Quantized blob graph-based method)

特徴

  • 10億ものオブジェクトの検索が可能
  • OS：Linux、macOS
  • 距離関数：L2
  • 対応言語：C++, C, Python

ユーティリティ

  • コマンド : qbg

対応言語

  • C++
  • C
  • Python （検索のみ対応）

ベンチマーク結果

以下はAWS c5.4xlargeのインスタンス上で測定したNGT vのベンチマーク（ann benchmarks）の結果です。

glove-100-angular

gist-960-euclidean

fashion-mnist-784-euclidean

nytimes-256-angular

sift-128-euclidean

ライセンス

Copyright (C) 2015 Yahoo Japan Corporation

ヤフー株式会社はApacheライセンスバージョン2.0の下で本ソフトウェアを公開致します。以下のサイトよりライセンスの内容をご確認頂けます。

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

貢献者ライセンス同意(CLA)

本ソフトウェアへのソースコードのご提供者は貢献者ライセンスに同意して頂きます。

なお、GitHub (https://github.com/yahoojapan/NGT) へのご提供の場合のみ、個別の同意書面なしに、上記貢献者ライセンスに同意して頂いたと見なしますので、ご注意ください。

お問い合わせ

masajiro

関連文献

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)