Papers we love: Black magic: het aantal elementen in een verzameling bepaald door de meest significante bits die sequentieel nul zijn

 
01 april 2017

Deze keer wil ik even stilstaan bij een probleem wat in eerste instantie heel triviaal lijkt, maar wat op grote schaal voor enorme uitdagingen kan zorgen. Dit probleem is het tellen van het aantal elementen in een verzameling, waarbij de verzameling technisch een zogenaamde multiset is. Concreet: gegeven een verzameling {2, 3, 2, 2, 3, 4, 5} zou je, vragend om het aantal unieke elementen, het antwoord 4 terug willen krijgen. De meest eenvoudige en trefzekere manier om dit te doen is door sequentieel door de verzameling heen te lopen en voor ieder element bij te houden dat je hem hebt gezien. Deze naïeve implementatie heeft als nadeel dat deze in lineaire tijd uitvoerbaar is en dat het geheugengebruik ook proportioneel is aan het aantal unieke elementen in de multiset.

Wanneer er sprake is van enorm grote sets is het geen mogelijkheid meer om op de hierboven beschreven manier de kardinaliteit van een element te bepalen. Door het geheugengebruik is de beschreven oplossing niet bruikbaar voor het gebruik op hele grote datasets. Om onder andered it probleem te aan te pakken zijn er in de loop der jaren verschillende algoritmes ontstaan die geen exact antwoord, maar een statistische benadering geven op dit soort vragen. Iemand die hier veel van zijn werk aan heeft gewijd en veel over heeft gepubliceerd was Philippe Flajolet. Door het onderwerp als een statistisch probleem te modelleren kun je ook uitspraken doen over de waarschijnlijkheid van de informatie in kwestie. Je gaat dus niet voor het exacte antwoord, maar je accepteert een foutmarge en neemt genoegen met een schatting. Meestal is een exact antwoord ook helemaal niet nodig. Voor een vraag als “hoeveel unieke zoekopdrachten zijn er op google.com geweest in deze maand” is het niet erg als je er een klein beetje naast zit.

Dit voorbeeld is niet toevallig. De paper van deze maand heet HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm en is een door Google-engineers geschreven uitbreiding op HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. De originele paper beschrijft het HyperLogLog algoritme voor de eerste keer. Het nadeel is dat dit een vrij formele en abstracte paper is. De paper van Google is veel praktischer, beschrijft een concrete implementetatie en laat als laatste ook nog een paar verbeteringen zien. Kortom, een meer toegankelijke paper die op het succes van het originele werk voortborduurt.

Dan is natuurlijk de vraag: hoe werkt HyperLogLog dan? Het antwoord hierop is verbazingwekkend eenvoudig, maar tegelijkertijd voelt het als iets magisch. In eerste instantie kan je (of in ieder geval ik) niet geloven dat het werkt. De crux zit hem in het uitdrukken van individuele elementen uit de multiset als (korte) hashes. In de originele HyperLogLog paper gebeurd dit met integers van 32 bit, in de recentere Google paper met 64 bit, al maakt dit conceptueel niet uit. Van de hash is het belangrijk dat alle gebruikelijke uitgangspunten van toepassing zijn. Door vervolgens van ieder element te bepalen hoeveel ‘leading zeroes’ er in de bitwise-representatie te zien zijn kun je uitspraken doen over de grootte van de gehele set.

Dit is een eenvoudige afweging van kansen: een set met elementen in de range 0 – 4 leert ons dat het patroon ‘000’ 20% van de totale opties beschrijft (alleen 0). Het patroon ‘010’ beschrijft al 60% van het bereik (0 + 1 + 2). Wanneer je dit combineert met een van de eigenschappen van een goede hash: het uniform verdelen van de mogelijke waardes tussen de upper-, en lower bound, heb je genoeg informatie om een goede schatting uit te voeren. Hoe meer significant bits er in de maximaal gevonden waarde voorkomen, hoe groter de set vermoedelijk is.

Natuurlijk zijn hier nog wel enkele bezwaren bij. Op een kleine set levert dit heel erg variabele resultaten op en op alle sets is er een kans dat je door de hashing functie te maken krijgt met een outlier. Voor beide scenarios worden ook oplossingen aangedragen. De kleine input size wordt genegeerd door dan te kiezen voor een ander algoritme. Voor de invloed van outliers wordt er gekozen om gebruik te maken van een verschillend aantal ‘buckets’. Een stream van n elementen deel je op in m losse substreams, welke de hoogste waarde allemaal in een eigen bucket opslaan. De maximale waarde is dan het gemiddelde (of eigenlijk het harmonisch gemiddelde) van de gemeten maximale waarden. Voor alle details verwijs ik jullie naar de paper, een uitgebreid blog artikel of een reference implementation van zo’n 150 regels aan python code.

Het gave van dit algoitme is de combinatie van het werken met enorme hoeveelheden data (de Google paper citeert “cardinalities well beyond 109 “) en het pure gevoel van magie van dit algoritme. Het is fascinerend dat je, door het bekijken van de bit patronen van waardes uit een set, kunt bepalen hoe groot die set (ongeveer) is. En dat tot onwaarschijnlijke grote input sets. Daarnaast is de daadwerkelijke implementatie van het algoritme ook nog relatief eenvoudig. In de paper staat de gehele implementatie, inclusief bijbehorende utility functies, op 1 pagina beschreven en ook de verschillende implementaties in bijvoorbeeld Redis [1, 2] zijn erg overzichtelijk. Mij spreekt het in ieder geval enorm tot de verbeelding. Een praktische, goed leesbare en enorm fascinerende paper.


Over deze papers we love: binnen Sogyo hebben we de traditie dat we maandelijks een nieuwsbrief rondsturen. De nieuwsbrief gaat veel over interne feitjes, echter sinds februari 2015 verzorgd Kevin van der Vlist het topic: papers we love. Hij deelt met ons papers die interessant zijn om te lezen en ons kunnen inspireren. De topic is uitgegroeid tot een mooie verzameling die we ook graag hier willen delen.


Werken met ?
Kijk dan bij onze mogelijkheden voor zowel starters als ervaren engineers.


Categorieën: Gave Technologie