ブルームフィルタの実装

Question

ブルームフィルタを使用して、スペースの最適化を行います。また、cassandraフレームワークにはBloom Filterの実装があります。しかし、詳細には、このスペースの最適化はどのように達成されていますか？

Answer 1

ブルームフィルタは「フレームワーク」ではありません。これは本当に単なるアルゴリズムに似ています。実装はそれほど長くはありません。

ここで（利用可能の.jar、ソースコードとJavaDocのすべて）私が試したJavaで一つだ：

（あなたがしたいことがあり、「カッコウハッシュとブルームの単独のJava実装をスタンドにはフィルタ」次のリンクはもう働いていない場合には、このためにグーグル）：

http://lmonson.com/blog/?page_id=99

Answer 2

だから私は前にこの質問を見ている、と私は上記のアドバイスを使用し、それは私のために遅くするための方法であることが判明。だから私は自分自身を書いた。それは完全に一般的ではありませんが、私は、彼らが自分自身でそれがより一般的になります午前のように誰かがパフォーマンスのために必死である場合には確信しています:)

私はあなたがここにダウンロードすることができつぶやきハッシュの実装を使用：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)); 


     } 
    } 

Answer 3

あなたはそれがこの例を使用して、スペースを節約する方法を理解することができます は、私はChromeチームでは、Googleのために働く、と私はURL彼が持っている場合は、ユーザーに通知し、ブラウザに機能を追加したいとしましょう入力されたURLは悪意のあるURLです。だから、私は約100万の悪意のあるURLのデータセットを持っています。このファイルのサイズは約25MBです。サイズはかなり大きいので（ブラウザ自体のサイズに比べて大きい）、私はこのデータをリモートサーバに保存します。

ケース1：ハッシュテーブルでハッシュ関数を使用します。私は効率的なハッシュ関数を決定し、ハッシュ関数を使って100万のURLをすべて実行し、ハッシュキーを取得します。次に、ハッシュ・キー（配列）を作成します。ここで、ハッシュ・キーはそのURLを配置するためのインデックスを与えます。ですから、今度はハッシュテーブルをハッシュして塗りつぶしたら、そのサイズを確認します。私はそれらがキーであると共に、ハッシュテーブルに百万のURLすべてを保存しました。したがって、サイズは少なくとも25 MBです。このハッシュテーブルは、そのサイズのためにリモートサーバーに格納されます。ユーザーがアクセスしてアドレスバーにURLを入力すると、悪意のあるかどうかを確認する必要があります。したがって、私は、ブラウザ自体がこれを行うことができますハッシュ関数を介してURLを実行し、私はそのURLのハッシュキーを取得します。そのハッシュキーを使用してリモートサーバーに要求し、その特定のキーを持つハッシュテーブル内の特定のURLがユーザーが入力したものと同じかどうかを確認する必要があります。はいの場合は悪意のあるもので、そうでない場合は悪意のあるものではありません。したがって、ユーザがURLを入力するたびに、それが悪意のあるURLであるかどうかをチェックするためにリモートサーバへの要求を行う必要があります。これには多くの時間がかかり、ブラウザが遅くなります。

ケース2：私はブルームフィルタを使用します。 100万のURLのリスト全体は、複数のハッシュ関数を使用してブルームフィルタを介して実行され、それぞれの位置は0の巨大な配列で1とマークされます。ブルームフィルタ計算機（http://hur.st/bloomfilter?n=1000000&p=0.01）を使用して、1％の偽陽性率が欲しいとしましょう。必要なブルームフィルタのサイズは1.13 MBになります。この小さなサイズは、配列のサイズが大きいにもかかわらず、ハッシュテーブルの場合と同じようにURLを格納するのではなく、1または0だけを格納するため、期待されます。この配列はビット配列として扱うことができます。つまり、1と0の2つの値しか持たないため、バイトではなく個々のビットを設定できます。これにより、8回のスペースが削減されます。この1.13 MBのブルームフィルタは、サイズが小さいため、Webブラウザ自体に保存することができます！したがって、ユーザーがURLを入力してURLを入力すると、（ブラウザ自体に）必要なハッシュ関数を適用し、（ブラウザに格納されている）ブルームフィルタ内のすべての位置を確認するだけです。いずれの位置にも値0を指定すると、このURLは悪意のあるURLのリストにはっきりとは存在せず、ユーザーは自由に進むことができます。したがって、サーバーへの呼び出しは行われず、時間が節約されました。値1は、悪意のあるURLのリストにURLが存在する可能性があることを示します。このような場合、我々はリモートサーバを呼び出し、その上に、最初のケースのようにいくつかのハッシュテーブルを持つ他のハッシュ関数を使用して、URLが実際に存在するかどうかを調べて調べることができます。たいていの場合、URLは悪意のあるものではないので、ブラウザの小さなブルームフィルタがそれを把握し、リモートサーバーへの呼び出しを避けることで時間を節約します。 BloomフィルタがURLが悪意のあるものであることがわかった場合にのみ、そのような場合にのみサーバーに電話をかけます。それは99％の権利です。

ブラウザに小さなブルームフィルタを使用することで、入力したすべてのURLに対してサーバーコールを行う必要がないため、時間が大幅に節約されました。

Answer 4

サーバーに基づくBloomフィルタをRedisson libに使用することができます。 128ビットのHighwayHashに基づいています。次に例を示します。

RBloomFilter<SomeObject> bloomFilter = redisson.getBloomFilter("sample"); 

// initialize bloom filter once with 
// expectedInsertions = 55000000 
// falseProbability = 0.03 
bloomFilter.tryInit(55000000L, 0.03); 

bloomFilter.add(new SomeObject(someStateHere1)); 
bloomFilter.add(new SomeObject(someStateHere2)); 
// does it contain object? 
bloomFilter.contains(new SomeObject(someStateHere3)); 

Answer 5

私はスペースの節約の問題に関連している願って、Javaの8つの機能を使用して、ブルームフィルタを実装についてshort postを書きました。私はbit furtherに行って、いくつかの情報検索システムがこれを行うとき、ブルームフィルタのコレクションをビットスライスする方法について議論しました。これは、ブルームフィルタがたくさんあるときの効率に関連しています。