あなたはどちらを好きですか？
どちらも同じようなタスクを達成するために使用できますが、私は実際のアプリケーションで人々が何を使っているのか、その理由を知ることが好奇妙です。
回答：
回答№1については9BloomフィルターとCuckooフィルターは、同様の状況で使用されますが、多くの違いがあり、通常はどちらを選択するのが良いかを判断します。
ブルームフィルタはデータベース内部で使用されますエンジン、特にApache Cassandraその理由は、他のポスターが述べたように、遅いセット操作のコストを削減することです。基本的には、コストが高い「これが多分、あるいは確かに存在しない」操作であれば、Bloomフィルタを使用してチェックの回数を減らすことができます。
今日のSaaSモデルの別の一般的な例コールごとのコストでリモートRESTサービスになります。 「this address INVALID」などのバイナリ回答を持つAPI呼び出しでは、ブルームフィルタを使用して、重複するクエリの90％以上を排除できます。 BloomとCuckooのフィルタは誤検出しているので、逆演算には役に立たないことに注意してください。 "this address VALID"
覚えておくべきことは、BloomとCuckooフィルターには偽陰性がありません。これにより、これらのフィルタは「これは間違いなくスパムではない」などのチェックに役立ちますが、ユーザーのアクセス許可のチェックなど、誤検知が許容できない操作には役立ちません。この側面では、それらは概念的にはキャッシュの反対であると考えることができる。 Bloom / Cuckooフィルタとキャッシュの両方は、キャッシュが誤検出を起こさず、Bloom / Cuckooが偽陰性を持たないことを除いて、主にブール型の回答で高価な操作のコストを削減するために使用されます。
Cuckoo / Bloomの注目すべき違いは次のとおりです。
組み合わせ。 ブルームフィルタは、同じパラメータで作成されている限り効率的にマージできます。迅速かつ少ない帯域幅で。このため、大規模に分散したシステムで頻繁に使用されるのがわかり、Bloomフィルタを交換するのが高速です。カッコウのフィルターは簡単には構成できないので、これらの状況では役に立たなくなります。
偽陽性率。 Cuckooフィルターはよりスペース効率が良いです。両方の構造のユースケースの多くは、低レベルのネットワーキングに焦点を当てています。弱いハードウェアでは、同じ偽陽性率のCuckooフィルターの約40％高い効率が重要になります。参照実装は、バケット内のアイテムの位置を利用して、より小さなスペースを節約するために、各バケット内のアイテムをソートします（後で説明します）。もし誰かが私の図書館を使っていたら、それを追加するかもしれません:)。
一定の偽陽性率。 ブルームフィルタは、設計されたサイズを上回るほど偽陽性率が漸近的に悪化する。あなたは永遠にアイテムを挿入し続けることができますが、最終的には偽陽性率はほぼ100％になります。 Cuckooハッシュに基づくCuckooフィルターは、実際に挿入が失敗するような容量を持っています。ランダムではないアイテムのハッシュを繰り返し挿入すると、Cuckooフィルターの挿入が失敗する可能性があります。
速度。 これは主観的であり、ハードウェアに大きく依存しますが、Cuckooフィルタは一般に平均的な場合（私の経験では）より高速です。ほとんどのブルームフィルタ設計では、ハッシュ関数が2回実行されます。特に安全なハッシュ関数を使用する場合、挿入された項目を一度だけハッシュするCuckooフィルターと比較して、大きなハンディキャップになります。私が見たコードでは、BloomとCuckooのフィルタにさまざまなハッシュ関数を使用しています。GoogleのGuava BloomはMurmur3を使用し、他の多くの実装ではSHA1などを使用しています。大文字と小文字を区別するためにハッシュの衝突を利用できる場合は、ライブラリが安全なハッシュを使用していることを確認してください。重要なのは、Cuckooフィルターが一定時間平均の場合、Bloomフィルターは挿入におよそ一定の時間がかかることです。 Cuckooフィルターは容量の数％以内に入るので、挿入速度は大幅に遅くなります。それでもインサート速度だけが遅くなり、他のすべての操作は一定の平均時間になります。
柔軟性。 Bloomフィルタは、insertとcontainsをサポートしています。 Cuckooフィルターはさらに、削除と限定カウントをサポートしています。リファレンスデザインでは、Cuckooフィルターは項目が挿入された回数を最大7回まで判別できます。ブルームフィルターはyes-noのみを判別できます。 Cuckooフィルタは、挿入されたアイテムの削除もサポートしています。これは、Bloomに比べて多くのユースケースで大きなポジティブです。 Bloomフィルタを使用する場合、古いアイテムを削除することができないため、フィルタが完全になったとき（最初の偽陽性率がしきい値を超えている場合）、最初からフィルタを再作成することはかなり標準的です。特定の状況では、再構築するのではなくフィルタの制限内に収まるようにアイテムを削除できるので、Cuckooフィルタがより便利です。
サポート。 Cuckooフィルターは、多くの言語のための新しい安定したライブラリであり、単に存在しません。
ブルームフィルタの最大の利点は、彼らはほとんどの言語でより成熟した図書館のサポートを持っています。ブルームフィルターの背後にある数学もまた科学者には理解されています。 Cuckooフィルターの特性の大部分は経験的に決定されていますが、Bloomフィルターは確かな数値ベースを持っています。実験的な証拠によれば、Cuckooフィルタがほとんどの状況でより良い性能を発揮することが示されていますが、これはパフォーマンスの検証が必要なリアルタイムおよびクリティカルシステムのCuckooフィルタを除外します。
恥知らずのプラグイン：私はJava用のCuckooフィルターライブラリーの開発者です。 CuckooFilter4J 。バケットセミソートがなくなっています空間効率が基準実装よりも幾分低い。プロジェクトのreadmeには、私が気づいている他の実装へのリンクがあります。どちらの構造が良いかは、あなたのユースケースに依存しますが、あなたの言語用の堅実なCuckooフィルタ実装が存在するかどうかによって決まります。
あなたは間違いなくソースを見てくださいCuckoo / Bloomフィルターをプロダクションで使用する前に私は自分自身を書く前に様々なライブラリを読みました...それらの多くは、32ビットの基本配列や明白なパフォーマンス上の問題のため、サイレントなサイズ制限がありました。ほとんどがゼロテストを受けました。グアバブルームの唯一の欠点は、セキュアなハッシュ関数を使用するオプションがないことであり、マルチスレッド化されています。
実動システムでは、速度のためのマルチスレッド。 GuuckのBloomに対する答えは、各スレッドごとに異なるフィルタを作成し、それらを時折組み合わせることです.Cuckooフィルタを組み合わせることはできないので、私はCuckooフィルタライブラリにスレッドを同時に追加しました。私が気づいている他のものは、スレッドセーフではないか、並行していません。
回答№2のための8
あなたはどちらが好きですか、ワインかチーズですか？
A ブルームフィルタ あなたがいるときのためのものです 限られたスペース, 高いクエリコスト、および 主に負のクエリ.
その場合、a ブルームフィルタ 〜と キーあたり8ビット そして 4つのハッシュ関数 あなたにあげる 2.5％の偽陽性率;あなたはほとんどのクエリを処理します 40倍高速化 これまで以上に、 キーあたり1バイト.
一方、いずれかの 以前の条件が成立しない、a キャッシュとして機能するハッシュテーブル それは明らかに エントリあたり1バイト以上のロット :-)
あなたはハードエッジのケースをスキップすることもできます 鳩のハッシュ それがキャッシュであれば、それはサイズ拡大の問題を 鳩のハッシュテーブル （または線形ハッシュ以外のもの）を使用しています。
回答№3のための5
Cuckooフィルター。
"Cuckoo Filter：Bloomよりも実質的に優れています。" Bin Fan、David Andersen、Michael Kaminsky、Michael Mitzenmacher CoNext 2014。 http://dx.doi.org/10.1145/2674005.2674994
著者の一人から、 ブログ：
私は鳩のフィルターといくつかの技術的な議論を避けたいのであれば、合理的に大きなサイズのセットの場合、対応するBloomフィルターと同じ偽陽性率のため、鳩尾フィルターはBloomより少ないスペースしか使用しないフィルタはルックアップで高速ですが（挿入や作成には時間がかかります）、驚くほどキーの削除も可能です（Bloomフィルタではできません）。 githubリポジトリ あなたのために鳩のフィルターのコードを書いてください。
答え№4の2
私は鳩のハッシュを好む。 私はより高いフィルファクターでブルームフィルターに現れるかもしれない誤ったポジティブを気にしています。
非常に大きなハッシュテーブルがあり、メモリの問題にぶち当たっていたアプリケーションで鳩のハッシングを使用しました。 私のeCollectionsライブラリをご覧ください http://codeplex.com/ecollections 鳩のハッシュの変形の実装のために。
敬具、
回答№5の場合は0
偽陽性を許容することができ、スペースが重要である場合、私はBloomフィルタを使用します。なぜなら、スペースが少なくて済むからです。それ以外の場合は、ハッシュを使用します。