【OSS情報アーカイブ】NGT

※当記事に記載されている情報は、古くなっている場合があります。オフィシャルサイトで最新情報をご確認ください。

「NGT」とは

「NGT」基本情報

■概要

NGT(Neighborhood Graph and Tree for Indexing)とは、高次元ベクトルデータ高速検索技術です。ビッグデータ分析/ディープラーニング領域に活用できる技術として注目されています。

■基本説明

NGT(Neighborhood Graph and Tree for Indexing High-dimensional Data)は、高次元ベクトルデータ空間(数十～数千次元)における大量データ(数百万～数千万のデータ項目)に対して高速近似検索を実行するコマンドおよびライブラリを提供します。

NGTは、大量のデータベースの中から、高次元データと定義される「テキストデータ」「画像データ」「商品データ」「ユーザーデータ」などの複数の特徴を持つデータを高速検索できるもので、ビッグデータ分析を高速化する技術です。

AIやIoTの普及によりますます巨大化するビッグデータ分析の高速化を実現するものとして注目されています。

■経緯

NGTは、もともと、Yahoo! JAPANによって「特定物体認識のための画像特徴量類似検索技術」として研究開発されていました。

Yahoo! JAPANは、2016年11月24日、ビッグデータ分析に向けた高次元データ検索技術「NGT(Neighborhood Graph and Tree for Indexing)」をオープンソース公開したことを発表しました。

■オフィシャルサイト情報

オフィシャルサイト

→Yahoo! JAPAN研究所　→NGT(Neighborhood Graph and Tree for Indexing High-dimensional Data)

ライセンス情報

NGTのライセンスは「Apache License v2」です。

詳細について、こちらを参照ください。
→Yahoo! JAPAN研究所　→NGT　→License

ダウンロード

→GitHub　→yahoojapan/NGT

■同様製品

同様な機能を提供する製品として、次のようなものがあります。

オープンソース製品：「Apache Spark」「Apache Drill」など。

「NGT」のユースケース

NGTはベクトルデータを対象とした高速検索を可能とするものであるため、さまざまな用途で活用できます。

■企業内ビッグデータ活用

NGTは「企業内ビッグデータ活用」に貢献できる技術として期待されています。NGTは、入力方法もフォーマットもバラバラで、多くの項目があり構造化されていない大量データに対して高速に照合できます。

企業内に蓄積されているものの活用しきれていないビッグデータを活用しやすい形に置き換える処理を行う「データ連携/変換/統合分野」で活用できます。

眠ったビッグデータ資産を質の高い情報資産ビッグデータに変換することで、「ビッグデータ分析」や「人工知能(AI)技術の精度向上」に利用できるようになり、知見の生成や発見につながります。

■分散表現高速分析

複数の特徴を持つデータ(機械翻訳/文書要約/ニュース記事/商品レコメンド/画像QA/音声認識など)は、分散表現(ベクトルデータ)と呼ばれます。

NGTは、このようなビッグデータに対する高速分析を実現します。

■特定物体認識

「特定物体認識」とは、計算機科学分野において、「画像に写っている物体とまったく同一の物体が写っている画像を膨大なデータベースから発見する処理」を意味します。

「物体特有の特徴が現れている」かつ「データベースが整備されている」などの条件が整えば、比較的容易に特定物体認識を行えます。

この技術は、撮影した商品について「Yahoo!ショッピング」内から最安値で販売している店舗を検索できる実験アプリ「サイヤスカメラ」として実装されています。

→Yahoo! JAPAN Tech Blog　→大規模特定物体認識のショッピングサービスへの適用　〜サイヤスカメラの紹介〜

■類似商品検索

「類似商品検索」とは、「特定物体認識」と同様な技術で、「見た目の特徴から似ている商品を瞬時に検索する」技術です。

これらの技術は、人や物や商品の画像をベクトルデータで表現する技術をベースとしています。対象商品について「色」「模様」「形状」「種別」「価格」「メーカー」などにカテゴリー化し、それぞれに区別された番号を付与することで、対象の商品をすべて数字に置き換えてベクトルデータ化する技術です。

商品Aに類似する商品を探したい場合、商品Aのベクトルデータに類似するデータをベクトル空間上で検索することで類似商品を検索できます。

■広告配信精度向上

NGTは広告配信精度の向上にも活用できます。

多くのユーザーの登録データや行動データから、ユーザー間の類似度分析を行うことで、対象ユーザーに対して適切なコンテンツをレコメンドできます。

「コンテンツのパーソナライズ配信」「運用型ディスプレイ広告配信」などへのさらなる精度向上への応用が期待できます。

■社会安全技術領域

NGTは、「遺伝子検索の高速化による創薬開発支援」や「高度な顔認識技術による犯罪抑止」など社会安全技術領域への活用も期待できます。

「NGT」の主な特徴

「NGT」の主な特徴

■近似k最近傍探索(k-Nearest Neighbor Search)

NGTは「近似k最近傍探索(k-Nearest Neighbor Search)」するためのソフトウエアです。

任意の密ベクトルに対して事前に登録した同次元のベクトルから最も距離が近いベクトルの上位数件(k件)を高速検索します。

「グラフ」と「ツリー」を組み合わせたインデックスを用いる近傍検索手法で、代表的なツリー型やハッシュ型のインデックスよりも高速検索を実現できることを実験で確認されています。

■サポート言語

NGTは以下の言語をサポートしています。
・Python
・Go
・C
・C++

■Python連携

NGTでは、Python用インターフェースを提供します。Python用機械学習ライブラリとNGTを組み合わせて利用できます。

「Pythonでインデックス作成まで行い、NGTで密ベクトル検索を行う」「機械学習の学習時バリデーション」「RNNで作成された中間表現の分析」などのように連携して活用できます。

→Yahoo! JAPAN Tech Blog　→高次元ベクトルデータ検索技術「NGT」のpythonライブラリ公開のお知らせ

「NGT」の高速インデックス技術

「NGT」の高速インデックス技術

■データ精度に関わる処理速度

膨大なデータ量を分析する場合、計算時間やサーバの負荷などがボトルネックとなり、リアルタイム性を妥協したり、精度を妥協したりするケースがあります。

特に高次元データであるほど処理時間を要するため、高次元データに対して高速処理できる技術が望まれていました。

■独自インデックス手法

NGTでは、次元数が多くなっても高速に検索できる独自インデックス手法を搭載することにより、高速検索を実現しています。

「ツリー構造型」と「グラフ構造型」

一般的に、すべてのベクトルデータとの距離を計算すると遅くなるため、事前にインデックスを生成し高速化を図ります。

代表的なインデックス構造として「ツリー構造型」と「グラフ構造型」があります。

インデックス構造のメリット/デメリット

[ツリー構造型]
・メリット＝次元数が少なければ高速検索できる
・デメリット＝次元数が数十次元以上に増えると検索効率が極端に下がる(次元の呪い)

[グラフ構造型]
・メリット＝高精度で検索速度も速い
・デメリット＝インデックス生成時間がツリー構造型よりも長い

NGTの独自組み合わせインデックス

NGTでは「ツリー構造型」と「グラフ構造型」を組み合わせたインデックスを用いています。グラフ型インデックスにデータを逐次登録し、作成中インデックス自体を高速化に用いることで生成時間を短縮しています。

検索段階では、一部、ツリー型インデックスを導入することで、高速な近傍検索を可能にしています。ツリーの上から下へたどることでクエリの近傍候補となるデータを取得した後に、逆にグラフをたどることで網羅的にデータを探索します。

■高速性

NGTは、同様技術と比較して、言語データや画像特徴データを約12倍以上高速に検索できる性能を実現しています。

言語データの場合

200万件/検索精度(適合率)90%のケースでの検索では、NGTは、既存類似高速検索技術「SASH」に対して約4倍高速、「FLANN」に対して約12倍高速という結果が出ています。

2016年8月に開催された自然言語処理分野の国際会議「ACL 2016(54th Annual Meeting of the Association for Computational Linguistics)」で論文として採択され、その有用性が高く評価されています。

画像データの場合

1000万件/検索精度(適合率)90%のケースでは、「NGT」は、「FLANN」に対して約13倍高速という結果が出ています。

■インデックスの共有メモリ配置

NGTは、インデックスを共有メモリ上にも配置できます。

共有メモリを使用すると、複数のプロセスが同一インデックスを使用している場合に、必要なメモリ量を削減できます。

また、インデックスのロード時間を短縮する効果もあります。

　

参考元サイト

• NGT
• Yahoo! JAPAN Tech Blog　→高次元ベクトルデータにおいて高速な近傍検索を実現するNGTの公開
• Yahoo! JAPAN Tech Blog　→高次元ベクトルデータ検索技術「NGT」の性能と使い方の紹介
• Yahoo! JAPAN Tech Blog　→高次元ベクトルデータ検索技術「NGT」のpythonライブラリ公開のお知らせ
• Yahoo! JAPAN Tech Blog　→高次元ベクトルデータ検索技術「NGT」のGo APIとサーバ機能のOSS公開
• Yahoo! JAPAN　→linotice　→街で見かけた服の類似商品を数ミリ秒で検索。Yahoo! JAPAN研究所「高次元ベクトル近傍検索（NGT）」の威力とは──
• ＠IT　→ヤフー、ビッグデータ分析を超高速化する「高次元データの高速検索技術」をOSS化　GitHubで公開
• クラウド Watch　→ヤフー、ビッグデータ分析の高速化を実現する高次元データ検索技術「NGT」をOSSとして公開
• Qiita　→ヤフーが公開した高次元ベクトルデータにおいて高速な近傍検索を実現するNGTがすごい！！

※定期的にメンテナンスを実施しておりますが、一部情報が古い場合がございます。ご了承ください。

この記事のタグ一覧

• NGT

  1

• 一覧はこちら
• 次の記事へ