Блумов филтар

Блумов филтер је просторно-ефикасна пробабилистичка структура података која служи за тестирање да ли је елемент члан скупа. Осмислио га је Бартон Хауард Блум 1970. године. Лажни позитивни резултати су могући, али лажни негативни нису; то значи да упит враћа или „јесте у скупу (што може да буде погрешно)“ или „дефинитивно није у скупу“. Елементи могу да се додају у скуп, али не могу да се из њега избацују (мада ово може да се реши помоћу бројачког филтера). Што се више елемената додаје у скуп, већа је вероватноћа лажних позитивних резултата.

Опис алгоритма

Пример Блумовог филтера, представља скуп {x, y, z}. Обојене сетрелице показују показују позиције у битовском низу у које је сваки елемент мапиран. Елемент w није у скупу {x, y, z}, јер једна од његових хеш вредности у низу садржи 0. На овој слици је m=18 и k=3.

Празан Блумов филтер је битовски низ од m битова који су сви постављени на 0. Такође је потребно и да буде дефинисано k различитих хеш функција, од којих свака пресликава неки скуп елемената у једну од m позиција са униформном случајном дистрибуцијом.

Како би се додао елемент у филтер, потребно је за њега израчунати сваку од k хеш вредности. Сваку од добијених k позиција у низу треба поставити на 1.

Како би се филтер претражио за неки елемент (тестирање да ли је елемент у скупу), поново се за њега рачуна свака од k хеш вредности како би се добило k позиција у низу. Ако је било који бит на некој од ових позиција једнак 0, елемент сигурно није у скупу – јер да јесте, онда би сви битови били постављени на 1 приликом уметања. Ако су све вредности једнаке 1, онда је или елемент у скупу, или су сви битови већ постављени на 1 током уметања других елемената скупа, што доводи до лажног позитивног резултата. У једноставном Блумовом филтеру не постоји начин да се разликују ова два случаја, али напредније технике могу да се користе за решавање овог проблема.

Захтев за дефинисањем k различитих независних хеш функција може да буде незгодан за велико k. Код „добре“ хеш функције са дугачким излазом, требало би да има јако мало или нимало корелација између различитих битовских поља таквог хеша, тако да оваква хеш функција може да се користи за генерисање више „различитих“ хеш функција тако што се њен излаз исецка у више битовских низова. Други приступ је да се проследи k различитих почетних вредности (на пример 0, 1, ..., k − 1) хеш функцији која узима два параметра, или да се ове вредности додају (допишу) елементу који се убацује у скуп. За веће m и(ли) k, услов независности између хеш функција може да се релаксира са занемарљивим порастом вероватноће лажних позитивних резултата (Dillinger & Manolios (2004a), Kirsch & Mitzenmacher (2006)). Специфично, показана је (Dillinger & Manolios (2004b)) ефективност добијања k индекса коришћењем унапређеног двоструког хеширања или троструког хеширања, што су варијанте двоструког хеширања које су ефективно једноставни генератори случајних бројева иницијализовани са две или три хеш вредности.

Уклањање елемената из једноставног Блумовог филтера је немогуће јер лажни негативни резултати нису дозвољени. Елемент се пресликава у k бита, и иако би постављање било ког од ових k бита на нулу било довољно да се елемент уклони, то би уједно уклонило и сваки други елемент који је пресликан у тај бит. Како не постоји начин да се утврди да ли је било који други елемент пресликан у неки од битова елемента који се уклања, постављање било ког од тих битова на 0 би увело могућност лажних негативних резултата.

Једнократно брисање елемента из Блумовог филтера може да се симулира додавањем другог Блумовог филтера који би садржавао елементе који су обрисани. Међутим, лажни позитивни резултати у другом филтеру би могли да произведу лажне негативне разултате, што није допуштено. У овом приступу не би било могуће поновно додавање претходно обрисаних елемената, јер би они морали да буду уклоњени из другог филтера.

Међутим, чест је случај да су сви елементи скупа доступни и могуће их је побројати, али је то скупо (на пример, јер захтева доста читања са диска). У овом случају, ако стопа лажних позитивних резултата постане сувише висока, филтер може да буде регенерисан; то би требало да се дешава релативно ретко.

Референце

• Koucheryavy, Y.; Giambene, G.; Staehle, D.; Barcelo-Arroyo, F.; Braun, T.; Siris, V. (2009), „Traffic and QoS Management in Wireless Multimedia Networks”, COST 290 Final Report, USA: 111, doi:XVI, 312  
• Kubiatowicz, J.; Bindel, D.; Czerwinski, Y.; Geels, S.; Eaton, D.; Gummadi, R.; Rhea, S.; Weatherspoon, H.; Weimer, W. (2000), „Oceanstore: An architecture for global-scale persistent storage” (PDF), ACM SIGPLAN NOTICES, USA: 190—201, doi:2000, VOL 35; PART 11  
• 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), стр. 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, стр. 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), стр. 30—39 
• Cohen, Saar; Matias, Yossi (2003), „Spectral Bloom Filters”, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data (PDF), стр. 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), стр. 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), стр. 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 (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 
• 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, стр. 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”, Ур.: Azar, Yossi; Erlebach, Thomas, Algorithms – ESA 2006, 14th Annual European Symposium (PDF), 4168, Springer-Verlag, Lecture Notes in Computer Science 4168, стр. 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, стр. 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), стр. 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”, Ур.: Demetrescu, Camil, Experimental Algorithms, 6th International Workshop, WEA 2007 (PDF), 4525, Springer-Verlag, Lecture Notes in Computer Science 4525, стр. 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), стр. 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, стр. 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, стр. 333—348 

Спољашње везе

• Табела удела лажно-позитивних резултата за различите конфигурације на сајту Универзитета у Висконсину-Медисон
• Блумови филтери и социјалне мреже, демо јава аплет, сајт Сан микросистемса
• Интерактивна демонстрација процесирања, ashcan.org
• „Оптималнији Блумови филтери“, Ели Порат (новембар 2007) Google TechTalk видео на Јутубу
• „Коришћење Блумових филтера“ детаљно објашњење Блумовог филтера помоћу Перла

Имплементације

• C имплементација, literateprograms.org
• C++ и Object Pascal имплементација, partow.net
• C# имплементација, codeplex.com
• Erlang имплементација, sites.google.com
• Haskell имплементација, haskell.org
• Java имплементација, tu-dresden.de
• Javascript имплементација, la.ma.la
• Lisp имплементација, lemonodor.com
• Perl имплементација, cpan.org
• PHP имплементација, code.google.com
• Python имплементација скалабилног Блумовог филтера, pypi.python.org
• Ruby имплементација, rubyinside.com
• Scala имплементација, codecommit.com
• Tcl имплементација, kocjan.org