OSS

Yahoo! JAPANが開発、開発協力しているOSSをご紹介します。

NGT

NGTロゴ

大規模高次元ベクトルデータに対して世界トップレベルの高速・高精度な近似近傍検索を提供するソフトウェアです。

近年、深層学習によりさまざまなオブジェクトから、その特徴を的確に示すベクトルデータが容易に抽出できるようになったことから、そのベクトルデータを高速に検索する技術が注目されています。
中でもNGTは世界トップレベルの高速・高精度な検索技術であることがann benchmarksで示されています。

この性能を活用してYahoo! JAPANでもNGTを利用した類似商品検索を提供しています。また、産業界における顕著な業績を認められ、情報処理学会の2019年度業績賞に選ばれました。

特徴

  • OS:Linux、macOS
  • データの追加削除が可能
  • 共有メモリ(マップドメモリ)のオプションによるNGTではメモリサイズを超えるデータが利用可能
  • データ型:1バイト整数、4バイト単精度浮動小数点
  • 距離関数:L1、L2、コサイン類似度、角度、ハミング、ジャッカード
  • 対応言語:PythonRubyRustGo、C、C++
  • 分散サーバ:ngtd, vald
  • 量子化版NGT(NGTQ)は10億ものデータの検索が可能

インデックスの構造

ツリー型とグラフ型の2種類のインデックスにより高速・高精度な検索を実現しています。

検索の流れ

1. ツリーインデックスを用いて与えられたクエリの近傍データをざっくりと取得し、それをグラフの探索の起点とします。

2. 探索起点からクエリに向けてグラフを探索します。

関連リンク