Anchor Graph Hashing の高速化

多次元データに対する近似類似検索を行う代表的なハッシング手法のひとつである Anchor Graph Hashing に対して検索精度を保ちつつ大幅に高速化する技術を考案しました。Anchor Graph Hashing にはハッシュ値の計算コストが大きいという問題がありましたが、考案した技術により莫大なデータに対して高速にハッシュ値を計算し瞬時に類似検索を行うことができるようになりました。

従来技術ではハッシュ値を計算するためにアンカー同士のつながりを表す m×m の密行列を計算します。従来のアンカーグラフハッシングではこの密行列の固有値分解を計算し、それの固有ベクトルからハッシュ値を計算します。しかし密行列の固有値分解には高い計算コストが必要になるためハッシュ値を計算する時間が長くなってしまいます。
本技術ではハッシュ値を計算するために m×m の密な行列を計算せずに、それと同じ固有値を持つ三重対角行列という疎な行列を計算します。この疎な三重対角行列を用いて固有値の下限値から高速に固有ベクトルを計算することでハッシュ値を計算する処理時間を大幅に低減しました。

本技術は従来手法より最大で 80% 以上計算時間を削減することができ、数千個以上のデータであっても１時間以内に格納し、瞬時に類似検索することを可能にすることができます。

本技術は検索結果を犠牲にすることなく高速にデータの格納を可能にします。アンカーグラフハッシングは創薬やがん検診などの様々なアプリケーションで利用されていて、本成果はこれらのアプリケーションを数千万個規模のデータに対しても実行可能にするブレークスルーとなることが期待されます。

1. Fujiwara, Kanai, Ida, Kumagai, Ueda, “Fast Algorithm for Anchor Graph Hashing”, Proc. VLDB Endow. 14(6): 916-928 (2021).
   http://www.vldb.org/pvldb/vol14/p916-fujiwara.pdf

藤原 靖宏 (Yasuhiro Fujiwara)
コミュニケーション科学基礎研究所 メディア情報研究部 メディア認識研究グループ