Simhashing (hopefully) made simple
Why Simhash? When it comes to figuring out how similar various pieces of data are from one another (and which is the closest matching one in a large group of candidates), simhashing is one of my favourite algorithms. It's somewhat simple, brilliant in its approach, but still not obvious enough for most people (myself included) to come up with it on their own. Readers may be familiar with hashing a
次元が高い場合に関してのsimhashの計算 - tsubosakaの日記
最近simhashの実装を行っていて、データの次元が高いとsimhashを計算するのに必要なランダムなベクトルをメモリ上に乗らないという事態が生じたのでad hocな方法で回避していたけど、論文[1]をよく見直すとほぼ同じ方法でより計算コストが少ない方法が紹介してあったので少し解説を行ってみる。ちなみに以下の解説では低次元のビットベクトルに縮約した後にハミング距離が近いものをどうやって探索するかについては述べないです、それに関しては[1],[2]を参照してください。 ちなみに自分が実装したのは各ビットごとに次元に対するハッシュ関数を定義して計算する方法でした。この方法だと以下で開設する手法よりもf倍の回数ハッシュ関数を計算する必要があるので実行時間が割とかかる。 解説 simhash[3](文献によってはLSHと呼ぶこともある[2])は次元削減の手法の一つで、高次元のデータを低次元のビット
今週のDBCLS & 車輪の再発明を恐れずにTinySimHash(LSH)作った - 糞ネット弁慶
最近はPubMedのデータを使って関連検索を作りたいと思っていた。 できれば特許のデータでもやりたい 一年ぐらい前から話題のocality Sensitive Hashing(LSH)を試そうと試みてライブラリを試すもうまく動かせなかったりして不満が残る なので練習 && 興味があったので車輪の再発明を恐れずにsimhashを実装 no title ストアしてるデータに対してまとめてハッシュテーブルを一度作って、あとはクエリに対して検索をさせようというのが目的。 現状じゃそれっぽく動くだけで、ハッシュテーブルですらテキストで書き出してるという体たらく 論文に書かれているハッシュを圧縮させる手法を実装しなければ id:tsubosakaさんの 次元が高い場合に関してのsimhashの計算 - tsubosakaの日記を参考にさせていただきました ひとつわからないことがある。ハッシュxのビット
『MPJoin を使った類似データ抽出 ―アルゴリズムシリーズ 1―』
Hattori です。以前書いた記事の冒頭 で、”今度はシリーズで何かエントリを書きたい ! ”と軽いノリで一文を表記しておいたら、ホントにやることになりました。 弊社のエンジニア組織の特徴のひとつに、手を上げる・声を上げると、『じゃ、やってよ。』というノリで返ってくるという事が挙げられるのですが、今回もその例に漏れなったわけですね・・・。シクシク・・・。 というわけで、何を書こうかなぁって話しなんですが・・・。私の場合アルゴリズム系の話しかできそうにないので、毎回ポツポツとマイナーで極一部の人にしかウケないテーマを紹介して行こうと思います。 で、初回の今回は SimilarityJoin 関連のアルゴリズムで "MPJoin" というやつを紹介したいと思います。 ■ Similarity Join とは何ぞや？ まず最初に SimilarityJoin [1] の定義なんですが、ざっくり
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.
http://eigenjoy.com/2011/05/09/cascading-simhash-a-library-to-cluster-by-minhashes-in-hadoop/
