5

ブルーム フィルターとハッシュ スケッチ (FM スケッチも) の違いは何ですか? また、それらの用途は何ですか?

4

2 に答える 2

6

ハッシュ スケッチ/Flajolet-Martin スケッチ

Flajolet, P./Martin, G. (1985): データベース アプリケーションの確率的カウント アルゴリズム。Journal of Computer and System Sciences、Vol. 31、No.2 (1985 年 9 月)、182-209 ページ。

Durand, M./Flajolet, P. (2003): Loglog Counting of Large Cardinalities, in: Springer LNCS 2832, Algorithms ESA 2003, pp. 605–617.

ハッシュ スケッチは、セット内の個別の要素の数をカウントするために使用されます。

与えられた：

  • 長さ l のビット配列 B[]
  • [0,1,...2^l) にマップされる (単一の) ハッシュ関数 h()
  • 入力のバイナリ表現の最下位 1 ビットの位置を与える関数 r() (たとえば、000101 は 1 を返し、001000 は 4 を返します)

要素 x の挿入:

  • pn := h(x) は擬似乱数を返します
  • r(pn) を適用してビット配列の位置を取得し、1 に設定します

セット内の異なる要素の数:

  • ビット配列の右端の 0 の位置 p を見つける
  • p = log2(n)、n について解いて、セット内の個別の要素の数を取得します。結果は、最大 1.83 マグニチュード オフになる可能性があります。

利用方法：

  • データマイニング、P2P/分散アプリケーション、ドキュメント頻度の推定など。

ブルームフィルター

Bloom, H. (1970): 許容可能なエラーを伴うハッシュ コーディングにおける空間/時間のトレードオフ、: Communications of the ACM、Vol. 13, No. 7 (1970 年 7 月), pp. 422-426.

ブルーム フィルターは、要素がセットのメンバーであるかどうかをテストするために使用されます。

与えられた：

  • 長さ m のビット配列 B[]
  • [0,...,m-1]、つまり m ビット配列の位置の 1 つにマップされる k 個の異なるハッシュ関数 h_k()

要素 x の挿入:

  • すべての k に対して h_k を x (h_k(x)) に適用します。つまり、k 値を取得します。
  • 配列 B の結果のビットを 1 に設定します (既に 1 に設定されている場合は、何も変更しないでください)。

y がすでにセットに含まれているかどうかを確認します。

  • すべてのハッシュ関数 h_k (h_k(y)) を使用してチェックする位置 p_k を取得します。つまり、関数 h_k ごとに位置 p_k を取得します。
  • 位置 p_k の 1 つが配列 B で 0 に設定されている場合、要素 y は決定的にセットに含まれていません。
  • p_k で指定されたすべての位置が 1 の場合、要素 y は (!) セット内にある可能性があります
  • 偽陽性率はおよそ (1 - e^(-kn/m))^k であり、偽陰性はあり得ません!
  • ハッシュ関数の数を増やすことで、偽陽性率を下げることができます。ただし、同時にブルーム フィルターが遅くなります。k の最適値は k = (m/n)ln(2) です。

利用方法：

  • 最初はクエリに一致しない要素を除外するためにデータベースで安価なフィルターとして使用されました
  • 今日では、Google BigTable などのさまざまなアプリケーションだけでなく、IP ルックアップなどのネットワーキングでも使用されています。
于 2012-11-08T11:44:50.640 に答える