ハッシュを用いた最大類似度探索法に関する研究

摘要

データベース中から入力に対して最も距離の小さいデータを探索する最近傍探索アルゴリズムは,固定次元ベクトルで表現できるデータに対して,距離の公理を満足する尺度を用いた場合にしか適用できない.このような条件を満足しない指紋の照合問題などでは,類似度を最大化するデータを検索する最大類似度探索が用いられる.この手法については,従来様々な方法が研究されてきており,前田らの提案したマッチングスコア行列を用いた最大類似度探索法は高速性と精度の両面で優れた性能を持つことが知られている.ただし,このマッチングスコア行列は,登録したデータ間のマッチングスコアを全て記憶するものであり,データ数の2乗のオーダのメモリを消費するため,数十万個のデータを記録し,最大類似度探索を行うことはほぼ不可能である.本研究では,不定次元パターンを独立性の高い複数のパターンとのマッチングスコア行列を用いて固定次元ベクトル化し,さらにわれわれの提案しているPrincipal Component Hashingと組み合わせることにより,高速な最大類似度探索を実現する方法を提案する.実験を通じて,この提案手法がマッチングスコア行列のサイズを小さくし,高速かつ高精度な最大類似度探索が行えることを実証する.