Bộ lọc Bloom

Bộ lọc Bloom, phát minh bởi Burton Howard Bloom năm 1970, là một cấu trúc dữ liệu xác suất để kiểm tra xem một phần tử có nằm trong một tập hợp hay không. Có thể có lỗi dương tính sai, nhưng không bao giờ có âm tính sai; nghĩa là kết quả thu được luôn là "nằm trong tập hợp (có thể sai)" hoặc "không nằm trong tập hợp". Có thể chèn thêm phần tử nhưng không thể xóa (nhược điểm này có thể được khắc phục bằng một bộ lọc đếm). Càng chèn nhiều phần tử thì xác suất dương tính sai càng cao.

Mô tả thuật toán

Một ví dụ của bộ lọc Bloom cho tập hợp {x, y, z}. Các mũi tên màu chỉ ra các vị trí mỗi phần tử ánh xạ đến. Phần tử w không nằm trong tập hợp {x, y, z}, bởi một trong các vị trí nó ánh xạ đến có giá trị 0. Trong ví dụ này, m=18 và k=3.

Một bộ lọc Bloom rỗng là một mảng m bit, tất cả đều bằng 0. Giả sử có k hàm băm khác nhau, mỗi hàm ánh xạ từ không gian các phần tử tới m vị trí trong bảng với xác suất như nhau. Thông thường k là một hằng số và nhỏ hơn nhiều so với m

Để chèn một phần tử, áp dụng k hàm băm để tính ra mảng k vị trí và gán cho các bit này giá trị 1.

Để kiểm tra một phần tử có nằm trong tập hợp hay không, áp dụng k hàm băm để tính ra k vị trí trong mảng và kiểm tra xem tất cả các bit đó có giá trị 1 hay không. Nếu có một bit nào đó bằng 0 thì phần tử cần kiểm tra chắc chắn không nằm trong mảng. Nếu tất cả chúng đều bằng 1 thì phần tử đó có thể nằm trong mảng.

Xác suất dương tính sai

Xác suất dương tính sai $p$ dưới dạng hàm số của số phần tử $n$ và kích thước $m$ của bộ lọc. Giả sử sử dụng $k=(m/n)\ln 2$ hàm băm

Giả sử các hàm băm lựa chọn các vị trí trong bảng với xác suất như nhau và hoàn toàn ngẫu nhiên và độc lập. Nếu m là số bit trong mảng thì xác suất một bit không được gán giá trị 1 khi ta băm một phần tử bằng một hàm băm là

$1-{\frac {1}{m}}.$

Xác suất nó không được gán giá trị 1 bởi bất kì hàm băm nào là

$\left(1-{\frac {1}{m}}\right)^{k}.$

Nếu chèn n phần tử, thì xác suất bit đó vẫn bằng 0 là

$\left(1-{\frac {1}{m}}\right)^{kn};$

nên xác suất nó bằng 1 là

$1-\left(1-{\frac {1}{m}}\right)^{kn}.$

Ta xét quá trình kiểm tra liệu một phần tử có nằm trong tập hay không. Thuật toán kiểm tra k vị trí trong mảng xem chúng có bằng 1 hay không. Xác suất tất cả chúng đều bằng 1 là

$\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}.$

Chứng minh này không toàn toàn đúng do nó giả sử xác suất mỗi bit trong mảng được gán giá trị 1 là độc lập với nhau. Tuy nhiên, giả sử đây là một xấp xỉ tốt, thì giá trị $k$ tối ưu để xác suất trên là nhỏ nhất là

${\frac {m}{n}}\ln 2\approx 0.7{\frac {m}{n}},$

cho giá trị xác suất dương tính sai là

$2^{-k}\approx {0.6185}^{m/n}.$

Có thể tính kích thước $m$ của mảng theo số phần tử $n$ và xác suất dương tính sai $p$ bằng cách thay giá trị tối ưu của $k$ vào biểu thức trên:

$p=\left(1-e^{-(m/n\ln 2)n/m}\right)^{(m/n\ln 2)}$

Đơn giản hóa biểu thức trên, ta thu được:

$\ln p=-{\frac {m}{n}}\left(\ln 2\right)^{2}.$

từ đó thu được:

$m=-{\frac {n\ln p}{(\ln 2)^{2}}}.$

Nghĩa là để xác suất sai là hằng số cố định, kích thước của mảng là tuyến tính với số phần tử của tập hợp.

Tham khảo

• Agarwal, Sachin; Trachtenberg, Ari (2006), “Approximating the number of differences between remote sets” (PDF), IEEE Information Theory Workshop, Punta del Este, Uruguay: 217, doi:10.1109/ITW.2006.1633815
• Ahmadi, Mahmood; Wong, Stephan (2007), “A Cache Architecture for Counting Bloom Filters”, 15th international Conference on Netwroks (ICON-2007), tr. 218, doi:10.1109/ICON.2007.4444089
• Almeida, Paulo; Baquero, Carlos; Preguica, Nuno; Hutchison, David (2007), “Scalable Bloom Filters” (PDF), Information Processing Letters, 101 (6): 255–261, doi:10.1016/j.ipl.2006.10.007
• Byers, John W.; Considine, Jeffrey; Mitzenmacher, Michael; Rost, Stanislav (2004), “Informed content delivery across adaptive overlay networks”, IEEE/ACM Transactions on Networking, 12 (5): 767, doi:10.1109/TNET.2004.836103
• Bloom, Burton H. (1970), “Space/time trade-offs in hash coding with allowable errors”, Communications of the ACM, 13 (7): 422–426, doi:10.1145/362686.362692
• Boldi, Paolo; Vigna, Sebastiano (2005), “Mutable strings in Java: design, implementation and lightweight text-search algorithms”, Science of Computer Programming, 54 (1): 3–23, doi:10.1016/j.scico.2004.05.003
• Bonomi, Flavio; Mitzenmacher, Michael; Panigrahy, Rina; Singh, Sushil; Varghese, George (2006), “An Improved Construction for Counting Bloom Filters”, Algorithms – ESA 2006, 14th Annual European Symposium (PDF), 4168, tr. 684–695, doi:10.1007/11841036_61
• Broder, Andrei; Mitzenmacher, Michael (2005), “Network Applications of Bloom Filters: A Survey” (PDF), Internet Mathematics, 1 (4): 485–509
• Chang, Fay; Dean, Jeffrey; Ghemawat, Sanjay; Hsieh, Wilson; Wallach, Deborah; Burrows, Mike; Chandra, Tushar; Fikes, Andrew; Gruber, Robert (2006), “Bigtable: A Distributed Storage System for Structured Data”, Seventh Symposium on Operating System Design and Implementation, Bản gốc lưu trữ ngày 3 tháng 1 năm 2010, truy cập ngày 27 tháng 10 năm 2011
• Charles, Denis; Chellapilla, Kumar (2008), “Bloomier Filters: A second look”, The Computing Research Repository (CoRR), arXiv:0807.0928
• Chazelle, Bernard; Kilian, Joe; Rubinfeld, Ronitt; Tal, Ayellet (2004), “The Bloomier filter: an efficient data structure for static support lookup tables”, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (PDF), tr. 30–39, Bản gốc (PDF) lưu trữ ngày 6 tháng 1 năm 2007, truy cập ngày 27 tháng 10 năm 2011
• Cohen, Saar; Matias, Yossi (2003), “Spectral Bloom Filters”, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data (PDF), tr. 241–252, doi:10.1145/872757.872787
• Deng, Fan; Rafiei, Davood (2006), “Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters”, Proceedings of the ACM SIGMOD Conference (PDF), tr. 25–36
• Dharmapurikar, Sarang; Song, Haoyu; Turner, Jonathan; Lockwood, John (2006), “Fast packet classification using Bloom filters”, Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems (PDF), tr. 61–70, doi:10.1145/1185347.1185356, Bản gốc (PDF) lưu trữ ngày 2 tháng 2 năm 2007, truy cập ngày 27 tháng 10 năm 2011
• Dietzfelbinger, Martin; Pagh, Rasmus (2008), “Succinct Data Structures for Retrieval and Approximate Membership”, The Computing Research Repository (CoRR), arXiv:0803.3693
• Dillinger, Peter C.; Manolios, Panagiotis (2004a), “Fast and Accurate Bitstate Verification for SPIN”, Proceedings of the 11th Internation Spin Workshop on Model Checking Software, Springer-Verlag, Lecture Notes in Computer Science 2989
• Dillinger, Peter C.; Manolios, Panagiotis (2004b), “Bloom Filters in Probabilistic Verification”, Proceedings of the 5th Internation Conference on Formal Methods in Computer-Aided Design, Springer-Verlag, Lecture Notes in Computer Science 3312
• Donnet, Benoit; Baynat, Bruno; Friedman, Timur (2006), “Retouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives”, CoNEXT 06 – 2nd Conference on Future Networking Technologies, Bản gốc lưu trữ ngày 17 tháng 5 năm 2009, truy cập ngày 27 tháng 10 năm 2011
• Eppstein, David; Goodrich, Michael T. (2007), “Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters”, Algorithms and Data Structures, 10th International Workshop, WADS 2007, Springer-Verlag, Lecture Notes in Computer Science 4619, tr. 637–648, arXiv:0704.3313
• Fan, Li; Cao, Pei; Almeida, Jussara; Broder, Andrei (2000), “Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol”, IEEE/ACM Transactions on Networking, 8 (3): 281–293, doi:10.1109/90.851975. A preliminary version appeared at SIGCOMM '98.
• Goel, Ashish; Gupta, Pankaj (2010), “Small subset queries and bloom filters using ternary associative memories, with applications”, ACM Sigmetrics 2010, 38: 143, doi:10.1145/1811099.1811056
• Kirsch, Adam; Mitzenmacher, Michael (2006), “Less Hashing, Same Performance: Building a Better Bloom Filter”, trong Azar, Yossi; Erlebach, Thomas (biên tập), Algorithms – ESA 2006, 14th Annual European Symposium (PDF), 4168, Springer-Verlag, Lecture Notes in Computer Science 4168, tr. 456–467, doi:10.1007/11841036, Bản gốc (PDF) lưu trữ ngày 31 tháng 1 năm 2009, truy cập ngày 27 tháng 10 năm 2011
• Mortensen, Christian Worm; Pagh, Rasmus; Pătraşcu, Mihai (2005), “On dynamic range reporting in one dimension”, Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, tr. 104–111, doi:10.1145/1060590.1060606
• Pagh, Anna; Pagh, Rasmus; Rao, S. Srinivasa (2005), “An optimal Bloom filter replacement”, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (PDF), tr. 823–829, Bản gốc (PDF) lưu trữ ngày 4 tháng 2 năm 2012, truy cập ngày 27 tháng 10 năm 2011
• Porat, Ely (2008), “An Optimal Bloom Filter Replacement Based on Matrix Solving”, The Computing Research Repository (CoRR), arXiv:0804.1845
• Putze, F.; Sanders, P.; Singler, J. (2007), “Cache-, Hash- and Space-Efficient Bloom Filters”, trong Demetrescu, Camil (biên tập), Experimental Algorithms, 6th International Workshop, WEA 2007 (PDF), 4525, Springer-Verlag, Lecture Notes in Computer Science 4525, tr. 108–121, doi:10.1007/978-3-540-72845-0, Bản gốc (PDF) lưu trữ ngày 23 tháng 6 năm 2007, truy cập ngày 27 tháng 10 năm 2011
• Sethumadhavan, Simha; Desikan, Rajagopalan; Burger, Doug; Moore, Charles R.; Keckler, Stephen W. (2003), “Scalable hardware memory disambiguation for high ILP processors”, 36th Annual IEEE/ACM International Symposium on Microarchitecture, 2003, MICRO-36 (PDF), tr. 399–410, doi:10.1109/MICRO.2003.1253244, Bản gốc (PDF) lưu trữ ngày 14 tháng 1 năm 2007, truy cập ngày 27 tháng 10 năm 2011
• Shanmugasundaram, Kulesh; Brönnimann, Hervé; Memon, Nasir (2004), “Payload attribution via hierarchical Bloom filters”, Proceedings of the 11th ACM Conference on Computer and Communications Security, tr. 31–41, doi:10.1145/1030083.1030089
• Starobinski, David; Trachtenberg, Ari; Agarwal, Sachin (2003), “Efficient PDA Synchronization”, IEEE Transactions on Mobile Computing, 2 (1): 40, doi:10.1109/TMC.2003.1195150
• Stern, Ulrich; Dill, David L. (1996), “A New Scheme for Memory-Efficient Probabilistic Verification”, Proceedings of Formal Description Techniques for Distributed Systems and Communication Protocols, and Protocol Specification, Testing, and Verification: IFIP TC6/WG6.1 Joint International Conference, Chapman & Hall, IFIP Conference Proceedings, tr. 333–348