Khái niệm cơ bản
Bộ lọc Bloom đếm (Counting Bloom filter) được định nghĩa là cấu trúc dữ liệu tổng quát (generalized) của bộ lọc Bloom, dùng để kiểm tra xem số lượng (count number) của một phần tử cho trước có nhỏ hơn ngưỡng cho trước hay không khi một chuỗi phần tử được cho. Là dạng tổng quát của Bloom filter, có khả năng dương tính giả (false positive matches), nhưng không có âm tính giả (false negatives) — với các từ khác, truy vấn trả về "có thể lớn hơn hoặc bằng ngưỡng" (possibly higher or equal than the threshold) hoặc "chắc chắn nhỏ hơn ngưỡng" (definitely less than the threshold).
Mô tả thuật toán
- Hầu hết tham số dùng trong counting bloom filter được định nghĩa giống Bloom filter, như n, k. m là số bộ đếm (counters) trong Counting Bloom filter, là mở rộng của m bit trong Bloom filter.
- Bộ lọc Bloom đếm rỗng được thiết lập là m bộ đếm, tất cả khởi tạo 0.
- Giống Bloom filter, cũng phải có k hàm băm khác nhau, mỗi hàm ánh xạ phần tử tập hợp đến một trong m vị trí mảng bộ đếm, tạo phân bố ngẫu nhiên đều. Cũng giống nhau, k là hằng số, nhỏ hơn nhiều so với m, tỷ lệ với số phần tử sẽ thêm.
- Tổng quát hóa chính của Bloom filter là thêm phần tử (appending). Để thêm phần tử, đưa nó qua k hàm băm để có k vị trí mảng và tăng bộ đếm 1 tại tất cả vị trí đó.
- Để truy vấn phần tử với ngưỡng θ (kiểm tra số lượng phần tử có nhỏ hơn θ không), đưa nó qua k hàm băm để có k vị trí bộ đếm.
- Nếu bất kỳ bộ đếm nào tại các vị trí đó nhỏ hơn θ, số lượng phần tử chắc chắn nhỏ hơn θ — vì nếu lớn hơn hoặc bằng, tất cả bộ đếm tương ứng đã lớn hơn hoặc bằng θ.
- Nếu tất cả lớn hơn hoặc bằng θ, thì hoặc số lượng thực sự lớn hơn/bằng θ, hoặc bộ đếm đã bằng nhờ may mắn.
- Nếu tất cả lớn hơn/bằng θ mà số lượng thực tế nhỏ hơn θ, đây gọi là false positive. Giống Bloom filter, cũng nên giảm thiểu.