Help us understand the problem. What is going on with this article?

ヤフーが公開した高次元ベクトルデータにおいて高速な近傍検索を実現するNGTがすごい!!

More than 3 years have passed since last update.

0. 前提知識

ソーシャルデータや多くのユーザーを抱えるWeb・モバイルサービスにとって、
高次元ベクトルデータの扱いに困ることは少なくないと思います。

多くのユーザーの行動データや登録データからユーザー間の類似度を算出したり、
行動データを解析して適切なコンテンツをレコメンドしたりする場合に、データ量によっては計算時間やサーバーの負荷などがボトルネックになり、リアルタイム性を妥協したり、精度を妥協したりすることが出てきてしまうことがあります。

今回ヤフーが公開したNGTというソフトウェアは高次元ベクトルデータにおいて超高速に近傍検索をしてくれるので、実際に使ってみたら結構すごかったので、実際に利用した内容も含めて公開したいと思います。

1. NGTの環境構築

CentOSにngtをインストール

console
wget http://i.yimg.jp/dl/docs/research_lab/ngt-0.0.1.zip 
unzip ngt-0.0.1.zip
cd ngt-0.0.1
mkdir build
cd build 
cmake ..
make 
make install
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib64

2. データの準備&実行

・ヤフーのngtのzipファイルに入っているテストデータで行う場合

console
cd ngt-0.0.1
ngt create -d 128 -o c index ./data/sift-dataset-5k.tsv
ngt search -n 20 index ./data/sift-query-3.tsv

・独自のデータも用意してみる

今回試してみたのは、userがuserに興味を示すようなデータを元にuser間の類似度を算出するというサンプルで試してみました。
user_user_favorite.tsv:userがuserに興味を示した度合いを要素にしたベクトルデータ
example_user_favorite.tsv:その中で抽出した1人のuserの興味ベクトルデータ

console
cd ngt-0.0.1
ngt create -d 128 -o c index ./data/user_user_favorite.tsv
ngt search -n 5 index ./data/example_user_favorite.tsv

3. 結果

特定のuser_idのユーザーとの距離が近い上位5人を取得してみると以下のような結果が得られる。

Rank IN-ID ID Distance
1 151 151 231.003
2 661 661 231.981
3 178 178 237.763
4 2241 2241 244.102
5 558 558 249.453

1列目:距離が近い順位
2列目:user_id
3列目:tsvデータ上のID
4列目:距離

1万×1万の正方行列のベクトルデータの計算でも500ms未満で返ってくるのはマジですごい!!

※残念ながら商用利用は不可なのでご注意を。

okappy
アトラエ取締役CTO兼yenta開発責任者やってます。 エンジニアの横の繋がりを大事にしたいので、何かあればfacebookで気軽にメッセージください。Qiitaの投稿に関することとかしないこととか、なんでもOKです。 http://www.facebook.com/toshi.oka.831
https://yenta.talentbase.io/yenta/?cn=qiita
atrae
People Techカンパニーとして、転職サイトGreen, ビジネスマッチングアプリyenta, 組織改善プラットフォームwevoxなどのサービスを運営。全ての社員が誇りを持てる組織と事業の創造にこだわり、関わる人々がファンとして応援したくなるような魅力ある会社であり続けることを目指しています。
https://atrae.co.jp/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away