• Bloom filter:あるデータが対象の集合に存在するか確認 ◦ k本のハッシュ関数でbitを立てる ▪ 全て1: 存在する ▪ いずれか0: 存在しない ◦ k ≈ (m/n)·ln2(n: 要素数, m: bit数, k: ハッシュ本数) • Count-Min sketch:ストリーム中の要素の出現回数の大概把握 ◦ 複数のハッシュ関数で要素を変換し、該当セルの値をインクリメント →ある要素の出現頻度は、該当するセル群の値の最小値 ◦ 幅 w ≈ e/ε, 行 d ≈ ln(1/δ)(誤差 ε, 失敗確率 δ) 1 1 1 x 1 0 1 h, g y z w h, g Bloom filter 1 0 2 0 1 2 0 0 0 3 0 0 eleA, eleA, eleB h g f 0 1 2 3 Count-Min sketch. h(eleA) = 2, f(eleA) = 1, g(eleA) = 1 h(eleB) = 0, f(eleB) = 0, g(eleB) = 1 eleAの出現頻度 min(2,2,3) = 2