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$:

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í$$$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

Cách chọn số lượng filter $k$ và kích thước filter $m$

Để tối ưu hóa Bloom Filter, việc chọn số lượng hàm băm $k$ và kích thước mảng bit cho filter $m$ là cực kỳ quan trọng. Nếu $k$ quá nhỏ, tỷ lệ dương tính giả (false positive) sẽ cao; nếu $k$ quá lớn, mảng bit sẽ nhanh chóng bị lấp đầy bởi các số 1, cũng dẫn đến tăng tỷ lệ sai sót và tốn chi phí tính toán.

Gỉa sử ta có:

• $n$: Số lượng phần tử dự kiến sẽ thêm vào bộ lọc.

• $m$: Kích thước của mảng bit.

• $k$: Số lượng hàm băm (hash functions).

Xác suất để một bit cụ thể vẫn bằng 0 sau khi chèn $n$ phần tử là:

ổng số lần băm đã thực hiện là $k \times n$ lần. Vì các hàm băm được giả định là độc lập và phân phối đều, xác suất để bit đó vẫn bằng 0 sau $kn$ lần băm là:

Từ đó, xác suất để tất cả $k$ vị trí băm của một phần tử mới đều bằng 1 (dẫn đến False Positive) là:

Ta có, như đã đề cập ở trên thì $p = e^{-kn/m}$ suy ra:

Thay giá trị $k$ vừa tìm được vào công thức của $P$:

Để tối thiểu hóa $P$, ta có thể tối thiểu hóa giá trị logarit của nó (vì hàm $\ln$ là hàm đồng biến):

Để tìm cực trị, ta đặt $f(p) = \ln(p) \ln(1 - p)$ và lấy đạo hàm theo $p$:

Giải phương trình để đạo hàm bằng $0$:

Phương trình này có dạng $g(1-p) = g(p)$ với $g(x) = x \ln(x)$. Do tính chất đối xứng, nghiệm duy nhất của phương trình này trong khoảng $(0, 1)$ là:

Thay $p=1/2$ vào công thức $e^{-kn/m}$ lấy log 2 vế, giải ra ta có:

Với một giá trị $m$ và $n$ cho trước, tỷ lệ sai sót $P$ sẽ đạt giá trị nhỏ nhất khi:

Thông thường trong thực tế, bạn sẽ xác định trước tỷ lệ sai sót chấp nhận được (ví dụ $P = 0.01$ hay 1%) và số lượng phần tử $n$. Khi đó, kích thước mảng bit $m$ cần thiết được tính bằng:

Nghĩa là:

• Để đạt tỷ lệ sai sót 1% ($P = 0.01$): Bạn cần khoảng 10 bit cho mỗi phần tử ($m/n \approx 10$).

• Để đạt tỷ lệ sai sót 0.1% ($P = 0.001$): Bạn cần khoảng 14 bit cho mỗi phần tử.

Ví dụ: Giả sử có khoảng 1 triệu phần tử và muốn tỷ lệ sai số khoảng 2% thì:

Sử dụng công thức: $m = -\frac{n \ln P}{(\ln 2)^2}$

• $P = 0,02 \implies \ln(0,02) \approx -3.9$

• $(\ln 2)^2 \approx 0.48$

Và