Count-Min Sketch — đếm tần suất xấp xỉ

TL;DR: Bài toán: trên một luồng hàng triệu sự kiện, đếm xem mỗi phần tử xuất hiện bao nhiêu lần — ví dụ sản phẩm nào đang được thêm vào giỏ nhiều nhất. Đếm chính xác tốn hàng GB. Count-Min Sketch đếm gần đúng mà chỉ tốn khoảng trăm KB cố định (ví dụ của bài: 106 KB). Mẹo: nhiều phần tử dùng chung một số ít ô (đụng nhau) nên số đếm hơi dư; dùng nhiều bộ ô trộn theo kiểu khác nhau rồi lấy con số nhỏ nhất. Kết quả không bao giờ thấp hơn thật. Redis có sẵn cấu trúc này (lệnh CMS.INCRBY/CMS.QUERY).

Ngày sale 11/11, một sàn thương mại điện tử nhận hàng chục triệu đơn. Với mỗi add-to-cart, service cần biết sản phẩm nào đang hot. Từ điển productId → số lần phình ra vài GB. Count-Min Sketch ước lượng tần suất với khoảng trăm KB cố định, chấp nhận đếm dư (over-count) kiểm soát được, không bao giờ đếm thiếu.

1. Trực giác: trò bỏ phiếu vào ít hộp

Bạn tổ chức bỏ phiếu cho rất nhiều ứng viên (hàng triệu), nhưng chỉ có vài cái hộp (ít hơn ứng viên rất nhiều). Mỗi ứng viên gán cố định vào một hộp, nên nhiều ứng viên dùng chung một hộp. Đọc số phiếu trong hộp của một ứng viên thì con số hơi dư, vì lẫn phiếu của người khác.

Đụng nhau chỉ làm số đếm dư lên, không bao giờ làm thiếu. Để bớt dư, dùng nhiều bộ hộp, mỗi bộ xếp ứng viên theo cách khác nhau: đụng nhau ở bộ này thường không đụng ở bộ kia. Đọc số của ứng viên ở mọi bộ rồi lấy con số nhỏ nhất, vì bộ dư ít nhất gần thật nhất.

Đổi hộp thành ô đếm thì ra bảng d × w:

Vì thế tên là Count-Min.