【論文】M. Datar, N. Immorlica, P. Indyk, and V.S. Mirrokni, Locality-Sensitive Hashing Scheme Based on p-Stable Distributions, Proceedings of the twentieth annual symposium on Computational geometry, 2004. Overview Locality Sensitive Hashing(以下LSH,局所性鋭敏型ハッシュ)は高次元データを次元圧縮するための手法で,圧縮したデータによるハッシュテーブルを作成して,効率的に近似的最近傍探索を行うための手法です.基本的なアイディアとしては高次元空間内での距離が近い2つのベクトルが,ハッシュテーブルにおいて高確率で同じバケットに入るように確率的な処理を行うと