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

Блумов филтер је просторно-ефикасна пробабилистичка структура података која служи за тестирање да ли је елемент члан скупа. Осмислио га је Бартон Хауард Блум 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 би увело могућност лажних негативних резултата.

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

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

Вероватноћа лажног позитивног резултата

Вероватноћа лажног позитивонг резултата $p$ као функција броја елемената $n$ у филтеру и величине филтера, $m$. Подразумеван је оптималан број хеш функција, $k= (m/n) \ln 2$.

Нека важи претпоставка да хеш функција бира сваки елемент низа са једнаком вероватноћом. Ако је m број битова у низу, вероватноћа да одређени бит није постављен на јединицу од стране одређене хеш функције током уметања елемента износи

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

Вероватноћа да тај бит није постављен на јединицу од стране било које хеш функције приликом уметања једног елемента је

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

Ако је уметнуто n елемената, вероватноћа да је одређени бит још увек једнак нули је

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

Из тога следи да је вероватноћа да је постављен на јединицу једнака

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

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

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

Ово није строго тачно јер подразумева независност вероватноћа постављања сваког бита. Међутим ако се претпостави да је то блиска апроксимација, важи да вероватноћа лажних позитивних резултата опада како m (број битова у низу) расте, и повећава се како n (број уметнутих елемената) расте. За дато m и n, вредност за k (број хеш функција) које минимизују вероватноћу лажног позитивног резултата је

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

што даје вероватноћу лажног позитивног резултата од

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

Потребан број битова, m за дато n (број уметнутих елемената) и тражену вероватноћу лажног позитивног резултата, p (уз претпоставку да се користи оптимална вредност за k) може да се израчуна заменом оптималне вредности за k у горњој једначини:

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

што може да се поједностави:

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

а то даје:

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

Ово значи да дужина Блумовог филтера мора да расте линеарно са бројем уметнутих елемената како би се одржала фиксна вероватноћа лажних позитивних резултата. Иако је горња формула асимптотска (то јест, важи за m, n → ∞), сасвим је прихватљива и за коначне вредности m и n; вероватноћа лажног позитивног резултата за коначни Блумов филтер од m битова, n елемената и k хеш функција је највише

$\left( 1-e^{-k(n+0.5)/(m-1)} \right)^k.$

Референце

• 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. et al. (2000), "Oceanstore: An architecture for global-scale persistent storage", 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", 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", 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, 4168, странице 684–695, doi:10.1007/11841036_61 
• Broder, Andrei; Mitzenmacher, Michael (2005), "Network Applications of Bloom Filters: A Survey", Internet Mathematics 1 (4): 485–509 
• Chang, Fay; Dean, Jeffrey; Ghemawat, Sanjay; Hsieh, Wilson; Wallach, Deborah; Burrows, Mike; Chandra, Tushar; Fikes, Andrew et al. (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) 
• 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, странице 30–39 
• Cohen, Saar; Matias, Yossi (2003), "Spectral Bloom Filters", Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, странице 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, странице 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, странице 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) 
• 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 
• 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", in Azar, Yossi; Erlebach, Thomas, Algorithms – ESA 2006, 14th Annual European Symposium, 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, странице 823–829 
• Porat, Ely (2008), "An Optimal Bloom Filter Replacement Based on Matrix Solving", The Computing Research Repository (CoRR) 
• Putze, F.; Sanders, P.; Singler, J. (2007), "Cache-, Hash- and Space-Efficient Bloom Filters", in Demetrescu, Camil, Experimental Algorithms, 6th International Workshop, WEA 2007, 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, странице 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