Bloom filter
Een Bloom filter is een datastructuur waarmee computers kunnen zien of een bepaald element in een set voorkomt. Bloeifilters gebruiken hiervoor hash-functies. Voor elk element dat wordt toegevoegd, wordt een hashwaarde berekend. Wanneer een nieuw element wordt toegevoegd, wordt de hashwaarde ervan vergeleken met die van de andere elementen in de verzameling. Een Bloom filter is een probabilistische datastructuur. Het is mogelijk om een vals-positief te krijgen, maar niet om een vals negatief te krijgen. Met andere woorden, een query geeft ofwel "mogelijk in set" ofwel "zeker niet in set". Elementen kunnen worden toegevoegd aan de set, maar niet verwijderd. Voor elk toegevoegd element groeit de kans om een vals-positief te krijgen.
Edward Bloom stelde de Bloom-filter voor in 1970. In het artikel veronderstelt Bloom dat er een algoritme is om woorden aan het eind van een regel af te breken. Volgens het voorbeeld hebben de meeste woorden eenvoudige afbreekpatronen. Maar ongeveer 10% van de woorden heeft tijdrovende opzoekingen nodig om de juiste regel te vinden. Zijn geval was dat van het afbreken van ongeveer 500.000 woorden. Hij zag dat het gebruik van de "normale" foutloze hashing technieken, het opslaan van de afbreekpatronen, veel geheugen nodig zou hebben. Hij vond dat hij met behulp van zijn techniek de meeste opzoekingen kon elimineren. Bijvoorbeeld, een hashgebied dat slechts 15% van de grootte heeft die nodig is voor een ideale foutvrije hash elimineert nog steeds 85% van de schijftoegangen.
Meer in het algemeen zijn er minder dan 10 bits per element nodig voor een vals-positieve kans van 1%, onafhankelijk van de grootte of het aantal elementen in de set.
Vragen en antwoorden
V: Wat is een Bloom-filter?
A: Een Bloom-filter is een gegevensstructuur waarmee computers kunnen zien of een bepaald element voorkomt in een set. Het gebruikt hashfuncties om dit te doen door de hashwaarde van elk toegevoegd element te berekenen en deze te vergelijken met de andere elementen in de set.
V: Wat voor soort gegevensstructuur is een Bloom-filter?
A: Een Bloom-filter is een probabilistische gegevensstructuur, wat betekent dat er een kans is op fout-positieven, maar niet op fout-negatieven.
V: Wie heeft de Bloom-filter voorgesteld?
A: Edward Bloom stelde de Bloom-filter voor in 1970.
V: Wat was Edwards voorbeeld voor het gebruik van zijn techniek?
A: Het voorbeeld van Edward was het afbreken van ongeveer 500.000 woorden; hij ontdekte dat hij met zijn techniek de meeste zoekacties kon elimineren en de toegang tot de schijf met 15% kon verminderen.
V: Hoeveel bits per element zijn nodig voor 1% fout-positieve waarschijnlijkheid?
A: Er zijn minder dan 10 bits per element nodig voor 1% fout-positieve waarschijnlijkheid, onafhankelijk van de grootte of het aantal elementen in de verzameling.
V: Is het mogelijk om elementen uit een bloomfilter te verwijderen nadat ze zijn toegevoegd?
A: Nee, elementen kunnen alleen aan de verzameling worden toegevoegd, maar niet worden verwijderd.
V: Verhoogt of verlaagt het toevoegen van meer elementen de kans op een vals-positief resultaat?
A: Meer elementen toevoegen verhoogt de kans op een fout-positief resultaat.
