« Littlewood's Law of Miracles -The law of truly large numbers | Main | Google PageRank Prediction - liten uppföljning »
april 09, 2004
Bloom-filter
Perl.com-artikeln Using Bloom Filters, skriven av Maciej Ceglowski (bloggar Idle Words) förklarar Bloom-filter samt visar hur man använder Bloom-filter i Perl samt har ett flertal länkar till vidare dokumentation.
Först förklaras principen med Bloom-filter och jämför med en enkel (brute force) uppslagning i hashtabell.
Many people don't realize that there is an elegant alternative to the lookup hash, in the form of a venerable algorithm called a Bloom filter. Bloom filters allow you to perform membership tests in just a fraction of the memory you'd need to store a full list of keys, so you can avoid the performance hit of having to use a disk or database to do your lookups. As you might suspect, the savings in space comes at a price: you run an adjustable risk of false positives, and you can't remove a key from a filter once you've added it in. But in the many cases where those constraints are acceptable, a Bloom filter can make a useful tool.
En av användningarna av dessa filter är inom sociala nätverk (artificiella sociala nätverk eller distribuerade sociala protokoll såsom FOAF, Friends Of A Friend) för att verifiera användare. Denna teknik används i LOAF, det spamfilterprogram som Maciej Ceglowski skrivit tillsammans med Joshua Schachte, skapare av bl.a. memepool, del.icio.us samt GeoURL.
One drawback of existing social network schemes is that they require participants to either divulge their list of contacts to a central server (Orkut, Friendster) or publish it to the public Internet (FOAF), in both cases sacrificing a great deal of privacy. By exchanging Bloom filters instead of explicit lists of contacts, users can participate in social networking experiments without having to admit to the world who their friends are. A Bloom filter encoding someone's contact information can be checked to see whether it contains a given name or email address, but it can't be coerced into revealing the full list of keys that were used to build it. It's even possible to turn the false-positive rate, which may not sound like a feature, into a powerful tool.
Se även
På About LOAF beskrivs programmet, länk för nedladdning av program. Notera även beskrivninarna av attacker på sociala nätverk.
Posted by hakank at april 9, 2004 11:42 FM Posted to Matematik | Social Network Analysis/Complex Networks