# ブルームフィルタ ## 定義 ブルームフィルタ(Bloom filter)は、ある要素が集合に含まれるかを、偽陽性を許して定数時間・小さな領域で答える確率的データ構造である。偽陰性は生じない。要素を削除できないため、削除が要る場合はカウンティング Bloom filter を使う。 (Source: [[@2017__VLDB__Quaestor - Query Web Caching for Database-as-a-Service Providers]]) ## 未解決の問い - 偽陽性の許容が安全側に働く用途(陳腐化の判定など)で、サイズと偽陽性率の関係をどう設計するか。 ## 未編纂の観察 - Quaestor の Expiring Bloom Filter は、サーバ側でカウンティング Bloom filter として TTL 切れの要素を取り除き、クライアントへは平坦な Bloom filter を配る。偽陽性は再検証を増やすだけで一貫性に影響しないため、偽陽性率を遅延側の費用として扱える。サイズを TCP の初期輻輳ウィンドウ(約 14.6 KB)に合わせると 1 往復で送れ、陳腐なクエリ 20,000 件で偽陽性率は 6%になる。 (Source: [[@2017__VLDB__Quaestor - Query Web Caching for Database-as-a-Service Providers]]) ## 関連 - ソース: [[@2017__VLDB__Quaestor - Query Web Caching for Database-as-a-Service Providers]] - 概念: [[Webキャッシュ]] / [[有界な陳腐化]] ## 出典 - [[@2017__VLDB__Quaestor - Query Web Caching for Database-as-a-Service Providers]]