膨大なデータ量を分析する場合、計算時間やサーバの負荷などがボトルネックとなり、リアルタイム性を妥協したり、精度を妥協したりするケースがあります。
特に高次元データであるほど処理時間を要するため、高次元データに対して高速処理できる技術が望まれていました。
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は、インデックスを共有メモリ上にも配置できます。
共有メモリを使用すると、複数のプロセスが同一インデックスを使用している場合に、必要なメモリ量を削減できます。
また、インデックスのロード時間を短縮する効果もあります。
参考元サイト
※定期的にメンテナンスを実施しておりますが、一部情報が古い場合がございます。ご了承ください。
OSS×Cloud ACCESS RANKING