ブルームフィルターを使用して、スペースの最適化を行います。cassandraフレームワークには、ブルームフィルターの実装もあります。しかし、詳細には、このスペースの最適化はどのように達成されますか？
17395 次
6 に答える
18
次の例を使用してスペースを節約する方法を理解できます: 私は Google の Chrome チームで働いており、ユーザーが入力した URL が悪意のある URL である場合にユーザーに通知する機能をブラウザーに追加したいとします。そのため、約 100 万の悪意のある URL のデータセットがあり、このファイルのサイズは約 25 MB です。サイズが非常に大きいため (ブラウザー自体のサイズと比較して大きい)、このデータをリモート サーバーに保存します。
ケース 1 : ハッシュ テーブルでハッシュ関数を使用します。効率的なハッシュ関数を決定し、ハッシュ関数を介して 100 万のすべての URL を実行してハッシュ キーを取得します。次に、ハッシュ テーブル (配列) を作成します。このハッシュ キーによって、その URL を配置するためのインデックスが得られます。そのため、ハッシュ テーブルをハッシュして埋めたら、そのサイズを確認します。100 万の URL すべてをハッシュ テーブルに格納し、それらをキーにしました。したがって、サイズは少なくとも 25 MB です。このハッシュ テーブルは、サイズが大きいため、リモート サーバーに格納されます。ユーザーが来て、アドレス バーに URL を入力すると、悪意があるかどうかを確認する必要があります。したがって、ハッシュ関数を介して URL を実行し (ブラウザー自体がこれを実行できます)、その URL のハッシュ キーを取得します。そのハッシュキーを使用して、リモートサーバーにリクエストを送信する必要があります。その特定のキーを持つハッシュ テーブル内の特定の URL が、ユーザーが入力したものと同じかどうかを確認します。はいの場合は悪意があり、そうでない場合は悪意はありません。したがって、ユーザーが URL を入力するたびに、それが悪意のある URL であるかどうかを確認するために、リモート サーバーへの要求を行う必要があります。これには多くの時間がかかるため、ブラウザが遅くなります。
ケース 2 : ブルーム フィルターを使用しています。100 万の URL のリスト全体が、複数のハッシュ関数を使用してブルーム フィルターを通過し、それぞれの位置が 1 としてマークされ、膨大な 0 の配列が表示されます。ブルーム フィルター計算機 ( http://hur.st/bloomfilter?n=1000000&p=0.01 ) を使用して、1% の偽陽性率が必要だとしましょう。) 、必要なブルーム フィルターのサイズはわずか 1.13 MB です。配列のサイズが巨大であっても、1 または 0 のみを保存し、ハッシュ テーブルの場合のように URL を保存しないため、この小さなサイズが予想されます。この配列はビット配列として扱うことができます。つまり、1 と 0 の 2 つの値しかないため、バイトではなく個々のビットを設定できます。これにより、使用されるスペースが 8 分の 1 に削減されます。この 1.13 MB のブルーム フィルターは、サイズが小さいため、Web ブラウザー自体に格納できます。したがって、ユーザーが来て URL を入力すると、必要なハッシュ関数を (ブラウザー自体で) 適用し、ブルーム フィルター (ブラウザーに保存されている) のすべての位置をチェックするだけです。いずれかの位置の値が 0 の場合、この URL は悪意のある URL のリストに確実に含まれておらず、ユーザーは自由に続行できることを示しています。したがって、サーバーを呼び出さなかったので、時間を節約できました。値 1 は、その URL が悪意のある URL のリストに含まれている可能性があることを示しています。これらのケースでは、リモート サーバーを呼び出し、最初のケースのようにハッシュ テーブルを使用して別のハッシュ関数を使用して、URL が実際に存在するかどうかを取得して確認できます。ほとんどの場合、URL が悪意のあるものである可能性は低いため、ブラウザーの小さなブルーム フィルターがそれを把握し、リモート サーバーへの呼び出しを回避することで時間を節約します。場合によっては、ブルーム フィルターによって、URL が悪意のある可能性があると判断された場合にのみ、サーバーに呼び出しが行われます。その「MIGHT」は 99% 正しいです。これらのケースでは、リモート サーバーを呼び出し、最初のケースのようにハッシュ テーブルを使用して別のハッシュ関数を使用して、URL が実際に存在するかどうかを取得して確認できます。ほとんどの場合、URL が悪意のあるものである可能性は低いため、ブラウザーの小さなブルーム フィルターがそれを把握し、リモート サーバーへの呼び出しを回避することで時間を節約します。場合によっては、ブルーム フィルターによって、URL が悪意のある可能性があると判断された場合にのみ、サーバーに呼び出しが行われます。その「MIGHT」は 99% 正しいです。これらのケースでは、リモート サーバーを呼び出し、最初のケースのようにハッシュ テーブルを使用して別のハッシュ関数を使用して、URL が実際に存在するかどうかを取得して確認できます。ほとんどの場合、URL が悪意のあるものである可能性は低いため、ブラウザーの小さなブルーム フィルターがそれを把握し、リモート サーバーへの呼び出しを回避することで時間を節約します。場合によっては、ブルーム フィルターによって、URL が悪意のある可能性があると判断された場合にのみ、サーバーに呼び出しが行われます。その「MIGHT」は 99% 正しいです。ブラウザーの小さなブルーム フィルターがそれを把握し、リモート サーバーへの呼び出しを回避して時間を節約します。場合によっては、ブルーム フィルターによって、URL が悪意のある可能性があると判断された場合にのみ、サーバーに呼び出しが行われます。その「MIGHT」は 99% 正しいです。ブラウザーの小さなブルーム フィルターがそれを把握し、リモート サーバーへの呼び出しを回避して時間を節約します。場合によっては、ブルーム フィルターによって、URL が悪意のある可能性があると判断された場合にのみ、サーバーに呼び出しが行われます。その「MIGHT」は 99% 正しいです。
したがって、ブラウザーで小さなブルーム フィルターを使用することで、入力されたすべての URL に対してサーバー呼び出しを行う必要がないため、多くの時間を節約できました。
于 2015-05-15T11:20:36.163 に答える
5
だから私は以前にこの質問を見たことがあります.上記のアドバイスを使用しましたが、私にとっては遅くなる方法であることがわかりました. だから私は自分自身を書きました。それは完全に一般的ではありませんが、誰かが私のようにパフォーマンスを切望しているなら、彼らはそれを自分でより一般的にするでしょう:)
ここからダウンロードできる Murmur ハッシュ実装を使用しました: http://d3s.mff.cuni.cz/~holub/sw/javamurmurhash/
コード: パッケージ uk.ac.cam.cl.ss958.SpringBoardSimulation;
import ie.ucd.murmur.MurmurHash;
import java.util.BitSet;
import java.util.Random;
public class FastBloomFilter {
private final BitSet bs;
final int [] hashSeeds;
final int capacity;
public FastBloomFilter(int slots, int hashFunctions) {
bs = new BitSet(slots);
Random r = new Random(System.currentTimeMillis());
hashSeeds = new int[hashFunctions];
for (int i=0; i<hashFunctions; ++i) {
hashSeeds[i] = r.nextInt();
}
capacity = slots;
}
public void add(int value) {
byte [] b = new byte[] {
(byte)(value >>> 24),
(byte)(value >>> 16),
(byte)(value >>> 8),
(byte)value};
for (int i=0; i<hashSeeds.length; ++i) {
int h = MurmurHash.hash32(b, 4, hashSeeds[i]);
bs.set(Math.abs(h)%capacity, true);
}
}
public void clear() {
bs.clear();
}
public boolean mightContain(int value) {
byte [] b = new byte[] {
(byte)(value >>> 24),
(byte)(value >>> 16),
(byte)(value >>> 8),
(byte)value};
for (int i=0; i<hashSeeds.length; ++i) {
int h = MurmurHash.hash32(b, 4, hashSeeds[i]);
if(!bs.get(Math.abs(h)%capacity)) {
return false;
}
return true;
}
public static void main(String [] args) {
FastBloomFilter bf = new FastBloomFilter(1000, 10);
System.out.println("Query for 2000: " + bf.mightContain(2000));
System.out.println("Adding 2000");
bf.add(2000);
System.out.println("Query for 2000: " + bf.mightContain(2000));
}
}
于 2013-05-09T15:14:14.737 に答える
3
ブルーム フィルターは「フレームワーク」ではありません。それは本当に単純なアルゴリズムのようなものです。実装はそれほど長くはありません。
これは私が試したJavaの1つです（.jar、ソースコード、JavaDocはすべて利用可能です）：
「Cuckoo Hashing および Bloom Filters のスタンドアロン Java 実装」 (次のリンクが機能しなくなった場合に備えて、Google で検索することをお勧めします):
于 2010-12-28T13:44:09.483 に答える
1
Java 8 機能を使用したブルーム フィルターの実装に関する短い記事を書きました。スペースの節約の問題に関連していることを願っています。ブルーム フィルターのコレクションをビット スライスする方法についてもう少し詳しく説明しました。これは、ブルーム フィルターが多数ある場合の効率に関係する情報検索システムによって行われる場合です。
于 2017-11-06T02:29:19.357 に答える