問題タブ [locality-sensitive-hash]

空間データを多数のバケット (リデューサー タスク) に分割するために、局所性に敏感なハッシング アルゴリズムを見つけたいと考えています。空間データは実際には軌跡であるため、LSH を控えめに説明すると、軌跡は一連の 2d ポイントで表されます。

ありがとう、アダム

同様のドキュメントを検索する近隣検索アプリケーションを実装しています。これまでのところ、LSH 関連の資料のかなりの部分を読みました (LSH の背後にある理論はある種の混乱を招き、まだ 100% 理解できていません)。

私のコードは、minhash 関数を使用して署名行列を計算できます (私は終わりに近づいています)。また、署名行列にバンディング戦略を適用します。ただし、バンド内の署名ベクトル (列の) をバケットにハッシュする方法を理解できません。

最後の質問が最も重要かもしれませんが、いくつかintroduction質問する必要があります。

q1: ハッシュ関数は同じベクトルのみを同じバケットにマップしますか? (十分なバケットがあると仮定します)

q2: ハッシュ関数は類似のベクトルを同じバケットにマップする必要がありますか? はいの場合、比較を計算しているのではなく、ハッシュを行っているため、この類似性の程度/定義は何ですか。

q3: 上記の質問に応じて、どのようなハッシュ テーブル アルゴリズムを使用すればよいですか?

q4: 私の一番の弱点は、入力としてベクトルを取り、出力としてバケットを選択するハッシュ関数を生成する方法がわからないことだと思います。q1とq2に応じて自分で実装できます... LSHのハッシュ関数の生成に関する提案はありbucketingますか?

Java で、任意の数のランダム ハッシュ関数 (私の場合は 240 個のハッシュ関数) を生成し、任意の数の整数 (現時点では 2000 個) を実行する必要があるミンハッシュ アルゴリズムをプログラミングしています。

これを行うために、240 個のハッシュ関数のそれぞれに対して乱数 a、b、c (1 ～ 2001 の範囲) を生成してきました。次に、ハッシュ関数は h = ((a*x) + b) % c を返します。ここで、h は戻り値で、x はそれを通る整数の 1 つです。

これはランダムハッシュの効率的な実装ですか、それとももっと一般的/受け入れられる方法はありますか?

この投稿は同様の質問をしていましたが、回答の文言にまだ混乱しています: Minhash implementation how to find hash functions for permutations

BRIEF メソッドを適用した画像のデータセットがあります。次のチュートリアルを使用しました: http://docs.opencv.org/trunk/doc/py_tutorials/py_feature2d/py_brief/py_brief.html

現在、マトリックスのサイズは非常に劇的に異なります。マトリックスのサイズを固定することに興味がありますが、方法がわかりません。SIFT や SURF などの別の方法を使用する解決策がある場合は、お知らせください。

私はPySpark (Scala で書かれたspark-hashプロジェクトに基づく) で局所性に敏感なハッシュを実装しようとしています。ハッシュのステップで奇妙な動作が発生しています。

各ベクトルに対して生成された minhash のリストのハッシュを取得するステップでは、この出力は、並列 (PySpark REPL) でハッシュするか、順次 (後collect) ハッシュするかに大きく依存するように見えます。たとえば、この方法でハッシュを生成すると ( を呼び出すとgroupByKey、同じバンドにハッシュされる要素が得られるはずです):

あなたが期待するものに似たリストを取得します。つまり、多くの一意の番号:

ただし、まったく同じデータを取得しますが、Spark コンストラクトを使用してハッシュします。

これで、次のようなリストが得られます。

同じハッシュが何度も繰り返されます。ただし、同じ Spark コンストラクトを使用し、最後の 1 秒で ResultIterable をfrozenset にキャストした場合:

ここで、一意のハッシュのリストを再度取得します。何が起こっているのか分かりますか？ResultIterableSpark の実行中にオブジェクトに対してハッシュがどのように機能するかについて何かおかしなことはありますか?