全2060文字
PR

 NTTは2021年8月17日、類似検索用データベースにデータを速く格納する新技術を開発したと発表した。

 類似検索とは、問い合わせデータに類似するデータをデータベース上から探すタスクである。例えば、「猫」をキーワードに、猫が写っている写真を検索する。類似検索用データベースには、現在さまざまなデータ構造の方式がある。新技術はその中の「アンカーグラフハッシング」という手法におけるハッシング(元データをハッシュ値という固定長データに置き換えること)の時間を短縮する。

 同社は、手書き文字の大規模データベース「mnist」やサイバー攻撃のデータベース「kitsune」などを対象に、新技術と従来手法のデータ格納時間を比較した。その結果、新技術ではハッシングの時間を最大80%以上短縮できることが分かった。画像検索に加え、創薬やがん検診における類似検索で効果が期待できるという。NTTは、2021年8月16~20日に開催するデータベース分野のトップ会議VLDB 2021でこの新技術を発表する。

 アンカーグラフハッシングは、主に類似検索用データベースの作成に使うハッシング手法である。データベースに格納したいデータを「アンカーグラフ」というグラフ構造に変換して、それを基にハッシュ値を計算し、各ハッシュ値に複数データを格納しておく。検索時には、問い合わせデータに対応するハッシュ値を呼び出して、そこに格納しておいた類似データを参照する。検索時間がデータベース内のデータ量によらず一定であるため、膨大な量のデータがあっても高速に検索できる利点がある。

アンカーグラフハッシングの概要
[画像のクリックで拡大表示]
アンカーグラフハッシングの概要
(出所:NTT)

 ただしアンカーグラフハッシングには、ハッシュ値の計算に長い時間がかかるという課題があった。アンカーグラフは、データと、クラスターを代表するデータである「アンカー」で構成する注1)。アンカー同士の類似度を示す行列をつくり、その固有ベクトルからハッシュ値を求めるのが常とう手段である。

注1)アンカーの数はクラスターの数に応じて設定する。また、すべてのデータはいずれかのアンカーに接続している。
アンカーグラフの構造
[画像のクリックで拡大表示]
アンカーグラフの構造
(出所:NTT)

 具体的には、データの個数をn、アンカーの個数をmとすると、このアンカーグラフはn×m行列で表現することができる。各要素の値は、データとアンカーが接続している場合には両者のユークリッド距離の逆数とし注2)、接続していない場合には0とする。したがって、疎行列となる。従来技術では、この行列から、各アンカーがどれだけ同じデータと接続しているか、つまりアンカー同士がどれだけ類似しているかを表すm×m行列を作成していた。この行列は密行列であるため計算負荷が大きい。

注2)実際には、各列の要素の和が1になるように正規化している。
固有値分解の計算時間短縮に向け、三重対角行列を活用
[画像のクリックで拡大表示]
固有値分解の計算時間短縮に向け、三重対角行列を活用
(出所:NTT)