Hadoop Streaming で Locality-Sensitive Hashing を実装してみる | Atsushi TATSUMA Web Pageはじめに 研究室では、大規模データベースを対象とした検索インデックスについて研究しています。 分散処理によるインデックス作成を考えていて、今回 Hadoop Streaming でどこまでできるかを試すべく、 Locality-Sensitive Hashing (LSH) を実装してみました。 実装したアルゴリズムについて LSH にはいくつかのアルゴリズムのバリエーションがあります。 LSH の詳細は、ブログなり論文なり本なりありますので、ここでは省略しますが、 類似したデータに同じハッシュ値を与えることで、検索を高速化しようというアイディアです。 このハッシュ値には、0101 とかの短いバイナリ符号が好まれます。 今回は、いくつかある LSH のアルゴリズムのうち、 Charikar,M., Similarity estimation techniques from ro
