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

TL;DR: Bài toán: đếm tần suất từng phần tử trên stream hàng triệu sự kiện — đếm chính xác cần O(số_key) bộ nhớ, không khả thi khi key space vô hạn. Count-Min Sketch (CMS) dùng ma trận d × w ô đếm kết hợp d hàm băm độc lập: update(x) tăng một ô mỗi hàng; query(x) trả về MIN qua d hàng. Sai số một chiều: kết quả luôn ≥ giá trị thật; với xác suất cao sai số không vượt ε·N (ε ≈ e/w, xác suất vượt là e^-d). Bộ nhớ cố định O(d·w) bất kể số key — đây chính là thế mạnh cốt lõi.

Ngày 11/11 năm ngoái, Shopee xử lý hơn 87 triệu đơn hàng trong 24 giờ — tương đương ~1.000 đơn/giây. Với mỗi sự kiện add-to-cart, service cần biết sản phẩm nào đang hot để đẩy lên "trending". Nếu dùng HashMap<productId, count>, dictionary sẽ có hàng triệu key; riêng phần bộ nhớ đã vài GB. Khi dữ liệu không vừa RAM, streaming tới DB lại tạo bottleneck.

Count-Min Sketch giải quyết bài này: ước lượng tần suất với bộ nhớ vài chục KB cố định, chấp nhận over-count kiểm soát được, không bao giờ under-count.

1. Bài toán: tần suất trên stream

Cho stream vô hạn các phần tử x_1, x_2, ..., x_t. Cần trả lời frequency(x) = số lần x xuất hiện cho tới hiện tại.

Đếm chính xác: dùng hash map key → count. Bộ nhớ O(số_key_distinct). Với log truy cập của một sàn thương mại điện tử, số key distinct có thể là hàng chục triệu — hash map chiếm GB RAM.

Yêu cầu thực tế: chấp nhận sai số nhỏ, đổi lấy bộ nhớ cố định O(d·w) — và d, w do ta chọn theo ràng buộc lỗi cho trước.

2. Cấu trúc Count-Min Sketch

CMS là một ma trận số nguyên CMS[d][w] (khởi tạo toàn 0) kết hợp d hàm băm độc lập h_1, h_2, ..., h_d, mỗi hàm ánh xạ key về [0, w-1].

function CMS_init(d, w):
    -- Tạo ma trận d hàng × w cột, khởi tạo 0
    for i <- 0 to d-1:
        for j <- 0 to w-1:
            table[i][j] <- 0
    return table
// Space: O(d * w)

Tham số:

• w (width) — số cột, kiểm soát sai số: ε ≈ e/w
• d (depth) — số hàng, kiểm soát xác suất: δ ≈ e^(-d)
• Ví dụ thực tế: w = 2000, d = 7 → sai số ≤ 0.14%·N, xác suất vượt < 0.1%, chỉ dùng 112 KB (nếu mỗi ô 8 byte).

flowchart LR
    X(["x = 'phone'"])
    H1["h_1(x) = 3"]
    H2["h_2(x) = 7"]
    H3["h_3(x) = 1"]
    C1["table[0][3]++"]
    C2["table[1][7]++"]
    C3["table[2][1]++"]
    X --> H1 --> C1
    X --> H2 --> C2
    X --> H3 --> C3

3. Thao tác update và query

3.1 Update — tăng đếm

function CMS_update(x):
    -- Tăng ô tương ứng trên mỗi hàng
    for i <- 0 to d-1:
        j <- h_i(x) mod w
        table[i][j] <- table[i][j] + 1
// Time: O(d)  Space: O(1) thêm

3.2 Query — ước lượng tần suất

function CMS_query(x):
    -- Lấy min qua tất cả hàng
    result <- +∞
    for i <- 0 to d-1:
        j <- h_i(x) mod w
        result <- min(result, table[i][j])
    return result
// Time: O(d)  Space: O(1)

Vì sao lấy MIN? Mỗi ô table[i][j] có thể chứa count của nhiều key bị collision tại cùng bucket. Collision chỉ làm tăng giá trị ô, không bao giờ giảm — nên ô nào cũng ≥ giá trị thật của x. Lấy MIN là cách lấy ước lượng sát nhất (tight upper bound). Với d hàm băm độc lập, xác suất tất cả d hàng đều bị collision nặng là rất nhỏ.

3.3 Trace ví dụ nhỏ — d=2, w=4

Stream: phone, laptop, phone, tablet, phone

Giả sử: h_1(phone)=0, h_1(laptop)=2, h_1(tablet)=0; h_2(phone)=1, h_2(laptop)=3, h_2(tablet)=3.

query(phone): min(table[0][0], table[1][1]) = min(4, 3) = 3. Thật là 3. ✓

query(tablet): min(table[0][0], table[1][3]) = min(4, 2) = 2. Thật là 1. Sai số +1 do collision tablet và phone cùng bucket 0 trên hàng 0.

Đây đúng là tính chất sai số một chiều: kết quả ≥ giá trị thật, không bao giờ dưới.

4. Phân tích sai số

Định lý: Với CMS kích thước d × w, query(x) trả về f̂(x) thoả:

f̂(x) ≥ f(x) luôn luôn (không bao giờ under-count).

P[f̂(x) > f(x) + ε·N] ≤ δ, với ε = e/w và δ = e^(-d).

N là tổng số phần tử trên stream. Khi chọn w = ⌈e/ε⌉ và d = ⌈ln(1/δ)⌉, ta đảm bảo sai số tương đối ≤ ε với xác suất ≥ 1 - δ.

Ví dụ thực tế: muốn sai số ≤ 0.1% tổng lượt (ε=0.001) với xác suất ≥ 99% (δ=0.01):

• w = ⌈e/0.001⌉ = ⌈2718.28⌉ = 2719
• d = ⌈ln(100)⌉ = ⌈4.6⌉ = 5
• Bộ nhớ: 5 × 2719 × 8 = 108,760 byte ≈ 106 KB

So với HashMap lưu 10 triệu key (mỗi entry ~50 byte) = ~500 MB — CMS tiết kiệm hơn 4.500 lần.

5. So sánh Bloom Filter vs Count-Min Sketch

Cả hai đều là cấu trúc xác suất dùng multiple hash functions + bit/ô đếm. Điểm khác biệt then chốt:

Cả hai đều KHÔNG bao giờ false negative: Bloom Filter không nói "không có" khi thật ra có; CMS không nói "ít hơn" khi thật ra nhiều hơn — đây là tính chất bảo toàn quan trọng cho ứng dụng thực tế.

Xem thêm về Bloom Filter tại bài 09 module tìm kiếm nhanh.

6. Ứng dụng thực tế

Heavy hitters (Top-K): chạy CMS song song với heap min-size-K. Mỗi lần update(x), nếu query(x) vượt ngưỡng → đẩy vào heap. Đây là ý tưởng cơ sở cho mini-challenge bài 06.

Rate limiting: thay vì lưu counter mỗi IP trong Redis, dùng CMS để ước lượng số request từ IP x trong cửa sổ thời gian. Over-count chỉ làm rate limit chặt hơn (false throttle thay vì false pass) — an toàn hơn cho security.

Network traffic monitoring: router cần biết flow nào chiếm băng thông lớn nhất. Với hàng triệu flow/giây, chỉ CMS mới đủ nhanh và nhỏ để chạy trên ASIC.

Database query planner: một số DB (như PostgreSQL sketch-based stats) dùng biến thể CMS để ước lượng cardinality histogram mà không scan toàn bảng.

7. Pitfall

Pitfall 1 — Nhầm CMS trả về giá trị chính xác

-- SAI: tin query() trả về đúng → dùng để billing
if CMS_query(userId) > 1000:
    charge(userId)     -- Lỗi: over-count có thể charge oan

-- DUNG: dùng CMS chỉ để lọc ứng viên, verify bằng nguồn chính xác
candidates <- items where CMS_query(x) > threshold
for x in candidates:
    exact_count <- DB.count(x)  -- verify chính xác trước khi hành động
    if exact_count > 1000: charge(x)

CMS phù hợp cho screening và monitoring, không phải billing hay audit cần độ chính xác tuyệt đối.

Pitfall 2 — Chọn d và w không dựa trên ràng buộc bài toán

-- SAI: đoán mò d=3, w=100 mà không kiểm tra ε và δ
-- ε = e/100 ≈ 2.7% — quá lớn nếu N = 10 triệu, sai số tuyệt đối ~270.000!

-- DUNG: tính ngược từ ràng buộc
epsilon <- 0.001   -- chấp nhận sai số 0.1% * N
delta   <- 0.01    -- xác suất vượt sai số ≤ 1%
w <- ceil(e / epsilon)        -- = 2719
d <- ceil(ln(1 / delta))      -- = 5

Luôn xuất phát từ ε và δ chấp nhận được, sau đó tính w và d. Ngược lại sẽ cho kết quả sai quá ngưỡng cho phép.

Pitfall 3 — Dùng hàm băm không độc lập hoặc dùng chung seed

-- SAI: dùng cùng 1 hàm băm với d offset khác nhau
h_i(x) = hash(x) + i   -- Không độc lập: cùng collision pattern!

-- DUNG: d hàm băm thực sự độc lập (khác seed hoặc thuật toán khác nhau)
h_i(x) = murmur3(x, seed=i)  -- seed độc lập → độc lập thống kê

Các hàm băm phải pairwise independent để đảm bảo bound lý thuyết. Dùng offset đơn giản không đủ độc lập — collision patterns bị correlated, bound sai số thực tế xấu hơn lý thuyết.

8. Liên hệ các bài khác

• Hash function — nền tảng băm: hàm băm độc lập là building block của CMS. Bài đó giải thích tính chất pairwise independence và avalanche effect — trực tiếp ảnh hưởng chất lượng CMS.
• Bloom Filter: anh em họ của CMS — cùng dùng multiple hash + array, nhưng trả lời câu hỏi membership thay vì frequency. Đọc bài đó để thấy rõ điểm tương đồng và khác biệt kiến trúc.
• HyperLogLog: cùng họ xác suất — HLL ước lượng cardinality (số distinct), CMS ước lượng frequency cá thể. Hai bài bổ sung nhau trong streaming analytics pipeline.
• Mini-challenge top-K: ứng dụng CMS kết hợp min-heap để tìm heavy hitters — bài thực hành trực tiếp của bài này.
• Amortized analysis: phân tích amortized giải thích tại sao O(d) mỗi thao tác, kết hợp với số thao tác tổng, vẫn cho throughput cao trong thực tế.

📚 Deep Dive

Tóm tắt

• Count-Min Sketch lưu ma trận d × w số nguyên + d hàm băm độc lập; bộ nhớ cố định O(d·w) bất kể số key.
• update(x): tăng ô table[i][h_i(x)] cho mỗi hàng i — O(d).
• query(x): trả về min qua d hàng — O(d). Kết quả luôn ≥ giá trị thật (không bao giờ under-count).
• Sai số ≤ ε·N với xác suất ≥ 1 - δ; chọn w = ⌈e/ε⌉, d = ⌈ln(1/δ)⌉.
• Phân biệt Bloom Filter (membership, bit) vs CMS (frequency, counter); cùng kiến trúc hash-matrix nhưng trả lời câu hỏi khác.
• Dùng để screening và monitoring; khi cần chính xác tuyệt đối, verify bằng nguồn chính xác.

Tự kiểm tra

Bài tiếp theo: Sliding window — thống kê trên cửa sổ trượt