Bloom filter chỉ tốt khi bạn cấp đúng số bit và đúng số hàm băm. Bài này đo thật: quét k từ 1 tới 15 cho thấy có một k tối ưu (7) cho tỉ lệ báo nhầm thấp nhất, nhiều hơn lại tệ hơn; công thức m = -n·ln(p)/(ln2)² cho đúng số bit để đạt 1%, 0.1%, 0.01%; và cái bẫy chết người — nhồi gấp đôi số phần tử dự kiến làm báo nhầm nhảy từ 0.8% lên 13.8%.
Bloom filter thường không xóa được — tắt bit sẽ phá phần tử khác. Counting Bloom thay mỗi bit bằng một bộ đếm nhỏ để hỗ trợ xóa. Bài này tự cài và đo thật: xóa 'bob' làm nó biến mất mà 'alice' vẫn còn nguyên; nhưng cái giá là tốn 4 lần bộ nhớ, có rủi ro tràn bộ đếm, và xóa phần tử chưa từng thêm có thể sinh báo sót. Cơ chế và khi nào đáng dùng.
Đếm 'bao nhiêu user duy nhất' hay 'bao nhiêu IP khác nhau' bằng set thì tốn RAM tỉ lệ số phần tử. HyperLogLog đếm số phần tử phân biệt bằng bộ nhớ CỐ ĐỊNH — bất kể 10 nghìn hay 1 triệu, vẫn 16KB. Bài này tự cài HLL và đo thật: đếm 1 triệu phần tử sai chỉ 1.06%, nhỏ hơn set 3479 lần. Trực giác về số 0 dẫn đầu, cơ chế register, và vì sao Redis dùng nó.
Ý tưởng HyperLogLog đẹp, nhưng công thức thô không chạy được. Bài này đo thật ba hiệu chỉnh biến nó thành thuật toán thật: trung bình điều hòa thay trung bình thường (sai số 1% thay vì 150% vì giảm ảnh hưởng ngoại lai), hằng số alpha bù thiên lệch, và linear counting cho cardinality nhỏ (thiếu nó sai tới 2900% ở tập nhỏ). Đây chính là những gì HyperLogLog++ của Google hoàn thiện.
Bloom trả lời 'có không', HyperLogLog trả lời 'bao nhiêu khác nhau'. Count-Min Sketch trả lời 'phần tử này xuất hiện bao nhiêu lần?' — bằng một ma trận nhỏ cố định thay vì một dict khổng lồ. Bài này tự cài CMS và đo thật: đếm phần tử phổ biến sai chỉ 0.07%, nhưng phần tử hiếm bị ước lượng vượt tới 2710%. Vì sao lấy MIN, và vì sao CMS hoàn hảo cho heavy hitters mà tệ với đuôi dài.
Count-Min Sketch đếm được tần suất nhưng không tự biết phần tử nào nóng. Ghép nó với một min-heap nhỏ là ra bộ tìm top-k. Bài này tự cài và đo thật: trên luồng 300.000 sự kiện với 15.000 phần tử, CMS + min-heap tìm đúng 9/10 heavy hitter (recall 90%), chỉ lệch ở phần tử ranh giới có tần suất sát nhau. Cơ chế, vì sao top-k thường đúng, và ứng dụng DDoS/trending.