User Tools

Site Tools


0639--b-l-c-bloom-la-gi

Bộ lọc Bloom, phát minh bởi Burton Howard Bloom năm 1970,[1] 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 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.

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à

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à

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

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

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à

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ị tối ưu để xác suất trên là nhỏ nhất là

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

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

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

từ đó thu được:

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.

  • 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 
  • 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 
  • 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 [liên kết hỏng]
  • 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 
  • 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 (11 tháng 10 năm 2018), “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 (11 tháng 10 năm 2018), “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 
  • 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, Algorithms – ESA 2006, 14th Annual European Symposium (PDF) 4168, Springer-Verlag, Lecture Notes in Computer Science 4168, tr. 456–467, doi:10.1007/11841036 
  • 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 
  • 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, 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 
  • 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 
  • 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 
0639--b-l-c-bloom-la-gi.txt · Last modified: 2018/11/07 17:09 (external edit)