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

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

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

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

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

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

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

Нека важи претпоставка да хеш функција бира сваки елемент низа са једнаком вероватноћом. Ако је 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}.

Референце

^ Knutт, Donald. „[[The Art of Computer Programming]], Errata for Volume 3 (2nd ed.)”. Архивирано из оригинала 06. 03. 2012. г. Приступљено 21. 01. 2012. Сукоб URL—викивеза (помоћ)

Литература

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
Kubiatowicz, J.; Bindel, D.; Czerwinski, Y.; Geels, S.; Eaton, D.; Gummadi, R.; Rhea, S.; Weatherspoon, H.; Weimer, W. (2000, VOL 35; PART 11), „Oceanstore: An architecture for global-scale persistent storage” (PDF), ACM SIGPLAN NOTICES, USA: 190—201, Архивирано из оригинала (PDF) 11. 3. 2012. г., Приступљено 21. 1. 2012 Проверите вредност парамет(а)ра за датум: |date= (помоћ)
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, Архивирано из оригинала (PDF) 06. 01. 2007. г., Приступљено 21. 01. 2012
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 (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, Архивирано из оригинала (PDF) 02. 2. 2007. г., Приступљено 21. 1. 2012
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, Архивирано из оригинала 17. 05. 2009. г., Приступљено 21. 01. 2012
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, Архивирано из оригинала (PDF) 31. 1. 2009. г., Приступљено 21. 1. 2012
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, Архивирано из оригинала (PDF) 04. 02. 2012. г., Приступљено 21. 01. 2012
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, Архивирано из оригинала (PDF) 23. 06. 2007. г., Приступљено 21. 01. 2012
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, Архивирано из оригинала (PDF) 14. 1. 2007. г., Приступљено 21. 1. 2012
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