グアバブルームフィルタの性能が悪いのはなぜですか？

Question

Google Guava's Bloom Filterが私のプロジェクトで動作するかどうかを判断しようとしていますが、私のテストでは、誤検出率が非常に高くなっています（おそらく高レベルのハッシュ衝突のためでしょうか？

2つのデータファイルを使用して実験を行っています。最初のものは、私がブルームフィルターに入れた2200万の固有の数値（整数）を含んでいます。 2つ目は、Bloom Filterで偽陽性をテストするために使用する、まったく異なる数の別のセットも含まれています。

これは、これらの数字の一部がどのように見えるかの例です：

1010061 
904436 
859990 
854448 
839175 
754186 
904491 
233955 
904491 
876342 
919575 
603051 
1012863 
989713 
323424 

私のコードは以下の通りです：

private static void experiment() { 

    // Load 22m unique IDs from file 
    ArrayList<String> skus = loadSkus("sku_1.txt"); 
    int numInsertions = skus.size(); 

    // Google Guava Bloom Filter 
    Funnel<String> strFunnel = (Funnel<String>) (from, into) -> into.putString(from, Charset.forName("US-ASCII")); 
    BloomFilter<String> bf = BloomFilter.create(strFunnel, numInsertions, 0.001); 

    for (String sku : skus) { 
     bf.put(sku); 
    } 

    int falsePositiveCount = 0; 
    double falsePositiveRate; 

    // Load another set of unique IDs that are NOT in the first set 
    ArrayList<String> skus2 = loadSkus("sku_2.txt"); 

    for (String sku : skus2) { 
     if (bf.mightContain(sku)) { 
      falsePositiveCount++; 
     } 
    } 

    falsePositiveRate = (double)falsePositiveCount/(double)skus2.size(); 

    System.out.println("Expected FPP:  " + Double.toString(bf.expectedFpp())); 
    System.out.println("Measured FP rate: " + Double.toString(falsePositiveRate)); 
} 

結果：

Expected FPP:  7.276343403395039E-27 
Measured FP rate: 0.9979594547309587 

測定率偽陽性の数は信じられないほど高いようです！これは、このデータ構造がどのように振舞うべきかではありません。ライブラリを何らかの方法で悪用していますか？私は本当にBloom Filterで適切なパフォーマンスを達成したいと思います。

Answer 1

結果を再現できませんでした。私が考えることができるのは、それがあなたのデータファイルと関係があるということだけです。

私はそうのようなSKUの生成を除いてあなたが投稿同じコードを使用：

final List<String> skus = ContiguousSet.create(Range.closedOpen(0, 22000000), DiscreteDomain.integers()).stream().map(String::valueOf).collect(Collectors.toList()); 

と

final List<String> skus2 = ContiguousSet.create(Range.closedOpen(-22000000, 0), DiscreteDomain.integers()).stream().map(String::valueOf).collect(Collectors.toList()); 

結果：

Expected FPP:  0.0010001451412535098 
Measured FP rate: 9.963636363636364E-4