次元が高い場合に関してのsimhashの計算 - tsubosakaの日記
最近simhashの実装を行っていて、データの次元が高いとsimhashを計算するのに必要なランダムなベクトルをメモリ上に乗らないという事態が生じたのでad hocな方法で回避していたけど、論文[1]をよく見直すとほぼ同じ方法でより計算コストが少ない方法が紹介してあったので少し解説を行ってみる。ちなみに以下の解説では低次元のビットベクトルに縮約した後にハミング距離が近いものをどうやって探索するかについては述べないです、それに関しては[1],[2]を参照してください。 ちなみに自分が実装したのは各ビットごとに次元に対するハッシュ関数を定義して計算する方法でした。この方法だと以下で開設する手法よりもf倍の回数ハッシュ関数を計算する必要があるので実行時間が割とかかる。 解説 simhash[3](文献によってはLSHと呼ぶこともある[2])は次元削減の手法の一つで、高次元のデータを低次元のビット
『MPJoin を使った類似データ抽出 ―アルゴリズムシリーズ 1―』
Hattori です。以前書いた記事の冒頭 で、”今度はシリーズで何かエントリを書きたい ! ”と軽いノリで一文を表記しておいたら、ホントにやることになりました。 弊社のエンジニア組織の特徴のひとつに、手を上げる・声を上げると、『じゃ、やってよ。』というノリで返ってくるという事が挙げられるのですが、今回もその例に漏れなったわけですね・・・。シクシク・・・。 というわけで、何を書こうかなぁって話しなんですが・・・。私の場合アルゴリズム系の話しかできそうにないので、毎回ポツポツとマイナーで極一部の人にしかウケないテーマを紹介して行こうと思います。 で、初回の今回は SimilarityJoin 関連のアルゴリズムで "MPJoin" というやつを紹介したいと思います。 ■ Similarity Join とは何ぞや？ まず最初に SimilarityJoin [1] の定義なんですが、ざっくり
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
