Moses Charikar's Home Page

http://www.cs.princeton.edu/~moses/
Similarity Estimation Techniques from Rounging Algorithmsなど。
近似アルゴリズムの専門家。
Locality Sensitive Hashing は、
2つのオブジェクトのハッシュ値が一致する確率が、
2つのオブジェクトの類似度と同じであるようなハッシング。

この論文では、
数ベクトルのコサイン類似度についてのLSHと
内積が定義されたベクトルのEarth Mover DistanceについてのLSHが構築されている。

これによって得られる近似的な類似度を使って、近似的なNearestNeighbourSearchを高速に行うアルゴリズム