Bloom Filter

Giới thiệu

Bloom Filter là một cấu trúc dữ liệu có tính chất xác suất dùng để kiểm tra một phần tử có nằm trong một tập hợp hay không. Nó rất hiệu quả về mặt không gian lưu trữ và tốc độ. Bloom filter có thể trả lời hai câu hỏi chính:

• Phần tử có thể nằm trong tập hợp (tính chất xác suất)

• Hoặc, phần tử chắn chắn không nằm trong tập hợp

Bloom Filter được ứng dụng trong blockchain để lọc các transaction nhanh chóng trong các block. Bloom filter cũng được dùng trong các cơ sở dữ liệu Cassandra và Bigtable.

Phương pháp hoạt động

Cho bloom filter được khởi tạo là một chuỗi bit độ dài \(m\) các giá trị \(0\):

$$BF = \{\underbrace{0,0,\dots,0}_{m}\}$$

Thêm một phần tử \(x\):

• Dùng \(k\) hàm hash phân biệt: \(h_1,h_2,\dots,h_k\) để tính giá trị các giá trị index \(idx_i = h_i(x) \mod m\)

• Lần lượt set các phần tử ở vị trí thứ \(idx_i\) của \(BF\) bằng \(1\): \(BF[idx_i] = 1\)

Tìm kiếm phần tử \(s\)

• Dùng \(k\) hàm hash ở trên để tính các giá trị index cho giá trị \(s\): \(ids_i = h_i(s) \mod m\)

• Lần lượt kiếm tra tất cả các giá trị \(BF[ids_i]\):

  • Nếu tồn tại bất kỳ một giá trị nào là \(0\) thì kết luận phần từ \(s\) chắc chắn không nằm trong tập hợp.

  • Ngược lại, phần tử \(s\) có thể nằm trong tập hợp.

Demo