Thẻ: count-min-sketch

Lập trình 22/09/2026 7 phút

Count-Min Sketch: đếm tần suất triệu phần tử trong luồng bằng 78KB

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.

#data-structures #count-min-sketch #probabilistic

Lập trình 22/09/2026 7 phút

Heavy hitters: tìm top-k phần tử nóng nhất trong luồng, không lưu hết

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.

#data-structures #count-min-sketch #heavy-hitters #probabilistic