局所鋭敏な階層的ハッシュ関数を用いた探索時可変パラメータの高次元近似最近傍探索手法

摘要

近年，局所鋭敏なハッシュ関数を利用した高次元空間の近似最近傍探索手法(LSH)が注目されている.しかしながらLSHは原理的にR-近傍探索手法であり，最近傍探索に適用するには，デー夕の分布の疎密の格差が大きい場合に一律のハッシュ関数では対応できないという問題がある.また，前処理時にデータに応じて最適なハッシュ関数と各種パラメータを決定する必要があり，探索時にパラメータを変更できないという問題もある.本論文では，階層的なハッシュ関数を使用することによりデータの分布によらず効率良く探索でき，また，探索に関するパラメータは前処理時に決定するのではなく実行時に指定できる手法を提案する.様々な条件による人工データと現実データによる実験で，提案手法の有効性を示す.