Strömmande algoritmer och blomfilters - dummies

I hjärtat av många strömmande algoritmer är Bloom-filter. Skapat för nästan 50 år sedan av Burton H. Bloom, i en tid då datavetenskapen fortfarande var ganska ung, var den ursprungliga avsikten för denna algoritms skapare att handla rymd (minne) och / eller tid (komplexitet) mot vad han kallade tillåtna fel. Hans ursprungliga papper heter Utrymme / tidshantering i Hash-kodning med tillåtna fel.

Du kanske undrar om det utrymme och den tid som Bloom anser motivatorer för hans algoritm. Föreställ dig att du måste bestämma om ett element redan har dykt upp i en ström med hjälp av en tidigare diskuterad datastruktur. Att hitta något i en ström innebär att inspelning och sökning är snabba. Därför verkar ett hashbord ett idealiskt val. Hash tabeller behöver helt enkelt lägga till de element som du vill spela in och lagra dem. Att återställa ett element från ett hashbord är snabbt eftersom hash-tabellen använder lätt manipulerade värden för att representera elementet, snarare än själva elementet (vilket kan vara ganska komplext). Ändå har lagring av båda elementen och ett index till dessa element begränsningar. Om ett hashbord står inför fler element än vad den kan hantera, till exempel elementen i en kontinuerlig och potentiellt oändlig ström, kommer du att sluta med minneproblem vid något tillfälle.

Ett viktigt övervägande för Bloom-filter är att falska positiva kan uppstå, men falska negativ kan inte. Till exempel kan en dataström innehålla realtidsövervakningsdata för en kraftverk. Vid användning av ett Bloom-filter skulle analysen av dataströmmen visa att förväntade mätningar sannolikt är en del av uppsättningen tillåtna värden, med vissa fel tillåtna. När ett fel inträffar i systemet visar emellertid samma analys att avläsningarna inte ingår i uppsättningen tillåtna värden. De falska positiva är osannolikt att orsaka problem, men frånvaron av falska negativ innebär att alla är säkra. På grund av potentialen för falska positiva egenskaper är filter som Bloom-filteret probabilistiska datastrukturer - de ger inte ett visst svar men en sannolik.

Hashes, de enskilda posterna i ett hashbord, är snabba eftersom de fungerar som index för en bok. Du använder en hashfunktion för att producera hasen; Inmatningen är ett element som innehåller komplex data, och utmatningen är ett enkelt tal som fungerar som ett index för det elementet. En hashfunktion är deterministisk eftersom den producerar samma nummer varje gång du matar in en specifik dataingång.Du använder hasen för att hitta den komplexa informationen du behöver. Blomfiltrar är användbara eftersom de är ett sparsamt sätt att spela in spår av många element utan att behöva lagra dem bort som ett hashbord gör. De fungerar på ett enkelt sätt och använder följande som huvudingredienser:

• En liten vektor: En lista med bitelement, där varje bit i elementet kan ha ett värde på 0 eller 1. Listan är en lång Antal bitar som heter m. Ju större m är, desto bättre, men det finns sätt att optimalt definiera sin storlek.
• En serie hashfunktioner: Varje hash-funktion representerar ett annat värde. Hashfunktionerna kan snabbt knäcka data och producera jämnt fördelade resultat, vilket är lika med från minsta till maximala utgångsvärden för hasen.