Objecten tellen in een gegevensstroom - dummies

Leren om objecten in een stream te tellen, kan u helpen de meest voorkomende items te vinden of gewone en ongewone gebeurtenissen te rangschikken. Dit algoritme maakt gebruik van hash-functies en benaderende schetsen. Dit gebeurt na het filteren van gedupliceerde objecten en het tellen van verschillende elementen die in de gegevensstroom zijn verschenen.

U gebruikt deze techniek om problemen op te lossen, zoals het vinden van de meest voorkomende zoekopdrachten in een zoekmachine, de best verkopende artikelen van een online verkoper, de zeer populaire pagina's in een website of de meest volatiele aandelen (door de tijden te tellen waarop een aandeel is verkocht en gekocht).

U past de oplossing voor dit probleem, Count-Min Sketch, toe op een datastream. Het vereist slechts één datapas en slaat zo weinig mogelijk informatie op. Dit algoritme wordt toegepast in veel real-world situaties (zoals het analyseren van netwerkverkeer of het beheren van gedistribueerde gegevensstromen). Het recept vereist het gebruik van een reeks hash-functies, elk geassocieerd met een bitvector, op een manier die lijkt op een Bloom-filter, zoals weergegeven in de afbeelding:

1. Initialiseer alle bitvectoren naar nullen in alle posities.
2. Pas de hashfunctie toe voor elke bitvector wanneer u een object uit een stream ontvangt. Gebruik het resulterende numerieke adres om de waarde op die positie te verhogen.
3. Pas de hashfunctie toe op een object en haal de waarde op de bijbehorende positie op wanneer u wordt gevraagd om de frequentie van een object in te schatten. Van alle waarden die worden ontvangen van de bitvectoren, neemt u de kleinste als de frequentie van de stream.

Hoe waarden worden bijgewerkt in een Count-Min-schets.

Omdat botsingen altijd mogelijk zijn bij gebruik van een hashfunctie, vooral als de bijbehorende bitvector weinig slots heeft, verzekert u dat meerdere bitvectoren bij de hand zijn, dat minstens één ervan de juiste waarde behoudt. De waarde van keuze moet de kleinste zijn, omdat deze niet wordt gemengd met vals-positieve tellingen als gevolg van botsingen.