[解決済み] 大規模な集合においてハミング距離の小さい2値文字列を効率的に探索する方法

質問

問題です。

大きな（～1億）符号なし32ビット整数のリストと、符号なし32ビット整数の入力値、そして最大の ハミング距離 が与えられた場合、入力値から指定されたハミング距離の範囲内にある全てのリストメンバーを返します。

リストを保持する実際のデータ構造はオープンで、パフォーマンス要件はインメモリソリューションを指示し、データ構造を構築するコストは二の次で、データ構造をクエリするための低コストは重要です。

例

For a maximum Hamming Distance of 1 (values typically will be quite small)

And input: 
00001000100000000000000001111101

The values:
01001000100000000000000001111101 
00001000100000000010000001111101 

should match because there is only 1 position in which the bits are different.

11001000100000000010000001111101

should not match because 3 bit positions are different.

今までの感想。

ハミング距離が0である縮退したケースについては、ソートされたリストを使用し、特定の入力値についてバイナリ検索を行うだけです。

ハミング距離が1しかない場合は、元の入力の各ビットを反転させ、上記を32回繰り返せばよい。

ハミング距離 >1を持つリストメンバーを（リスト全体をスキャンすることなく）効率的に発見するにはどうしたらよいでしょうか。

どのように解決するのですか？

質問です。 ハミング距離d(x,y)について、私たちは何を知っていますか？

答えてください。

1. 非負である：d(x,y) ≥ 0
2. 同一の入力に対してのみ0となる：d(x,y) = 0 ⇔ x = y
3. 対称である：d(x,y) = d(y,x)
4. に従う。 三角形の不等式 , d(x,z) ≦ d(x,y) + d(y,z)

質問です。 なぜ私たちは気にするのでしょうか？

答えてください。 なぜなら、ハミング距離というのは メトリック のための メトリック空間 . メトリック空間をインデックス化するアルゴリズムがあります。

• メトリックツリー (ウィキペディア)
• BK-ツリー (ウィキペディア)
• M-ツリー (ウィキペディア)
• VP-ツリー (ウィキペディア)
• カバーツリー (ウィキペディア)

また、空間がユークリッドでなく、一般的な空間インデックスのアルゴリズムも調べることができます。 です。 であることを知った上で、一般的な空間インデックスのアルゴリズムを調べることもできます。 この主題に関する多くの書籍は、ハミング距離のようなメトリックを使用した文字列インデックスの作成について扱っています。

脚注です。 固定幅の文字列のハミング距離を比較する場合、アセンブリやプロセッサの intrinsics を使用することで、大幅な性能向上が得られる可能性があります。 たとえば、GCC で ( マニュアル ) では、このようにします。

static inline int distance(unsigned x, unsigned y)
{
    return __builtin_popcount(x^y);
}

もし、SSE4aを搭載したコンピュータ用にコンパイルしていることをGCCに知らせれば、2つのオペコードに減らすことができると思います。

編集します。 多くのソースによると、これは通常の mask/shift/add コードよりも時々/しばしば遅くなるそうです。 ベンチマークによると、私のシステム上では、CバージョンはGCCの __builtin_popcount を約 160% 上回っています。

追記です。 私自身この問題に興味があったので、線形探索、BKツリー、VPツリーの3つの実装をプロファイリングしてみました。 VP ツリーと BK ツリーは非常によく似ていることに注意してください。 BK木のノードの子は、木の中心からそれぞれ一定の距離にある点を含む木の殻です。 VP木のノードは、ノードの中心を中心とする球の中にあるすべての点を含む子と、その外側にあるすべての点を含む子の2つの子を持つ。 つまり、VPノードは、多数の細かい殻ではなく、2つの非常に厚い殻を持つBKノードと考えることができます。

結果は私の 3.2 GHz PC でキャプチャされ、アルゴリズムはマルチコアを利用しようとはしません (これは簡単なはずです)。 データベース サイズは 100M の擬似ランダム整数を選択しました。 結果は、距離 1 ～ 5 については 1000 クエリ、6 ～ 10 および線形探索については 100 クエリの平均です。

• データベース 100M個の疑似乱数整数
• テストの数 距離1～5で1000回、距離6～10で100回、線形で100回
• 結果 クエリヒットの平均値 (非常に概算)
• 速度：1秒あたりのクエリ数
• カバレッジ。クエリごとに検査されるデータベースの平均割合

                -- BKツリー -- -- VPツリー -- -- 線形
Dist 結果 速度 Cov 速度 Cov 速度 Cov
1 0.90 3800 0.048% 4200 0.048%
2 11 300 0.68% 330 0.65%
3 130 56 3.8% 63 3.4%
4 970 18 12% 22 10%
5 5700 8.5 26% 10 22%
6 2.6e4 5.2 42% 6.0 37%
7 1.1e5 3.7 60% 4.1 54%
8 3.5e5 3.0 74% 3.2 70%
9 1.0e6 2.6 85% 2.7 82%
10 2.5e6 2.3 91% 2.4 90%
いずれか 2.2 100

コメントで、こうありました。

BK-treeは、ルートノードの異なるBK-treeを大量に生成して、それを分散させれば改善されると思うのですが。

これはまさに、VPツリーがBKツリーより（少し）良いパフォーマンスをする理由だと思います。 浅い」のではなく「深い」ので、より少ないポイントに対してより細かい比較を行うのではなく、より多くのポイントに対して比較を行います。 高次元の空間では、その差はより極端になるのではないかと思います。

最後のヒント: ツリーのリーフ ノードは、線形スキャンでは単に整数のフラット配列であるべきです。 小さなセット (おそらく 1000 ポイント以下) では、この方が高速でメモリ効率もよいでしょう。