布隆過濾器

布隆過濾器（英語：Bloom Filter）是1970年由伯頓·霍華德·布隆（Burton Howard Bloom）提出的。^[1]它實際上是一個很長的二進制向量和一系列隨機對映函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的演算法，缺點是有一定的誤辨識率和刪除困難。

基本概念

如果想判斷一個元素是不是在一個集合里，一般想到的是將集合中所有元素儲存起來，然後通過比較確定。鏈結串列、樹、雜湊表（又叫雜湊表，Hash table）等等數據結構都是這種思路。但是隨着集合中元素的增加，我們需要的儲存空間越來越大。同時檢索速度也越來越慢，上述三種結構的檢索時間複雜度分別為${\displaystyle O(n),O(\log n),O(1)}$。

布隆過濾器的原理是，當一個元素被加入集合時，通過K個雜湊函數將這個元素對映成一個位陣列中的K個點，把它們置為1。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。所以布隆過濾器可能會產生假陽性（誤報），但不會產生假陰性（漏報）。

演算法描述

布隆過濾器範例，表示集合{x, y, z} 。彩色箭頭顯示每個集合元素對映到位數組中的位置。元素w不在集合{x, y, z} 中，因為它雜湊到一個包含「0」的位數組位置。本例中，m = 18，k = 3。

一個「空布隆過濾器」是一個由m位組成的位陣列（英語：bit array），所有位都被設置為0。它配備了k個不同的雜湊函數，這些函數將集合元素對映到m個可能的數組位置之一。為了達到最佳效果，雜湊函數應為均勻分佈且獨立。通常，k是一個小的常數，它取決於期望的假陽性（誤報）率ε，而m與k和要添加的元素數量成正比。

要「添加」一個元素，將其分別輸入到k個雜湊函數中，以獲得k個數組位置。將所有獲得的位置的位設置為1。

要「檢驗」一個元素是否在集合中，將其輸入到每個k雜湊函數中，以獲得k個數組位置。如果這些位置「存在」位為0的位置，則該元素一定不在集合中；如果它在集合中，那麼當它被插入時，所有位都應該已經是1。如果所有位都已為1，説明該元素可能在集合中，又或許這些位是在插入其他元素時碰巧被設置爲1，從而導致假陽性。就一個簡單的布隆過濾器而言，並不能區分這兩種情況，但更先進的技術可以解決這個問題。

設計k個不同的獨立雜湊函數的要求對於大的k可能是難以實現的。對於一個具有寬輸出的良好雜湊函數，這種雜湊的不同位域之間應該幾乎沒有相關性，因此這種雜湊類型可以用於通過將其輸出切片成多個位域來生成多個「不同」的雜湊函數。或者，可以將k個不同的初始值（例如0, 1, ..., k − 1）傳遞給一個接受初始值的雜湊函數；或者將這些值加入（或追加）到鍵。對於較大的m和/或k，雜湊函數之間的獨立性可以放寬，而假陽性率的增加可以忽略不計。^[2]（具體而言，Dillinger & Manolios (2004b)展示了使用增強雙重雜湊和三重雜湊（雙雜湊的變體，實際上是用兩個或三個雜湊值播種的簡單隨機數生成器）導出k個索引的有效性。）

這樣簡單的布隆過濾器無法移除元素，因爲無法得知它對映到的k位中的哪些位應該被移除。雖然將這些k位中的任何一位設置為零足以移除該元素，但它也會移除任何恰好對映到該位的其他元素。由於簡單的演算法沒有提供任何方法來確定是否已添加任何其他影響要移除元素的位的元素，因此清除任何位都會引入假陰性（漏報）的可能性。

若要模擬從布隆過濾器中一次性移除元素的操作，可以引入一個輔助布隆過濾器（「移除過濾器」），用於儲存已移除的元素。 然而，第二個過濾器中的假陽性會變成複合過濾器（「原過濾器」與「移除過濾器」的聯合體）中的假陰性，這是不被希望遇到的。在這種方法中，卻無法重新添加先前被移除的元素，因為還須將其從「移除過濾器」中移除，這又會回到最初的問題。

常見的情況是，所有鍵（待過濾的所有元素）都能夠被獲取（可用），但枚舉它們的代價較高（例如，需要多次的硬碟讀取）。當假陽性率變得太高時，可以重新生成過濾器；但此類事件應該是相對罕見的。

優點

相比於其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器儲存空間和插入/查詢時間都是常數（${\displaystyle O(k)}$）。另外，雜湊函數相互之間沒有關係，方便由硬件並列實現。布隆過濾器不需要儲存元素本身，在某些對保密要求非常嚴格的場合有優勢。

布隆過濾器可以表示全集，其它任何數據結構都不能；

${\displaystyle k}$和${\displaystyle m}$相同，使用同一組雜湊函數的兩個布隆過濾器的交並^{[來源請求]}運算可以使用位元運算進行。

缺點

但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨着存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用雜湊表足矣。

另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位陣列變成整數陣列，每插入一個元素相應的計數器加1, 這樣刪除元素時將計數器減掉就可以了。然而要保證安全地刪除元素並非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器裏面。這一點單憑這個過濾器是無法保證的。另外計數器迴繞也會造成問題。

在降低誤算率方面，有不少工作，使得出現了很多布隆過濾器的變種。

參考

參照

1. Bloom (1970).
2. Dillinger & Manolios (2004a); Kirsch & Mitzenmacher (2006).

文獻

• Agarwal, Sachin; Trachtenberg, Ari. Approximating the number of differences between remote sets. 2006 IEEE Information Theory Workshop (PDF). Punta del Este, Uruguay. 2006: 217. CiteSeerX 10.1.1.69.1033 . ISBN 978-1-4244-0035-5. S2CID 2048278. doi:10.1109/ITW.2006.1633815.
• Ahmadi, Mahmood; Wong, Stephan, A Cache Architecture for Counting Bloom Filters, 15th international Conference on Networks (ICON-2007): 218, 2007, CiteSeerX 10.1.1.125.2470 , ISBN 978-1-4244-1229-7, S2CID 2967865, doi:10.1109/ICON.2007.4444089
• Almeida, Paulo; Baquero, Carlos; Preguica, Nuno; Hutchison, David, Scalable Bloom Filters (PDF), Information Processing Letters, 2007, 101 (6): 255–261, doi:10.1016/j.ipl.2006.10.007, hdl:1822/6627 
• Apache Software Foundation, 11.6. Schema Design, The Apache HBase Reference Guide, Revision 0.94.27, 2012
• Bloom, Burton H., Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM, 1970, 13 (7): 422–426, CiteSeerX 10.1.1.641.9096 , S2CID 7931252, doi:10.1145/362686.362692
• Blustein, James; El-Maazawi, Amal, optimal case for general Bloom filters, Bloom Filters — A Tutorial, Analysis, and Survey, Dalhousie University Faculty of Computer Science: 1–31, 2002
• Boldi, Paolo; Vigna, Sebastiano, Mutable strings in Java: design, implementation and lightweight text-search algorithms, Science of Computer Programming, 2005, 54 (1): 3–23, doi:10.1016/j.scico.2004.05.003
• Bonomi, Flavio; Mitzenmacher, Michael; Panigrahy, Rina; Singh, Sushil; Varghese, George, An Improved Construction for Counting Bloom Filters, Algorithms – ESA 2006, 14th Annual European Symposium (PDF), Lecture Notes in Computer Science 4168: 684–695, 2006, ISBN 978-3-540-38875-3, doi:10.1007/11841036_61
• Broder, Andrei; Mitzenmacher, Michael, Network Applications of Bloom Filters: A Survey (PDF), Internet Mathematics, 2005, 1 (4): 485–509, S2CID 1560675, doi:10.1080/15427951.2004.10129096 
• Byers, John W.; Considine, Jeffrey; Mitzenmacher, Michael; Rost, Stanislav, Informed content delivery across adaptive overlay networks, IEEE/ACM Transactions on Networking, 2004, 12 (5): 767, CiteSeerX 10.1.1.207.1563 , S2CID 47088273, doi:10.1109/TNET.2004.836103
• Calderoni, Luca; Palmieri, Paolo; Maio, Dario, Location privacy without mutual trust: The spatial Bloom filter (PDF), Computer Communications, 2015, 68: 4–16, ISSN 0140-3664, doi:10.1016/j.comcom.2015.06.011, hdl:10468/4762
• Calderoni, Luca; Palmieri, Paolo; Maio, Dario, Probabilistic Properties of the Spatial Bloom Filters and Their Relevance to Cryptographic Protocols, IEEE Transactions on Information Forensics and Security, 2018, 13 (7): 1710–1721, ISSN 1556-6013, S2CID 3693354, doi:10.1109/TIFS.2018.2799486, hdl:10468/5767 
• Chang, Fay; Dean, Jeffrey; Ghemawat, Sanjay; Hsieh, Wilson; Wallach, Deborah; Burrows, Mike; Chandra, Tushar; Fikes, Andrew; Gruber, Robert, Bigtable: A Distributed Storage System for Structured Data, Seventh Symposium on Operating System Design and Implementation, 2006
• Charles, Denis Xavier; Chellapilla, Kumar, Bloomier filters: A second look, Halperin, Dan; Mehlhorn, Kurt (編), Algorithms: ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15–17, 2008, Proceedings, Lecture Notes in Computer Science 5193, Springer: 259–270, 2008, ISBN 978-3-540-87743-1, S2CID 643445, arXiv:0807.0928 , doi:10.1007/978-3-540-87744-8_22
• Chazelle, Bernard; Kilian, Joe; Rubinfeld, Ronitt; Tal, Ayellet, The Bloomier filter: an efficient data structure for static support lookup tables, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (PDF): 30–39, 2004
• Cohen, Saar; Matias, Yossi, Spectral Bloom Filters, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data (PDF): 241–252, 2003 [2019-10-24], ISBN 978-1581136340, S2CID 1058187, doi:10.1145/872757.872787, （原始內容 (PDF)存檔於2021-03-10）
• Deng, Fan; Rafiei, Davood, Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters, Proceedings of the ACM SIGMOD Conference (PDF): 25–36, 2006
• Dharmapurikar, Sarang; Song, Haoyu; Turner, Jonathan; Lockwood, John, Fast packet classification using Bloom filters, Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems (PDF): 61–70, 2006, CiteSeerX 10.1.1.78.9584 , ISBN 978-1595935809, S2CID 7848110, doi:10.1145/1185347.1185356, （原始內容 (PDF)存檔於2007-02-02）
• Dietzfelbinger, Martin; Pagh, Rasmus, Succinct data structures for retrieval and approximate membership, Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (編), Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, Proceedings, Part I, Track A: Algorithms, Automata, Complexity, and Games, Lecture Notes in Computer Science 5125, Springer: 385–396, 2008, ISBN 978-3-540-70574-1, S2CID 1699996, arXiv:0803.3693 , doi:10.1007/978-3-540-70575-8_32
• Dillinger, Peter C.; Manolios, Panagiotis, Fast and Accurate Bitstate Verification for SPIN, Proceedings of the 11th International Spin Workshop on Model Checking Software, Springer-Verlag, Lecture Notes in Computer Science 2989, 2004a
• Dillinger, Peter C.; Manolios, Panagiotis, Bloom Filters in Probabilistic Verification, Proceedings of the 5th International Conference on Formal Methods in Computer-Aided Design, Springer-Verlag, Lecture Notes in Computer Science 3312, 2004b
• Donnet, Benoit; Baynat, Bruno; Friedman, Timur, Retouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives, CoNEXT 06 – 2nd Conference on Future Networking Technologies, 2006, （原始內容存檔於2009-05-17）
• Eppstein, David; Goodrich, Michael T., 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, Lecture Notes in Computer Science 4619, Springer-Verlag: 637–648, 2007, Bibcode:2007arXiv0704.3313E, arXiv:0704.3313 
• Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D., Cuckoo filter: Practically better than Bloom, Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies: 75–88, 2014, ISBN 9781450332798, doi:10.1145/2674005.2674994 . Open source implementation available on github.
• Fan, Li; Cao, Pei; Almeida, Jussara; Broder, Andrei, Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol (PDF), IEEE/ACM Transactions on Networking, 2000, 8 (3): 281–293 [2018-07-30], CiteSeerX 10.1.1.41.1487 , S2CID 4779754, doi:10.1109/90.851975, （原始內容 (PDF)存檔於2017-09-22）. A preliminary version appeared at SIGCOMM '98.
• Goel, Ashish; Gupta, Pankaj, Small subset queries and bloom filters using ternary associative memories, with applications (PDF), ACM SIGMETRICS Performance Evaluation Review, 2010, 38: 143, CiteSeerX 10.1.1.296.6513 , doi:10.1145/1811099.1811056
• Graf, Thomas Mueller; Lemire, Daniel, Xor Filters, ACM Journal of Experimental Algorithmics, 2020, 25: 1–16, Bibcode:2019arXiv191208258M, S2CID 209405019, arXiv:1912.08258 , doi:10.1145/3376122
• Grandi, Fabio, On the analysis of Bloom filters (PDF), Information Processing Letters, 2018, 129: 35–39, doi:10.1016/j.ipl.2017.09.004
• Kirsch, Adam; Mitzenmacher, Michael, Less Hashing, Same Performance: Building a Better Bloom Filter, Azar, Yossi; Erlebach, Thomas (編), Algorithms – ESA 2006, 14th Annual European Symposium (PDF), Lecture Notes in Computer Science 4168, Springer-Verlag, Lecture Notes in Computer Science 4168: 456–467, 2006, ISBN 978-3-540-38875-3, doi:10.1007/11841036, （原始內容 (PDF)存檔於2009-01-31）
• Koucheryavy, Y.; Giambene, G.; Staehle, D.; Barcelo-Arroyo, F.; Braun, T.; Siris, V., Traffic and QoS Management in Wireless Multimedia Networks, COST 290 Final Report, 2009: 111
• Kubiatowicz, J.; Bindel, D.; Czerwinski, Y.; Geels, S.; Eaton, D.; Gummadi, R.; Rhea, S.; Weatherspoon, H.; et al, Oceanstore: An architecture for global-scale persistent storage (PDF), ACM SIGPLAN Notices, 2000: 190–201 [2011-12-01], （原始內容 (PDF)存檔於2012-03-11）
• Maggs, Bruce M.; Sitaraman, Ramesh K., Algorithmic nuggets in content delivery (PDF), ACM SIGCOMM Computer Communication Review, July 2015, 45 (3): 52–66, CiteSeerX 10.1.1.696.9236 , S2CID 65760, doi:10.1145/2805789.2805800, （原始內容 (PDF)存檔於2021-08-14）
• Mitzenmacher, Michael; Upfal, Eli, Probability and computing: Randomized algorithms and probabilistic analysis, Cambridge University Press: 107–112, 2005, ISBN 9780521835404
• Mortensen, Christian Worm; Pagh, Rasmus; Pătrașcu, Mihai, On dynamic range reporting in one dimension, Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing: 104–111, 2005, ISBN 978-1581139600, S2CID 56473, arXiv:cs/0502032 , doi:10.1145/1060590.1060606
• Mullin, James K., Optimal semijoins for distributed database systems, IEEE Transactions on Software Engineering, 1990, 16 (5): 558–560, doi:10.1109/32.52778
• Pagh, Anna; Pagh, Rasmus; Rao, S. Srinivasa, An optimal Bloom filter replacement, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (PDF): 823–829, 2005
• Palmieri, Paolo; Calderoni, Luca; Maio, Dario, Spatial Bloom Filters: Enabling Privacy in Location-Aware Applications, Proc. 10th International Conference on Information Security and Cryptology (Inscrypt 2014) 8957, Springer-Verlag, Lecture Notes in Computer Science: 16–36, 2014, CiteSeerX 10.1.1.471.4759 , ISBN 978-3-319-16744-2, doi:10.1007/978-3-319-16745-9_2
• Porat, Ely, An optimal Bloom filter replacement based on matrix solving, Frid, Anna E.; Morozov, Andrey; Rybalchenko, Andrey; Wagner, Klaus W. (編), Computer Science, Theory and Applications: Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18–23, 2009, Proceedings, Lecture Notes in Computer Science 5675, Springer: 263–273, 2009, ISBN 978-3-642-03350-6, S2CID 3205108, arXiv:0804.1845 , doi:10.1007/978-3-642-03351-3_25
• Pournaras, E.; Warnier, M.; Brazier, F. M. T., A generic and adaptive aggregation service for large-scale decentralized networks, Complex Adaptive Systems Modeling, 2013, 1 (19): 19, doi:10.1186/2194-3206-1-19 . Prototype implementation available on github.
• Putze, F.; Sanders, P.; Singler, J., Cache-, Hash- and Space-Efficient Bloom Filters, Demetrescu, Camil (編), Experimental Algorithms, 6th International Workshop, WEA 2007 (PDF), Lecture Notes in Computer Science 4525, Springer-Verlag, Lecture Notes in Computer Science 4525: 108–121, 2007 [2007-07-18], ISBN 978-3-540-72844-3, doi:10.1007/978-3-540-72845-0, （原始內容 (PDF)存檔於2007-06-23）
• Rottenstreich, Ori; Kanizo, Yossi; Keslassy, Isaac, The Variable-Increment Counting Bloom Filter, 31st Annual IEEE International Conference on Computer Communications, 2012, Infocom 2012 (PDF): 1880–1888, 2012, CiteSeerX 10.1.1.174.7165 , ISBN 978-1-4673-0773-4, doi:10.1109/INFCOM.2012.6195563
• Sethumadhavan, Simha; Desikan, Rajagopalan; Burger, Doug; Moore, Charles R.; Keckler, Stephen W., Scalable hardware memory disambiguation for high ILP processors, 36th Annual IEEE/ACM International Symposium on Microarchitecture, 2003, MICRO-36 (PDF): 399–410, 2003, CiteSeerX 10.1.1.229.1254 , ISBN 978-0-7695-2043-8, S2CID 195881068, doi:10.1109/MICRO.2003.1253244, （原始內容 (PDF)存檔於2007-01-14）
• Starobinski, David; Trachtenberg, Ari; Agarwal, Sachin, Efficient PDA Synchronization (PDF), IEEE Transactions on Mobile Computing, 2003, 2 (1): 40, CiteSeerX 10.1.1.71.7833 , doi:10.1109/TMC.2003.1195150
• Stern, Ulrich; Dill, David L., 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: 333–348, 1996, CiteSeerX 10.1.1.47.4101 
• Wessels, Duane, 10.7 Cache Digests, Squid: The Definitive Guide 1st, O'Reilly Media: 172, January 2004, ISBN 978-0-596-00162-9, Cache Digests are based on a technique first published by Pei Cao, called Summary Cache. The fundamental idea is to use a Bloom filter to represent the cache contents.
• Tarkoma, Sasu; Rothenberg, Christian Esteve; Lagerspetz, Eemil, Theory and practice of bloom filters for distributed systems, IEEE Communications Surveys & Tutorials, no. 1. (PDF) 14: 131–155, 2012
• Zhiwang, Cen; Jungang, Xu; Jian, Sun, A multi-layer Bloom filter for duplicated URL detection, Proc. 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE 2010) 1: V1–586–V1–591, 2010, ISBN 978-1-4244-6539-2, S2CID 3108985, doi:10.1109/ICACTE.2010.5578947

外部連結

• Hash和Bloom Filter介紹 （頁面存檔備份，存於互聯網檔案館）
• 布隆過濾器視覺化頁面: 視覺化的位陣列添加，直觀理解布隆過濾器原理。