Xét bài toán cơ bản sau:

Hai yếu tố quan trọng khi thiết kế một cấu trúc dữ liệu để trả lời câu hỏi trên: bộ nhớ để lưu trữ cấu trúc phải đủ nhỏ vì $S$ rất lớn và các truy vấn có thể được trả lời một cách nhanh chóng. Chú ý, lưu trữ $S$ cần ít nhất $\Omega(n\log n)$ bít (tại sao lại có thêm nhân tử $\log n$ ở đây?). Bloom [1] đề xuất một cấu trúc, gọi là Bloom filter, sử dụng $O(n)$ bít và có thể trả lời truy vấn trong thời gian $O(1)$. Bài này ta sẽ tìm hiểu cấu trúc đó.

Problem 1 cơ bản tới mưc gần như nó xuất hiện gần như khắp mọi nơi, đặc biệt trong thời đại dữ liệu lớn (big data). Trang wikipedia liệt kê rất nhiều ứng dụng của Bloom filter trong các hệ thống lớn hiện tại, mà bạn đọc có thể tham khảo. Ví dụ Medium sử dụng Bloom Filter để loại ra các bài mà một user đã đọc khi muốn gợi ý các bài mới cho user đó.

Bài này mình chủ yếu tập trung trình bày ý tưởng và dựa trên chương 5 trong cuốn sách kinh điển của Mitzenmacher và Upfal [2] (một trong những cuốn sách yếu thích của mình).

Ý tưởng của Bloom filter

Về mặt ý tưởng, cấu trúc Bloom filter rất đơn giản; tất cả những thứ không đơn giản lại nằm ở phép phân tích. Gọi $n$ là số phần tử trong $S$. Bloom filter sử dụng một mảng $m$ bít $A[1,\ldots, m]$ và $k$ hàm băm $\mathcal{H} = \{h_1(.), \ldots, h_k(.)\}$. Ban đầu các bít đều có giá trị $0$ ($A[i] = 0$ với mọi $i$), ta nói các bít bị tắt. Giả sử đầu ra của các hàm băm khi áp dụng cho một đầu vào $x$ là một chỉ số trong tập $\{1,2,\ldots, m\}$. Với mỗi $s \in S$, ta sẽ bật $k$ bít ở $k$ vị trí $h_1(s), \ldots, h_k(s)$ trong mảng $A$ ($k$ vị trí này không nhất thiết là đôi một khác nhau). Giả mã như sau:

 
Để kiểm tra xem một phần tử $x$ có trong $S$ hay không, ta sẽ kiểm tra $k$ vị trí $h_1(x), \ldots, h_k(x)$ của mảng $A$. Nếu tất cả $k$ vị trí này đều là $1$, ta sẽ kết luận $x$ có trong $S$. Ngược lại, ta kết luận $x$ không có trong $S$.

Dễ thấy, nếu $x \in S$ thì Bloom filter luôn trả lời đúng. Tuy nhiên, nếu $x$ không nằm trong $S$ thì có thể $k$ bít của $A$ tương ứng với $k$ mã băm của $x$ đều đã được bật trước đó. Trong trường hợp này, Bloom filter sẽ cho câu trả lời sai. Ta gọi đó là hiện tượng False Positive (FP).

Figure 1: Ví dụ một Bloom filter, với $\mathcal{H}$ có 3 hàm băm. Phần tử $a$ không có trong $S$ vì có 1 bít trong $A$ có giá trị $0$ khi ta kiểm tra 3 vị trí tương ứng với đầu ra của 3 hàm băm khi áp dụng trên $a$. Phần tử $b$ không có trong $S$, nhưng Bloom filter vẫn trả lời là có trong $S$, do 3 vị trí tương ứng với đầu ra của 3 hàm băm khi áp dụng trên $b$ đều có giá trị $1$; hiện tượng FP xảy ra với $b$.

Câu hỏi đặt ra là: cần chọn $m$ và $k$ như thế nào để xác suất FP là thấp nhất. Hay câu hỏi thú vị và quan trọng hơn là:

Phần tiếp theo, ta sẽ chứng minh:

Từ Theorem 1, ta có hệ quả:

Trong các phát biểu trên, ta giả sử $k,m$ đều là các số nguyên.

Ý nghĩa của Theorem 1: Theorem 1, ngoài cho phép ta kiếm soát được xác suất FP (Corollary 1), còn cho phép chúng ta thấy được sự thay đổi của xác suất FP khi ta tăng/giảm bộ nhớ của Bloom filter. Nếu chọn $m = 8n$, có nghĩa là ta sử dụng trung bình 8 bít cho mỗi phần tử của tập $S$, thì xác suất FP chỉ khoảng 2%. Chú ý, kích thước của mỗi phần tử của tập $S$ ít nhất là $\Omega(\log n)$ bít, và trong thực tế, lớn hơn 8 bít rất nhiều.

Chứng minh Theorem 1

Với mọi $i$, ta giả sử xác suất hàm băm $h_i(.)$ sẽ băm $x$ vào một ô cố định $j \in \{1,\ldots, m\}$ là $1/m$.

Ta sẽ sử dụng phương pháp phân tích ngược (backward analysis) để chứng minh Theorem 1. Giả sử $x \not\in S$. FP xảy ra khi tất cả $k$ ô $h_1(x), \ldots,h_k(x) $ của mảng $A$ đều bị bật. Để đơn giản, ta sẽ tính xác suất $A[h_1(x)]=1$ và giả sử $k$ sự kiện các $k$ ô bị bật là độc lập với nhau (đây là một giả sử không đúng, nhưng nó sẽ làm phép phân tích đơn giản hơn; xem thêm thảo luận bên dưới).

Nếu phân tích xuôi, $S$ được băm trước $x$ và ta sẽ tìm xác suất để hàm $h_1(.)$ băm $x$ vào một ô đã bị bật trước đó hay chưa. Tuy nhiên, ta không biết được bao nhiêu ô đã bị bật, nên việc tính xác suất theo phân tích xuôi khá khó khăn. Trong phép phân tích ngược, ta sẽ giả sử khóa $x$ sẽ được băm vào bảng $A$ trước khi ta băm $S$. Sau đó ta sẽ tính xác suất mà một phần tử $s$ nào đó của $S$ bị băm vào ô $h_1(x)$. Đó cũng chính là xác suất $A[h_1(x)]=1$.

Dễ thấy, xác suất mỗi lần băm một phần tử $s \in S$ không vào ô $h_1(x)$ là $1-1/m$. Do mỗi phần tử của $S$ được băm $k$ lần, xác suất để $kn$ lần băm không trúng ô $h_1(x)$ là:

$(1-\frac{1}{m})^{kn} \qquad (1)$

Do đó, xác suất để ít nhất 1 lần trong $kn$ lần băm trúng phải ô $h_1(x)$ là:

$(1-(1-\frac{1}{m})^{kn}) \qquad (2)$

Do ta giả sử sự kiện $k$ ô $h_1(x), \ldots,h_k(x) $ bị bật là độc lập, theo (2), xác suất để xảy ra FP là:

$(1-(1-\frac{1}{m})^{kn})^k \qquad (3)$

Áp dụng xấp xỉ $(1 - 1/m)^m\sim e^{-1}$, ta có thể biến đổi $(3)$ về dạng:

$(1-e^{-k\frac{n}{m}})^k \qquad (4)$

Giờ ta sẽ tìm $k$ để $(4)$ nhỏ nhất. Đặt $p = 1 - e^{-k\frac{n}{m}}$, ta có thể biến đổi $(4)$ về dạng:

$e^{-\ln(p)\ln(1-p) \frac{m}{n}} \qquad (5)$

Dễ thấy $(5)$ cực tiểu khi và chỉ khi $p = 1/2$, lúc đó ta sẽ suy ra các giá trị của $k$ như trong Theorem 1.

Remark: Như đã nói ở phần đầu, giả sử $k$ sự kiện $k$ ô bị bật là độc lập với nhau là một giả sử sai vì $k$ sự kiện này không độc lập với nhau. Tuy nhiên, bằng các công cụ lý thuyết khác, người ta chứng minh được cho dù không có giả thiết này thì xác suất FP cũng xấp xỉ như công thức $(4)$. Ssách của Mitzenmacher và Upfal [2] giới thiệu phương pháp xấp xỉ Posison. Một số nguồn tham khảo khác cho vấn đề này bạn đọc có thể xem tại wikipedia.

So sánh với bảng băm

Trước hết, nếu nói đến cấu trúc tìm kiếm nhanh một phần tử trong một tập hợp, ta thường sử dụng bảng băm (hash table) $T[1,\ldots, m]$ có kích thước $m$. Trong cấu trúc bảng băm, ta chỉ sử dụng một hàm băm $h(.)$. Tuy nhiên, do $S$ quá lớn, ta không thể lưu trữ $S$ trong bảng. Thay vào đó, ta có thể chỉ dùng $1$ bít để đánh dấu xem một ô của bảng có rỗng hay không. Do đó, Bloom filter có thể coi là một cấu trúc tổng quát hơn bảng băm bằng cách dùng nhiều hàm băm thay vì dùng một hàm băm duy nhất.

Câu hỏi đặt ra là nếu ta chỉ dùng 1 hàm băm ($k = 1$), để xác suất FP không quá $\epsilon$ thì số lượng bít $m$ trong bảng là bao nhiêu? Đây là một bài tập rất hay mà mình khuyến khích các bạn thử suy nghĩ và giải. Số lượng bít cần thiết là:

$m =\frac{n}{-\ln(1-\epsilon)}\sim \frac{n}{\epsilon} \qquad (6)$

So với biểu thức trong Corollary 1 thì sự phụ thuộc của $m$ vào $\epsilon$ khi sử dụng Bloom filter tốt hơn lũy thừa lần khi sử dụng bảng băm.

Update: Survey của Luo, Guo, Ma, Rottenstreich và Luo [3] có thông tin về rất nhiều loại Bloom Filter. Nếu bạn cần một trong số ứng dụng hoặc biến thể nào đó có Bloom Filter thì paper này là một điểm khởi đầu.

Tham khảo

[1] B. H. Bloom. Space/time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM 13.7 (1970): 422-426.
[2] M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Chapter 5. Cambridge University Press, 2005.
[3] L. Luo, D. Guo, R. T.B. Ma, O. Rottenstreich, and X. Luo. Optimizing Bloom Filter: Challenges, Solutions, and Comparisons. Arxiv, Accessed 16/04/2018.