ヤフーは2016年11月24日、ビッグデータ分析領域の技術として、画像データや言語データなどのような特徴量数が多い高次元データを高速に検索できるソフト「NGT(Neighborhood Graph and Tree for Indexing)」をオープンソース(OSS)としてGitHubに公開したと発表した。主流の既存類似技術の12倍を超える検索速度を実現したとしている。

既存の類似技術との比較グラフ(1000万件の画像特徴データを対象に検索した場合)
(出所:ヤフー)
[画像のクリックで拡大表示]

 数多くの特徴を数値化したデータに対して検索し、類似のデータを高速に抽出できるソフトである。特徴とは、例えば画像であれば、画像が似ているかどうかを判断するために、画像を構成する複数の特徴を見出し、これを数値化して検索に使う。文章であれば、政治の話題という特徴や、サッカーの話題という特徴など、それぞれ異なる特徴を見出し、これを数値化して検索に使う。

 今回ヤフーは、検索機能を実装したライブラリーとコマンド(ngtコマンド)を公開した。C++で実装してあり、動作確認済みの環境はCentOS release 6.x。ngtコマンドを使って、インデックスの生成、検索、インデックスへのデータの追加/削除などができる。

 NGTのサンプルアプリケーションとして同社は、スマートフォンのカメラを任意の商品に向けてかざすだけで「Yahoo!ショッピング」を検索し、該当製品を最安値で扱うストアの商品ページを特定できる「サイヤスカメラ」(iOSアプリのみ)を開発した。11月18日から実験的に公開している。

 NGTの検索性能を他の検索ソフトと比較したデータも公開している。

 画像データの検索では、適合率90%として1000万件の画像特徴データを対象に検索した場合、既存の類似技術の中で最も高速な技術「直積量子化手法(PQ:Product Quantization)」の検索時間がおよそ7.9ミリ秒かかるのに対して、NGTは最速でおよそ1.4ミリ秒と約5.6倍の高速性を実現した。なお、既存の類似技術の中でも主流の技術「FLANN」と比べると約13.5倍(およそ18.9ミリ秒)も高速だったという。

 言語データの検索では、適合率90%として200万件の言語データを対象に検索を行った場合、既存の類似技術の中で最も高速な技術「SASH」の検索時間がおよそ2.4ミリ秒かかるのに対して、NGTは最速でおよそ0.6ミリ秒と約4.0倍の高速性を実現した。なお、既存の類似技術の中でも主流の技術「FLANN」と比べると約12.3倍(およそ7.4ミリ秒)も高速だったという。