Locality-Sensitive Hashing

Locality-Sensitive Hashing [1] (以降、LSH)は，Indykらによって提案された最近接点探索の確率的な近似アルゴリズム．

LSHはハッシュテーブルを用いることで高次元のデータセットでも最近接点探索を高速に実行する．

・ハッシュテーブル(hash table)

キーと値の組（エントリと呼ぶ）を複数個格納し，キーに対応する値をすばやく参照するためのデータ構造．

・ハッシュ関数(hash function)

あるデータが与えられた場合にそのデータを代表する数値を得る操作．または，その様な数値を得るための関数のこと．

ハッシュ関数から得られた数値のことをハッシュ値または単にハッシュという．

LSHの重要なポイントは，類似しているデータ間のハッシュ値は一致し，類似していいないデータ間のハッシュ値は異なるようなハッシュ関数を用いることにある．

これにより，ハッシュテーブルを用いた探索が可能となり，ハッシュテーブルの特徴であるデータ参照の速さをいかした探索が可能となる．

参考文献

[1] A. Gionis, P. Indyk and R. Motwani, "Similarity Search in High Dimensions via Hashing," Proc. of the 25th VLDB Conference, pp. 518-528, 1999.