高次元ベクトルデータにおいて高速な近傍検索を実現するNGTの公開

Yahoo! JAPAN研究所の岩崎です。

私は主に特定物体認識の研究開発を行っていますが、その一方で特定物体認識において必須技術である高次元ベクトルデータの近傍検索の研究開発も行っています。近傍検索の一種であるk最近傍検索とは、クエリとしてベクトルデータが与えられた時に、クエリと空間内に点在するベクトルデータとの距離に基づき近い順にk個のデータを検索する、ことです。kが5の場合の最近傍検索の例を図1に示します。図中の数字は距離の順位で、青い点が検索結果となるデータです。

空間内のすべてのデータとの距離を計算すると時間がかかるので、高速化のためにインデックスを利用します。インデックスを用いることにより数次元といった低次元のベクトルデータ空間では高速な検索が比較的容易に実現できます。しかし、インデックスを用いても100次元を超えるような高次元ベクトルデータの場合には高速に検索することが困難となります。Yahoo! JAPAN 研究所では高次元ベクトルデータにおいても高速な検索を実現するためにグラフとツリーを組み合わせたインデックスを用いる近傍検索手法を研究開発しています。図2にそのインデックスの構造を示します。図のようにツリーの上から下へたどる（青の矢印）ことでクエリの近傍候補となるデータを取得した後に、そこからグラフをたどる（緑の矢印）ことで網羅的にデータを探索します。詳細は参考文献をご覧下さい。

研究成果としてこの高速な近傍検索を実現するソフトウエア（NGT）を公開致します。研究の発端は画像特徴量の検索ですが、NGTはベクトルデータであれば検索が可能ですので、さまざまな用途にご利用いただけます。なお、代表的なツリー型やハッシュ型のインデックスよりも高速なk最近傍検索が実現できることを実験で確認しています。NGTにはコマンドラインツール（ngt）とライブラリ（libngt）、そして、その全ソースコードが含まれています。なお、ライセンス上NGTの商用利用はお控えください。

コマンドツール（ngt）の主な機能は以下の通りです。

• インデックスの生成・データ登録
• インデックスへのデータ追加登録
• 近傍検索
• インデックスからのデータ削除

NGTは共有メモリ上にインデックスを配置することも可能です。技術戦略本部の宮崎が作成した共有メモリ用のコードを利用することにより、複数のプロセスから同一インデックスを利用する場合にメモリ使用量を抑制できます。また、インデックスのロード時間を短縮する効果もあります。共有メモリを利用するにはビルド環境構築時のオプションを変更した後にビルドする必要があります。詳しくは、NGTに同梱されているREADMEをご覧ください。

参考文献

1. 岩崎雅二郎, 近似k最近傍グラフによる距離空間の近傍検索, 情報処理学会論文誌：データベース, Vol. 3, No. 1. pp.18-28, 2010
2. 岩崎雅二郎, 木構造型インデックスを利用した近似k最近傍グラフによる近傍検索, 情報処理学会論文誌, Vol. 52, No. 2. pp.817-828, 2011
3. 岩崎雅二郎, 商品画像検索へのグラフ構造型インデックスの適用, 画像電子学会誌, Vol. 42, No. 5. pp.633-641, 2013

関連サービス

• monotag

Yahoo! JAPAN研究所 岩崎 雅二郎
（開発協力：技術戦略本部 宮崎 大輔）