ビット列最近接検索

Question

私は長さ32ビットのスパースビット列を何十万も持っています。

私はそれらに最寄りの検索を行いたいと思います。検索のパフォーマンスは重要です。私はさまざまなアルゴリズムを読んできましたが、バイナリ文字列ではなくテキスト文字列を対象としています。私は局所的に敏感なハッシュやスペクトルハッシュが良い候補に見えると思います。これらのいずれかが私のビット列問題にうまくいくのでしょうか？どんな方向性や指導も大変ありがとう。

Answer 1

これは、高速で簡単な方法です（ ）。より多くのメモリを使用してより優れたパフォーマンスを実現するバリアントです。

In：配列Uint X []、 1M 32ビットワード
募集：機能near(Uint q) - > J小さなhammingdist(q, X[j])
方法でバイナリ検索ソートXでq、 がその周りにブロックを検索線形。
擬似コード：

def near(q, X, Blocksize=100): 
    preprocess: sort X 
    Uint* p = binsearch(q, X) # match q in leading bits 
    linear-search Blocksize words around p 
    return the hamming-nearest of these. 

これは速いです - サイズ100 のブロックで +最寄りhammingdistが私のMac PPC上< 10私たちを取る Binary search 1Mワード。 （これは非常にキャッシュ依存—あなたの走行距離あるが異なります。）

どのように近く、これは本当の最寄りX [j]を見つけに来ませんか？ 私は数学を行うことはできません：実験をすることはできません。 最も近い一致は平均で4-5ビット離れています 対真の最も近い1M）：

near32 N 1048576 Nquery 1048576 Blocksize 100 
binary search, then nearest +- 50 
7 usec 
distance distribution: 0 4481 38137 185212 443211 337321 39979 235 0 

near32 N 1048576 Nquery 100 Blocksize 1048576 
linear scan all 1048576 
38701 usec 
distance distribution: 0 0 7 58 35 0 

ブロックサイズでデータを実行するには、一致距離がドロップ方法を確認するために50と100 を言います。

---

は
は、スワップ上位/下位ハーフワードと Xの をコピー Xswapを作成し、返し、二回メモリのコストで、でも近い取得するにはたくさんの

near(q, X, Blocksize) 
near(swap q, Xswap, Blocksize) 

のより良いですメモリでは、X、 など、より多くのビットシャッフルコピーを使用できます。 32回転。
パフォーマンスはNshuffleとBlocksizeによってどのように変化するのかわかりません— LSH理論家に質問があります。

---

（追加）：の近く一致ビット列に320ビット、10ワード、 ワード0、ワード1 ... 、上記のようbinsearchとサーチブロックでソートポインタの10のアレイを作るを言います。

nearest(query word 0, Sortedarray0, 100) -> min Hammingdist e.g. 42 of 320 
nearest(query word 1, Sortedarray1, 100) -> min Hammingdist 37 
nearest(query word 2, Sortedarray2, 100) -> min Hammingdist 50 
... 
-> e.g. the 37. 

ほぼ一致した単一の単語は、 近くではありませんが、それは非常にシンプルだし、ソートやbinsearchが驚異速いですもちろんミスのこの意志。 ポインタ配列は、データビットと同じくらいのスペースをとります。 100ワード、3200ビットはまったく同じ方法で動作します。
しかし、これは0ビットと1ビットの数字がおおよそ等しい場合にのみ有効で、 では99％ではありません。

Answer 2

この問題を解決した論文が出ました。

Randomized algorithms and NLP: using locality sensitive hash function for high speed noun clustering（Ravichandranら、2005）

基本的な考え方は、（ビットの異なる順列によってソート辞書順）デニスの答えに似ていますが、それは追加のアイデアやのための更なる参照の数を含んでいますトピックに関する記事。

実際には私が見つけたhttps://github.com/soundcloud/cosine-lsh-join-sparkに実装されています。