Ý 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.
Đo độ tương đồng hai tập lớn (Jaccard) cần giao chúng — tốn khi có triệu tập. MinHash rút mỗi tập thành một chữ ký vài trăm số, và một sự thật đẹp: xác suất min-hash của hai tập trùng nhau đúng bằng Jaccard similarity. Bài này tự cài và đo thật: MinHash ước lượng Jaccard bám sát giá trị thật, sai số giảm theo 1/√k, và mỗi tập chỉ tốn 1KB thay vì 250KB. Nền của phát hiện trùng lặp và gợi ý.
Làm sao lấy ngẫu nhiên 1000 dòng từ một log đang chảy, khi bạn không biết nó sẽ dài bao nhiêu và không thể giữ hết trong RAM? Algorithm R làm được với một lượt duyệt và bộ nhớ O(k). Bài này tự cài và đo thật: chạy 200.000 lần, mọi phần tử — đầu hay cuối luồng — đều được chọn với xác suất k/N (lệch tối đa 0.18 điểm phần trăm). Cơ chế, vì sao đều, và ứng dụng.
Bài Debug phần 11 tính percentile bằng cách sort cả mảng — tốn RAM tuyến tính và không mergeable. t-digest gom dữ liệu thành centroid, nén dày ở hai đuôi để p99/p999 sắc nét. Bài này cài t-digest rút gọn bằng Python, chạy thật 2 triệu latency: 171 centroid (~2,7 KB) thay 16 MB mảng, p99 sai chỉ 0,1%, và giải thích vì sao nó bền hơn histogram ô đều khi có outlier.