9

MySQL を使用してブルーム フィルターを実装したいと思います (その他の代替案)。

問題は次のとおりです。

次の値を持つ 8 ビット整数を格納するテーブルがあるとします。

1: 10011010
2: 00110101
3: 10010100
4: 00100110
5: 00111011
6: 01101010

これにビットごとの AND であるすべての結果を見つけたいと思います:

00011000

結果は行 1 と 5 になります。

ただし、私の問題では、それらは 8 ビット整数ではなく、n ビット整数です。これをどのように保存し、どのように照会しますか? スピードが鍵です。

4

6 に答える 6

19

int 列を含むテーブルを作成します (このリンクを使用して適切な int サイズを選択してください)。数値を 0 と 1 のシーケンスとして保存しないでください。

あなたのデータでは、次のようになります。

number

154
53
148
38
59
106

24 に一致するすべてのエントリを検索する必要があります。

次に、次のようなクエリを実行できます

SELECT * FROM test WHERE number & 24 = 24

アプリケーションで 10 基数への変換を回避したい場合は、それを mysql に渡すことができます。

INSERT INTO test SET number = b'00110101';

そして、このように検索します

SELECT bin(number) FROM test WHERE number & b'00011000' = b'00011000'
于 2008-12-11T21:45:07.947 に答える
8

これにはMySQLを使用しないことを検討してください。

まず、64ビットを超えるテーブルには組み込みの方法がない可能性があります。Cで記述されたユーザー定義関数に頼る必要があります。

次に、MySQLはクエリにインデックスを使用できないため、各クエリでは全表スキャンが必要になります。したがって、テーブルが非常に小さい場合を除いて、これは高速ではありません。

于 2008-12-14T05:37:13.487 に答える
1

データベースを使用してブルーム フィルターを実装するには、別の方法で考えます。

2 レベル フィルターを使用します。単一のマルチビット ハッシュ関数を使用して ID を生成し (これは、ハッシュ テーブルのバケット インデックスに似ています)、行内のビットを使用して、より古典的な種類の残りの k-1 ハッシュ関数を使用します。行内では、(たとえば) 100bigint列になる可能性があります (パフォーマンスと BLOB も比較します)。

事実上、N 個の個別のブルーム フィルターになります。ここで、N は最初のハッシュ関数のドメインです。アイデアは、ハッシュ バケットを選択することで、必要なブルーム フィルターのサイズを削減することです。インメモリ ブルーム フィルターのように完全な効率は得られませんが、すべての値をデータベースに格納してインデックスを作成する場合と比較して、格納する必要があるデータの量を大幅に削減できます。おそらく、そもそもデータベースを使用する理由は、完全なブルーム フィルター用のメモリが不足しているためです。

于 2019-10-15T15:10:29.313 に答える