2014•2015
FACULTEIT WETENSCHAPPEN master in de informatica
Masterproef Big Data Counting : Hoe kunnen we een zeer groot aantal distincte objecten efficiënt tellen? Promotor : Prof. dr. Jan VAN DEN BUSSCHE
De transnationale Universiteit Limburg is een uniek samenwerkingsverband van twee universiteiten in twee landen: de Universiteit Hasselt en Maastricht University.
Jana Broeckx
Scriptie ingediend tot het behalen van de graad van master in de informatica
Universiteit Hasselt | Campus Hasselt | Martelarenlaan 42 | BE-3500 Hasselt Universiteit Hasselt | Campus Diepenbeek | Agoralaan Gebouw D | BE-3590 Diepenbeek
2014•2015
FACULTEIT WETENSCHAPPEN master in de informatica
Masterproef Big Data Counting : Hoe kunnen we een zeer groot aantal distincte objecten efficiënt tellen?
Promotor : Prof. dr. Jan VAN DEN BUSSCHE
Jana Broeckx
Scriptie ingediend tot het behalen van de graad van master in de informatica
Abstract In bedrijven zoals Selligent worden er dagelijks grote hoeveelheden informatie opgeslagen over marketingcampagnes van klanten, waaronder bijvoorbeeld e-mailcampagnes. Het is nodig deze enorme hoeveelheid data op een correcte en effici¨ente manier te verwerken. E´en van de grote problemen in het gebied van Big Data is het tellen van het aantal unieke elementen in een dataset, we bestuderen dit in deze thesis. Selligent is vooral ge¨ınteresseerd in het tellen van het aantal unieke gebruikers. We willen deze telling uitvoeren mits slechts gebruik te maken van een sublineaire hoeveelheid geheugen. We bestuderen hiervoor verscheidene algoritmen. In deze scriptie leggen we uiteindelijk de focus op het HyperLogLog algoritme, dit werd ook ge¨ımplementeerd. We gebruiken een dataset van Selligent om het algoritme empirisch te kunnen evalueren.
Dankwoord Graag wil ik Prof. dr. Jan Van den Bussche en dr. Lode Vanacken bedanken voor de goede begeleiding, hun advies en het opvolgen van deze thesis. Ook wil ik mijn ouders, Mathijs Creemers, Melissa Volont, Sven Broeckx en Kim Broeckx bedanken voor hun constante morele steun.
Inhoudsopgave 1 Inleiding
1
2 Big Data
3
2.1
RDBMS, NoSQL en NewSQL . . . . . . . . . . . . . . . .
4
2.2
Big Data in business . . . . . . . . . . . . . . . . . . . . .
7
2.3
Big Data en wetenschap . . . . . . . . . . . . . . . . . . .
9
2.4
Approximatie-algoritmen . . . . . . . . . . . . . . . . . . .
11
2.4.1
Originele approximatie-algoritmen . . . . . . . . . .
12
2.4.2
Approximatie-algoritmen en Big Data . . . . . . . .
12
3 Voorkennis 3.1
3.2
3.3
15
Basisbegrippen van de kanstheorie . . . . . . . . . . . . . .
16
3.1.1
Probabiliteit . . . . . . . . . . . . . . . . . . . . . .
16
3.1.2
Verwachtingswaarde . . . . . . . . . . . . . . . . .
16
3.1.3
Variantie . . . . . . . . . . . . . . . . . . . . . . . .
17
Belangrijke ongelijkheden
. . . . . . . . . . . . . . . . . .
17
3.2.1
Ongelijkheid van Markov . . . . . . . . . . . . . . .
17
3.2.2
Ongelijkheid van Chebyshev . . . . . . . . . . . . .
18
3.2.3
Ongelijkheid van Chernoff/Hoeffding . . . . . . . .
20
Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.3.1
Universeel hashen . . . . . . . . . . . . . . . . . . .
24
3.3.2
Uniforme hash-functies . . . . . . . . . . . . . . . .
24
i
3.3.3 3.4
Paarsgewijze onafhankelijkheid . . . . . . . . . . .
25
Streaming . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4 Heavy hitters 4.1
4.2
29
Frequentieschatting . . . . . . . . . . . . . . . . . . . . . .
30
4.1.1
Misra-Gries algoritme . . . . . . . . . . . . . . . . .
30
4.1.2
Count-Min algoritme . . . . . . . . . . . . . . . . .
33
4.1.3
Count-Sketch algoritme . . . . . . . . . . . . . . . .
38
Heavy Hitters . . . . . . . . . . . . . . . . . . . . . . . . .
46
4.2.1
Misra-Gries . . . . . . . . . . . . . . . . . . . . . .
47
4.2.2
Count-Min . . . . . . . . . . . . . . . . . . . . . . .
47
5 Distinct counting 5.1
5.2
5.3
5.4
53
Eenvoudige algoritmen . . . . . . . . . . . . . . . . . . . .
55
5.1.1
Morris algoritme . . . . . . . . . . . . . . . . . . .
55
5.1.2
Flajolet-Martin algoritme . . . . . . . . . . . . . .
61
LogLog . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
5.2.1
Het LogLog algoritme . . . . . . . . . . . . . . . .
67
5.2.2
Het SuperLogLog algoritme . . . . . . . . . . . . .
70
HyperLogLog . . . . . . . . . . . . . . . . . . . . . . . . .
72
5.3.1
Het HyperLogLog algoritme . . . . . . . . . . . . .
73
5.3.2
Het HyperLogLog++ algoritme . . . . . . . . . . .
77
Alternatieve manieren . . . . . . . . . . . . . . . . . . . .
87
6 Implementatie en toepassing
89
6.1
HyperLogLog implementatie . . . . . . . . . . . . . . . . .
89
6.2
HyperLogLog++ implementatie . . . . . . . . . . . . . . .
91
6.3
Resultaten . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
6.3.1
93
Eenvoudige kardinaliteiten . . . . . . . . . . . . . . ii
6.4
6.3.2
Use case: Per campagne en gebruikerslijst het aantal unieke gebruikers tellen . . . . . . . . . . . . . . . . 102
6.3.3
Use case: Per campagne, actie, gebruikerslijst en sensor . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.3.4
Toepassing in Selligent . . . . . . . . . . . . . . . . 104
Open-source implementaties . . . . . . . . . . . . . . . . . 110
7 Conclusie
113
A Resultaten implementatie
119
A.1 Het totaal aantal rijen tellen . . . . . . . . . . . . . . . . . 119 A.2 Het totaal aantal unieke gebruikers tellen . . . . . . . . . . 120 A.3 Het totaal aantal unieke gebruikers per gebruikerslijst tellen 121
iii
Hoofdstuk 1 Inleiding Er worden constant meer en meer data gecre¨eerd met behulp van smartphones, computers, sensoren, en zoveel andere hulpmiddelen. Dit kan veel voordelen bieden voor bijvoorbeeld bedrijven om hun klanten beter te verstaan. Er is echter ook een valkuil: we moeten nieuwe manieren vinden om met deze immense hoeveelheden data, ook wel Big Data genoemd, om te gaan. De traditionele manier van data management kan hier niet altijd een oplossing bieden. Daarom bestuderen we eerst wat de klassieke data management systemen zijn, en waarom deze wel of niet geschikt zijn voor het behandelen van Big Data in Hoofdstuk 2. Aangezien we met enorme hoeveelheden data werken, zullen approximatie-algoritmen belangrijk zijn. Intelligente approximatie-algoritmen kunnen ons mits een mogelijk kleine foutmarge een schatting geven van het exacte resultaat zonder excessief veel geheugen te gebruiken. Dit is vaak wat we willen indien we werken met Big Data. Zoals al aangehaald is het verwerken van deze data belangrijk voor bedrijven, zoals Selligent, het bedrijf dat het onderwerp voor deze masterthesis voorgesteld heeft. Ze hebben verscheidene vestigingen in Europa, waaronder Hasselt, en een SaaS platform in de V.S. Ze specialiseren zich in het aanbieden van services voor bedrijven, zoals onder andere het uitsturen van e-mails, het opvolgen van mobiele interacties, en meer. Ze maken het mogelijk verscheidene statistieken te bekijken zoals: of een gebruiker op een e-mail klikte, of een gebruiker op een link in een e-mail klikte, etc. Aangezien er grote hoeveelheden data binnenkomen, hebben we hier zeker en vast met Big Data te maken. E´en van de statistieken die nu niet optimaal wordt afgehandeld is distinct counting: het effici¨ent tellen van het aantal unieke elementen in een stream van getallen. Ze willen dit gebruiken om bijvoorbeeld het aantal unieke gebruikers te kunnen opvragen. Hierdoor zijn ze ge¨ınteresseerd om alternatieven te evalueren. 1
Voordat we echter met distinct-count algoritmen aan de slag kunnen gaan, is er voorkennis vereist in verband met kanstheorie, ongelijkheden, hashing en streaming. Dit wordt overlopen in Hoofdstuk 3. We veronderstellen dat de data die we hebben een read-once sequentie van items is, met andere woorden een stream. We defini¨eren hiervoor een aantal streaming algoritmen in Hoofdstuk 4. Deze tellen nog niet het aantal unieke elementen, maar geven een basis in verband met streaming algoritmen die we kunnen gebruiken in volgende hoofdstukken. We bekijken eerst frequentieschatting, dit is een relatief simpel probleem dat we kunnen oplossen met streaming algoritmes. De algoritmen die we bekijken zijn Misra-Gries, Count-Min en Count-Sketch. Deze vormen een basis voor het bepalen van de heavy hitters in een stream van data. Simpelweg kunnen we dit beschrijven als het bepalen van de meest frequente items. Door het bestuderen van het heavy hitters-probleem verwerven we een goede basis om de vraagstelling van deze thesis te bestuderen: het tellen van het aantal unieke elementen in een datastream. We beschrijven dit in Hoofdstuk 5. Een simpele oplossing zou zijn een lijst bijhouden van alle unieke elementen. Dit is echter niet effici¨ent en gebruikt teveel geheugen. Wat we willen is een algoritme dat mits weinig geheugengebruik toch een mooie approximatie van de kardinaliteit van een data-set kan bepalen. Het eerste streaming algoritme dat hiervoor ontworpen werd was dat van Flajolet en Martin. Het LogLog-algoritme kwam een paar jaar later als verbetering van het originele Flajolet-Martin algoritme. Tenslotte bestuderen we HyperLogLog, wat een verbeterde versie van het LogLog algoritme is. Ondanks dat de uitwerking in elk algoritme verschillend is, is het basisidee hetzelfde: we gebruiken een gepaste hash-functie om alle waarden in de stream te hashen. We bekijken dan het aantal voorloopnullen van deze hash-waarden en het maximum wordt bijgehouden. Met behulp van die waarde kunnen we het aantal unieke elementen in een stream schatten. Hoe we dit schatten is echter voor elk van de algoritmes verschillend. Uiteindelijk bekijken het HyperLogLog++ algoritme wat een empirisch ge¨evalueerde verbetering is van HyperLogLog. Aangezien de toepassing van dit algoritme vooral van belang is voor Selligent, programmeren we zowel het HyperLogLog als het HyperLogLog++ algoritme in Java. Belangrijke punten van de implementatie worden besproken in Hoofdstuk 6. Met behulp van dataset aangeboden door Selligent voeren we testen uit in verband met de effici¨entie en het geheugengebruik van de twee algoritmen. De resultaten van deze testen vergelijken we met de manier waarop Selligent nu het aantal unieke gebruikers telt.
2
Hoofdstuk 2 Big Data Big Data verwijst naar technologie¨en en initiatieven om data op te slaan, op te halen en te analyseren die te divers, te snel veranderd of te enorm zijn voor conventionele technologie¨en, methoden en infrastructuur om effici¨ent te kunnen behandelen. Big Data is anders in drie aspecten: volume, snelheid en vari¨eteit. Het volume van Big Data is enorm. In 2012 werd er bijvoorbeeld ongeveer 2,5 exabytes aan data gecre¨eerd per dag. Dit getal stijgt nog steeds elke maand. Voor veel toepassingen is de snelheid waarop data worden gecre¨eerd zelfs nog belangrijker dan het volume. Zo slaagde een groep in het MIT Media Lab erin om de locatie van verscheidene mobiele telefoons te gebruiken om te bepalen hoeveel mensen er op de parking van Macy’s waren op Black Friday. De wetenschappers konden nu schatten hoeveel er die dag gekocht zou worden voordat deze aankopen gedaan werden. Data kunnen opgehaald worden in de vorm van berichten, foto’s en filmpjes en andere updates op sociale netwerken, maar bijvoorbeeld ook als GPS signalen en sensoren op gebouwen. Veel van deze manieren van data ophaling zijn redelijk nieuw. Hierdoor bestaat er een grote vari¨eteit in de data die opgehaald kunnen worden. [20] Enkele grote bronnen van Big Data zijn sociale netwerkprofielen, likes en commentaren op blogs of forums, activiteit-gegenereerde data (zoals website tracking, logs van applicaties en data van sensoren), Software as a Service (SaaS) en cloud applicaties, publiek beschikbare data (zoals informatie op Wikipedia en IMDb), Hadoop MapReduce applicatieresultaten, en digitale archieven. [23]
3
2.1
RDBMS, NoSQL en NewSQL
We deden echter al aan datamanagement voordat we te maken hadden met Big Data. Conventionele technologie¨en om data te managen en te verwerken zijn relationele databasemanagementsystemen (RDBMS). Data worden vaak beheerd met behulp van de querytaal SQL. Het relationele model en SQL werden ontworpen om als administratieve hulpmiddelen te gebruiken. Het doel was applicaties voor bijvoorbeeld het bankwezen makkelijker te maken. Deze traditionele manier van werken werd ontworpen in een tijdperk waar de hardware en software nog niet moesten voldoen aan de performantie- en schaalbaarheidsvereisten van enorme hoeveelheden, vaak ongestructureerde data die op diverse manieren verwerkt worden. Toch wordt het relationeel model en SQL ook nog steeds zeer veel gebruikt de dag van vandaag. [2] Het is mogelijk om databasesystemen van op afstand te gebruiken door gebruik te maken van telecommunicatietechnologie. Eveneens is het mogelijk om databases die op verschillende locaties verspreid staan aan te spreken als ´e´en logische database. In beide gevallen spreken we over gedistribueerde databasesystemen, wat de dag van vandaag zeer vaak gebruikt wordt. Formeel beschrijven we dit als volgt: meerdere, logisch samenhangende databases zijn gedistribueerd over verscheidene machines die niet allemaal verbonden zijn met een gemeenschappelijke centrale verwerkingseenheid, maar gekoppeld zijn met behulp van een computernetwerk. Dit kan voordelen bieden zoals een betere prijs/performantie ratio, geografische verspreiding, betere betrouwbaarheid en uitbreidbaarheid. Indien we cruciale bestanden op meerdere machines opslaan, zullen we deze niet verliezen indien ´e´en van de machines faalt, we noemen dit replicatie. We kunnen natuurlijk ook de data horizontaal of verticaal fragmenteren, m.a.w. data verspreiden over verscheidene machines. [24] Het CAP theorema, ook wel Brewer’s stelling genoemd, zegt dat gedistribueerde computersystemen maximaal aan twee van de volgende voorwaarden kunnen voldoen tegelijkertijd mits een aanvaardbare reactietijd: consistentie, beschikbaarheid en tolerantie van de partitie. Consistentie betekent dat elke node in het systeem dezelfde data ziet op hetzelfde moment. Beschikbaarheid betekent dat we altijd een antwoord zullen krijgen op een request, m.a.w. elk algoritme dat aangeroepen wordt, moet uiteindelijk stoppen, maar we zetten geen begrenzing op hoe lang dit algoritme runt. Tolerantie van de partitie betekent dat het systeem blijft functioneren bij verlies van willekeurige berichten. [12] [34] De klassieke relationele databases voldoen aan consistentie en tolerantie 4
van de partitie, maar niet aan beschikbaarheid. Om deze consistentie en tolerantie te garanderen voldoen bijvoorbeeld MySQL en Microsoft SQL Server meestal aan ACID transacties. ACID staat voor een set van vier regels waar databases aan kunnen voldoen: operaties worden gecommit of falen in hun geheel (atomiciteit), de uitvoering van transacties zorgt voor een consistente staat van de database (consistentie), de gevolgen van een transactie staan los van de concurrente uitvoering van andere transacties (isolatie) en een transactie wordt permanent zodra ze wordt uitgevoerd (duurzaamheid). Een transactie die voldoet aan deze regels wordt atomair, consistent, ge¨ısoleerd en duurzaam uitgevoerd. Zonder ACID-regels kan het dat twee transacties tegelijkertijd bijvoorbeeld eenzelfde tupel willen aanpassen, waardoor het mogelijk is dat er inconsistenties in de database ontstaan. Sociale netwerksites, waar gedistribueerde gegevensverwerking belangrijk is, vinden deze regels meestal niet zo cruciaal, aangezien consistentie geen vereiste is. Financi¨ele instellingen willen wel dat elke transactie betrouwbaar wordt uitgevoerd, dus hier zijn deze regels wel belangrijk. [38] Doordat relationele databases deze ACID regels ondersteunen, betekent dit dat er vaak veel overhead is voor alledaagse transacties. Dit kan een soort van handicap worden indien het bedrijf met grote hoeveelheden data werkt. Indien we een relationele database willen uitbreiden om meer gelijktijdige gebruikers te ondersteunen en meer data te kunnen opslaan, moeten we grote en dure servers met meer CPU’s, geheugen en schijfopslag voorzien. Op een gegeven moment wordt zelfs de capaciteit van de grootste server overtroffen en is verder schalen niet meer mogelijk. We zien dat verscheidene operaties die zeer belangrijk zijn voor Big Data moeilijk kunnen gerealiseerd worden met behulp van de relationele databases: zoals al aangehaald is de schaalbaarheid eerder gelimiteerd en vaak kostelijk, er kan niet goed omgegaan worden met ongestructureerde data of data in onverwachte formaten en basisqueries zoals het kortste pad implementeren gaat moeizaam met behulp van SQL. [5] [28] [34] Indien er sprake is van Big Data, wordt er vaker voor NoSQL gekozen, dit is een breed gamma van databasemanagementsystemen die een groot verschil vertonen in vergelijking met de klassiekere relationele databasemanagementsystemen. In plaats van consistentie en tolerantie van de partitie, wordt NoSQL gebruikt als acroniem voor “niet alleen SQL”. Ondanks dat er geen formele overeenkomst is, hebben deze vaak de volgende vier kenmerken: simpele en flexibele niet-relationele datamodellen, de mogelijkheid horizontaal te schalen over servers met relatief eenvoudige hardware, hoge beschikbaarheid en het vaak niet ondersteunen van ACID transacties. Databases die gebouwd werden zonder relaties zijn schaalbaarder, wat een vereiste is indien we met Big Data werken. Het is niet nodig om dure, krachtigere, grotere servers aan te schaffen indien er uitgebreid 5
moet worden zoals bij relationele databasemanagementsystemen aangezien de database gedistribueerd kan worden over verscheidene hosts indien nodig. Deze manier van schalen is makkelijk en vaak goedkoper. Deze manier van werken biedt voordelen in verband met web applicaties omdat er veel transacties gebeuren en beschikbaarheid hiervoor belangrijk is. Het tegengestelde van de ACID regels is de BASE aanpak, wat staat voor beschikbaarheid, soft state en uiteindelijk consistent. In tegenstelling tot ACID wordt dit wel vaak gebruikt in NoSQL. [2] [15] [34] De afwezigheid van de ACID-regels in NoSQL kan wel een probleem vormen voor missiekritische systemen. Soms is het beter om de performantieproblemen veroorzaakt door overmatig gebruik van transacties op te lossen, in plaats van het gebrek van transactieondersteuning te omzeilen. Verder zijn ook het gebruik van low-level querytalen, het gebrek aan gestandaardiseerde interfaces en de grote investering in SQL redenen waarom er niet altijd voor NoSQL wordt gekozen. [15] Om deze problemen op te lossen, werd NewSQL voorgesteld. Dit is een klasse van moderne relationele databasemanagementsystemen. De schaalbare performantie, die NoSQL biedt, kan nu wel ondersteund worden voor bijvoorbeeld online transactieverwerking, ondanks dat de ACID regels van een traditionele database blijven gelden. Alle commerci¨ele NewSQL data stores ondersteunen het relationele model en gebruiken SQL als hun querytaal, ook al zijn ze gebaseerd op andere veronderstellingen en architecturen dan traditionele relationele databasesmanagementsystemen. [15] Er is echter een probleem: de relatie tussen ACID transacties en het CAP theorema. Het lijkt dat deze twee incompatibel zijn doordat er bijna geen hoog beschikbare systemen zijn die arbitraire operaties met meerdere objecten en ACID semantiek ondersteunen. Dit komt mogelijk door het ontwerp van gedistribueerde databasesystemen waar consistentie verkozen werd in plaats van hoge beschikbaarheid. Daarom gebruiken NewSQL en ACID transacties vaak een zwakkere vorm van isolatie. Dit betekent dat traditionele implementaties van garanties zoals lock-based niet voorhanden zijn, aangezien dit voor onbeschikbaarheid zou zorgen. Recent werd er echter aangetoond dat hoge beschikbaarheid en ACID transacties elkaar niet uit hoeven te sluiten. Het is mogelijk de semantiek van de ACID en NewSQL databases met elkaar te matchen zonder hoge beschikbaarheid op te offeren. Daardoor werden Highly Available Transactions (HATs) ge¨ıntroduceerd, een klasse van transactionele garanties die uitvoerbaar zijn met hoge beschikbaarheid en lage reactietijd in partitie-gevoelige omgevingen. [3] We concluderen dat RDBMS niet het optimale databasemanagementsysteem is indien we gebruik maken van Big Data. We kunnen NoSQL gebrui6
ken, maar zoals besproken kunnen we hier niet gebruik maken van ACID transacties. Indien dit echter een vereiste is, kunnen we overgaan op het gebruik van NewSQL, wat gelijkaardige garanties biedt als relationele databases, ondanks dat we toch makkelijk kunnen schalen, wat belangrijk is bij Big Data.
2.2
Big Data in business
We zijn ondertussen op de hoogte van verscheidene (al dan niet traditionele) databasemanagementsystemen. We weten ook dat Big Data simpelweg betekent dat we te maken hebben met een enorm grote hoeveelheid data. We bekijken nu enkele toepassingen om te verduidelijken hoe belangrijk Big Data de dag van vandaag net is. Er zijn tegenwoordig zeer veel manieren waarop data kunnen worden opgehaald: via telefoons, kredietkaarten, televisies, computers, sensoren op gebouwen of vliegtuigen en zoveel meer. Opdat deze data nuttig kunnen gebruikt worden, is het belangrijk dat ze op slimme manieren verwerkt worden. [33] Intelligent verwerkte data kunnen gebruikt worden om kennis te cre¨eren. Daarom is knowledge management een essenti¨ele competentie geworden voor vele bedrijven. Met de komst van Big Data is knowledge management alleen maar belangrijker en krachtiger geworden. Indien data goed ge¨ınterpreteerd worden, kunnen deze gebruikt worden om effici¨ente ‘datadriven’ beslissingen te maken, kan men leren van fouten of successen waardoor er bepaalde operaties of processen kunnen verbeterd worden en worden culturele verandering en innovatie gestimuleerd. We kunnen betere voorspellingen maken, slimmere beslissingen en doeltreffende interventies houden in gebieden waar nodig. Bedrijven die data-driven beslissingen nemen zijn gemiddeld zowel productiever als winstgevender dan de competitie. Om wat verduidelijking te geven, behandelen we eerst voorbeelden in verband met Big Data voor bedrijven. [20] [27] Voor de komst van online winkels konden boekhandels alleen de boeken die klanten kochten gebruiken om bijvoorbeeld een loyaliteitsprogramma op te starten. Door de komst van online winkels zoals Amazon, kan ook opgeslagen worden welke boeken de klant heeft bekeken, hoe de klant de website gebruikt, hoe fel men be¨ınvloed wordt door reviews, promoties of het uitzicht van een pagina, en gelijkenissen tussen individuen en groepen kunnen opgespoord worden. Deze informatie kan gebruikt worden om een lijst te maken van boeken die de klant mogelijk interessant vindt. Telkens de klant op de website surft, kan deze lijst verfijnd worden. [20] [31] 7
In luchthavens moet de informatie over aankomsttijden zeer accuraat zijn. Indien een vliegtuig landt voordat het grondpersoneel hier klaar voor is, of omgekeerd, zorgt dit voor hogere kosten aangezien er altijd een groep werknemers niet kan werken. Jarenlang gebruikte men de ge¨estimeerde tijd van aankomst (ETA) dat de piloot schatte voordat het vliegtuig moest landen. Het bedrijf PASSUR begon in 2001 geschatte aankomsten aan te bieden als service. Door rekening te houden met het weer, vliegschema’s en andere factoren zoals feeds van een passief radarstationsnetwerk dichtbij het vliegveld. In 2012 waren er al meer dan 155 van deze installaties. Elke 4,6 seconden worden er gegevens verstuurd over een vliegtuig dat wordt waargenomen. Er is dus een enorme hoeveelheid data dat constant wordt vastgelegd. Door deze ‘RightETA’-benadering te gebruiken worden openingen tussen geschatte en eigenlijke aankomsttijden bijna volledig ge¨elimineerd. Door het gebruik van Big Data kon er preciezer worden geschat, waardoor er betere beslissingen werden genomen. [20] Sears Holdings besliste enkele jaren geleden dat ze meer waarde moesten halen uit de grote hoeveelheden data dat ze collecteerden om betere aanbiedingen te geven aan klanten, of zelfs gepersonaliseerde promoties aan te bieden in bepaalde gebieden. Het bleek echter niet zo makkelijk te zijn als gedacht, aangezien het 8 weken kon duren voordat de gepersonaliseerde promoties gegenereerd werden. De data die nodig waren voor zulke analyses waren te volumineus en gefragmenteerd. Daarom koos Sears Holdings om over te stappen op Big Data technologie¨en en praktijken. Sears begon met het gebruik van een Hadoop cluster om alle inkomende data in op te slaan. Doordat de data niet langer van verschillende bronnen werden opgehaald, versnelde dit het analyseproces. Hierdoor kon het bedrijf veel sneller en preciezer aanbiedingen aan klanten geven. Ze kunnen nu bijna real-time de prijs van producten aanpassen afhankelijk van gepersonaliseerde coupons en locatie. [20] [37] Buiten technische veranderingen, brengt Big Data ook een aantal leidinggevende aanpassingen met zich mee. Bedrijven zullen niet alle voordelen van de transitie naar Big Data ervaren als deze verandering niet goed wordt beheerd. Leiderschap is nodig om doelstellingen te formuleren, om te defini¨eren wat succes betekent en om de juiste vragen te stellen. Menselijk inzicht is nog steeds van kritische significantie. [20] De beslissingen die moeten genomen worden en wie deze moet maken is een volgende aanpassing. Het beslissingsrecht ligt vaak nog steeds bij senior management, die vaak gebruik maken van ervaring en intu¨ıtie. Om Big Data effici¨ent te gebruiken, moet hiervan afgestapt worden en moeten de juiste personen gebruikt worden om data-driven beslissingen te kunnen maken. Het is mogelijk nodig om extra mensen in dienst te nemen die 8
kennis hebben van de data die geanalyseerd werden, om zo correcte conclusies te kunnen verwerven die gebruikt kunnen worden om toekomstige beslissingen in het bedrijf te nemen. [20] [41] Verder is het nodig dat wetenschappers en andere professionals weten wat ze moeten doen aangezien het volume zo groot en de opslagkost voor data zo klein is. Het is belangrijk te weten hoe er correct moeten omgegaan worden met Big Data. Zulke werknemers zijn echter moeilijk te vinden. Indien de switch naar Big Data wordt gemaakt, moet ook de technologie ge¨ updatet worden. Hiervoor is vele goede open-source software beschikbaar. Om deze software effici¨ent te kunnen gebruiken, moeten de werknemers echter wel de juiste vaardigheden hebben. Om goede beslissingen te maken, is het nodig dat de juiste data naar de goede persoon gebracht worden, zodat deze op de meest effici¨ente manier kunnen gebruikt geworden. Zowel mensen die het probleem verstaan als personen die ervaring hebben in het oplossen van problemen zijn van belang. Tenslotte is het nodig dat het bedrijf minder op intu¨ıtie, maar meer op data gaat vertrouwen. [20]
2.3
Big Data en wetenschap
Net zoals in de economische wereld wordt er in wetenschap ook belang gehecht aan Big Data. Big Data kan bijvoorbeeld helpen in de gezondheidsindustrie om een epidemie te voorspellen en misschien ook te voorkomen. Dit gebeurt door het analyseren van grote datasets en daarin patronen te herkennen. Big Data kan gebruikt worden in verscheidene toepassingsgebieden zoals bio-informatica, genetica, geneeskunde, onderwijs en ingenieurswetenschappen. Voorbeelden van mogelijke bronnen van informatie zijn telefoongegevens, deeltjesversnellers, databanken van overheden en andere grote instellingen of zelfs grootschalige enquˆetes en experimenten. [33] In Kenia heeft Nathan Eagle samengewerkt met het gezondheidsministerie om een systeem te cre¨eren dat de bloedbanken in ziekenhuizen monitort. Verpleegsters werden gevraagd een sms te sturen zodra er bloed gebruikt werd, zodat dit bijgevuld kon worden indien nodig. Initieel was het geen groot succes. Dit project kostte de verpleegsters geld aangezien ze met hun eigen GSM berichten moesten sturen. Het project werd echter gered toen GSM operatoren wilden meewerken. [33] [35] Big Data kan ook gebruikt worden om de bacteri¨en die op en in mensen leven beter te bestuderen. Deze bacteri¨en helpen bijvoorbeeld energie uit voedsel te verkrijgen en gezondheid te behouden. Iedereen heeft een an9
Figuur 2.1: De opslagkost van data vanaf 1992 tot en met 2013 [21]
dere combinatie van bacteri¨en in zijn maag-darmstelsel en onderzoekers weten nog steeds niet alles over dit onderwerp. Studies die hier onderzoek naar doen, hebben vaak behoefte aan immense hoeveelheden data. Dit komt doordat vele testpersonen volledig andere data genereren zoals informatie over hun gezondheid, hun omgeving, en de mensen waarmee de pati¨ent frequent in contact komt. Een ander topic binnen dit onderwerp is bijvoorbeeld welke microben op onze smartphones zitten en hoe deze daar gekomen zijn. Een ander project dat nog veel meer data vereist, is het bestuderen van de invloed van deze microben op mensen in de loop van verscheidene decennia. Zo kunnen er mogelijk redenen gevonden worden waarom bepaalde aandoeningen zoals allergie¨en, het prikkelbaredarmsyndroom of het metaboolsyndroom nu meer voorkomen dan vroeger. [33] [39] Voor de komst van Big data moesten wetenschappers een experiment plannen door te beslissen welke data ze zouden collecteren, daarna werden deze geanalyseerd. Tegenwoordig zijn de opslagkosten voor data echter zo laag, zoals te zien in Figuur 2.1, dat vaak alle mogelijke data worden opgehaald om daarna te kunnen zoeken naar significante patronen. Dit komt wel met extra risico’s. [33] Het kan zijn dat er twijfelachtige of bedrieglijke correlaties gevonden worden met bepaalde datasets. Het is nog steeds nodig dat wetenschappers zich de juiste vragen stellen om een hypothese te cre¨eren, een test te ontwerpen en te bepalen of de hypothese bevestigd kan worden met behulp 10
van de data. [33] Een voorbeeld van bedrieglijke correlaties is te vinden in een ander onderzoek van Nathan Eagle. Hij werkte ook in Rwanda mee aan een project in verband met mobiele telefoongegevens. Er werd gekeken naar waar mensen dagelijks of wekelijks naartoe pendelden. Al snel werden er patronen herkend. Indien er mensen in een bepaald dorp minder bewogen, dan hadden ze vaker een overdraagbare ziekte, zoals de griep of zelfs cholera. Uiteindelijk kwam Eagle erachter dat het systeem geen ziekte, maar overstromingen omschreef waardoor de wegen tijdelijk niet bruikbaar waren. Er was geen Big Data nodig om overstromingen te vinden. Maar indien mensen in dergelijke dorpen echter informatie verschaffen, tegen een kleine vergoeding, zoals ‘Zijn er griepsymptomen? ’, kon het project wel uitgroeien tot een krachtig werktuig aangezien data verzamelen in armere gebieden niet vanzelfsprekend is. Eagle bouwde een platform voor dergelijke peilingtechnologie in ontwikkelingsgebieden uit dat nu commercieel gebruikt wordt, genaamd Jana. Informatie die kan opgehaald worden via telefoons is zeer waardevol, niet alleen in armere gebieden. Het kan gebruikt worden om allerlei voorspellingen te maken, aankooppatronen van mensen te bekijken, mogelijke ziektes te voorspellen en meer. Hierbij moet wel rekening gehouden worden met de privacy van de personen wiens informatie bestudeerd wordt. [33] [35]
2.4
Approximatie-algoritmen
Ondertussen weten we waarom het belangrijk is dat we Big Data verwerken, hiervoor hebben we verscheidene redenen opgenoemd. We weten echter nog niet hoe we dit doen. Om Big Data te kunnen verwerken, zoals hierboven in enkele voorbeelden beschreven staat, moeten we natuurlijk gebruik maken van intelligent ge¨ımplementeerde algoritmen. Big Data brengt echter een complicatie met zich mee aangezien de data meestal niet volledig in het geheugen passen, m.a.w. we kunnen niet alle data tegelijk lezen. Soms zijn de data zelfs te groot om te kunnen opslaan. Een eerste trend in het verwerken van grotere hoeveelheden data was MapReduce dat werd ge¨ıntroduceerd door Google. Het is een programmeerparadigma dat toelaat een grote taak op te splitsen in deeltaken, deze worden in parallel uitgevoerd waardoor de uitvoering veel sneller kan gebeuren. Vereenvoudigd kunnen we stellen: eerst wordt de ‘map’ uitgevoerd waar een data-set gemapt wordt naar (key,value)-paren, daarna wordt ‘reduce’ uitgevoerd waar deze paren worden gereduceerd. Zowel map als reduce kunnen parallel uitgevoerd worden, we beginnen echter pas te reduceren 11
als het mappen vervolledigd werd. We bekijken deze methode echter niet in detail in deze tekst. [6] MapReduce is niet de enige manier waarmee we kunnen zorgen voor Big Data-verwerking. Aangezien het verwerken van data vaak te lang duurt indien we alles lezen, kiezen we meestal voor algoritmen die als resultaat een schatting geven en niet alle data lezen. Deze zijn veel effici¨enter en kunnen in veel minder tijd uitgevoerd worden.
2.4.1
Originele approximatie-algoritmen
Een probleem kan worden opgelost in polynomiale tijd indien hier een polynomiaal algoritme voor bestaat. Een algoritme is polynomiaal als het voor een bepaalde input van grootte n en positieve integer k O(nk ) stappen doet. Dergelijke algoritmen worden beschouwd als snel. Spijtig genoeg kunnen niet alle algoritmen snel uitgevoerd worden. [32] NP-harde problemen is een klasse van problemen die minstens zo moeilijk zijn als de moeilijkste problemen in NP. We vermoeden dat deze niet in polynomiale tijd opgelost kunnen worden. Gelukkig bestaan er er wel algoritmen die een benaderd resultaat geven dat toch dichtbij de optimale oplossing ligt. Dergelijke algoritmen worden approximatie-algoritmen genoemd en kunnen vaak wel in polynomiale tijd uitgevoerd worden. [19] De komst van Big Data zorgde echter voor een nieuwe klasse van approximatiealgoritmen.
2.4.2
Approximatie-algoritmen en Big Data
Indien we kleine datasets hebben, kunnen we door exacte en vaak ineffici¨ente algoritmen te gebruiken redelijk snel een antwoord krijgen op problemen zoals “Wat is het maximum of minimum voor deze rij van getallen?”. Door Big Data is ondertussen onze technische capaciteit ingehaald door de voorheen ongekende snelheid van data-generatie. Het is niet meer mogelijk dezelfde algoritmen te gebruiken om problemen op te lossen aangezien we te veel data nodig hebben dat niet tegelijkertijd in het geheugen past. Dit zou ineffici¨ent zijn en zou teveel tijd in beslag nemen, mogelijk zelfs dagen. We kunnen echter met een deel van de input ook zeer veel berekenen, zolang dat we er rekening mee houden dat we geen exacte, maar geschatte oplossingen krijgen voor het probleem. Approximatie-algoritmen zijn dus voor Big Data ook belangrijk. Degene die gebruikt worden voor NP-harde 12
problemen hebben als doel een oplosbaar algoritme aan te bieden dat het probleem benadert in polynomiale tijd. De focus bij approximatiealgoritmen gebruikt voor het oplossen van Big Data-queries ligt op het gebruik van minder (slechts sublineair) geheugen, ook al vraagt het algoritme maar polynomiale tijd, zodat de query beslisbaar is in verband met Big Data. [14] Het probleem dat vooral in deze tekst zal behandeld worden is distinct counting. Hiervoor zijn verscheidene approximatie-algoritmen ontworpen. Om deze echter te begrijpen, is wat voorkennis nodig die eerst zal aangehaald worden.
13
14
Hoofdstuk 3 Voorkennis Om alle algoritmen die zullen volgen in deze thesis goed te kunnen verstaan, beginnen we met enkele basisconcepten. In dit hoofdstuk wordt er daarom een stuk kanstheorie, hashing en streaming behandeld. Dit hoofdstuk is gebaseerd op de ‘Big Data’ cursustekst van Floris Geerts [11]. We beginnen met een herhaling van kanstheorie waarin we zullen ingaan op verscheidene basisbegrippen zoals de verwachtingswaarde en de variantie. Daarna bestuderen we een aantal ongelijkheden die belangrijk zijn in komende hoofdstukken om een begrenzing te kunnen geven op bepaalde kansen. Vervolgens exploreren we hashing. Simpelweg kunnen we dit zien als een manier om een groot getal op een kleiner getal af te beelden om bijvoorbeeld data sneller terug te vinden. Dit komt natuurlijk met een aantal nadelen, aangezien het kan zijn dat verscheidene elementen op eenzelfde kleiner getal worden afgebeeld. Indien we echter gebruik maken van een goede hash-functie, kan dit ons verscheidene voordelen bieden. Big Data wordt vaak voorgesteld als een grote stream van data, vaak zijn dit read-once sequenties. We kunnen enkel over de stream lezen, en hebben geen toegang tot willekeurige elementen in de stream. Om deze data te kunnen verwerken, zijn vaak specifieke streaming algoritmes nodig. Er zijn verschillende streaming modellen die elk andere eigenschappen hebben. We bekijken streaming en een aantal streaming modellen meer in detail in dit hoofdstuk.
15
3.1
Basisbegrippen van de kanstheorie
Aangezien approximatie-algoritmen geen exact antwoord geven, kunnen we de kans berekenen dat het algoritme een goed of fout antwoord terugkrijgt. Zoveel te hoger de kans is dat het antwoord correct is, zoveel te betrouwbaarder het algoritme zal zijn.
3.1.1
Probabiliteit
Om een uniforme notatie te gebruiken in dit werk herinneren we een aantal basisprincipes in verband met de kanstheorie zoals probabiliteit, verwachtingswaarde en variantie. D is een eindig domein dat sample space wordt genoemd. Elementen in D zijn elementaire of atomaire events; subsets van D zijn events. We gebruiken kleine letters om atomaire events aan te geven en hoofdletters om algemene events aan te duiden. + Een probabiliteit P : D → RP is een functie die een positief getal aan elk P event A ∈ D toekent zodat A∈D P[A] = 1 en P[A] = a∈A P(a).
Hieruit volgen de axioma’s: 1. P[A] ≥ 0 voor eender welk event A 2. P[D] = 1 3. P voor elke sequentie A1 , A2 , . . . van disjuncte events geldt P[∪i Ai ] = i P[Ai ]
3.1.2
Verwachtingswaarde
Een stochastische variabele is een re¨ele functie X : D → R. De verwachtingswaarde van een stochastische variabele kunnen we intu¨ıtief beschrijven als de waarde die deze ‘gemiddeld genomen’ zal aannemen. Voor een stochastische variabele X over domein D defini¨eren we de verP wachtingswaarde van X formeel als E[X] = x∈R P[X = x] · x. We nemen hier alle waarden in R, wat een oneindig domein is, maar dit is geen probleem aangezien D eindig is. Het beeld van X is ook eindig, zodat voor alle x ∈ R ∈ / Bld(X) geldt dat “X = x” = ∅, dus P(∅) = 0. P P Indien P[A] = a∈A P(a) dan weten we dat E[X] = a∈D P(a)X(a). 16
3.1.3
Variantie
Zoals al aangehaald kunnen we de verwachting van een stochastische variabele intu¨ıtief als een soort van gemiddelde waarde zien. We weten echter nog niets over de spreiding van de waarden rond dat ‘gemiddelde’. Hiervoor gebruiken we de variantie. We defini¨eren dit als Var[X] = E[X 2 ]−(E[X]2 ).
3.2
Belangrijke ongelijkheden
Binnen kansrekenen kunnen we gebruik maken van verscheidene ongelijkheden om bepaalde waarden te begrenzen. Deze waarden zijn anderzijds mogelijk moeilijk te berekenen. Deze zijn ook belangrijk voor enkele algoritmen die in dit werk nog zullen komen, aangezien dit de basis is voor de gedachtegang die volgt. We illustreren elke ongelijkheid met ´e´en of meer voorbeelden.
3.2.1
Ongelijkheid van Markov
De ongelijkheid van Markov is een bekende stelling uit de kanstheorie die de bovengrens beschrijft van de kans dat een positieve stochastische variabele groter of gelijk is aan een zekere positieve constante. Ze wordt geformuleerd als volgt: Voor een niet-nulzijnde, stochastische variabele X : Ω → R en X(s) ≥ 0 voor elke s ∈ Ω; en een positieve integer a > 0:
P[X ≥ a] ≤
E[X] . a
Equivalent kunnen we ook zeggen: 1 P[X ≥ aE[X]] ≤ . a Met deze ongelijkheid kunnen we al een aantal goede schattingen maken, zoals te zien in volgende voorbeelden. Voorbeeld 1 Stel, er zitten n ballen in een doos die zwart of wit zijn. Het percentage van het aantal zwarte ballen noemen we p. Het aantal ballen dat we hebben 17
gezien noemen we k, waarvan b ballen zwart waren. We schatten dat p gelijk is aan b/k. We defini¨eren een stochastische variabele Xi (met i ≤ i ≤ k) zodat Xi = 1 als de ide bal zwart is, of 0 indien dit niet P zo is. P[Xi = 1] = p, hierdoor weten we dat E[Xi ] = p. We stellen b = ki=1 Xi . Dus: " E[b] = E
k X
# Xi =
i=1
k X
E[Xi ] = kp.
i=1
We gebruiken nu de ongelijkheid van Markov waarbij X = b en a = 2E[b] waardoor we het volgende resultaat krijgen: 1 2 1 P[b ≥ 2kp] ≤ 2 1 P[b/k ≥ 2p] ≤ . 2
P[b ≥ 2E[b]] ≤
We weten nu dat we p met een factor van 2 kunnen overschatten met hoogstens 50% probabiliteit, onafhankelijk van hoeveel ballen we hebben. Voor elke k ≥ 1 is de kans dat b/k ≥ 2p hoogstens 1/2. ♦ Voorbeeld 2 Gooi n munten op. Xi geeft het event aan dat de ide munt op de kopkant naar boven landt. We weten nu dat: X 2n 2n E landt met de kopkant naar boven = E Xi ≥ 3 3 P n E [ Xi ] 3 2 ≤ = 2n = .♦ 2n 4 3 3
3.2.2
Ongelijkheid van Chebyshev
De ongelijkheid van Chebyshev garandeert dat in elke kansverdeling bijna alle waarden dichtbij het gemiddelde liggen. De variantie wordt gebruikt om de kans dat een stochastische variabele ver afwijkt van het gemiddelde te begrenzen. De ongelijkheid wordt gedefinieerd als volgt: 18
P[|X − E[X]| ≥ a] ≤
Var[X] a2
met Var[X] = E[(X − E[X])2 ] en a > 0. Deze ongelijkheid geeft een striktere begrenzing dan de ongelijkheid van Markov. Desondanks kunnen we toch deze laatste gebruiken om de ongelijkheid van Chebyshev af te leiden. We beschouwen de stochastische variabele (X − E(X)2 ) en constante a2 . We vullen de ongelijkheid van Markov in:
P[(X − E(X)2 ) ≥ a2 ] ≤
E[(X − E(X)2 )] . a2
We kunnen de ongelijkheid van Chebyshev afleiden als volgt:
P[|X − E[X]| ≥ a] = P[(X − E(X)2 ) ≥ a2 ] ≤
E[(X − E(X)2 )] Var[X] = . 2 a a2
Voorbeeld 1 Volgend voorbeeld toont aan dat de ongelijkheid van Chebyshev een striktere begrenzing i.v.m. een telling of percentage definieert dan de ongelijkheid van Markov. We gebruiken hetzelfde scenario als in het eerste voorbeeld in Paragraaf 3.2.1, dat is het percentage p van de zwarte ballen in een doos te berekenen. We willen aantonen dat indien δ eender welke waarde mag zijn zodat 0 < δ < 1, met k = 1/(2 δ), dan is de kans dat |b/k − p| ≤ minstens 1 − δ. We tonen dit aan door zoals in het vorige voorbeeld de stochastische variabele Xi te gebruiken, die voorstelt of de ide bal al dan niet zwart is, met 1 ≤ i ≤ k. Hier stelt k het aantal ballen die zwart zijn tot nu toe voor. E[Xi ] = p en Var[Xi ] = E[Xi2 ] − E[Xi ]2 = E[Xi ] − p2 = p − p2 P = p(1 − p), 2 want Xi = Xi aangezien Xi = 0 of Xi = 1. We weten dat b = ki=1 Xi en dat alle Xi paarsgewijs onafhankelijk zijn. 19
We berekenen dat E[b] = kp en Var[b] =
Pk
i=1
Var[Xi ] = kp(1 − p).
b P | − p| ≥ = P[|b − kp| ≥ k] k Var[b] kp(1 − p) p(1 − p) ≤ = = 2 2 (k) (k) 2 k 1 ≤ 2 =δ k
De kans dat het slecht gaat is dus δ; en is de gewenste nauwkeurigheid met kans minstens 1 − δ. We zien nu ook in waarom k = 1/(2 δ). ♦
3.2.3
Ongelijkheid van Chernoff/Hoeffding
De Chernoff/Hoeffding ongelijkheid geeft exponentieel dalende begrenzingen op kansverdelingen van de sommen van stochastische variabelen. Laat X1 , . . . , Xn onafhankelijke stochastische variabelen zijn in het interval P [0, 1] en laat X = Xi , zodat: 2t2 P[|X − E[X]| ≥ t] ≤ 2exp − n
.
Equivalent kunnen we ook zeggen dat: 22 E[X]2 P[|X − E[X]| ≥ E[X]] ≤ 2exp − , n P[|X − E[X]| ≥ n] ≤ 2exp(−22 n). Deze ongelijkheid is nog sterker dan de ongelijkheid van Chebyshev. Dit komt omdat de grens sneller daalt in t dan in t−1 . We tonen dit aan door het voorbeeld uit de vorige twee paragrafen opnieuw te verbeteren. Voorbeeld 1 We verbeteren de schatting van het tellen van de ballen, zoals aangehaald in Paragraaf 3.2.1 en later in 3.2.2, nog meer. Herinner je dat we weten dat E[b] = kp. Om de Chernoff/Hoeffding ongelijkheid in te kunnen vullen, moeten we een invulling hebben voor n en t, in dit voorbeeld zijn deze 20
respectievelijk k en k. We leiden nu af dat: b P | − p| ≥ = P[|b − kp| ≥ k] k = P[|b − E[b]| ≥ k] ≤ 2e−2
(k)2 k
2
= 2e−2 k .
2
Als we nu k uit 2e−2 k = δ halen, weten we dat k = − 212 ln( 2δ ) = 212 ln( 2δ ). We weten nu dat voor elke k ≥ 212 ln( 2δ ) geldt dat P[| kb − p| ≤ ] ≥ δ. ♦
3.3
Hashing
Hashing kunnen we simpelweg bekijken als een transformatie van een string van karakters in een substantieel kleinere waarde met een vaste lengte die de originele string voorstelt. Het basisidee is dat een zekere hashfunctie h elk mogelijk item x in een kleinere integer h(x) transformeert. We zullen x in gleuf h(x) van een array opslaan. Deze array noemen we een hash-tabel. Op deze tabel kunnen we typisch drie operaties uitvoeren: zoeken, toevoegen en verwijderen van items. De hash-tabel kan gebruikt worden om snel te kunnen bepalen of een item deel uitmaakt van een set of niet. Dit hoofdstuk is gebaseerd op de ‘Big Data’ cursustekst van Floris Geerts [11] en het boek ‘Probability and Computing’ van Mitzenmacher [22]. Een manier om hashing voor te stellen is het ballen-en-dozen-model. Indien we bijvoorbeeld willen checken of een wachtwoord dat een gebruiker neerschreef zeer vaak gebruikt wordt en snel te kraken is, zouden we een gesorteerde lijst kunnen bijhouden met alle onacceptabele wachtwoorden. We voeren een binaire zoekopdracht uit om in de lijst te zoeken, dit kost O(log n) tijd voor n woorden. Een betere oplossing is de woorden in dozen plaatsen. Elke doos bevat een gelinkte lijst van woorden. Het plaatsen van deze woorden in dozen wordt gerealiseerd met een hash-functie h die woorden van universum U transformeert in waarden uit de reeks [0, m − 1]. Het universum in het voorbeeld zijn de mogelijke wachtwoorden. De collectie van dozen is onze hash-tabel. Deze vorm van hashing noemen we chain hashing aangezien de items samen in een gelinkte lijst worden geplaatst. We veronderstellen dat de hash-functie h willekeurig is: voor elke x ∈ U is de kans dat h(x) = j 1/m voor 0 ≤ j ≤ m − 1 en de waarden van h(x) voor x zijn onafhankelijk van elkaar. Om nu een item te zoeken berekenen we de hash-waarde om te weten in welke doos deze moet zitten en dan kunnen we door de gelinkte lijst gaan in die doos om na te gaan of we 21
het element vinden. Stel dat we n woorden in m dozen willen plaatsen. Bij het zoeken naar een woord dat niet in de lijst zit, verwachten we dat er n/m woorden in de doos zitten van de hash-waarde van dat item. Bij het zoeken naar een woord dat wel in de lijst zit, verwachten we dat er 1 + (n − 1)/m woorden in de lijst zitten. De maximale tijd die nodig is om een woord te zoeken, is proportioneel met het maximum aantal woorden in een doos. Wanneer n = m dan is dit maximum O(ln m/ ln ln m) met kans dichtbij 1. Met andere woorden: we kunnen met grote kans zeggen dat dit de maximale zoektijd is in een hash-tabel, dit is nog steeds sneller dan binair zoeken, maar kan wel meer geheugen in beslag nemen. Deze vorm van hashing wordt daarom vooral gebruikt als we tijd willen besparen in tegenstelling tot geheugenruimte. Indien we eerder minder geheugenruimte willen gebruiken in plaats van minder tijd, kunnen we hashing ook op een andere manier gebruiken. Stel dat we opnieuw een woordenboek van onaanvaardbare wachtwoorden willen bijhouden en stel dat een wachtwoord uit 8 ASCII karakters (64 bits) bestaat. We kunnen nu een hash-functie gebruiken om elk woord te mappen op een 32-bit string. Deze string kunnen we beschouwen als een vingerafdruk voor het woord dat we bijhouden in een gesorteerde lijst. Indien we binair zoeken in de lijst en we vinden de vingerafdruk van het woord, dan is het wachtwoord onacceptabel. In dit geval kan het echter zijn dat we een vals positief resultaat terugkrijgen, omdat de “vingerafdrukken” niet uniek zijn voor elk woord. Het is echter niet mogelijk een vals negatief antwoord terug te geven. Hoewel dit niet ideaal is, is dit ook geen groot probleem in ons voorbeeld aangezien we gewoon een iets grotere hoeveelheid wachtwoorden niet aanvaarden. Uit bovenstaande voorbeelden zien we dat hashing ons een snelle en makkelijke manier geeft om te zoeken in een lijst. Hashing heeft echter nog verscheidene andere toepassingen, zoals: AI-zoekprogramma’s om situaties die al berekend zijn op te slaan, cryptografie, netwerken en complexiteitstheorie. Formeel kunnen we hashing als volgt bepalen. We hebben elementen die uit een groot universum U komen, waarbij u = |U|. Er is een set S ∈ U die de elementen bevat die we willen bestuderen. We stellen dat n = |S|. Meestal is n veel kleiner dan u. Een hash-tabel is een array T [1..m] met m een positieve integer die de grootte van de tabel voorstelt waarin we toevoegingen en zoekopdrachten kunnen op uitvoeren. Meestal is m ook veel kleiner dan u. We defini¨eren ook hash-functie h:
h : U → {0, 1, . . . , m − 1}, 22
waarin we elke mogelijke waarde uit U mappen op een ‘gleuf’ in de hashtabel. Een item x ‘hasht’ naar de gleuf T [h(x)]. Indien de grootte van het universum en de grootte van de tabel gelijk zijn aan elkaar, kunnen we een triviale hash-functie gebruiken: h(x) = x. Dit neemt meestal echter teveel geheugenruimte in beslag en vaak moeten we slechts een fractie van U opslaan. Een ideale situatie is dat de tabel met grootte m ongeveer gelijk is aan het aantal items n dat we willen opslaan. Indien m echter veel kleiner is dan n, worden zogenaamde hash-collisies veel waarschijnlijker. Hash-botsingen komen voor indien h(x) = h(y). Er zijn nu twee problemen die we moeten oplossen: hoe kiezen we een hashfunctie die het aantal collisies dat voorkomt beperkt, en hoe behandelen we collisies die toch voorkomen. Er zijn enkele voorwaarden waaraan het hash-schema moet voldoen om een goede performantie te garanderen: de elementen zijn mooi verdeeld zodat collisies niet te vaak voorkomen, m = O(n) zodat de hash-tabel niet veel groter is dan het aantal elementen n, en de functie h is snel te berekenen zodat dit de executietijd niet te sterk be¨ınvloedt. In de analyse gaan we er vanuit dat de tijd die nodig is om h(x) te berekenen constant is. De complexiteit van een zoekopdracht of verwijdering is nu O(lengte van de lijst T [h(x)]). Om een item toe te voegen kunnen we simpelweg het element vooraan in de lijst plaatsen waardoor dit een complexiteit van O(1) heeft. We hebben al kennis gemaakt met chain hashing in bovenstaand voorbeeld. Dit is ´e´en van de manieren waarop we kunnen omgaan met hashing en collisies doordat alle items die dezelfde hash-waarde hebben als een gelinkte lijst worden opgeslagen in de juiste doos. Indien we een goede hash-functie hebben, is de lengte van de gelinkte lijsten in de verschillende dozen redelijk klein. We willen de elementen in een hash-tabel zoveel mogelijk uitspreiden om te voorkomen dat we veel botsingen zullen krijgen. Dit is natuurlijk niet zo vanzelfsprekend. Er bestaan veel simpele hash-functies die vaak echter geen goede worst-case garantie geven. We weten dat voor eender welke hash-functie h geldt dat er een set S bestaat die n elementen bevat waarvoor alle elementen naar dezelfde locatie hashen indien u ≥ (n − 1)m + 1. We kunnen dit bewijzen met behulp van het duiventilprincipe. Aangezien onze hash-functie deterministisch is, is re-hashing geen optie indien de input teveel collisies genereerde. Daarom maken we gebruik van willekeurigheid bij constructie van h, ondanks dat deze deterministisch zal blijven. Wat we willen bereiken is dat onze hash-functie h pseudowillekeurig is. Dit betekent dat we voor eender welke sequentie van op23
zoekoperaties en toevoegingen een goede performantie voor hash-functie h garanderen door h op een probabilistische manier te kiezen. We noemen dit universeel hashen.
3.3.1
Universeel hashen
We maken gebruik van een familie van hash-functies H waarbij voor elke functie geldt h : U → {0, 1, . . . , m−1}. We noemen deze familie universeel indien geldt voor alle x 6= y in U: Ph∈H [h(x) = h(y)] ≤
1 . m
Door deze mathematische eigenschap kunnen we een betere garantie geven in verband met verwachte botsingen, zelfs bij slecht gekozen data. Indien H universeel is, dan geldt voor eender welke set S ⊆ U van grootte n, voor eender welke x ∈ U, als we h ∈ H kiezen, dat het verwachte aantal botsingen van x met andere elementen in S maximaal n/m is. We bewijzen dit als volgt: elke y ∈ S waarbij x 6= y heeft maximaal 1/m kans om met x te botsen door de definitie van universele hash-functies. We stellen dat Cxy = 1 als x en y botsen, anders is dit 0. We laten Cx het totaal aantal botsingen voor x voorstellen. We weten dat E[Cxy ] = P[x en y botsen] ≤ 1/m voor x 6= y, en 1 voor P x = y. Dus door de lineariteit van verwachting weten we dat E[Cx ] = y E[Cxy ] < n/m. We kunnen nu stellen dat als H universeel is voor eender welke sequentie van L toevoeg-, verwijder- of zoekoperaties waarvoor er hoogstens m elementen tegelijk in het systeem zitten, de verwachte totale kost van de L operaties voor een willekeurige h ∈ H slechts O(L) bedraagt indien we de berekening van h als een constante bekijken. We kunnen deze universele familie van hash-functies ook makkelijk construeren met behulp van bv. de matrix-methode, maar dit behandelen we niet in deze tekst.
3.3.2
Uniforme hash-functies
Vaak gaan we er ook vanuit dat de hash-functies die we gebruiken uniform zijn. Dit betekent dat de functie elementen evenredig distribueert in juiste gleuven van de hash-tabel. We kunnen zelfs zeggen dat elk item dat gehasht moet worden een gelijke kans heeft om in een bepaalde gleuf 24
te worden geplaatst, onafhankelijk van de elementen die al in een gleuf geplaatst zijn. We gaan ervanuit dat: P[h(x) = h(y)] =
1 . m
Universele hash-functies impliceren uniformiteit echter niet altijd. Om dit echter wel te garanderen kunnen we gebruik maken van sterke universaliteit.
3.3.3
Paarsgewijze onafhankelijkheid
Een sterkere conditie dan universaliteit is paarsgewijze onafhankelijkheid. We noemen een hash-functie die hieraan voldoet ook wel een sterk universele hash-functie. Een familie van hash-functies H is sterk universeel als voor elk paar x1 , x2 in het universum en waarden y1 , y2 , de kans Ph∈H [h(x1 ) = y1 & h(x2 ) = y2 ] =
1 . m2
Vergewis je ervan dat paarsgewijze onafhankelijkheid universaliteit impliceert. We zien dit inderdaad in door te stellen y1 = y2 en een som te maken van alle mogelijke waarden van y1 . Evenals uniformiteit, dus: Ph∈H [h(x1 ) = h(x2 )] =
1 . m
Paarsgewijze onafhankelijkheid geeft een betere garantie in verband met de lage verwachting van het aantal botsingen. Ook garanderen sterke universele hash-functies uniformiteit, in tegenstelling tot universele hashfuncties.
3.4
Streaming
Veel moderne applicaties werken vaak met Big Data, wat betekent dat ze een enorme hoeveelheid data effici¨ent moeten kunnen verwerken. Er worden constant grote hoeveelheden data gegenereerd die vaak te groot zijn om te indexeren en op te slaan. Streaming kan hiervoor een oplossing bieden. 25
Streaming algoritmen worden gebruikt om data streams te verwerken waarbij de input een sequentie van items is die maar enkele keren kan worden bestudeerd. Vaak is het niet mogelijk om zelfs maar ´e´en keer over een grote stream van updates te gaan. De bedoeling is een compacte samenvatting op te slaan, omdat er maar gelimiteerde geheugenruimte is, meestal minder dan de inputgrootte, en ook gelimiteerde verwerkingstijd per item. Met de samenvatting van de stream moeten we eigenschappen van de input kunnen ontdekken en sterke garanties over de kwaliteit van het resulterende antwoord kunnen geven. In de loop van deze tekst maken we vaak gebruik van een streaming model genaamd vanilla streaming model. De input stream σ is zeer lang en kan formeel gedefinieerd worden als een sequentie: σ = ha1 , a2 , . . . , an i, waarbij alle tokens ai uit het universum U komen. Indien nodig transformeren we de input zodat we U kunnen defini¨eren als {1, 2, . . . , u}. Hieruit leiden we twee zeer belangrijke grootteparameters af: de lengte van de stream n, en de grootte van het universum u. Het doel is de input stream te verwerken met een kleine hoeveelheid geheugenruimte, s. We gebruiken dus s bits van random-access werkgeheugen. Aangezien n en u zeer groot zijn, willen we ervoor zorgen dat s sublineair is ten opzichte van zowel n als u: s = o(min{n, u}). Om dit te verwezenlijken proberen we s te defini¨eren als volgt: s = O(log2 n + log2 u). Dit is de hoeveelheid geheugenruimte die nodig is om een constant aantal tokens van de stream en een constant aantal tellers dat de lengte van de stream telt bij te houden. We weten dat we maximum log2 n geheugenruimte nodig hebben om een teller, die hoogstens n is, op te slaan en maximum log2 u geheugenruimte nodig hebben om een token, dat hoogstens u is, op te slaan. In een stream hebben we geen willekeurige toegang tot alle tokens, we kunnen maar ´e´en keer scannen in een gegeven volgorde. Bij elke t ∈ [0, n], σt = ha1 , . . . , at i hoort een multiset St = {a1 , . . . , at }. We gebruiken multisets om de elementen in de stream te beschrijven om zo identieke elementen te bewaren. We maken ook gebruik van een frequentievector f = (f1 (σ), f2 (σ), . . . , fu (σ)), met: 26
fj (σ) := |{i | ai = j, ai ∈ σ}| = aantal keer dat j voorkomt in σ. Als σ geen context heeft, kunnen we ook fj schrijven in plaats van fj (σ). Hetzelfde kan gezegd worden over de frequentievector. We kunnen de stream σ bekijken als een sequentie van update-instructies die moeten uitgevoerd worden voor vector f. Bijvoorbeeld: een token dat aankomt updatet de frequentievector, aangezien fj wordt ge¨ıncrementeerd. Er zijn echter situaties waar we de updates van f wat algemener willen bekijken. Er mogen zowel items aankomen als vertrekken van de multisets. Hiervoor gebruiken we het turnstile model. Frequenties van fj kunnen nu zowel ge¨ıncrementeerd als gedecrementeerd worden. Tokens in σ behoren tot U × {−L, −L + 1, . . . , 0, . . . , L − 1, L}, waarbij L de maximale waarde is waarmee de items in U vermeerderd of verminderd kunnen worden. Bij de aankomst van een token aj = (j, c), wordt fj ge¨ updatet als volgt: fj ← fj + c. In dit model kan de rol van de parameter n veranderen. In plaats van de lengte van de stream, kan het ook het maximum aantal items in de multiset St op een bepaald punt t voorstellen. Formeel wordt dit gedefinieerd als: ||f ||1 = |f1 | + · · · + |fu | ≤ n. Een speciaal geval van het turnstile model is het strikte turnstile model. In dit model gaan we ervan uit dat het volgende altijd geldt: f ≥ 0. Een tweede speciaal geval is het cash register model, waar we alleen positieve updates toelaten. Voor elke update (j, c) weten we dat c > 0.
27
28
Hoofdstuk 4 Heavy hitters Voordat we beginnen met distinct counting en al kennis hebben gemaakt met zowel hashing als streaming, bestuderen we eerst een gelijkaardig probleem in detail, namelijk heavy hitters. Dit probleem vraagt om de items op te sporen die het meest frequent voorkomen in een gegeven stream van items. Dit is net zoals distinct counting een zeer belangrijk probleem in verband met data stream algoritmen. We bestuderen hiervoor eerst frequentieschatting, wat we kunnen gebruiken om het heavy hitters probleem op te lossen. Dit hoofdstuk is gebaseerd op de ‘Big Data’ cursustekst van Floris Geerts [11]. Ondanks dat frequentieschatting en heavy hitters makklijkere problemen zijn dan bijvoorbeeld distinct counting, laat ons dit wel toe een basiskennis op te bouwen in verband met streams en streaming algoritmes die we later kunnen gebruiken om het tellen van het aantal unieke items makkelijker en zo goed mogelijk te doorgronden. Net zoals de distinct count-algoritmes die we later nog zullen bespreken, gebruiken de meeste algoritmes in dit hoofdstuk willekeurigheid dat ge¨ıntroduceerd werd door hashing om een resultaat te kunnen berekenen. Heavy hitters worden frequent gebruikt bij het monitoren van netwerkverkeer, het ontdekken van eventuele bedreigingen in een netwerk en data mining. Het is dus belangrijk dat we bijna real-time een schatting kunnen maken in verband met het de meest voorkomende items in een stream, daarom maken we gebruik van een effici¨ent approximatie-algoritme.
29
4.1
Frequentieschatting
Frequentieschatting kan gebruikt worden om het heavy hitters probleem op te lossen. Gegeven een stream σ van n elementen van een universum U, willen we voor elk element i weten wat fi , hoeveel keer dit element voorkomt in de stream, bedraagt. Er is een na¨ıeve manier om dit op te lossen: alle items overlopen en voor elk uniek element een teller bijhouden die de frequentie voorstelt. Dit neemt echter veel tijd in beslag indien we met een grote hoeveelheid items werken. Algoritmen die dit probleem effici¨ent trachten op te lossen, zullen een gelimiteerde hoeveelheid geheugenruimte gebruiken. We berekenen daarom slechts een schatter fˆi die fi benadert. Er worden enkel details bijgehouden over een klein aantal items, waardoor schattingen mogelijk 0 als antwoord geven. Het doel van deze schatters is een beknopte representatie van de data te geven, met een controleerbare trade-off tussen de grootte van de beschrijving en de approximatiefout. We zullen drie algoritmen overlopen: Misra-Gries, Count-Min en CountSketch. In volgende tabel zien we de geheugenruimte en foutbegrenzing voor elk algoritme: Algoritme Misra-Gries Count-Min Count-Sketch
Type teller sketch sketch
Geheugenruimte O((1/)(log2 u + log2 n)) O((1/) log2 (1/δ)(log2 u + log2 n)) O((1/2 ) log2 (1/δ)(log2 u + log2 n))
Foutbegrenzing |fj − fˆj | ≤ (||f ||1 − fj ) |fj − fˆj | ≤ (||f ||1 − fj ) |fj − fˆj | ≤ (||f ||2 − fj2 )
Pu k ( Hier is ||f || = ( k i=1 |fi | ) 1/k). Dus ||f ||1 = |f1 | + · · · + |fu | en ||f ||2 = p f12 + · · · + fu2 . We weten dat ||f ||2 ≤ ||f ||1 .
4.1.1
Misra-Gries algoritme
Als eerste algoritme gaan we het Misra-Gries algoritme bestuderen. Dit is een simpel, deterministisch algoritme gebaseerd op een teller. Het is effici¨ent, maar niet heel nauwkeurig. We stellen dit algoritme voor als een set van m emmers. In elke emmer zitten telkens ballen van maar ´e´en kleur. Indien er een nieuwe bal aankomt, gaan we deze in een emmer plaatsen waar reeds ballen van dezelfde kleur inzitten, of in een lege emmer. Indien er geen emmer van dezelfde kleur en geen lege emmer is, gaan we ´e´en bal uit elke emmer nemen. We gebruiken het vanilla streaming model met stream σ = ha1 , a2 , . . . , an i met elke ai ∈ U. De frequentievector van σ defini¨eren we als f = (f1 , . . . , fu ). Merk op dat ||f ||1 = |f1 | + · · · + |fu | = n. Algoritme 1 bevat het uitgeschreven algoritme. 30
Algoritme 1 Misra-Gries(σ,m) 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:
Initialiseer m tellers t0 , . . . , tm−1 op 0 for elk element in ai in de stream σ do if ai wordt niet opgevolgd door ´e´en van de tellers && er bestaat een teller tj = 0 then incrementeer tj , deze teller volgt nu elementen met dezelfde waarde als ai op else if ai wordt reeds opgevolgd door teller tj then incrementeer tj else decrementeer tj voor elke j ∈ [0, . . . , m − 1] end if end if end for return alle elementen die opgevolgd worden door een teller 6= 0
Figuur 4.1: Voorbeeld Misra-Gries algoritme
31
In Figuur 4.1 zien we een uitgewerkt voorbeeld. De stream die we gebruiken is bovenaan de afbeelding te zien en bevat 13 elementen. We gebruiken 4 tellers (voorgesteld als buckets) die we kunnen gebruiken. Situaties A, B en C stellen de verschillende buckets voor tot vlak voor er een decrement uitgevoerd wordt. Het eerste element in de stream plaatsen we in de eerste bucket. In situatie A zien we dit doordat er een blauwe bal in de eerste bucket zit. De volgende twee elementen worden door een andere teller geteld, zoals te zien aan de tweede emmer met twee oranje ballen. We zullen hetzelfde doen voor de groene en gele elementen die volgen. Nu zijn echter de buckets vol en we komen een nieuwe kleur tegen: roze. We moeten elke teller decrementeren, met andere woorden: ´e´en bal uit elke bucket halen. Er liggen nu in de tweede en vierde emmer nog steeds ´e´en element, maar de eerste en derde zijn leeg. We doen niets met de roze bal. Het achtste element is opnieuw roze, deze keer zijn er echter wel buckets leeg, dus gebruiken we de eerste teller voor het tellen van roze elementen. Dit kunnen we zien in situatie B. Het volgende element is oranje, dus dit kunnen we toevoegen aan de tweede bucket, aangezien hier nog een oranje bal in zit. We gebruiken een nieuwe teller om het blauwe element te tellen: de derde bucket. Daarna komt er weer een roze element, dit voegen we toe in de eerste bucket. Er zijn opnieuw geen buckets leeg, en er komt een nieuwe kleur aan: groen. We decrementeren elke teller opnieuw, en doen niets met het groene element. De derde en vierde bucket zijn leeg. Het laatste element is blauw, en zal opnieuw toegewezen worden aan de derde bucket, zoals te zien in situatie C. We noemen d het aantal keren dat een element in de stream een decrement heeft veroorzaakt voor m tellers en het huidige element dus genegeerd werd. Indien er een decrement voorvalt, weten we dus dat er m + 1 afgetrokken wordt van de som van alle tellers. Hierdoor kunnen we de som van alle tellers ||ˆf||1 na afloop defini¨eren als: ||f ||1 . ||ˆf||1 = ||f || − (m + 1)d ≥ 0, en d ≤ m+1 Voor elke j ∈ U stellen we dat: ||f ||1 fˆj ≥ fj − d ≥ fj − . m+1 We kunnen dit gebruiken om een nauwkeurigheidsgrens voor het MisraGries algoritme te bepalen: ||f ||1 fj − fˆj ≤ . m+1 32
Deze grens kan nog verbeterd worden. Aangezien fˆ ≥ fj − d voor elke j ∈ U stellen we dat: ||ˆf||1 = ||f || − (m + 1)d ≥ fj − d. Hieruit volgt dat:
||f || = fj +
u X
fi ≥ fj + dm ⇔
i=1,i6=j
||f || − fj ≥ d. m
Dus de verbeterde grens formuleren we als volgt: ||f || − fj fj − fˆj ≤ m Stel dat de bovengrens aangeeft op de fout, en m = O(1/). We kunnen zeggen dat het algoritme met m tellers verzekert dat |fj −fˆj | ≤ (||f ||1 −fj ). Indien we het aantal tellers verhogen, verkleint de bovengrens op de fout. Het algoritme neemt O((1/)(log2 u + log2 n)) geheugenruimte in beslag.
4.1.2
Count-Min algoritme
Als tweede algoritme bekijken we het Count-Min algoritme. Dit is iets complexer, maar zal een accurater resultaat geven in vergelijking met het Misra-Gries algoritme. In tegenstelling tot vorige paragraaf maken we hier gebruik van een stochastisch algoritme door de hantering van willekeurigheid door de introductie van een hash-functie. Indien we een andere hash-functie toepassen, is het mogelijk dat we niet dezelfde uitkomst(en) krijgen, in tegenstelling tot het deterministische algoritme in vorige paragraaf, wat altijd dezelfde uitkomst zal geven. In de komende hoofdstukken in deze tekst maken we vaak gebruik van stochastische algoritmen, aangezien we meestal een hash-functie zullen hanteren. Voor het vorige algoritme maakten we gebruik van het vanilla streaming model, waar we enkel elementen aan de stream konden toevoegen. Indien we ook items willen verwijderen, kunnen we het Misra-Gries algoritme niet meer gebruiken. Het Count-Min algoritme maakt gebruik van het strikte turnstile model eerder aangehaald in de tekst. We kunnen nu zowel toevoegen als verwijderingen voorstellen zonder dat een teller negatief mag gaan. 33
We willen een datastructuur die antwoord kan geven op de count query. Op elk moment t voor elk element moeten we kunnen weten wat fj is. We willen dat de foutbegrenzing klein is met een hoge probabiliteit, terwijl we een minimale hoeveelheid geheugenruimte gebruiken. 4.1.2.1
Basisalgoritme
We beginnen met een simpele versie van Count-Min. We maken gebruik van de hash-functie h : U → {0, 1, . . . , m − 1} voor een passende, grote integer m. Deze functie zal willekeurigheid introduceren. We maken gebruik van een array T [1 . . . m] waarin we m tellers opslaan. Het algoritme werkt als volgt: voor elk element (j, c) gaan we j mappen met behulp van hashfunctie h, wat ons locatie h(j) als uitkomst geeft. De teller opgeslagen in T [h(j)] wordt nu vermeerderd met c. Algoritme 2 bevat het uitgeschreven algoritme. Algoritme 2 Basic Count-Min(σ, m, h) 1: 2: 3: 4: 5:
Initialiseer array T [1 . . . m] op 0 for elk element (j, c) in de stream σ do T [h(j)] ← T [h(j)] + c end for return fˆj = T [h(j)]
We vragen ons nu af hoe accuraat de schatting fˆj echt is. We weten dat voor het huidige element (j, c) T [h(j)] zeker en vast c bevat. Maar het kan zijn dat er al een ander element j 0 gemapt is op dezelfde locatie indien h(j) = h(j 0 ). We defini¨eren de indicatorvariabele Ij,j 0 als:
Ij,j 0
( 1 als h(j) = h(j 0 ) = 0 anders.
We weten nu dat: T (h(j)) =
X
fj 0 · Ij,j 0 = fj +
j 0 ∈U
X j 0 ∈U \{j}
dus fˆj − fj =
X j 0 ∈U \{j}
34
fj 0 · Ij,j 0 .
fj 0 · Ij,j 0 ,
Aangezien we werken met het strikte turnstile model, weten we dat we altijd positieve fj ’s hebben, en fj ≤ fˆj aangezien we de frequenties enkel kunnen overschatten. De kwaliteit van de schatting hangt af van de botsingeigenschappen van de gekozen hash-functie. Indien er veel botsingen zijn, worden er meer elementen op dezelfde locatie gemapt. Dit zorgt voor slechtere schattingen. De kans is klein dat er geen of weinig botsingen plaatsvinden indien we eender welke hash-functie kiezen, daarom maken we gebruik van een hash-functie die uit een universele familie H van hash-functies komt. Door gebruik te maken van lineariteit van de verwachting in de eerste gelijkheid en de definitie van een universele familie in de ongelijkheid, maken we de volgende berekening in verband met de foutmarge: X X E fj 0 · Ij,j 0 = fj 0 · E[Ij,j 0 ] j 0 ∈U \{j}
j 0 ∈U \{j}
=
X
fj 0 · P[h(j) = h(j 0 )]
j 0 ∈U \{j}
≤
X j 0 ∈U \{j}
=
fj 0 ·
1 m
||f −j ||1 ||f ||1 − fj = . m m
De maximale waarde van ||f ||1 is n, dit gebeurt enkel indien er geen verwijderingen plaatsvinden. De verwachte fout is dus maximum n/m. We hebben echter alleen een begrenzing voor de verwachte fout E[fˆj − fj ], maar wat we echt wilden was een lage foutverwachtingswaarde. Dit kan door het algoritme uit te breiden. 4.1.2.2
Count-Min
In het Count-Min algoritme maken we gebruik van een gelijkaardige werkwijze als in de simpele versie hierboven beschreven. In plaats van ´e´en array en ´e´en hash-functie, gaan we echter gebruik maken van k hash-functies h1 , . . . , hk waarbij hi ∈ H, en k arrays T1 , . . . , Tk . De bedoeling is dat we het bovenstaande algoritme k keren onafhankelijk van elkaar uitvoeren. We gebruiken de ide hash-functie om de locatie in de ide array te kiezen. Uiteindelijk combineren we de k schattingen die gemaakt werden per (hi , Ti )-paar tijdens het verloop van het algoritme. Aangezien we weten dat deze overschattingen zijn, nemen we het minimum van de verschillende berekeningen. Algoritme 3 bevat het uitgeschreven algoritme. 35
Algoritme 3 Count-Min(σ, m, k, H) 1: 2: 3: 4: 5: 6: 7: 8:
Initialiseer k arrays Ti [1 . . . m] op 0 Kies k onafhankelijke hash-functies h1 , h2 , . . . hk , met hi ∈ H en hi : U → {0, 1, . . . , m − 1} for elk element (j, c) in de stream σ do for i = 1, . . . , k do Ti [hi (j)] ← Ti [hi (j)] + c end for end for return fˆj = min1≤i≤k Ti [hi (j)]
We bekijken het voorbeeld voorgesteld in Figuur 4.2. We hebben een stream met 17 items. Als waarde voor m kiezen we 3, en als waarde voor k kiezen we 4. We hebben als gevolg 4 tabellen T1 , T2 , T3 , T4 en hash-functies h1 , h2 , h3 , h4 . We zien dat er twee items worden verwijderd in de stream, deze items zijn aangegeven met een prullenmandicoon. Het eerste item in de stream is (blauw, 1). Zoals in het algoritme beschreven staat, moeten we de hash-functies gebruiken om te bepalen welke elementen in de tabellen ge¨ updatet moeten worden. We leiden af dat we T1 [h1 (blauw)] = [T1 [0], T2 [h2 (blauw)] = T2 [2], T3 [h3 (blauw)] = T3 [1] en T4 [h4 (blauw)] = T4 [2] moeten updaten, of met andere woorden: we vermeerderen de waarde van deze vier elementen met c = 1. We geven dit aan door blauwe streepjes te trekken in de middelste tabel op de figuur. We herhalen hetzelfde proces voor alle elementen tot aan het gele element dat verwijderd moet worden. Het item (geel, −1) moet op dezelfde manier behandeld worden, maar in plaats van de elementen in de tabellen te incrementeren, zullen we ze decrementeren, aangezien c = −1. We kunnen met behulp van de tabel van de hash-functies zien dat we T1 [2], T2 [2], T3 [2] en T4 [1] moeten updaten. We geven deze decrement aan met de rode streepjes in de middelste tabel in de figuur. Indien we de volledige stream hebben behandeld, moeten we nog het minimum van alle schatters voor ´e´en bepaald item nemen. Voor de kleur blauw nemen we het minimum van T1 [0] = 6, T2 [2] = 7 − 1 = 6, T3 [1] = 5 en T4 [2] = 7 − 1 = 6, dus de geschatte waarde voor blauw is 5. We gebruiken dezelfde denkwijze voor de rest van de kleuren. De geschatte waarde voor de andere elementen, staan in de figuur. Herinner je dat de verwachte error in het simpele Count-Min algoritme hoogstens ||f −j ||1 /m is. Dus:
E[fˆj − fj ] ≥ 36
||f || − fj . m
Figuur 4.2: Voorbeeld Count-Min algoritme We vragen ons nu af wat de kans is dat ´e´en enkele schatting een fout heeft die groter is dan 2||f −j ||1 /m. Met behulp van de ongelijkheid van Markov stellen we: ||f −j ||1 ˆ P fj − fj > 2 ≤ P[fˆj − fj > 2E[fˆj − fj ]] m 1 ≤ . 2 We maken gebruik van de onafhankelijkheid van de keuze van de hashfuncties. We bepalen wat de kans is dat alle k herhalingen van het algoritme meer dan 2||f −j ||1 /m fout hebben: ||f −j ||1 de P elke k herhaling heeft een fout groter dan 2 m k Y ||f −j ||1 1k de = P de i herhaling heeft een error groter dan 2 ≤ . m 2 i=1 We hebben een fout van maximum 2||f −j ||1 /m met kans minstens 1−1/2k . We kiezen nu parameters m en k zodat de kans op succes 1 − δ is. We stellen dat m = d2/e en k = log2 (1/δ). De fout wordt begrensd door 2||f −j ||1 /m = ||f −j ||1 . De kans op falen is 1/2k = 1/2log2 (1/δ) = δ. De kans op succes is 1 − δ zoals gewild: h i P |fˆj − fj | ≤ ||f −j ||1 ≥ 1 − δ. 37
In bovenstaande ongelijkheid zien we dat de accuraatheid op zeldzame kleuren slechter is dan de accuraatheid voor de kleuren die vaak voorkomen. Dit volgt uit ||f −j ||1 : we gebruiken het aantal elementen die niet kleur j hebben. Zoals aangehaald maken we gebruik van een universele familie van hashfuncties waaruit k functies gekozen worden. Deze functies kunnen opgeslagen worden in O(k log2 u) geheugenruimte. Elke km teller heeft hoogstens O(log2 n) geheugenruimte nodig. We hebben dus O(k log2 u + km log2 n) geheugenruimte nodig. Indien we nu de parameters invullen krijgen we: O
1 log2
1 (log2 u + log2 n) . δ
Het grote nadeel van Count-Min is dat fouten accumuleren. We krijgen telkens overschattingen, zoals aangehaald werd. We kunnen dit echter verbeteren door enkele aanpassingen door te voeren op het algoritme.
4.1.3
Count-Sketch algoritme
We proberen nu een manier te vinden zodat de fouten die accumuleren in Count-Min teniet worden gedaan, in plaats van deze te accumuleren. Dit gebeurt in het Count-Sketch algoritme door de introductie van extra willekeurigheid door het gebruik van een tweede hash-functie. Hierdoor krijgen we een betere accuraatheid, gegeven een hogere hoeveelheid geheugenruimte. We maken dit keer gebruik van het algemene turnstile model, waar fj zowel negatief als positief kan worden, in tegenstelling tot het strikte turnstile model in het vorige algoritme.
4.1.3.1
Basisalgoritme
Zoals in het basisalgoritme van Count-Min, maken we hier gebruik van ´e´en hash-functie h en ´e´en array T . We introduceren ook een tweede hashfunctie g : U → {−1, 1}, die uit een sterke universele familie G komt. De bedoeling is dat we de hash-functie h gebruiken zoals voorheen. We gebruiken g om de fouten teniet te doen, zoals eerder aangehaald. We doen dit door c te vermenigvuldigen met g(j). Algoritme 4 bevat het uitgeschreven algoritme. In tegenstelling tot het Count-Min algoritme, krijgen we een schatter die gemiddeld (over alle mogelijke steekproeven) genomen precies de juiste 38
Algoritme 4 Basic Count-Sketch(σ, ) 1: 2: 3: 4: 5: 6: 7: 8:
Initialiseer m = d3/2 e Initialiseer array T [1 . . . m] op 0 Kies een willekeurige hash-functie h : U → {0, 1, . . . , m−1} met h ∈ H Kies een willekeurige hash-functie g : U → {−1, 1} met g ∈ G for elk element (j, c) in de stream σ do T [h(j)] ← T [h(j)] + cg(j) end for return fˆj = g(j) · T [h(j)]
waarde geeft. We noemen fˆj een zuivere schatter voor fj . We tonen dit vervolgens aan. Voor een bepaalde j ∈ U schatten we de kwaliteit van de schatter fˆj . Net als bij het basisalgoritme van Count-Min maken we gebruik van de indicatorvariabele Ij,j 0 die aangeeft of h(j) = h0 (j). We stellen nu dat: X fˆj = g(j)( fj 0 g(j 0 )Ij,j 0 ) j 0 ∈U
X
= g(j)2 fj +
fj 0 g(j)g(j 0 )Ij,j 0
j 0 ∈U \{j}
= fj +
X
fj 0 g(j)g(j 0 )Ij,j 0 .
j 0 ∈U \{j}
Voor elementen waarbij j 0 6= j kunnen we zeggen dat:
fj 0 g(j)g(j 0 )Ij,j 0
f j 0 = −fj 0 0
als g(j) = g(j 0 ) en Ij,j 0 = 1 als g(j) 6= g(j 0 ) en Ij,j 0 = 1 anders.
g 0 We gebruiken een tweede indicatorvariabele Ij,j 0 voor g(j) = g(j ). Door de sterke universaliteit van de hash-familie G waaruit g komt, weten we dat g E[Ij,j 0 ] = 1/2 en door de universaliteit van de familie H waaruit h komt, weten we dat E[Ij,j 0 ] = 1/m − a voor een constante a ≥ 0. Aangezien h en g onafhankelijk van elkaar gekozen zijn, weten we: 1 1 g g E[Ij,j 0 Ij,j 0 ] = E[Ij,j 0 ]E[Ij,j 0 ] = · −a 2 m 1 1 g g −a E[(1 − Ij,j 0 )Ij,j 0 ] = E[(1 − Ij,j 0 )]E[Ij,j 0 ] = · 2 m 1 E[(1 − Ij,j 0 )] = 1 − + a. m
39
Dus:
E[fj 0 g(j)g(j 0 )Ij,j 0 ] = fj 0 (
1 1 1 − a)( − ) = 0. m 2 2
Met andere woorden kunnen we zeggen dat j 0 geen bijdrage levert voor fˆj : E[fˆj ] = fj +
X
E[fj 0 g(j)g(j 0 )Ij,j 0 ] = fj
j 0 ∈U \{j}
waarbij de lineariteit van de verwachting gebruikt wordt. We willen nu de fout |fˆj − fj | = |fˆj − E[fˆj ]| begrenzen. We doen dit met behulp van de ongelijkheid van Chebyshev: Var[fˆj ] , P[|fˆj − E[fˆj ]| ≥ η] ≤ η2 waarbij Var[fˆj ] = E[(fˆj − E[fˆj ])2 ] en η > 0. We moeten Var[fˆj ] berekenen en een goede waarde voor η vinden. We weten dat fj en g(j) constanten zijn, dus voor een gegeven j ∈ U hebben we: X
Var[fˆj ] = Var[fj +
fj 0 g(j)g(j 0 )Ij,j 0 ]
j 0 ∈U \{j}
= g(j)2 Var
X
fj 0 g(j 0 )Ij,j 0
j 0 ∈U \{j}
X
= Var
fj 0 g(j 0 )Ij,j 0
j 0 ∈U \{j}
2
= E
X
= E
fj 0 g(j 0 )Ij,j 0
j 0 ∈U \{j}
X
X
fj 0 g(j 0 )Ij,j 0 − E
j 0 ∈U \{j}
2
2 + E fj20 g(j 0 )2 Ij,j 0
j 0 ∈U \{j}
X
fj 0 fj 00 g(j 0 )g(j 00 )Ij,j 0 Ij,j 00
j 0 ,j 00 ∈U \{j},j 0 6=j 00
2
−
X j 0 ∈U \{j}
40
fj 0 E[g(j 0 )Ij,j 0 ] .
We berekenen:
X
E
X
2 fj20 g(j 0 )2 Ij,j = 0
j 0 ∈U \{j}
2 fj20 E[Ij,j 0]
j 0 ∈U \{j}
X
=
fj20 E[Ij,j 0 ]
j 0 ∈U \{j}
X
≤
j 0 ∈U \{j}
fj20
1 , m
waarbij de laatste ongelijkheid voorkomt uit het feit dat h uit een universele familie hash-functies komt. Verder stellen we ook dat: X E fj 0 fj 00 g(j 0 )g(j 00 )Ij,j 0 Ij,j 00 j 0 ,j 00 ∈U \{j},j 0 6=j 00
X
=
fj 0 fj 00 E[g(j 0 )g(j 00 )Ij,j 0 Ij,j 00 ]
j 0 ,j 00 ∈U \{j},j 0 6=j 00
X
=
fj 0 fj 00 E[g(j 0 )g(j 00 )]E[Ij,j 0 Ij,j 00 ]
j 0 ,j 00 ∈U \{j},j 0 6=j 00
= 0. De voorlaatste gelijkheid vloeit voort uit de onafhankelijkheid van h en g. De laatste vloeit voort uit de sterk universele familie van hash-functies. Daarom zijn we zeker dat E[g(j 0 )g(j 00 )] = −1/2+1/2 = 0. Hierdoor mogen we afleiden dat: X 1 Var[fˆj ] ≤ fj20 m 0 j ∈U \{j}
||f ||22 − fj2 = . m We stellen η = · in:
q ||f ||22 − fj2 . We vullen de ongelijkheid van Chebyshev Var[fˆj ] 2 · (||f || − fj2 ) 1 1 ≤ = , 2 m 3
q h i P |fˆj − E[fˆj ]| ≥ · ||f ||22 − fj2 ] ≤
we weten dat m =
3 . 2
Dus: 41
q i 1 h P |fˆj − fj | ≥ · ||f ||22 − fj2 ] ≤ . 3 q De kans op succes is 1 − 1/3 = 2/3. De nauwkeurigheid · ||f ||22 − fj2 ] wordt bepaald door de frequenties van de andere kleuren, en de kleur j zelf. Zoveel te frequenter een gegeven kleur voorkomt, zoveel te betrouwbaarder de schatting zal zijn. 4.1.3.2
Count-Sketch
We kunnen de kans op succes verbeteren door de mediaan te gebruiken in plaats van het minimum, wat dus de waarschijnlijkheid op een fout zal minderen. We maken zoals, in de verbeterde versie van Count-Min, ook gebruik van k hash-functies h1 , . . . , hk waarbij hi ∈ H, een universele familie, en k arrays T1 , . . . , Tk . Net als in het basisalgoritme voor CountSketch, maken we ook gebruik van een tweede hash-functie, of beter gezegd k hash-functies g1 , . . . , gk waarbij gi ∈ G, een sterk universele familie. We gebruiken deze hash-functies opnieuw om het algoritme k keer onafhankelijk van elkaar uit te voeren, en uiteindelijk de mediaan van alle oplossingen te nemen. De reden dat we voor de mediaan kiezen en niet het gemiddelde, is omdat de mediaan uitschieters negeert, maar het gemiddelde niet. Herinner je dat de mediaan de waarden in een lijst sorteert in stijgende volgorde en de waarde neemt op positie dk/2e. Algoritme 5 bevat het uitgeschreven algoritme. Algoritme 5 Count-Sketch(σ, H, δ) Initialiseer m = d3/2 e en k = O(log2 (1/δ)) Initialiseer k arrays Ti [1 . . . m] op 0 Kies k willekeurige hash-functies hi : U → [k] met hi ∈ H Kies k willekeurige hash-functie gi : U → {−1, 1} met gi ∈ G for elk element (j, c) in de stream σ do for i = 1, . . . , k do Ti [hi (j)] ← Ti [hi (j)] + cgi (j) end for end for fˆji := gi (j) · Ti [hi (j)] 11: return median1≤i≤k fˆji 1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
We verduidelijken het algoritme met behulp van een voorbeeld, gegeven in Figuur 4.3. Als waarde voor m hebben we 3, voor k nemen we als waarde 42
4. We gebruiken dezelfde stream als in het Count-Min voorbeeld, maar twee keer k hash-functies, deze zijn ook gegeven in de figuur. De items die verwijderd moeten worden, zijn opnieuw aangegeven met een prullenmandicoontje. Voor het eerste element (blauw, 1), moeten we opnieuw dezelfde elementen in de tabellen aanpassen zoals in het vorige voorbeeld: T1 [0], T2 [2], T3 [1], T4 [2]. In plaats van gewoon een increment te doen voor deze elementen aangezien c = 1, moeten we ook rekening houden met de tweede reeks hash-functies g1 , g2 , g3 en g4 , deze zullen altijd 1 of −1 als waarde teruggeven. Zoals in het algoritme beschreven staat, gebruiken we gi om te bepalen of we de elementen in de tabel moeten vermeerderen of verminderen. We krijgen volgend resultaat: T1 [0] ← T1 [0] + 1 · g1 (blauw) = 1, T2 [2] ← T2 [2] + 1 · g2 (blauw) = −1, T3 [1] ← T3 [1] + 1 · g3 (blauw) = −1 en T1 [2] ← T4 [2] + 1 · g4 (blauw) = −1. Zoals in vorig voorbeeld stellen we de optellingen voor met de blauwe en de aftellingen met de rode streepjes in de tabel rechts in de figuur. We herhalen dit proces voor elk element in de stream. Indien we te maken hebben met een verwijdering is c = −1. Per kleur verkrijgen we een aantal schatters. Voor de 1 kleur blauw krijgen we: fˆblauw = g1 (blauw) · T1 [h1 (blauw)] = 1 · T1 [0] = 2 ˆ 1 · 6 = 6, fblauw = g2 (blauw) · T2 [h2 (blauw)] = −1 · T2 [2] = −1 · −6 = 6, 3 4 fˆblauw = g3 (blauw) · T3 [h3 (blauw)] = −1 · T3 [1] = −1 · −3 = 3 en fˆblauw = g4 (blauw) · T4 [h4 (blauw)] = −1 · T4 [2] = −1 · −5 = 5. We nemen nu de 1 2 3 4 mediaan van fblauw , fblauw , fblauw en fblauw , dit geeft ons 5, 5 als resultaat. We kunnen een identieke redenering voor de overige kleuren gebruiken. De resultaten van de verscheidene schatters en de mediaan staan in de figuur onderaan weergegeven. In Figuur 4.2 gebruikten we dezelfde hash-functies h1 , h2 , h3 , h4 en dezelfde stream. We weten dat de exacte resultaten voor blauw, groen, rood, oranje, geel, roze en paars respectievelijk 4, 1, 2, 2, 2, 0, 3, 1 zijn. Bij het uitvoeren van het Count-Min algoritme kregen we als schatters respectievelijk 5, 2, 3, 4, 2, 3, 2. In Figuur 4.3 observeren we respectievelijk 5, 5; 1, 5; 5; 5; 4; 5; 1. We zien duidelijk dat het Count-Sketch algoritme voor sommige resultaten een beter resultaat geeft, maar echter ook een slechter voor anderen. Natuurlijk hangt de uitkomst van ons algoritme ook sterk af van de keuze van de hash-functie. We leiden af uit het basisalgoritme van Count-Sketch dat voor elke run i ∈ [1 . . . k] geldt: h
P |fˆj − fj | ≥ ·
q i 1 2 2 ||f ||2 − fj ] ≤ . 3
In het Count-Sketch algoritme maken we gebruik van de mediaan van de verschillende schattingen fˆj1 , fˆj2 , . . . , fˆjk . Hierdoor willen we een begrenzing 43
Figuur 4.3: Voorbeeld Count-Sketch algoritme
44
voor de volgende kans: q i h P |median1≤i≤k {fˆji } − fj | ≥ · ||f ||22 − fj2 . Met andere woorden kunnen we zeggen dat we de begrenzing voor de kans willen weten zodat er minstens dk/2e waarden fˆji zijn waarvoor · q ||f ||22 − fj2 geldt. Anders zou de dk/2ede waarde in de gesorteerde seq quentie niet voldoen aan |fˆji − fj | ≥ · ||f ||22 − fj2 . Alle schattingen fˆji na het dk/2ede element voldoen aan vorige ongelijkheid aangezien deze schattingen in toenemende volgende gesorteerd zijn. We gebruiken indicatorvariabele Xi :
Xi =
q ( 1 als |fˆji − fj | ≥ · ||f ||22 − fj2 0 anders.
P We defini¨eren X = ki=1 Xi , deze indicatorvariabele geeft het aantal elementen die voldoen aan de ongelijkheid aan. We moeten nu nog een ondergrens vinden P voor P[X ≥ k/2]. We maken om dit te berekenen gebruik van E[X] = ki=1 E[Xi ] ≤ k/3, dit volgt uit de begrenzing die we berekenden voor het basisalgoritme. We berekenen nu: k k P X≥ = P X − E[X] ≥ − E[X] 2 2 k ≤ P |X − E[X]| ≥ − E[X] 2 k k ≤ P |X − E[X]| ≥ − 2 3 k = P |X − E[X]| ≥ . 6 We kunnen nu de ongelijkheid van Chernoff/Hoeffding invullen: k k 2 P X≥ ≤ P |X − E[X]| ≥ ≤ 2e−2(1/6) k = 2e−ck 2 6 voor een bepaalde constante c. Doordat k = log2 (1/δ), stellen we dat P[X ≥ k/2] ≤ δ, dus P[X < k/2] > δ. We hebben nu een begrenzing voor de kans die we zochten: q h i P |median1≤i≤k {fˆji } − fj | ≥ · ||f ||22 − fj2 > 1 − δ. 45
In vergelijking met Count-Min geeft Count-Sketch een betere kans voor zeldzame kleuren, aangezienqwe een bepaalde kleur negeren, en de norm nemen zonder deze kleur in ||f ||22 − fj2 ; m.a.w. een zeldzame kleur heeft minder effect dan de kans die we gegeven hebben voor Count-Min. Tenslotte kunnen we voor Count-Sketch een soortgelijke analyse maken als voor Count-Min om af te leiden hoeveel geheugenruimte het algoritme gebruikt: O
1 1 log2 ( )(log2 u + log2 n) . 2 δ
Count-Sketch zal ons in theorie een beter resultaat geven dan Count-Min doordat we de accumulatie van fouten teniet doen door extra willekeurigheid te introduceren. De kans op succes is ook beter voor zeldzame kleuren voor het Count-Sketch algoritme in tegenstelling tot Count-Min. We weten nu hoe we frequentieschatting moeten uitvoeren. Deze algoritmen kunnen we gebruiken om de heavy hitters in een lijst te kunnen opsporen.
4.2
Heavy Hitters
We kunnen gebruik maken van zowel Misra-Gries als Count-Min als CountSketch om het heavy hitter-probleem in een stream σ op te lossen. Voordat we dit echter aantonen, bekijken we eerst het heavy hitter-probleem in wat meer detail. Een φ-heavy hitter in een stream σ is een item j wiens multipliciteit een fractie φ van de totale kardinaliteit overschrijdt: fj ≥ φ||f ||1 . Er kunnen natuurlijk verscheidene heavy hitters in ´e´en stream voorkomen. Veronderstel dat j1 , . . . , jK φ-heavy hitters zijn in σ voor K > 1/φ, dan PK i=1 fj ≥ Kφ||f ||1 > ||f ||1 , maar dit is onmogelijk. Er komen dus enkel tussen 0 en 1/φ heavy hitters in een stream voor. Het (geschatte) heavy hitter-probleem oplossen betekent dat we een lijst L construeren, bestaande uit items ∈ U die in de stream voorkomen zodat: 1. alle φ-heavy hitters zitten in de lijst L, 2. als j ∈ U in de lijst L zit, dan is j een φ-heavy hitter. 46
We maken nu gebruik van de algoritmen die we voorheen hebben gezien om dit heavy hitter probleem op te lossen. We zullen zowel Misra-Gries als Count-Min gebruiken om het probleem op te lossen. We kunnen natuurlijk ook Count-Sketch utiliseren zoals al vermeld. Dit wordt niet in detail in deze tekst behandeld, omdat de redenering achter het construeren van een Heavy Hitter algoritme met behulp van Count-Sketch zeer gelijkaardig is aan eentje dat Count-Min gebruikt.
4.2.1
Misra-Gries
Herinner je het Misra-Gries algoritme waar we gegeven een input stream φ en > 0 garanderen dat fj − (||f ||1 − fj ) ≤ fˆ ≤ fj . Dit garandeert dus ook voor alle j ∈ U: fj − ||f ||1 ≤ fˆ ≤ fj . Als we nu < φ kiezen, dan is j een φ-heavy hitter, φ||f ||1 ≤ fj en dus 0 < fj − ||f ||1 ≤ fˆj . Voor deze keuze van zullen alle heavy hitters een niet-negatieve schattingswaarde hebben, en dus gemonitord worden door een teller. Het is echter mogelijk dat er valse positieven optreden: niet-nul tellers die elementen opvolgen die geen φ- en geen φ/2-heavy hitters zijn. Om dit te vermijden moeten we een extra keer over de input stream gaan zodat de exacte frequenties fj voor de elementen j zodat fˆj > 0 geteld worden. Dit two-pass algoritme berekent dan de exacte set van φ-heavy hitters.
4.2.2
Count-Min
Bij het vorige algoritme moesten we gebruik maken van een two-pass algoritme om een juiste set van heavy hitters te berekenen. Indien we gebruik maken van Count-Min om frequenties te berekenen, gebruiken we echter een single-pass algoritme. Zoals bij het Count-Min algoritme zelf starten we eerst met een simpel basisalgoritme uitgeschreven als Algoritme 6. Algoritme 6 Heavy Hitters(σ, γ, φ) 1: 2: 3: 4: 5: 6:
Kies δ < uγ en initialiseer = φ4 for elke j ∈ U do if fˆj > 34 φ||f ||1 met fˆj gebaseerd op Count-Min then Voeg j ∈ U toe aan L end if end for 47
Herinner je dat Count-Min garandeert dat P[|fˆj − fj | ≤ ||f −j ||1 ] ≥ 1 − δ. Aangezien we weten dat fj ≤ fˆj doordat we altijd overschatten, zeggen we ook dat: P[fˆj − fj ≤ ||f ||1 ] ≥ 1 − δ. We kunnen nu stellen dat j een φ-heavy hitter is als fj ≥ φ||f ||1 > (3/4)φ||f ||1 . Aangezien fˆj fj overschat en fˆj > (3/4)φ||f ||, zal j in de lijst L zitten, zoals alle andere φ-heavy hitters. We willen graag weten wat de kans op fouten is, we willen met andere woorden weten wat
3 φ P fj < ||f ||1 en fˆj > φ||f ||1 2 4
is. Vergewis je ervan dat fj < (φ/2)||f ||1 en fˆj > 3φ/4||f ||1 impliceren dat: fˆj − fj >
3 1 − 4 2
1 φ||f ||1 = φ||f ||1 = ||f ||1 , 4
voor onze keuze van . We weten al dat de kans dat dit gebeurt kleiner is dan δ. Dit geldt voor elke j ∈ U en door de gebruik te maken van de unie krijgen we: u X φ P[L bevat een fout item] ≤ P j in L, fj < ||f 1 || < γ, 2 j=1 aangezien δ < γ/u. De lijst L dat wordt teruggegeven door het algoritme bevat alle φ-heavy hitters en bevat elementen met fj < φ/2||f ||1 met de lage kans γ. De geheugenruimteconsumptie van dit algoritme is O
1 log2 φ
u (log2 u + log2 n) . γ
De tijdscomplexiteit is minder begeerlijk aangezien we in het slechtste geval de lijsten in Count-Min zoveel keer moeten afgaan als er elementen in u zijn. We moeten O(u log2 (u/γ)) elementen checken, indien we veronderstellen dat we een waarde van een array krijgen in constante tijd. We brengen nu enkele verbeteringen aan om het algoritme bij te schaven en de tijdscomplexiteit te verlagen. Het idee erachter is het volgende: in 48
plaats van alle lijsten af te gaan voor elk element in U, bouwen we een perfecte binaire boom en gebruiken we een ‘divide-and-conquer’ benadering. We veronderstellen dat de grootte u van U een macht van 2 is: u = 2d . We gebruiken I j om de partitie voor te stellen van {1, 2, . . . , u = 2d } in buckets van grootte 2j :
I j = {{1, 2, . . . , 2j }, {2j +1, 2j +2, . . . , 2j+1 }, . . . , {2d−1 +1, 2d−1 +2, . . . , 2d }}. We bouwen een boom op met diepte d + 1 = log2 (u) + 1. Op elk level j ∈ [0, d] hebben we u/2j nodes, waar level 0 de bladeren voorstelt, ´e´en voor elk element in U. Op elk level, definieer: X
f j = (f j1 , . . . , f ju/2 ), met f ji = j0
is in partitie
fj 0 . Iij
Vergewis je ervan dat f 0 = (f1 , f2 , . . . , fu ) gelijk is aan de standaard frequentievector. Voor hogere levels zal f j de som van de frequenties die worden gegroepeerd volgens de partitie op het level voorstellen. Voor een bepaald level j ∈ [0, d], passen we het algoritme Count-Min aan j zodat het een schatting ˆfi geeft voor f ji voor i ∈ [1, 2j ]. We kiezen in plaats van de hash-functies van U → {0, . . . , m − 1} k hash-functies hjl van {1, . . . , u/2j } → {0, 1, . . . , m − 1} met l ∈ [1, k]. De intervallen Iij worden behandeld als de elementen van de stream die moeten gehasht worden. Wanneer een item (j 0 , c) uit een stream σ wordt bekeken, moeten we identificeren tot welk interval dit behoort en de volgende update uitvoeren: Tl [hjl (i)] := Tl [hjl (i)] + c. Uiteindelijk wordt ˆfji = min Tl [hj [i]] l 1≤l≤k
teruggegeven. Met behulp van een gelijkaardige analyse als bij het eerste Heavy Hitters algoritme, tonen we aan dat voor een bepaalde en δ: j P[ˆfi − f ji ≤ ||f ||1 ] ≥ 1 − δ.
Het algoritme wordt uitgeschreven als Algoritme 7. 49
Algoritme 7 Heavy Hitters (improved)(σ, γ, φ) 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
Initialiseer δ = logγφ(u) en = φ4 2 for elk level j ∈ [0, d] do Hou log2 (u) + 1 kopie¨en bij van Count-Min(σ, , δ) Sla ook de approximatie ˆfj van f j op if fˆij > 34 φ||f ||1 met fˆij gebaseerd op Count-Min then Ga omlaag in de boom if fˆj0 > 43 φ||f ||1 then Voeg blad j ∈ U toe aan L end if end if end for
Een item j behoort tot log2 (u) + 1 = d + 1 intervallen. Hoe hoger we in de boom zitten, hoe hoger de schattingen aangezien er meer elementen worden opgeteld. Zoals we al zeiden in het vorige algoritme, als j 0 ∈ U een heavy hitter is, dan fˆj00 > (3/4)φ||f ||1 . Dit geldt voor elke fˆij dat overeenkomt met het interval Iij op level j waartoe j 0 behoort. De lijst L bevat dus zeker alle φ-heavy hitters aangezien een item j 0 zal worden verwerkt door het algoritme. We bekijken nu de kans dat L foute items bevat. Elke level j in de boom kan maximaal O(1/φ) φ-heavy hitters bevatten. Het algoritme krijgt schattingen voor f ji van maximaal O(log2 (u)/φ) intervallen. We weten dat we door onze keuze van en δ het volgende kunnen stellen: j φ γφ j P ˆfi − f i > ||f ||1 ≤ . 4 log2 (u) j Gelijkaardig aan het vorige algoritme weten we dat ˆfi − f ji > φ/4||f ||1 het event is dat voorstelt dat we slechte beslissing maakten. Indien we O(log2 (u)/φ) intervallen controleren kunnen we, met behulp van de unie, afleiden dat de kans dat minstens ´e´en van hen voldoet aan het event, begrensd is door δ. Dus, de kans op succes is minstens 1 − γ.
Dit algoritme heeft 1 1 O log2 (u) log2 log2 log2 (u)(log2 (u) + log2 (n) φ φγ geheugenruimte nodig. Waarbij log2 (u) het aantal levels, (1/φ) log2 (1/φγ) log2 log2 (u) het aantal tellers en (log2 (u)+log2 (n)) de grootte van de tellers 50
voorstelt. De tijdscomplexiteit is ook beter omdat de lineaire afhankelijkheid op de grootte u van U er niet meer is. Dit zorgt echter wel voor een grotere geheugensconsumptie dan het vorige algoritme. Nu we een goede basis hebben in verband met streaming algoritmes door het bestuderen van frequentieschatting en heavy hitters, kunnen we overgaan op een complexer probleem, namelijk het tellen van het aantal unieke elementen, wat natuurlijk het onderwerp van deze paper is. Zoals voorheen werd aangehaald, zullen we hier ook gebruik maken van hashing om willekeurigheid te introduceren en correcte schattingen te kunnen maken in verband met het aantal unieke elementen in de stream die wel als input krijgen.
51
52
Hoofdstuk 5 Distinct counting Tot nu toe hebben we gekeken hoe we de frequentie van items in een stream kunnen bepalen met behulp van bijvoorbeeld het Count-Sketch algoritme. We hebben ook gekeken hoe we de heavy hitters uit een stream kunnen halen, of met andere woorden de elementen die het vaakst voorkomen. Zoals al aangehaald zijn we echter ge¨ınteresseerd in een iets complexere materie. Stel dat je een zeer grote multiset van data hebt met dubbele elementen, die niet gesorteerd is. Indien we willen weten hoeveel unieke elementen er in de lijst zitten, zou het niet praktisch zijn om deze eerst te sorteren en daarna te tellen, aangezien deze lijst niet volledig in het geheugen past. We moeten de lijst in stukken inlezen aangezien we niet de volledige hoeveelheid data ineens in het geheugen kunnen inlezen, dit zorgt voor een gecompliceerd sorteeralgoritme. Ook neemt dit veel tijd in beslag. We willen het aantal unieke elementen op een effici¨ente manier kunnen tellen. Met andere woorden: we willen de kardinaliteit van een zeer grote multiset bepalen. Meestal is deze multiset simpelweg een grote datastream. [11] Dit probleem is van toepassing in verschillende gebieden van data-mining, database query-optimalisatie en analyse van routerverkeer. In deze context is de data ofwel te groot om in het geheugen te passen of soms zelfs te groot om te kunnen worden opgeslagen, aangezien er een continue toevloed is van datapakketten. In database query-optimalisatie kunnen schattingen in verband met de kardinaliteit zeer nuttig zijn. Voor een typische complexe query zijn er verschillende operaties zoals joins, projecties en dergelijke die moeten gebeuren, alsook operaties in verband met verzamelingen zoals de intersectie. Indien we op voorhand de kardinaliteit zouden weten van verscheidene sets, zou dit mogelijk helpen om een effici¨ente verwerkingsstrategie te kiezen om de query op te lossen voor de gegeven data. Net zoals bij heavy hitters kan de analyse van netwerkverkeer bij routers 53
ook baat hebben bij kardinaliteitsschatting. Wormen en virussen kunnen worden onthuld door alarmerend hoge kardinaliteiten van verschillende connecties. In netwerkverkeer zouden deze onopgemerkt kunnen blijven, maar dit kan opgelost worden met het tellen van de kardinaliteit. [8] [11] Net zoals in het vorige hoofdstuk zullen we het gewenste resultaat niet exact berekenen. We offeren een deel van de accuraatheid op zodat we minder geheugenruimte gebruiken. We maken een schatting van de kardinaliteit met behulp van een een probabilistisch algoritme. Elk betrouwbaar algoritme zal gebruik maken van willekeurigheid die ge¨ıntroduceerd wordt door het gebruik van een hash-functie die zo werd ontworpen dat de bits van de gehashte waarden verondersteld worden onafhankelijk van elkaar te zijn en elk voorkomen met kans 1/2. De beste kardinaliteitsschatters vertrouwen erop geschikte observaties te maken van de gehashte waarden h(M) van de input multiset M, waardoor we een geschikte waarde voor de schatter van de ongekende kardinaliteit n kunnen afleiden. We zullen een observabele defini¨eren van multiset S ≡ h(M) van {0, 1}∞ strings, of equivalent re¨ele [0, 1] getallen, als een functie die gebaseerd is op de onderliggende set van S, een grootheid die onafhankelijk is van replicatie. We defini¨eren twee categorie¨en: [8]
• Bitpatroon observabele: gebaseerd op een zeker patroon van bits die in het begin (of op het einde) van de (binaire) S-waarden voorkomen. Indien we in het begin van een string in stream S het bitpatroon 0ρ−1 1 waarnemen, kunnen we stellen dat dit een indicatie voor de kardinaliteit 2ρ is. • Geordende steekproefstatistiek observabele: gebaseerd op geordende steekproeven. Indien X = min(S), hopen we dat n ongeveer van de orde 1/X is aangezien E(X) = 1/(n + 1). Het voordeel van het gebruik van observabelen is dat deze niet veel geheugen vereisen om te kunnen opslaan, dit betekent wel dat ze enkel een ruwe indicatie van de gezochte kardinaliteit zullen bezorgen zoals log2 n of 1/n. Door de mogelijk grote spreiding zou deze schatting echter compleet fout kunnen zijn, dus we zullen een manier zoeken om dit probleem op te lossen. Een oplossing zou zijn in parallel verscheidene experimenten uit te voeren en deze later samen te voegen. Voor m experimenten die elk als standaardafwijking σ hebben, zal het volledige experiment slechts een √ standaardafwijking van σ/ m bedragen. Dit zou echter betekenen dat we zeer veel moeten berekenen, en ook m verschillende hash-functies hebben. [8] 54
We trachten nu echter het effect van m experimenten na te bootsen met slechts ´e´en hash-functie. We verdelen de input stream h(M) in m substreams. Voor elk van deze substreams berekenen we een observabele. Deze worden uiteindelijk gecombineerd om een schatting te kunnen geven over de kardinaliteit. Deze techniek wordt stochastic averaging genoemd en werd voorgesteld door Flajolet en Martin [9]. We passen deze techniek vaak nog toe. In de komende algoritmen zullen we zien dat we enkel gebruik maken van bitpatroon observabelen om een schatting te kunnen maken in verband met de kardinaliteit. We maken geen gebruik van geordende steekproefobservabelen. [8]
5.1
Eenvoudige algoritmen
Voordat we beginnen aan complexere algoritmen, overlopen we eerst een aantal eenvoudige oplossingen voor het tellen van de kardinaliteit. We beginnen met twee simpelere algoritmes die een basis vormen voor wat er nog zal komen. We brengen daarna alsmaar verfijningen aan aan het algoritme om het effici¨enter te maken, ondanks toch een betrouwbare schatting van de kardinaliteit te bekomen. Dit paragraaf is gebaseerd op de ‘Big Data’ cursustekst van Floris Geerts [11].
5.1.1
Morris algoritme
Het eerste algoritme dat we bespreken is het Morris algoritme, wat in 1978 het eerste echte streaming algoritme was dat werd bedacht. Ondanks dat het algoritme het volledige aantal elementen in een lijst telt, en niet alleen unieke items, geeft dit enkele goede technieken in verband met het verlagen van de geheugenruimtecomplexiteit. In het vanilla streaming model bekijken we een stream σ = ha1 , a2 , . . . , an i simpelweg als h1, 1, . . . , 1i aangezien het niet uitmaakt wat de waarde van een item ai net is. We kunnen zeer makkelijk een exact algoritme opstellen dat gebruik maakt van een sublineaire hoeveelheid geheugenruimte dat O(log2 n) bits nodig heeft. Deze bits worden gebruikt om de som n op te slaan die de som van alle eentjes in de stream voorstelt, of met andere woorden het aantal elementen in de stream telt. Algoritme 8 bevat het uitgeschreven algoritme. Als we echter een stuk van de accuraatheid willen opofferen, verlagen we de hoeveelheid geheugenruimte die nodig is echter naar O(log2 log2 (n)). Het idee achter dit algoritme is dat we het aantal benaderen door machten van 55
Algoritme 8 Exact Count(σ) 1: 2: 3: 4: 5:
Initialiseer de teller c op 0 for elk element in de stream σ do c := c + 1 end for return c
twee: 2i , en enkel de exponent op te slaan. Aangezien 2log2 log2 (n) = log2 (n), neemt dit dus slechts O(log2 log2 (n)) geheugenruimte in beslag. We moeten een manier vinden om deze zogenaamde “log teller” te berekenen. We kunnen dit vergelijken met het opgooien van c muntstukken. Indien deze allemaal op de kopkant belanden, dan moet de teller worden ge¨ıncrementeerd. Algoritme 9 bevat het uitgeschreven algoritme. Algoritme 9 Morris(σ) 1: 2: 3: 4: 5:
Initialiseer de teller c op 0 for elk element in de stream σ do Incrementeer c met kans 21c end for return cˆ = 2c − 1
Door deze updateprocedure weten we zeker dat E[ˆ c] = n en dus hebben we een zuivere schatter als resultaat. We zien dit makkelijk in aan de hand van volgend voorbeeld: • Als n = 1, dan is E[ˆ c] = E[2X1 −1] = 1, omdat c = 1 en cˆ = 21 −1 = 1. • Als n = 2, dan is E[ˆ c] = 21 (1 + 3) = 2, omdat: – we met kans
1 2
kunnen stellen dat c = 1 en cˆ = 1,
– en we met kans
1 2
kunnen stellen dat c = 2 en cˆ = 22 − 1 = 3.
We kunnen dit ook algemeen defini¨eren. We gebruiken Xn als stochastische variabele die de waarde van de teller voorstelt op het moment dat de effectieve teller gelijk is aan n. We hebben in het voorbeeld aangetoond dat E[2X1 − 1] = 1. We veronderstellen dat E[2Xn−1 − 1] = n − 1. We tonen nu met behulp van inductie aan dat E[2Xn − 1] = n.
56
E[2Xn ] =
P
j≥1
2j P[Xn = j]
(E[X] =
P 1 j j≥1 2 (1 − 2j )P[Xn−1 = j] P 1 )P[Xn−1 = j − 1]) + j≥1 2j ( 2j−1 P P = 2j P[Xn−1 = j] − j≥1 P[Xn−1 = j] j≥1 P +2 j≥1 P[Xn−1 = j − 1] =
= E[2Xn−1 ] − 1 + 2
P
x
P[X = x] · x)
(niet verhoogd; counter was j) (verhoogd; counter was j − 1)
(som van alle kansen is 1)
= n+1
2Xn − 1 is een zuivere schatter voor n. We tonen ook aan dat Var[2Xn − 1] gelijk is aan O(n2 ).
Var[2Xn −1 ] =
Var[2Xn ]
(veronderstel: v.d. vorm an2 + bn + c)
= E[22Xn ] − (E[2Xn ])2 = E[22Xn ] − (n + 1)2
(tweede term is in orde, we focussen op de eerste)
Veronderstel dat E[22Xn ] = an2 + bn + c. We berekenen nu enkele verwachtingswaarden. E[22X1 ] =
22 = 4
(voor n = 1) a+b+c=4
E[22X2 ] =
22·2 · 12 + 22 ·
1 2
= 8 + 2 = 10
1e iteratie 1/2
(voor n = 2)
2e iteratie c=2
c=1 1/2 c=1
57
4 · a + 2 · b + c = 10
E[22X3 ] =
2 2 2 8
+ 58 24 + 18 26 = 1 + 10 + 8 = 19
1e iteratie
2e iteratie
(voor n = 3)
3e iteratie 1/4 c=3
c=2 1/2 3/4
c=2
1/2
c=2
1/2
c=1
c=1 1/2 c=1 9 · a + 3 · b + c = 19
We lossen met behulp van de drie vergelijkingen die we hebben een stelsel op om zo tot een waarde voor a, b en c te komen.
a + b + c = 4 4a + 2b + c = 10 9a + 3b + c = 19
3 a = 2 ⇒ b = 32 c=1
We weten dat E[22X1 ] = (3/2) · 12 + (3/2) · 1 + 1 correct is voor n = 1. We bewijzen nu opnieuw per inductie dat dit voor n ook geldt. We veronderstellen als inductiehypothese dat E[22Xn−1 ] = (3/2) · (n − 1)2 + (3/2) · (n − 1) + 1.
E[22Xn ] =
X
=
X
22j P[Xn = j]
j≥1
22j (1 −
j≥1
+
X j≥1
22j (
1 )P[Xn−1 = j](niet verhoogd; counter was j) 2j 1
2j−1
)P[Xn−1 = j − 1])(verhoogd; counter was j − 1)
58
=
X
22j P[Xn−1 = j] −
j≥1
+4
X
2j P[Xn−1 = j]
j≥1
X
j−1
2
P[Xn−1 = j − 1]
j≥1 2Xn−1
=E[2
] − E[2Xn−1 ] + 4E[2Xn−1 ]
=E[22Xn−1 ] + 3E[2Xn−1 ](gebruik inductiehypothese) 3 3 = (n − 1)2 + (n − 1) + 1 + 3n 2 2 3 2 3 = n + n+1 2 2 We hebben nu aangetoond dat Var[2Xn − 1] = O(n2 ). We kunnen het algoritme evenwel nog verbeteren. Veronderstel dat we het Morris algoritme m keer onafhankelijk van elkaar runnen. We gebruiken cˆi P als schatter voor ˆi . Door de de ide run. Daarna gebruiken we als resultaat cˆ = (1/m) m i=1 c lineariteit van de verwachting, is dit nog steeds een zuivere schatter. Door de onafhankelijkheid leiden we ook af dat: # 2 m 1 X n Var cˆi = O . m i=1 m "
Dit gebruiken we om de ongelijkheid van Chebyshev in te vullen zodat we een foutbegrenzing krijgen: Var[ˆ c] P [|ˆ c − n| > n] ≤ 2 2 ≈ O n
n2 m
1 =O 2 n2
1 m2
.
Voor m = 1/2 mogen we zeggen: 1 P [|ˆ c − n| > n] ≤ . 3 De verbetering van het algoritme werd uitgeschreven in Algoritme 10. Tenslotte roepen we dit nieuwe algoritme nog een aantal keren onafhankelijk van elkaar op en gebruiken we de mediaan om het resulaat terug te geven om nog een beter eindresultaat te bekomen. Hier gebruiken we de ongelijkheid van Chernoff/Hoeffding die ons kan zeggen hoe vaak we het algoritme moeten runnen om de echte teller te benaderen met nauwkeurigheid en met hoge kans (1 − δ). Zoals we in Count-Sketch ook deden, laten we cˆi de schatter zijn voor het bovenstaande Morris (semi-improved) algoritme. Indien we het algo59
Algoritme 10 Morris (semi-improved)(σ,,δ) 1: Initialiseer m = O 12 2: for elke i ∈ [1, m] do 3: cˆi is de approximatie van n teruggegeven door Morris(σ) . elke call is onafhankelijk van elkaar 4: end for Pm 1 ˆi 5: return cˆ = m i=1 c ritme k keer runnen en telkens het resultaat bijhouden, leiden we uiteindelijk het volgende eindresultaat af: c˜ = median1≤i≤k cˆi . We zeggen dat ci − n| ≤ n en Pk Yi de indicatorvariabele is voor het event |ˆ dus is Y = i=1 Yi . Y heeft dus als waarde het aantal runs waarin geen fouten zijn voorgekomen. Aangezien we de mediaan gebruiken kunnen we met behulp van de ongelijkheid van Chernoff/Hoeffding stellen: k P [|˜ c − n| > n] ≤ P Y ≤ 2 k ≤ P Y − E[Y ] ≤ − E[Y ] 2 k 2k ≤ P Y − E[Y ] ≤ − 2 3 k = P Y − E[Y ] ≤ − 6 k = P E[Y ] − Y ≥ 6 k ≤ P |Y − E[Y ]| ≥ 6 −γk < 2e
voor een constante γ. We stellen k = O(log2 (1/δ)) en m = O(1/2 ), zodat: P [|˜ c − n| > n] > 1 − δ. Het nieuwe algoritme hebben we uitgeschreven in Algoritme 11. De geheugenruimtecomplexiteit van het derde Morris algoritme is 60
Algoritme 11 Morris (improved)(σ,,δ) 1: Initialiseer k = O log2 ( 1δ ) 2: for elke i ∈ [1, k] do 3: cˆi is de approximatie van n van Morris(semi-improved)(σ,,δ) . elke call is onafhankelijk van elkaar 4: end for 5: return c˜ = median1≤i≤k cˆi
O
1 log2 2
1 log2 log2 (n) . δ
Het Morris algoritme heeft ons geleerd hoe we het aantal elementen in een stream moeten tellen. We hebben ook bekeken dat het meermaals aanroepen van het algoritme een betere schatting kan vormen indien we al deze resultaten bundelen om een correctere uitkomst te bekomen. Toch missen we nog een vitaal deel van onze vraagstelling: we willen niet het aantal elementen, maar het aantal unieke elementen benaderen.
5.1.2
Flajolet-Martin algoritme
Indien we geen rekening hoeven te houden met geheugengebruik, zien we in dat we met O(n) geheugenruimte het aantal unieke elementen makkelijk kunnen tellen in O(n log2 n) tijd door te sorteren. Maar we zoeken een algoritme dat we kunnen gebruiken om het aantal elementen in een stream te tellen die mogelijk niet volledig in het geheugen past, zoals bij Big Data het geval kan zijn. We zoeken dus een algoritme waarvoor we slechts een sublineaire hoeveelheid geheugenruimte nodig hebben. Het FlajoletMartin algoritme wordt vaak ook√probabilistic counting genoemd [9] en heeft een standaardfout van 0.78/ m. We maken gebruik van een licht gemodificeerde versie van het FlajoletMartin algoritme voorgesteld door Alon, Matias en Szegedy [1]. De reden dat we gebruik maken van de gemodificeerde versie is dat Flajolet en Martin veronderstellen dat we een expliciete familie van hash-functies die ideale stochastische eigenschappen ter beschikking hebben, maar men weet echter niet of zo’n familie bestaat. In tegenstelling tot het originele algoritme maken we slechts gebruik van een lineaire hash-functie. Dit algoritme gebruikt O(log2 n) geheugenruimte en vormt de basis voor het LogLog en HyperLogLog algoritme dat later aan bod komt. Het idee achter het algoritme is dat we gebruik maken van een hash-functie 61
die elk element in een stream mapt in een bepaalde bucket. Aangezien we gebruik maken van een goede hash-functie, mogen we verwachten dat 1/2n elementen een binaire representatie hebben die eindigt in 0n . We verwachten nu bijvoorbeeld dat ongeveer de helft een binaire representatie zal hebben die eindigt in 0; of met andere woorden deelbaar is door 2, of dat bijvoorbeeld 1/4de van de elementen een binaire representatie heeft die eindigt in 00. Algemeen stellen we dat indien de hash-functie een integer genereert die eindigt in 0n bits dat we een stream kunnen verwachten met 2n items. We moeten dus bijhouden wat het maximum aantal nullen is achteraan de hash-waarden. Voorbeeld We verduidelijken dit met volgend voorbeeld. Stel dat we een stream hebben: σ = h1, 3, 2, 1, 2, 3, 4, 3, 1, 2, 3, 1, . . . i met waarden uit universum U. We gebruiken de hash-functie h(x) = 3x + 1 mod 5. En dus:
h(σ) = h4, 0, 2, 4, 2, 0, 3, 0, 4, 2, 0, 4, . . . i = h100, 0, 10, 100, 10, 0, 11, 0, 100, 10, 0, 100, . . . i
(in binair).
Indien we nu het maximaal aantal laatste nullen van de binaire representaties van bovenstaande stream willen opslaan, krijgen we uiteindelijk de waarde 2, en dus krijgen we als schatting dat we 22 = 4 unieke elementen in de stream vinden. ♦ Formeel stellen we dat we voor een bepaalde integer p > 0, we zeros(p) het aantal laatste nullen van de binaire representatie van p laten voorstellen: zeros(p) = max{i | 2i deelt p}. We gebruiken dit als bitpatroon observabele. We schrijven dit uit in Algoritme 12. We veronderstellen als vergemakkelijking dat n = 2w . Merk op dat we in bovenstaande beschrijving een zogenaamde stream gebruiken die we ook “ideale” multiset met kardinaliteit n (het aantal unieke elementen) kunnen noemen. De definitie van een ideale multiset is dat we de elementen kunnen beschouwen als gebouwd te zijn uit een onafhankelijke n-sequentie uit universum U, dan worden de elementen op een arbitraire manier gekopieerd en uiteindelijk wordt er een arbitraire permutatie uitgevoerd. Om dit te verwezenlijken gebruiken we de hash-functie h die elementen uit universum U omvormt in voldoende lange binaire strings. Hierdoor hebben we dus geen informatie over de data in de multiset, we kunnen dus geen statistische assumpties maken in verband met de data. 62
Algoritme 12 Flajolet-Martin(σ) 1: 2: 3: 4: 5: 6: 7: 8:
Kies h : [n] → [n], een willekeurige hash-functie van een sterk universele hash-familie Initialiseer z = 0 for elk element j in de stream σ do if zeros(h(j)) > z then z = zeros(h(j)) end if end for return cˆ = 2z
Het algoritme houdt ´e´en counter van grootte O(log2 n) = O(w) bij. We willen weten of cˆ nu echt een goede schatter is voor het aantal unieke elementen c in σ. We gebruiken voor j ∈ U en elke integer r ≥ 0 de stochastische variabele X Pr,j als indicator voor het event “zeros(h(j)) ≥ r”. We zeggen Yr = j:fj >0 Xr,j . Dus: E[Xr,j ] = P[zeros(h(j)) ≥ r] = P[2r deelt h(j)]. Er zijn 2w−r elementen die deelbaar zijn door 2r en aangezien P[h(j) = i] = 1/2w door de sterke universaliteit van de hash-familie hebben we: 1 2w−r E[Xr,j ] = w = r 2 2 en
2 Var[Xr,j ] = E[Xr,j ] − (E[Xr,j ])2 =
1 1 (1 − r ). r 2 2
We berekenen nu de variantie en verwachte waarde voor Yr als volgt:
E[Yr ] =
X
E[Xr,j ] =
j:fj >0
c , 2r
met c het aantal unieke elementen in de stream. Aangezien h uit een sterk universele hash-familie komt, en de stochastische variabelen Yr paarsgewijs 63
disjunct zijn, stellen we dat: X X X Var[Yr ] = Var[ Xr,j ] = Var[Xr,j ] = E[Xr,j ] j:fj >0
=c
j:fj >0
j:fj >0
1 c 1 (1 − r ) < r = E[Yr ]. r 2 2 2
Voor elke γ > 3 willen we aantonen dat de kans dat c/γ ≤ cˆ ≤ γc minstens 1−3/γ is. We bewijzen dus twee dingen, dat (1) c/γ ≤ cˆ en dat (2) cˆ ≤ γc. 1. We stellen dat (1) geldt als Yr1 6= 0 voor een bepaalde r1 , aangezien er dan minstens ´e´en element j is wiens hash-waarde h(j) ons groter dan of gelijk aan r1 nullen achteraan geeft. Dus 2r1 ≤ cˆ = 2z . We kiezen nu de kleinste r1 waarvoor geldt c/γ ≤ 2r1 . En dus geldt 1/γ ≤ cˆ. 2. We gebruiken een gelijkaardige redenering voor (2). Yr2 = 0 betekent dat er geen enkel element j is waarvoor de hash-waarde h(j) ons r2 laatste nullen geeft. En dus: cˆ = 2z ≤ 2r2 . We nemen als r2 de kleinste waarde zodat 2r2 ≤ γc. Hierdoor geldt cˆ ≤ γc. We bekijken nu de events Yr2 = 0 en Yr1 6= 0. Het Flajolet-Martin algoritme is correct indien beide events voorvallen. We berekenen een begrenzing hiervoor met behulp van het complement van de individuele events. We gebruiken de ongelijkheid van Markov om een begrenzing te krijgen voor de kans dat Yr2 groter is dan nul: P[Yr2 > 0] = P[Yr2 ≥ 1] ≤ E[Yr2 ] =
1 c . < r 22 γ
We gebruiken de ongelijkheid van Chebyshev om een begrenzing te krijgen voor de kans dat Yr1 gelijk is aan nul: P[Yr1 = 0] = P [Yr1 − E[Yr1 ] = −E[Yr1 ]] ≤ P [|Yr1 − E[Yr1 ]| = E[Yr1 ]] ≤ P [|Yr1 − E[Yr1 ]| ≥ E[Yr1 ]] Var[Yr1 ] ≤ (E[Yr1 ])2 c/2r1 2r1 = . ≤ (c/2r1 )2 c 64
Door onze keuze van r1 weten we dat 2r1 < 2c/γ en dus is P[Yr1 = 0] < 2/γ We hebben nu begrenzingen voor het complement van de events Yr2 = 0 en Yr1 6= 0. We nemen nu de unie zodat minstens ´e´en van de twee events voorvalt, hierdoor krijgen we:
P[Yr2 > 0 of Yr1 = 0] ≤
3 1 (1 + 2) = . γ γ
Indien we het complement hiervan nemen, hebben we een begrenzing voor de correctheid van het Flajolet-Martin algoritme:
3 P[Yr2 = 0 en Yr1 6= 0] ≥ 1 − . γ
Deze kans op succes is echter redelijk klein. We kunnen dit verbeteren door gebruik te maken van k verschillende, uniforme hash-functies en daarna de mediaan te gebruiken zoals we bij enkele vorige algoritmen al gedaan hebben. Voor elke i ∈ [1, k], defini¨eren we:
( 0 als cˆi ∈ [ γc , cγ] Xi = 1 anders.
We weten dat P[Xi = 1] hoogstens 3/γ < 1/2 is, indien γ groter is dan 6. De verwachte waarde E[Xi ] ≤ 3/γ en dus:
" E
k X
# Xi ≤
i=1
3k . γ
P Vergewis je ervan dat c/γ ≤ cˆ ≤ γc geldt indien ki=1 Xi < k/2. We moeten dus een begrenzing vinden voor dit event. We stellen dat X = 65
Pk
i=1
Xi . We maken gebruik van de ongelijkheid van Chernoff/Hoefding: P[X ≥
k k ] = P[X − E[X] ≥ − E[X]] 2 2 k ≤ P[|X − E[X]| ≥ − E[X]] 2 k 3k ≤ P[|X − E[X]| ≥ − ] 2 γ (γ − 6) = P |X − E[X]| ≥ k 2γ 2 γ−6 −2( 2γ k) k . ≤ 2e
Als waarde voor k kiezen we O(log2 (1/δ)). Hierdoor krijgen we P[X ≥ k/2] ≤ O(δ) en dus geldt P[X < k/2] ≤ 1 − O(δ), zoals we wilden. We kunnen het aantal unieke elementen in een lijst dus benaderen door enkel 1 O log2 log2 n δ geheugenruimte te gebruiken, waarbij log2 (1/δ) het aantal hash-functies voorstelt en log2 n de hash-functie zelf. Na de basis die gelegd werd in dit algoritme volgden er echter nog effici¨entere streaming algoritmes, zoals het LogLog algoritme. We zullen snel zien dat het LogLog algoritme veel gesofisticeerder is dan het FlajoletMartin algoritme. Dit betekent echter ook dat het LogLog algoritme iets complexer zal zijn.
5.2
LogLog
LogLog zorgt ervoor dat we op een effici¨ente en accurate manier het aantal unieke elementen kunnen tellen. Daarom kan het gebruikt worden voor bijvoorbeeld online toepassingen waar men op elk moment een schatting wil hebben voor de kardinaliteit van een stream zonder zeer lang te wachten of enorm veel geheugen te gebruiken. We gebruiken voor deze paragraaf de originele LogLog paper als referentie [7]. Het algoritme werd opnieuw mede-ontworpen door Flajolet. We bekijken hier de datastream als een multiset. Het algoritme werkt incrementeel in een sinlge-pass voor een gegeven data flow. We kunnen het 66
algoritme ook gedistribueerd of parallel gebruiken met optimale speed-up en minimale communicatie tussen de verscheidene processen. Doordat we enkel een kleine hoeveelheid extern geheugen nodig hebben voor het algoritme, kunnen we dit voordeel uitbuiten door verscheidene statistieken voor bepaalde datasets tegelijk te genereren indien gewenst. We maken gebruik van m geheugeneenheden, met elke geheugeneenheid een “kleine byte” groot die ongeveer log2 log2 Nmax bits omvat, waarbij Nmax een a priori bepaalde bovengrens is op de kardinaliteit. Dit is in tegenstelling tot het Flajolet-Martin algoritme wat gebruik maakt van zogenaamde “woorden” die uit veel meer bits bestaan. Als resultaat krijgen we een √ asymptotisch√ zuivere schatter met een accuraatheid die dichtbij 1, 30/ m en 1, 05/ m ligt voor respectievelijk het LogLog algoritme en het geoptimaliseerde Super-LogLog algoritme. Een groot voordeel van LogLog, net zoals het Flajolet-Martin algoritme, is dat het ten opzichte van andere distinct counting algoritmes universeel is en het geen verwachtingen heeft in verband met de statistische regelmaat van de data. Toen de paper over LogLog verscheen in 2003, konden we het beschouwen als de beste general-purpose algoritmische oplossing voor het schatten van grote kardinaliteiten tot dan toe.
5.2.1
Het LogLog algoritme
We willen de kardinaliteit van een multiset van data items weten, het aantal unieke elementen die behoren tot een zeker universum U = {0, 1}∞ . Het idee achter het LogLog algoritme is dat we door de multiset M lopen, elementen hashen en patronen van de vorm 0∗ 1 observeren die voorkomen in het begin van de gehashte waarden. We kunnen nu gebruik maken van het aantal voorloopnullen die we waarnemen om assumpties te maken over de kardinaliteit. We gaan er vanuit dat we een hash-functie h ter beschikking hebben die elementen uit het universum U omvormt tot binaire strings van voldoende lengte zodat de bits waaruit de gehashte waarde is opgemaakt willekeurig uniforme onafhankelijke bits zo goed mogelijk benaderen. We maken dus gebruik van willekeurigheid die ge¨ıntroduceerd wordt door een hashfunctie, zoals bij de vorige algoritmes die gebruik maken van hashing. We stellen dat ρ(v) de positie voorstelt van de meest linkse 1-bit, bijvoorbeeld: ρ(0000101) = 5. We weten dat de hash-functie uniforme hash-waarden genereert. We kunnen daardoor afleiden dat we voor het bitpatroon met het maximaal aantal voorloopnullen 0p−1 1 een kardinaliteit van 2p hebben. We verwachten dat n/2p van de unieke elementen in 67
M dezelfde ρ-waarde hebben als p. We maken dus gebruik van volgende bitpatroon observabele: R(M) := max ρ(v). v∈M
Dit is een zeer ruwe schatting voor log2 n en bijgevolg is 2R dus een schatting voor de kardinaliteit n van de multiset. Deze schatting is onafhankelijk van de volgorde en structuur van de multiset M. Met dank aan de research die hierover is uitgevoerd [26], kunnen we zelfs zeggen dat R in exact dezelfde manier gedistribueerd is als 1 plus het maximum van n onafhankelijke geometrische variabelen van parameter 1/2. R schat log2 n met een additieve bias van 1,33 en een standaardafwijking van 1,87. Vergewis je er wel van dat de verwachting van 2R oneindig is, dus we kunnen dit echter niet gebruiken om n te schatten. Om dit probleem op te lossen, gebruiken we stochastic averaging, wat eerder al werd aangehaald: we gebruiken m emmers, ook substreams genoemd, waarbij m = 2p , met p ∈ Z>0 . We vullen elk van deze emmers op met waarden uit M en berekenen een schatting van de kardinaliteit voor elk van deze emmers. Deze resultaten worden daarna samengevoegd om een schatting van de totale kardinaliteit te bekomen. We gebruiken de eerste p bits van gehashte waarde h(v) met v ∈ M als de binaire index van de emmer en de rest van de bits worden gebruikt om de kardinaliteit te kunnen schatten. We berekenen R voor elke emmer, maar we negeren de eerste p bits die we gebruiken als index. We stellen M [j], de waarde van de emmer met P nummer j, gelijk aan de parameter R. Het aritmetisch gemiddelde (1/m) m j=1 M [j] geeft nu wel een legitieme schatting voor log2 (n/m) mits een additieve bias. We schrijven het volledige LogLog algoritme uit in Algoritme 13. In bovenstaande pseudo-code zien we echter dat we een iets gecompliceerdere schatter teruggeven dan slechts het aritmetisch gemiddelde: E := αm m2(1/m)
Pm
j=1
M [j]
.
We moeten nog vermenigvuldigen met constante αm . In de LogLog paper [7] wordt een gedetailleerde analyse besproken waarom geldt dat αm := −m R∞ Γ(−1/m)((1 − 21/m )/ log 2) , waarbij Γ(s) := (1/s) 0 e−t ts . We laten deze analyse echter achterwege, maar kan teruggevonden worden in de originele paper. De reden waarom we de constante gebruiken in het LogLog algoritme is omdat dit de systematische bias van het aritmetisch gemiddelde in de asymptotische limiet teniet doet. 68
Algoritme 13 LogLog(M, p) 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
Laat h : D → [0, 1] ≡ {0, 1}∞ data hashen van domein D naar het binaire domein Laat ρ(s), voor elke s ∈ {0, 1}∞ de positie zijn van de meest linkse 1-bit Initialiseer m als 2p met p ∈ Z>0 Initialiseer registers M [1], . . . , M [m] op 0 for elke v ∈ M do x := h(v) j := 1 + hx1 . . . xp i2 . binaire adres bepaald door eerste p bits van x w := xp+1 xp+2 . . . M [j] := max(M [j], ρ(w)) end for 1 Pm return E := αm m2 m j=1 M [j]
We √ stellen nog vast dat αm ∼ α∞ − (2π 2 + log2 2)/(48m), met α∞ = e1−γ 2/2 = 0.39701. In praktische implementaties kunnen we αm met α∞ verwisselen zonder merkwaardige bias te veroorzaken voor waarden van m ≥ 64. De schatter E √ is asymptotisch zuiver voor n → ∞ en de standaardfout benadert 1, 30/ m. Indien we bijvoorbeeld een standaardfout van ongeveer 2% willen, moeten we m gelijkstellen aan (1, 30/0, 0229)2 ≈ 2048 en dus hebben we een precisie p die gelijk is aan 11: 211 = 2048. Merk op dat we in bovenstaande beschrijving opnieuw een zogenaamde “ideale” multiset M met kardinaliteit n (het aantal unieke elementen) gebruiken. Om dit te verwezenlijken gebruiken we de hash-functie h. We hebben dus geen informatie over de data in de multiset en we kunnen geen statistische assumpties maken. Het LogLog algoritme maakt gebruik van O(log2 log2 n) geheugen indien we tellen tot n. In de pseudo-code gaan we ervan uit dat we m integerregisters kunnen gebruiken, waarbij m ongelimiteerd is. Dit is praktisch natuurlijk niet mogelijk. We maken daarom gebruik van een `gerestricteerd algoritme, zodat elk van de M [j] registers ` bits gebruikt. We kunnen als gevolg een integer opslaan tussen 0 en 2` − 1. We bekijken dit nu mathematisch met behulp van volgende eigenschap: Log-log eigenschap. We laten ω(n) een functie zijn die zeer traag naar oneindig gaat en functie `(n) = log2 log2 (n/m)+ω(n). Het `(n)-gerestricteerd algoritme en het LogLog algoritme bieden nu dezelfde output met kans neigend naar 1 zoals n neigt naar oneindig. 69
De totale geheugenruimte dat het algoritme nodig heeft om te kunnen tellen tot n is m log2 log2 (n/m)(1 + o(1)) aangezien we m keer “kleine bytes” van grootte `(n) opslaan. De hash-functie die we al hebben beschreven, moet dus de originele waarden hashen op exact 2`(n) + log2 m bits. Ga er vanuit dat we een accuraatheid van ongeveer 4% verwachten, dus hebben we een waarde van m = 1024 = 210 . We willen kardinaliteiten kunnen tellen tot 227 . Elke emmer wordt ongeveer n/m = 131.072 = 217 keer bezocht. We krijgen log2 log2 217 = 4, 09. Stel ω(n) = 0, 91, zodat elk register ` = 5 bits bedraagt, waardoor we waarden kleiner dan 32 kunnen opslaan. We kunnen nu met behulp van het LogLog algoritme kardinaliteiten schatten van de orde 108 met een standaardfout van ongeveer 0, 04 mits het gebruik van tabel die 1024 · 5 = 5120 bits = 0, 64 kilobytes bedraagt. Het LogLog algoritme kunnen we echter nog optimaliseren. Deze optimalisatie wordt voorgesteld in volgende paragraaf. We zullen de accuraatheid verbeteren zonder extra kost en we maken gebruik van kleinere registerwaarden waardoor we het geheugenruimtegebruik kunnen verbeteren en dus het effect van lengterestrictie zoals hierboven beschreven teniet doen.
5.2.2
Het SuperLogLog algoritme
LogLog is een goed algoritme om de kardinaliteit van een stream te kunnen berekenen, maar indien we dit algoritme praktisch testen, zijn er nog enkele regels die we kunnen toepassen om ervoor te zorgen dat we een effici¨enter algoritme krijgen. We zullen zowel een truncatie- als een restrictieregel defini¨eren. Indien een bucket v elementen ontvangt, zal de variabele M het maximum van de v stochastische variabelen bedragen die onafhankelijk en geometrisch verdeeld zijn volgens P[M ≤ k] = 1/(2k−1 ). We weten dat het maximum van v geometrische stochastische variabelen een verwachte waarde heeft van ongeveer log2 n. De staarten van deze verdeling zijn zacht, maar aangezien de schatter die teruggegeven wordt door het algoritme een gemiddelde van de emmerregisters als exponent bevat, is het mogelijk dat dit de schatter negatief be¨ınvloed. Dit hangt natuurlijk af van de data die we als input krijgen. Om dit probleem echter te kunnen omzeilen, maken we gebruik van truncatie om de uitschieters te vermijden. De truncatieregel gaat dus als volgt: bij het ophalen van de registerwaarden om de schatter te produceren, houden we enkel de m0 := bθ0 mc kleinste waarden en negeren we de rest, waarbij θ0 een re¨eel getal is tussen 0 en 1. Empirische testen wijzen uit dat een waarde van 0,7 bijna optimale resultaten produceert, met andere woorden: we snijden de top 30% 70
van de registers weg. Het gemiddelde van deze registers wordt berekend zoals voorheen en dus geeft het algoritme het volgende resultaat terug: 1 P∗m0 M [j] , waarbij α ˜ m een aangepaste constante voorstelt om bias α ˜ m m0 2 m0 j=1 te vermijden. Indien we het algoritme met truncatieregel empirisch testen, zien √ we dat de accuraatheid verhoogt, aangezien de standaardfout 1, 05/ m bedraagt. We gaan ervan uit dat θ0 = 0, 7. Verdere empirische studies tonen ons ook dat registerwaarden begrensd kunnen worden op dlog2 (n/m)e + δ zonder waarneembaar effect tot δ = 3. Hieruit volgt de restrictieregel: we gebruiken registerwaarden die in het interval [0, . . . , B] liggen, waarbij dlog2 (Nmax /m) + 3e ≤ B. Voor het voorbeeld uit vorige paragraaf zou het volstaan een B-waarde te kiezen van 20 voor n = 227 en m = 1024. Indien we de truncatieregel en de restrictieregel toepassen op het LogLog algoritme, krijgen we het SuperLogLog algoritme,√ wat een hogere accuraatheid heeft. De standaardfout bedraagt nu 1, 05/ m indien we m “kleine bytes” gebruiken. Een kleine byte is dlog2 dlog2 (Nmax /m) + 3ee bits. Algoritme Flajolet-Martin LogLog Super-LogLog
Standaardfout (σ) √ 0, 75/ m √ 1, 30/ m √ 1, 05/ m
Kost m woorden (≤ 32 bits) m “kleine” bytes (5 bits) m “kleine” bytes (5 bits)
n = 108 , σ = 0.02 ± 6,0 kbytes 2,64 kbytes 1,72 kbytes
In bovenstaande tabel zien we een vergelijking tussen de verschillende distinct count algoritmen tot nu toe voor kardinaliteiten van de orde ≤ 108 en een accuraatheid van 2%. De “kleine bytes” die in de tabel staan beschreven zijn typisch 5 bits, aangezien log2 log2 (Nmax ) ≈ 5 bits nodig hebben om het maximum aantal voorloopnullen van de gehashte waarden van de dataset met kardinaliteit Nmax van de orde 108 voor te kunnen stellen. In de praktijk gebruiken we daarom vaak een 32-bit hash-functie, we kunnen dus niet meer dan 232 unieke elementen tellen. We slaan altijd minder dan 32 voorloopnullen op, wat in log2 32 = 5 bits past. √ We werken de berekening uit voor SuperLogLog: we weten dat 1, 05/ m = 0, 02, dus m = 2756, 25, waardoor we berekenen dat we 2756, 25 · 5 bits ≈ 1, 72 kilobytes. We zien duidelijk dat voor een standaardfout van 0, 02 en een kardinaliteit van de orde 108 , we het minste geheugen gebruiken indien we gebruik maken van het Super-LogLog algoritme. Zoals eerder al aangehaald kunnen we het algoritme ook makkelijk parallelliseren. Het volstaat om de data in stukken op te delen en dan met dezelfde hash-functie de data te verwerken. Daarna kunnen we simpelweg de verscheidene tabellen van registers samenvoegen. We hebben dus duidelijk een optimale speed-up en de hoeveelheid interprocess communicatie blijft gelimiteerd tot enkele kilobytes. 71
5.3
HyperLogLog
Enkele jaren na de komst van het LogLog (en Super-LogLog) algoritme verscheen er een paper over een nog beter algoritme: het HyperLogLog algoritme. We baseren deze paragraaf dan ook voornamelijk op de originele paper [8] en in mindere mate ook op artikels van de Neustar Research website [29], ook dit algoritme werd mede-ontworpen door Flajolet. Het doel is hetzelfde: geef een schatting voor de kardinaliteit van een multiset dat meestal een zeer grote stream van elementen is. HyperLogLog is gebaseerd op dezelfde observabele als LogLog, namelijk de maximumwaarde van ρ wordt bijgehouden, waarbij ρ(x) de positie is van de eerste 1-bit in een binaire string x indien we beginnen tellen vanaf de meest linkse bit. Daarna passen we stochastic averaging toe, zoals we ook bij het LogLog algoritme deden. Het algoritme verschilt echter van LogLog door zijn evaluatiefunctie. We merkten eerder al op dat we door het gebruik van aritmetische gemiddelden om een schatting te maken van de kardinaliteit problemen kunnen hebben met uitschieters die een negatieve invloed kunnen hebben op ons resultaat. Daarom introduceerden Flajolet en Durand het SuperLogLog algoritme wat probeerde deze problemen te omzeilen met een quick-fix methode: de truncatie- en restrictieregel. Deze versie van het LogLog algoritme werd ook niet in detail geanalyseerd in de paper. Daarom zorgden Flajolet en zijn medewerkers in het HyperLogLog algoritme voor een grondigere oplossing: we baseren ons op harmonische gemiddelden, in tegenstelling tot aritmetische gemiddelden. Het idee hiervoor ontstond omwille van het werk van Chassaing en G´erin [4]. Harmonische gemiddelden gaan beter om met eventuele uitschieters. We maken opnieuw gebruik van willekeurigheid die verzekerd wordt door het gebruik van een hash-functie h : D → {0, 1}∞ . We gaan er opnieuw vanuit dat deze functie waarden genereert die dichtbij een uniform model van willekeurigheid liggen: we verwachten dat de bits van de gehashte waarden onafhankelijk zijn van elkaar en elk voorkomen met kans 1/2. √ De standaardfout van het HyperLogLog algoritme ligt dichtbij 1, 04/ m. Het algoritme moet ook een collectie van registers bijhouden, zoals bij het LogLog algoritme ook het geval was. Elk van deze is maximum log2 log2 Nmax + O(1) bits als de kardinaliteit die geschat moet worden ≤ Nmax . Voor eenzelfde accuraatheid heeft HyperLogLog slechts 64% van het geheugen nodig in vergelijking met LogLog. We zien dit in als volgt: stel dat we een accuraatheid van 2% willen hebben, met andere woorden een standaardfout van 0, 02. We weten dat de standaardfout voor LogLog 72
√ gelijk is aan 1, 30/ m, indien we m hieruit afleiden krijgen we m = 4225. √ We weten dat bij HyperLogLog de standaardfout gelijk is aan 1, 04/ m, indien we nu m berekenen krijgen we als resultaat 2652, 25. Aangezien het geheugengebruik afhangt van m, ligt dit bij het HyperLogLog algoritme veel lager ondanks dat we dezelfde accuraatheid krijgen dan bij het LogLog algoritme. Stel m = 2048, dan kunnen we hashen op 32 bits en “kleine bytes” van 5 bits elk gebruiken. Indien de kardinaliteit ≤ Nmax van de orde 109 is,√ kunnen we dus een schatting maken met een accuraatheid van 1, 04/ 2048 ≈ 2% met slechts 2048 · (log2 log2 109 ) ≈ 1, 3 kilobytes geheugenruimte.
5.3.1
Het HyperLogLog algoritme
De eerste fase van het HyperLogLog algoritme is gelijkaardig aan het LogLog algoritme. We krijgen zowel een multiset M met elementen uit universum U = {0, 1}∞ en een precisie p mee als parameters, waarbij p ∈ Z>0 . We trachten een schatting te maken van de kardinaliteit, het aantal unieke elementen, in M. Opnieuw maken we gebruik van een passende hashfunctie h en we vertrouwen op een specifieke bitpatroon observabele in conjunctie met stochastic averaging. We gebruiken ρ(s), met s ∈ {0, 1}∞ , om de positie van de meest linkse bit van s aan te geven. De stream M wordt opgesplitst in m = 2p emmers of substreams gebaseerd op de eerste p bits van de gehashte waarden. We bekijken elke emmer onafhankelijk van elkaar. Voor N ≡ Mj gebruiken we de volgende observabele: R(N ) := max ρ(x), v∈N
waarbij we veronderstellen dat R(∅) = −∞. Het algoritme gaat voor elke emmer met index j = 1, ..., m deze waarde bijhouden. We berekenen nu volgende indicator :
Z :=
m X
!−1 2−M [j]
.
j=1
We geven nu een genormaliseerde versie van het harmonisch gemiddelde van 2M [j] in de vorm: 73
αm m2 P E := m −M [j] met αm := j=1 2
Z m 0
∞
m −1 2+u log2 du . 1+u
Een analyse in verband met constante αm kan teruggevonden worden in de HyperLogLog paper [8]. We schrijven het volledige HyperLogLog algoritme uit in Algoritme 14. Algoritme 14 HyperLogLog(M, p)
11:
Laat h : D → [0, 1] ≡ {0, 1}∞ data hashen van domein D naar het binaire domein Laat ρ(s), voor elke s ∈ {0, 1}∞ de positie zijn van de meest linkse 1-bit Initialiseer m als 2p met p ∈ Z>0 Initialiseer registers M [1], . . . , M [m] op −∞ for elke v ∈ M do x := h(v) j := 1 + hx1 . . . xp i2 . binaire adres bepaald door eerste p bits van x w := xp+1 xp+2 . . . M [j] := max(M [j], ρ(w)) end for −1 P m −M [j] . de “indicator” functie 2 Z := j=1
12:
return E := αm m2 Z
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
De intu¨ıtie van het algoritme gaat als volgt: stel dat n de onbekende kardinaliteit voorstelt van M. Elke substream zal ongeveer n/m elementen bevatten. Dan is de R-parameter een ruwe schatting voor log2 (n/m). De harmonische verwachting mZ van de hoeveelheden 2R is dan van dezelfde grootteorde als n/m. Dus, m2 Z moet van dezelfde grootteorde zijn als n. De constante αm wordt uiteindelijk gebruikt om de systematische multiplicatieve bias die door m2 Z wordt ge¨ıntroduceerd teniet doen. We maken ook opnieuw gebruik van “ideale” multisets met kardinaliteit n: een sequentie wordt verkregen door arbitraire replicaties en permutaties toegepast op n uniforme identiek gedistribueerde stochastische variabelen over het re¨eel interval [0, 1]. In Algoritme 15 is een praktische versie van het HyperLogLog algoritme uitgeschreven. We introduceren hier drie modificaties: initialisatie van registers, small range correctie en large range correctie. We initialiseren de registers op 0 in plaats van −∞ om te vermijden dat we 0 als resultaat krijgen voor n << m log m waar n de kardinaliteit 74
Algoritme 15 HyperLogLog(M, p) Laat h : D → [0, 1] ≡ {0, 1}32 data hashen van domein D naar binaire 32-bit woorden 2: Laat ρ(s), voor elke s ∈ {0, 1}32 de positie zijn van de meest linkse 1-bit 1:
Fase 0: Initialization 3: Initialiseer m als 2p met p ∈ [4..16] 4: Initialiseer registers M [1], . . . , M [m] op 0 5: Definieer α16 = 0.673, α32 = 0.697, α64 = 0.709, αm = 0.7213/(1 + 1.079/m) voor m ≥ 128
6: 7: 8: 9: 10: 11:
Fase 1: Aggregatie for elke v ∈ M do x := h(v) j := hx31 . . . x32−p i2 . binaire adres bepaald door eerste p bits van x w := x31−p x0 . . . M [j] := max(M [j], ρ(w)) end for
13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25:
Fase 2: Resultaatberekening −1 P m −M [j] 2 . de “raw” HyperLogLog schatter E := αm m j=1 2 if E ≤ 5m/2 then . small range correctie Laat V het aantal registers = 0 zijn if V 6= 0 then E ∗ := LinearCounting(m, V ) else E ∗ := E end if else if E ≤ 232 /30 then . intermediate range - geen correctie ∗ E := E else . large range correctie E ∗ := −232 log(1 − E/232 ) end if return E ∗
26: 27: 28:
function LinearCounting(m,V) return m log(m/V ) end function
12:
75
van de multiset voorstelt. De schatter heeft nog steeds een asymptotisch unbiased karakter, maar we krijgen nu voor zeer kleine kardinaliteiten betere schattingen. In Algoritme 15 passen we dit toe op regel 4. Uitgebreide simulaties van het HyperLogLog algoritme demonstreren dat er voor kardinaliteiten n < 5m/2 niet-lineaire vervormingen kunnen voorkomen. Indien we registers initialiseren op 0 krijgen we als schatting αm m = 0.7m terug voor n = 0. Dit moet gecorrigeerd worden. Hiervoor gebruiken we een zogenaamde small range correctie. We bekijken een fenomeen dat al uitgebuit werd in het Hit Counting algoritme [40] ge¨ıntroduceerd door Whang, Vander-Zanden en Taylor in verband met probabilistische eigenschappen van willekeurige allocaties. Stel dat we n ballen in m willekeurige emmers gooien, dan is het aantal lege emmers ongeveer me−µ met µ := n/m. Indien we vaststellen dat V van de m emmers leeg zijn, kunnen we verwachten dat µ dichtbij log(m/V ) zal liggen. Dus n moet dichtbij m log(m/V ) liggen. In Algoritme 15 passen we dit toe op regels 13-19. Voor kardinaliteiten in de reeks [1..Nmax ] met Nmax van de orde 109 , moeten we hashen over minstens L = 32 bits gebruiken (232 = 4 · 109 ). Als de kardinaliteit echter 2L begint te benaderen, komen hash-botsingen steeds vaker voor. We kunnen dit modelleren door hetzelfde bal/emmer-model als in de vorige alinea, maar in plaats van m gebruiken we 2L . We kunnen dus stellen dat de waarde van E het aantal verschillende hash-waarden schat, wat met grote waarschijnlijkheid ongeveer gelijk is aan 2L (1 − e−Λ ) met Λ = n/2L . De inversie van die relatie geeft ons de benaderende vergelijking n = −2L log(1 − E/2L ). We noemen dit large range correctie. In Algoritme 15 passen we dit toe op regels 22-24. √ We kunnen stellen voor het algoritme dat indien σ ≈ 1, 04/ m de standaardfout is, dat de schattingen van het HyperLogLog algoritme binnen σ, 2σ, 3σ van de exacte kardinaliteit liggen in respectievelijk 65%, 95%, 99% van de gevallen. De executietijd van het algoritme wordt gedomineerd door de berekening van de hash-functie. Dit betekent dat het maar drie of vier keer trager is dan een scan van de data. Net zoals het LogLog algoritme kunnen we het HyperLogLog algoritme perfect parallelliseren indien gewenst. We kunnen ook makkelijk een gedistribueerde versie van het algoritme implementeren. Tenslotte hernemen we de tabel die we eerder al aanhaalden in de vorige paragraaf en voegen HyperLogLog toe. Per algoritme bekijken we de geheugenkost (en eenheden), de relatieve accuraatheid (m.a.w. de standaardfout) en het geheugenverbruik gegeven een accuraatheid van 2% en een maximale kardinaliteit van de orde 108 :
76
Algoritme Flajolet-Martin LogLog Super-LogLog HyperLogLog
Standaardfout (σ) √ 0, 75/ m √ 1, 30/ m √ 1, 05/ m √ 1, 04/ m
Kost m woorden (≤ 32 bits) m “kleine” bytes (5 bits) m “kleine” bytes (5 bits) m “kleine” bytes (5 bits)
n = 108 , σ = 0.02 ± 6,0 kbytes 2,64 kbytes 1,72 kbytes 1,69 kbytes
In bovenstaande tabel zien we dat HyperLogLog inderdaad ongeveer 64% van het geheugen verbruikt in vergelijking met LogLog zoals we al aanhaalden. Ook ligt het geheugenverbruik nog lager ten opzichte van de praktische Super-LogLog variant. Het voordeel van HyperLogLog ten opzichte van Super-LogLog is dat we geen gebruik maken van quick-fix oplossingen zoals eerder aangehaald. We concluderen dat HyperLogLog zo goed als optimaal is, maar het is ook praktisch, veelzijdig en (na uitgebreid testen) voldoet aan wat de analyse heeft voorspeld.
5.3.2
Het HyperLogLog++ algoritme
We kunnen het praktische algoritme (beschreven in Algoritme 15) verbeteren in verband met geheugengebruik en accuraatheid. Deze nieuwe versie van HyperLogLog zullen we HyperLogLog++ noemen [17]. Het is ontworpen door een groep onderzoekers van Google en wordt ook gebruikt voor een systeem van Google. Het werd empirisch ge¨evalueerd en vergeleken met het HyperLogLog algoritme en bleek inderdaad betere resultaten te geven. Net zoals HyperLogLog kunnen we dit parallelliseren en de kardinaliteit berekenen in een enkele pass. We bespreken drie grote veranderen in volgende paragrafen.
5.3.2.1
64-bit hash-functie
Zoals we al weten kunnen we met een hash-functie van L bits kardinaliteiten schatten van maximum 2L unieke waarden, maar indien de kardinaliteit 2L benadert, dan worden hash-collisies veel waarschijnlijker en wordt het zo goed als onmogelijk om een accurate schatting te krijgen. We weten dat het HyperLogLog algoritme niet lineair met L meegroeit wat betreft geheugenruimte. Deze hangt af van het aantal registers en de maximumwaarde van ρ(w). Voor een hash-functie van L bits en een precisie p ∈ [4..16] is deze maximumwaarde L − p + 1. De geheugenruimte die hiervoor nodig is, is duidelijk dlog2 (L − p + 1)e · 2p bits. Het originele HyperLogLog-algoritme gebruikt een 32-bit hash-functie, we zagen dat p minstens 4 was in de praktische pseudo-code, dus hebben we hiervoor 77
maximum dlog2 (32 − 4 + 1)e = 5 bits nodig per register in array M . Om echter kardinaliteiten veel groter dan 232 te kunnen tellen, gebruiken we een 64-bit hash-functie. De grootte van een enkel register verhoogt maar met 1 bit aangezien dlog2 (64 − 4 + 1)e = 6. Enkel als de kardinaliteit 264 benadert, zullen we hash-botsingen krijgen. Aangezien 264 enorm groot is, is het zeer onwaarschijnlijk dat de kardinaliteit in de meeste praktische gevallen zo groot zal worden. We kunnen dus de large range correctie die we in vorige paragraaf beschreven weglaten.
5.3.2.2
Kleine kardinaliteiten schatten
In de praktische versie van het HyperLogLog algoritme gebruiken we een small range correctie indien onze “raw” schatting kleiner is dan 5m/2. We passen LinearCounting toe. Met behulp van simulaties zien we echter in dat de overschatting van de kardinaliteit van kleine sets vooral door bias komt. We hebben eerder al opgemerkt dat voor n = 0 de bias 0, 7m bedraagt. De statistische variabiliteit van de schatter is echter klein, dus we proberen deze bias te corrigeren om betere schattingen te verkrijgen. De Google onderzoekers die het HyperLogLog++ algoritme hebben bedacht [17], zijn erin geslaagd de bias empirisch te corrigeren. Eerst en vooral maten ze het resultaat van het HyperLogLog algoritme dat gebruik maakt van een 64-bit hash-functie voor een reeks verschillende kardinaliteiten zowel met als zonder de toepassing van LinearCounting. Voor ´e´en bepaalde hash-functie werden er voor kardinaliteit n en precisie p 5000 verschillende willekeurig gegenereerde datasets met kardinaliteit n gebruikt. Met behulp van de hash-functie zorgden we voor willekeurigheid. Dit werd herhaald voor elke mogelijke precisie. Om nu de bias te bepalen, berekenen we het gemiddelde van alle raw schattingen voor een bepaalde kardinaliteit min de exacte kardinaliteit. Het HyperLogLog algoritme weet echter niet wat de correcte kardinaliteit is in niet-experimentele situaties. We kunnen echter voor elke kardinaliteit de raw schatting en de bias opslaan. Het algoritme kan nu de raw schatting gebruiken om de bias te corrigeren in plaats van de exacte kardinaliteit. Om dit praktisch werkzaam te maken, werden er 200 kardinaliteiten gekozen als interpolatiepunten, waarvoor de gemiddelde raw schatting en bias werden opgeslagen. Met behulp van k-nearest neighbor interpolatie voor een gegeven raw schatter kunnen we nu de bias bepalen. We kunnen bijvoorbeeld k = 6 kiezen. De optimale waarde voor k kan experimenteel bepaald worden, maar deze lijkt weinig invloed te hebben op het uitein78
Figuur 5.1: De mediaan van de fout van de raw schatting, de bias-gecorrigeerde schatting en LinearCounting voor p = 14, gebaseerd op 5000 datapunten per kardinaliteit. Ook de 5% en 95% kwantielen van de error zijn in de figuur te zien. [17]
delijke resultaat van het algoritme. Maar werkt deze methode beter dan LinearCounting? Hiervoor werd een tweede experiment uitgevoerd. Er werd gebruik gemaakt van drie versies van het algoritme: gebruik de bias-gecorrigeerde raw schatter, gebruik de raw schatter, en gebruik LinearCounting. Deze drie algoritmes werden uitgevoerd voor verschillende kardinaliteiten en daarna werd de foutdistributie vergeleken. De resultaten van dit experiment zijn te zien in Figuur 5.1. Tot kardinaliteiten van 61000 had de bias-gecorrigeerde raw schatter een kleinere error vergeleken met degene zonder biascorrectie. Voor grotere kardinaliteiten convergeert de fout van de twee schatters naar hetzelfde niveau totdat de twee foutdistributies samenvallen voor kardinaliteiten groter dan 5m. Voor kleine kardinaliteiten lijkt LinearCounting nog steeds een betere methode te zijn dan de bias-gecorrigeerde raw schatter. We zien dat bijvoorbeeld voor p = 14 de foutcurves elkaar snijden bij een kardinaliteit van 11500 in Figuur 5.1. We kunnen dezelfde testen ook voor andere precisie-waarden uitvoeren. Links van deze intersectie kunnen we best Li79
nearCounting gebruiken, rechts van deze gebruiken we de biascorrectie, maar zoals voorheen weet het algoritme natuurlijk niet hoeveel de kardinaliteit bedraagt. Aangezien we weten dat de drempelwaarde in een bereik ligt waar LinearCounting een kleine fout heeft, gebruiken we de schatter en vergelijken we deze met de drempelwaarde om te kunnen bepalen of we LinearCounting moeten toepassen of niet. Natuurlijk is het alleen nuttig om de bias te corrigeren indien we daar de fout significant mee omlaag krijgen. Uit testen is gebleken dat voor n > 5m de correctie niet langer een significant verbetert resultaat zal opleveren.
5.3.2.3
Schaarse representatie
Tijdens de uitvoering van het HyperLogLog algoritme met bias-correctie hebben we een constante geheugenruimte van 6m bits nodig, onafhankelijk van n. Indien n << m, dan zullen de meeste registers nooit gebruikt worden. We kunnen gebruik maken van een schaarse representatie waarin we (idx, ρ(w))-paren opslaan. Indien we op een punt komen dat we meer geheugen nodig hebben dan in de dichte representatie (dus 6m bits), dan kunnen we de schaarse lijst converteren naar een dichte representatie. Paren met dezelfde index kunnen we samenvoegen door enkel degene met de grootste ρ(w) waarde op te slaan. In de implementatie van het HyperLogLog++ algoritme zullen we de (idx, ρ(w))-paren als een integer representeren door bitpatronen met elkaar te concateneren. We houden nu een gesorteerde lijst integers bij van alle paren. Om echter snelle toevoegingen te kunnen maken, zullen we ook een tijdelijke lijst bijhouden die wordt samengevoegd met de gesorteerde lijst indien deze te groot wordt (bijvoorbeeld groter dan 25% van de maximumgrootte van de schaarse representatie). De samenvoeging kan gebeuren in een enkele lineaire pass over de gesorteerde set en de tijdelijke set. Tijdens het samenvoegen moeten we er wel rekening mee houden dat we voor de paren met dezelfde index degene bijhouden met de grootste ρ(w) waarde. Om uiteindelijk een schatting te berekenen met behulp van deze gesorteerde lijst, moeten we weten welke indices geen nul-waarde hebben. We gaan ervan uit dat elke index die niet in de lijst zit, de waarde 0 heeft, met andere woorden we kunnen simpelweg de lengte van de gesorteerde lijst gebruiken om LinearCounting uit te voeren. Deze schaarse representatie zorgt voor een kleine overhead aangezien we gebruik maken van een tijdelijke lijst, maar er wordt wel veel minder geheugenruimte gebruikt voor kleine kardinaliteiten. 80
5.3.2.3.1
Hogere precisie voor de schaarse representatie
In de schaarse representatie hebben we voor elk item p + 6 bits nodig om zowel de index (p bits) als de waarde van het register op te slaan. We laten ook toe een tweede precisie-argument te gebruiken p0 > p dat toelaat een hogere accuraatheid te gebruiken in gevallen waar enkel de schaarse representatie gebruikt wordt. Indien de tabel in de schaarse representatie groter wordt dan 6m bits, switchen we naar precisie p en de dichte representatie. De conversie van paar (idx0 , ρ(w0 )) dat bepaald wordt door precisie p0 naar paar (idx, ρ(w)) dat bepaald wordt door precisie p gaat als volgt: 1. We weten dat idx0 bestaat uit de p0 meest significante bits van h(v). Aangezien p < p0 kunnen we de idx bepalen door de eerste p bits van idx0 te nemen. 2. Voor ρ(w) moeten we het aantal voorloopnullen van de bits van h(v) na de index bits weten: de bits 63 − p tot 0. De bits 63 − p tot 63 − p0 weten we door naar de index te kijken. Indien minstens ´e´en van deze bits 1 is, dan kunnen we ρ(w) berekenen door enkel naar deze bits te kijken. Indien alle bits echter nul zijn, gebruiken we ρ(w0 ): ρ(w) = ρ(w0 ) + (p0 − p). Een goede waarde voor p0 kiezen is een trade-off. Indien p0 hoger is, betekent dit een kleinere fout in gevallen waar enkel de schaarse representatie gebruikt wordt. Maar als p0 groter wordt, moeten we ook meer geheugen gebruiken wat betekent dat de drempel die gebruikt wordt om te switchen naar de dichte representatie sneller bereikt wordt. We kunnen p0 verhogen tot 64. We slaan dan de volledige hash-code op. 5.3.2.3.2
Schaarse representatie comprimeren
Indien gewenst kunnen we de schaarse representatie nog comprimeren met behulp van variable length encoding en difference encoding. We doen dit tijdens het samenvoegen van de tijdelijke en de gesorteerde lijst. Indien we overschakelen naar de dichte representatie kunnen we dit makkelijk decomprimeren. We behandelen dit echter niet in detail. 5.3.2.3.3
Hash-waarde encoderen
We kunnen de geheugenruimte-effici¨entie nog verbeteren. Als de schaarse representatie gebruikt wordt voor de complete aggregatiefase, dan gebruiken we tijdens het berekenen van het resultaat altijd LinearCounting. De 81
drempel waar we switchen tussen LinearCounting en de bias-gecorrigeerde raw schatter is veel hoger dan het maximum aantal hash-waarden die we kunnen opslaan in de schaarse representatie. Aangezien LinearCounting enkel het aantal verschillende indices en m nodig heeft om een schatting te kunnen maken, hebben we geen nood aan ρ(w0 ). Deze waarde wordt alleen gebruikt als we switchen van schaarse naar dichte representatie en zelfs dan hebben we dit niet altijd nodig. Indien we een goede hash-functie gebruiken met uniforme hash-waarden, dan is 0 de kans dat we de waarde van ρ(w0 ) opslaan slechts 2p−p . We kunnen een indicatie-bit gebruiken om dit te verwezenlijken. We stellen dat indien de bits hx63−p , ..., x64−p0 i allemaal gelijk zijn aan 0, we het volgende opslaan (waarbij k een concatenatie voorstelt):
hx63 , ...x64−p0 i k ρ(w0 ) k h1i.
In andere gevallen slaan we het volgende op:
hx63 , ...x64−p0 i k h0i.
De minst significante bit laat ons nu toe om deze integer makkelijk te encoderen. We geven de pseudo-code voor het complete HyperLogLog++ algoritme in 16. De drie verbeteringen die we hebben besproken zijn onafhankelijk van elkaar. Indien we bijvoorbeeld weten dat we bijna nooit kleine kardinaliteiten zullen tellen en dus zelden nood zouden hebben aan de schaarse representatie, kan het nadelig zijn deze telkens te gebruiken aangezien er een kleine overhead is waar we moeten overschakelen van schaarse naar dichte representatie. In vergelijking met het HyperLogLog algoritme scoort het HyperLogLog++ algoritme vaak beter op gebied van accuraatheid dan het HyperLogLog algoritme tijdens empirische evaluatie, dit is te zien in Figuur 5.2. Ook gebruikt het veel minder geheugen voor kleine kardinaliteiten indien we gebruik maken van de schaarse representatie. 82
Algoritme 16 HyperLogLog++(M, p, p0 ) Laat h : D → [0, 1] ≡ {0, 1}32 data hashen van domein D naar binaire 32-bit woorden 2: Laat ρ(s), voor elke s ∈ {0, 1}32 de positie zijn van de meest linkse 1-bit 1:
3: 4: 5: 6: 7: 8: 9:
10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31:
Fase 0: Initialization 0 Initialiseer m0 als 2p met p0 ≤ 64 Initialiseer m als 2p met p ∈ [4..p0 ] Initialiseer registers M [1], . . . , M [m] op 0 Definieer α16 = 0.673, α32 = 0.697, α64 = 0.709, αm = 0.7213/(1 + 1.079/m) voor m ≥ 128 f ormat := sparse tmp set := ∅ sparse list := [] Fase 1: Aggregatie for elke v ∈ M do x := h(v) switch f ormat do case normal idx := hx63 . . . x64−p i2 . binaire adres bepaald door eerste p bits w := x63−p . . . x0 M [idx] := max(M [idx], ρ(w)) end case case sparse k := EncodeHash(x, p, p0 ) tmp set := tmp set ∪ {k} if tmp set is te groot then sparse list := Merge(sparse list,Sort(tmp set)) tmp set := ∅ if |sparse list| > m · 6 bits then f ormat := normal M := ToNormal(sparse list) end if end if end case end switch end for
83
36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53:
Fase 2: Resultaatberekening switch f ormat do case normal Pm −M [j] −1 E := αm m2 . de “raw” HyperLogLog schatter j=1 2 E 0 := (E ≤ 5m)?(E − EstimateBias(E, p)) : E Laat V het aantal registers = 0 zijn if V 6= 0 then H := LinearCounting(m, V ) else H := E 0 end if if H ≤ Treshold(p) then return H else return E 0 end if end case case sparse sparse list := Merge(sparse list, Sort(tmp set)) return LinearCounting(m0 , m0 − |sparse list|) end case end switch
54: 55: 56:
function LinearCounting(m,V) return m log(m/V ) end function
57: 58:
function Treshold(p) end function
59:
function EstimateBias(E,p)
33: 34: 35:
. Geeft empirisch bepaalde treshold terug
. Bereken bias (k-nearest neighbor
interpolatie) 60:
end function
84
62: 63: 64: 65: 66: 67: 68:
function EncodeHash(x,p,p’) . Encodeer hash-code x if hx63−p , . . . , x64−p0 i = 0 then return hx63 , . . . , x64−p0 i k hρ(hx63−p0 ,...,x0 i)i k h1i else return hx63 , . . . , x64−p0 i k h0i end if end function
69: 70: 71: 72: 73: 74: 75:
function GetIndex(k,p) if hk0 i = 1 then return hkp+6 , . . . , k7 i else return hkp , . . . , k1 i end if end function
76: 77: 78: 79: 80: 81: 82: 83:
function DecodeHash(k,p,p’) if hk0 i = 1 then r := hk6 , . . . , k1 i + (p0 − p) else r := ρ(hkp0 −p−1 , . . . , k1 i) end if return (GetIndex(k, p), r) end function
84: 85: 86: 87: 88: 89: 90: 91:
function ToNormal(sparse list,p,p’) M := NewArray(m) for all k ∈ DecodeSparse(sparse list) do (idx, r) := DecodeHash(k, p, p0 ) M [idx] := max{M [idx], r} end for return M end function
92: 93:
function Merge(a,b) end function
94:
function DecodeSparse(a)
. Voeg twee gesorteerde lijsten samen
. Decomprimeert een gesorteerde, schaarse
lijst 95:
end function
85
Figuur 5.2: Vergelijking van het originele HyperLogLog en het HyperLogLog++ algoritme. Er werden 5000 datapunten per kardinaliteit gebruikt. Ook de 5% en 95% kwantielen van de error zijn in de figuur te zien. [17]
86
5.4
Alternatieve manieren
LogLog en HyperLogLog zijn natuurlijk niet de enige algoritmen die ontworpen werden om kardinaliteiten te tellen. Er zijn verscheidene alternatieven. Er zijn er echter weinigen die zo goed presteren als de hierboven beschreven algoritmen. We halen in deze paragraaf twee alternatieve methodes aan, maar treden niet in detail. Een bekend alternatief is een Bloom filter [18]. Een Bloom filter werkt als volgt. We hebben een stream van n elementen uit een groot universum U. We beginnen met een bitarray van m elementen en een aantal hash functies hi (x) met 1 ≤ i ≤ k die waarden uit universum U mappen naar waarden in de reeks {1, . . . , m}. We vullen de bitarray met nullen. Voor elk item in de stream gaan we de hash-waarde berekenen voor alle k hashfuncties; we zetten telkens de hi (x)de in de bitarray op 1. Als alle hi (y) op 1 staan, kunnen we veronderstellen dat y in stream S zit. Het kan echter wel zijn dat het algoritme vals positieve antwoorden terugkrijgt. Het is echter niet mogelijk om een fout negatief antwoord te krijgen. Ondanks dat deze ontworpen is om set-lidmaatschap te kunnen testen, kan dit ook gemanipuleerd worden om heavy hitters op te vragen en zelfs de kardinaliteit te kunnen tellen, zoals beschreven door Papapetrou, Siberksi en Nejdl [25]. De schatting van de kardinaliteit vereist enkel het aantal positieve bits in de filter, het aantal hash-functies en de lengte van de Bloom filter. We kunnen nu de kardinaliteit schatten als volgt: 1 kn ˆ . S(n) = m × 1 − 1 − m Verdere details en berekeningen in verband met de kansen zijn terug te vinden in de paper [25]. Een tweede alternatief is een algoritme voorgesteld door Kane, Nelson en Woodruff [10] in 2010 als het optimale algoritme voor het schatten van de kardinaliteit van een set. Ze gaan er in de paper vanuit dat er een willekeurig orakel nodig is om bijvoorbeeld HyperLogLog uit te kunnen voeren, namelijk de hash-functie. Het algoritme dat zij bespreken gebruikt O(−2 + log2 n) plaats en maakt geen gebruik van orakels. Het algoritme werd echter niet ge¨ımplementeerd is ook nog niet in de praktijk toegepast. Het volledige algoritme is terug te vinden in de paper [10], maar zal omwille van de complexiteit ervan in deze tekst niet verder besproken worden.
87
88
Hoofdstuk 6 Implementatie en toepassing Voor Selligent is het belangrijk dat het tellen van de kardinaliteit van een stream in de praktijk kan toegepast worden, daarom werd er een implementatie van zowel het HyperLogLog als het HyperLogLog++ algoritme voorzien. Aangezien de pseudo-code voor beide algoritmen al beschreven werd in het vorige hoofdstuk, gaan we hier de focus leggen op enkele moeilijkheden die naar boven kwamen tijdens de implementatie van de algoritmen, en ook de resultaten die we verkregen bij het achteraf testen. De implementatie werd gemaakt in Java. Voor beide algoritmes werd er een klasse aangemaakt, respectievelijk HyperLogLog en HyperLogLogPlusPlus. Er is geen expliciete constructor voorzien en we maken gebruik van static functies in Java. Het is dus mogelijk het algoritme aan te roepen zonder dat we eerst een instantie van de klasse moeten aanmaken.
6.1
HyperLogLog implementatie
De implementatie van het HyperLogLog algoritme is gebaseerd op Algoritme 15. De pseudo-code is simpel en makkelijk te implementeren. Er waren geen grote problemen die aan bod kwamen tijdens de implementatie. We maken geen gebruik van speciale data-structuren en gebruiken simpelweg vooraf gedefinieerde types zoals int, long, int-arrays en longarrays. Als hash-functie gebruiken we 32-bit MurmurHash3 waarvoor we makkelijk de Guava library [13] van Google kunnen importeren. De details van de implementatie kunnen altijd bekeken worden in de source code. We bespreken hieronder enkele belangrijke punten. In de aggregatiefase van het algoritme maken we gebruik van bit-shifts om de juiste bits te kunnen selecteren. Voor de index te kunnen isoleren 89
uit gehashte waarde x, maken we gebruik van een unsigned right shift operatie >>>. We gebruiken een unsigned bit shift in tegenstelling tot een right shift >> aangezien Java geen ongetekende getallen ondersteunt en dus de eerste bit van een getal als tekenbit bekijkt. De rest van de bits in x moeten we gebruiken om het aantal voorloopnullen te tellen, dus hiervoor kunnen we gewoon een simpele left shift operatie uitvoeren <<. Het volledige stukje code staat hieronder uitgeschreven:
// f o r e v e r y e l e m e n t i n stream s f o r ( i n t i = 0 ; i < s . l e n g t h ; i ++) { x = getHashValue ( s [ i ] ) ; // g e t hashed value i d x = x >>> ( I n t e g e r . SIZE − p ) ; // f i r s t p bits of x w = ( x << p ) ; // l e a d i n g z e r o s o f r e s t o f bits mArray [ i d x ] = Math . max( mArray [ i d x ] , I n t e g e r . numberOfLeadingZeros (w) +1) ; // M[ i d x ] = max{M[ i d x ] , rho (w) } }
Empirisch bewijs toont aan dat large range correctie vaak de schatting kan verslechteren, dus deze correctie werd in de implementatie achterwege gelaten. [36] In Paragraaf 5.3 haalden we aan dat we slechts 5 bits nodig hebben om het aantal nullen in array M op te kunnen slaan voor kardinaliteiten van maximum 232 . Aangezien het kleinste primitieve type in Java, een byte, echter 8 bits beslaat, maken we gebruik van 8 bits in plaats van 5 bits per element. Een mogelijkheid om het aantal bits dat gebruikt wordt te verminderen, is bijvoorbeeld het gebruik van een BitSet-array in Java of het gebruik van een zelf-gedefinieerd datatype. Aangezien dit de implementatie wat ingewikkelder zou maken, werd er toch gekozen voor een byte-array. Indien geheugengebruik echter een zeer belangrijke factor is, kan het type van de array M natuurlijk aangepast worden zodat er minder dan 8 bits nodig zijn om dit op te slaan. De implementatie voorziet ook file I/O waardoor we de kardinaliteit van een stream in verschillende stukken kunnen berekenen. We schrijven namelijk de waarde van m en de elementen in de array M (mArray) weg naar een file zodat we deze later opnieuw kunnen inlezen om verder te tellen. 90
6.2
HyperLogLog++ implementatie
De implementatie van het HyperLogLog++ algoritme is gebaseerd op Algoritme 16. In tegenstelling tot de pseudo-code van HyperLogLog is dit complexer en minder voor de hand liggend. Er zijn zeer veel hulpfuncties die ge¨ımplementeerd moesten worden en ook veel meer bit-shifts, waar makkelijk fouten in kunnen voorkomen. We maken opnieuw enkel gebruik van simpele datastructuren en maken gebruik van 64-bit MurmurHash3 als hash-functie. De details van de implementatie kunnen altijd bekeken worden in de source code. We bespreken hieronder enkele belangrijke punten. Zoals eerder aangehaald in Paragraaf 5.3, hebben we maximaal 6 bits nodig om het aantal nullen op te slaan in array M om kardinaliteiten tot 264 te kunnen tellen, maar aangezien het kleinste primitieve type in Java een byte is, maken we net zoals bij de implementatie van HyperLogLog gebruik van 8 bits per element in de array. Zoals eerder aangehaald zou een BitSet-array of het defini¨eren van een eigen datatype hiervoor een oplossing kunnen bieden, dit werd echter niet ge¨ımplementeerd. Om de bias te corrigeren en de treshold te kunnen opzoeken, gebruiken we de tabellen die de groep onderzoekers van Google online ter beschikking hebben gesteld [16]. Voor de k-nearest neigbor interpolatie maken we gebruik van 6 interpolatiepunten die we opzoeken in deze tabellen om de bias te schatten. Als waarde voor p0 nemen we telkens 25. De reden hiervoor is dat dit een zeer hoge accuraatheid geeft voor de schaarse representatie. We kunnen nu ook een integer gebruiken om de ge¨encodeerde hash-waarden op te slaan aangezien we p0 bits nodig hebben voor de index, maximaal 6 bits voor het aantal voorloopnullen en 1 bit als indicatiebit. In totaal zijn dit 32 bits, wat net in een integer in Java past. Dit zorgt ervoor dat we de schaarse lijst langer kunnen gebruiken dan indien we een long hadden gekozen, wat 64 bits lang is en dubbel zoveel plaats inneemt. We maken ook geen gebruik van variable length of difference encoding om waarden in de schaarse representatie te comprimeren aangezien we slechts een integer nodig hebben om de ge¨encodeerde waarde op te kunnen slaan. We laten de tijdelijke 32-bit integer-array tmp set groeien totdat deze 25% van de capaciteit van de 32-bit integer-array sparse list bedraagt voor we deze twee lijsten samenvoegen indien we werken met de schaarse representatie. Dit betekent dus dat indien m = 1024, dan mag de schaarse lijst niet meer dan 8m = 6144 bits omvatten, dus niet meer dan 6144/32 = 192 elementen. De tijdelijke lijst kan maximaal 48 elementen bevatten. Merk 91
op dat we in de implementatie de ge¨encodeerde hash-waarden altijd in een integer zullen opslaan, we zagen echter in het vorige hoofdstuk dat we niet altijd de positie van de eerste 1-bit hoeven op te slaan, waardoor we 6 bits minder geheugen kunnen gebruiken indien we een effici¨enter datatype zouden hanteren. Net zoals voor de implementatie van het HyperLogLog algoritme, voorzien we de nodige file I/O zodat we een stream in verscheidene stukken kunnen inlezen indien gewenst.
6.3
Resultaten
Voor Selligent is het belangrijk om zeker te zijn dat het tellen van het aantal unieke elementen effici¨ent is in de praktijk. De implementatie werd daarom verwezenlijkt om testen te kunnen uitvoeren op een dataset van het bedrijf: een CSV-bestand dat zeer veel verschillende tupels bevat met gegevens in verband met de acties die gebeuren binnen bepaalde campagnes van een specifiek bedrijf. De campagnes waarover we spreken zijn e-mails die worden uitgezonden naar specifieke groepen van gebruikers in de database. Indien een gebruiker een e-mail leest, of op een link in de email klikt, wordt dit opgeslagen. Deze informatie wordt achteraf gebruikt om te kunnen bepalen hoeveel unieke gebruikers de e-mail hebben geopend, hoeveel mensen effectief op een link in de e-mail hebben geklikt, en zelfs welke personen nadien op de website een aankoop hebben verricht. Met behulp van sensoren in de e-mail is het zelfs mogelijk na te gaan op welke link de gebruikers klikten. De tupels in het bestand dat werd aangeboden bevatte 6 velden: ID, userID, listID, campaignID, actionID en probeID. De eerste kolom ID is een unieke identifier voor elk tupel in de tabel. UserID is de identifier voor elke specifieke user, elk van deze gebruikers kunnen door de klanten van Selligent worden ingedeeld in verschillende lijsten (zoals werknemers, etc.), dus listID vertelt ons in welke lijst deze gebruiker net zit. CampaignID is de identifier voor de campagne die de klant heeft uitgevoerd, er kunnen meerdere mails per campagne verstuurd worden. ActionID is de identifier voor componenten zoals een e-mail, een data look-up of data storage. ProbeID stelt de actie voor die bij dat component hoort, zoals een e-mail die verzonden werd, een e-mail die bekeken werd, een link waarop geklikt werd, etc. Met behulp van file I/O in Java werd dit bestand ingelezen en de gewenste gegevens werden eruit gehaald om te kunnen worden geteld door het Hy92
perLogLog algoritme. Om te weten hoe de gegevens geteld moeten worden, werden er ook twee voorbeeld-use cases vermeld. Deze use cases gebruikt Selligent om data te kunnen verwerken en zo klanten verscheidene statistieken te geven van data die opgeslagen werden. Nu kan er met behulp van de implementatie van HyperLogLog en HyperLogLog++ bestudeerd worden hoe effici¨ent de algoritmes zijn en of deze meerwaarde zouden kunnen toevoegen voor het bedrijf.
6.3.1
Eenvoudige kardinaliteiten
Voordat we beginnen met de use cases te analyseren, gaan we eerst enkele simpelere kardinaliteiten berekenen. Zo krijgen we een idee hoe accuraat het algoritme effectief is wanneer het toegepast wordt in de praktijk. 6.3.1.1
Totaal aantal rijen
De dataset van Selligent werd ge¨ımporteerd via MySQL, om de exacte resultaten te kunnen bepalen. Het uitvoeren van dergelijke queries neemt minstens enkele minuten in beslag en is dus veel te traag om te gebruiken indien we met Big Data werken. We kunnen dit echter wel gebruiken om resultaten van approximatie-algoritmen zoals HyperLogLog en HyperLogLog++ mee te vergelijken. Daarom beginnen we met een query op te stellen om het aantal rijen in de tabel te tellen: s e l e c t count ( ∗ ) from t a b l e ; .
Het resultaat van deze query is 28.660.533. We weten nu dat er ongeveer 28 miljoen rijen in de tabel zitten. Als input voor zowel het HyperLogLog als het HyperLogLog++ algoritme gebruiken we enkel een array die alle ID’s bevat. Als parameter voor de precisie geven we voor HyperLogLog een precisie tussen 4 en 16 mee en voor HyperLogLog++ een precisie tussen 4 en p0 , de precisie van de schaarse representatie. Deze laatste wordt in de implementatie altijd gelijkgesteld aan 25. In Figuur 6.1 zien we de uitkomsten van beide algoritmen alsook de exacte uitkomst voor elke precisie. We schakelen bij het HyperLogLog++ algoritme telkens over naar de dichte representatie aangezien de schaarse teveel plaats inneemt. Dit geldt voor zowel het gebruik van 8 bits per element in array M , maar ook indien elk van de elementen maar 6 bits zouden bedragen. In Figuur 6.1 is duidelijk te zien dat een hogere precisie een beter resultaat geeft, maar dit zorgt natuurlijk ook voor het gebruik van meer 93
Figuur 6.1: ID count van de volledige tabel
geheugen. Indien we bijvoorbeeld voor p de waarde 15 kiezen, hebben we 8m = 8 · 215 = 8 · 32.768 = 262.144 bits = 32, 768 kilobytes geheugen nodig voor zowel HyperLogLog als HyperLogLog++, aangezien we bij deze laatste altijd overstappen naar de dichte representatie en nooit enkel de schaarse gebruiken. In theorie of bij gebruik van een effici¨enter algoritme kunnen we echter stellen dat we voor het HyperLogLog en HyperLogLog++ algoritme respectievelijk 5m = 163.840 bits = 20, 48 kilobytes en 6m = 196.608 bits = 24, 576 kilobytes nodig hebben om array M op te slaan. Aangezien het geheugengebruik onafhankelijk is van de kardinaliteit voor het HyperLogLog algoritme en de dichte representatie van het HyperLogLog++ algoritme en enkel afhankelijk is van de precisie, heeft de data die we als parameter krijgen geen invloed op het geheugengebruik. In Figuur 6.2 zien we het geheugengebruik in bits per precisie voor zowel het HyperLogLog en HyperLogLog++ algoritme. Indien we echter enkel gebruik maken van de schaarse representatie tijdens de uitvoering van het HyperLogLog++ algoritme, gebruiken we minder geheugen dan in Figuur 6.2 beschreven staat, anders zouden we overgestapt zijn van schaarse naar dichte representatie. Hoeveel geheugen we exact gebruiken hangt af van de hash-functie, de schaarse precisie p0 en de data waarvoor we de kardinaliteit willen schatten. We berekenen in Figuur 6.3 de standaardfout van HyperLogLog gegeven de kardinaliteit van de array die 28.660.533 bedraagt. Vergewis je ervan dat √ de standaardfout van HyperLogLog 1, 04/ m is. Doordat de waarden van p (en dus ook m) relatief laag liggen, zien we een zeer slechte accuraatheid voor de kleinere precisies, we zagen dit reeds in Figuur 6.1. Indien p 14, 15 94
Figuur 6.2: Geheugenverbruik HyperLogLog en HyperLogLog++ algoritme
95
Figuur 6.3: Fout HyperLogLog vergeleken met standaardfout voor ID count of 16 bedraagt zien we echter dat we een accuraatheid hebben van minder dan 1%, wat beter is dan bijvoorbeeld 26% voor precisie 4. We merken op dat we in de praktijk soms een iets grotere error zullen krijgen dan we berekend hebben met behulp van de standaardfout zoals te zien in de figuur. De exacte output van zowel het ge¨ımplementeerde HyperLogLog als het HyperLoglog++ algoritme staan beschreven in Bijlage A. 6.3.1.2
Aantal unieke gebruikers
De volgende stap in het uitwerken van de use case is het tellen van het aantal unieke gebruikers in de dataset: s e l e c t count ( d i s t i n c t u s e r i d ) from t a b l e ; .
Na het uitvoeren van deze query zien we dat er 9.171.857 unieke gebruikers in de tabel te vinden zijn. We gebruiken HyperLogLog en HyperLogLog++ om een approximatie te krijgen. We zien opnieuw in Figuur 6.4 dat een hogere precisie een beter resultaat geeft. Dit komt natuurlijk ten koste van een hoger geheugengebruik. In theorie hebben we opnieuw slechts 5m bits nodig, maar in de implementatie gebruiken we 8m bits om de tabel M voor het HyperLogLog 96
Figuur 6.4: UserID count van de volledige tabel algoritme op te kunnen slaan. We schakelen opnieuw over naar de dichte representatie tijdens het uitvoeren van het HyperLogLog++ algoritme, behalve voor precisie p = 25. In de schaarse representatie zullen we minder dan 6m of 8m bits gebruiken, maar hoe groot de schaarse tabel exact is, hangt af van de data. Om de schaarse representatie op te slaan maken we gebruik van een array van 32-bit integers die maximaal 8m/32 elementen mag bevatten, waarbij m = 2p . We maken ook gebruik van een tijdelijke lijst, die maximaal 8m/128 elementen bevat. In deze lijsten slaan we de eerste p0 bits van de hash-waarde op, dus in ons geval is dit 25, eventueel 6 bits die het aantal voorloopnullen bevat, en een indicatiebit om aan te geven of we het aantal voorloopnullen wel degelijk hebben opgeslagen. Voor elke p0 eerste bits van de hash-waarde slaan we enkel degene op met het maximaal aantal nullen. We hebben hoogstens 32 bits nodig, dus we gebruiken hiervoor een integer-tabel die dynamisch kan groeien indien dit nodig is. Deze integer-tabel bevat maximaal 8m/32 elementen. Indien we switchen naar de dichte representatie maken we gebruik van een byte-tabel, maar deze groeit niet dynamisch en zal m elementen van elk 8 bits omvatten. Voor implementaties die slechts gebruik maken van 6 bits schakelen we natuurlijk sneller over naar het gebruik van de dichte representatie: de schaarse tabel bevat hoogstens 6m/32 elementen. In Figuur 6.5 zien we opnieuw de fout die het HyperLogLog algoritme ons geeft vergeleken met het resultaat dat we krijgen met behulp van de standaardfout. We zien dat we telkens een fout hebben die kleiner is dan de error die we berekenden met behulp van de standaardfout, behalve voor 97
Figuur 6.5: Fout HyperLogLog vergeleken met standaardfout voor UserID count
precisie 12 en 15. Stel dat we de kardinaliteit van een stream exact zouden willen bepalen. Indien we deze stream ook in delen willen inlezen, zouden we veel meer geheugen nodig hebben dan we gebruiken in het HyperLogLog algoritme. Elk uniek ID wordt als een integer opgeslagen, waardoor we een array van 32-bit elementen nodig hebben. In deze array zitten alle unieke elementen. In ons geval zijn er dit 9.171.857, en dus hebben we 293.499.424 bits = 36.687,428 kilobytes geheugen nodig hebben om deze array op te kunnen slaan. Zoals te zien in Figuur 6.2 weten we dat we voor maximale precisie 16 voor HyperLogLog in theorie 5 · m = 5 · 65.536 bits = 40, 96 kilobytes gebruiken, of in de praktijk 8 · m = 8 · 65.536 bits = 65, 536 kilobytes. Voor maximale precisie 25 gebruiken we voor het HyperLogLog++ algoritme 6 · m = 6 · 33.554.432 bits = 25.165, 824 kilobytes, of in de praktijk 8 · m = 8 · 33.554.432 bits = 33.554, 432 kilobytes. Dit is nog steeds lager dan alle unieke elementen opslaan, maar dit verschil is wel zeer klein. Indien we echter een lagere precisie kiezen, hebben we wel een veel lager geheugengebruik. De exacte output van zowel het HyperLogLog als het HyperLoglog++ algoritme staan beschreven in Bijlage A. 98
6.3.1.3
Aantal unieke gebruikers per gebruikerslijst
De volgende stap is het aantal unieke gebruikers tellen per gebruikerslijst: s e l e c t l i s t i d , count ( d i s t i n c t u s e r i d ) from t a b l e group by l i s t i d o r d e r by l i s t i d ; .
De query geeft ons 58 rijen terug. We tellen voor elk van deze 58 lijsten het aantal unieke gebruikers. Als input hebben we de lijst nodig van alle gebruikers met ´e´en bepaalde listID. We voeren opnieuw voor zowel HyperLogLog als HyperLogLog++ de algoritmes uit voor respectievelijk precisies 4 tot 16 en 4 tot 25. Aangezien dit zeer veel output genereert, maken we een analyse van alle resultaten. Het gemiddelde aantal unieke gebruikers van alle 58 verschillende lijsten is 185.685 en de mediaan is 33. We hebben hier dus te maken met veel kleinere kardinaliteiten aangezien onze gebruikers opgedeeld worden in kleinere groepen. Zo goed als alle kardinaliteiten zijn kleiner dan 50.000, en de meerderheid zelfs kleiner dan 1.000, met als uitzonderingen: ListID 9 171 172
Kardinaliteit 1.329.969 154.434 9.171.841
Het HyperLogLog algoritme geeft ons 13 verschillende precisie-parameters · 58 verschillende lijsten = 754 resultaten terug. Er wordt 392 keer een exact resultaat teruggegeven. Dit is ongeveer 51% van het totaal aantal resultaten. Het HyperLogLog++ algoritme geeft ons 22 verschillende precisie-parameters · 58 verschillende lijsten = 1276 resultaten. Van deze resultaten wordt er 973 keer het exacte resultaat teruggegeven, ongeveer 76%. Het HyperLogLog++ algoritme scoort veel beter omdat we voor kleinere kardinaliteiten wel vaak enkel de schaarse representatie gebruiken, omdat de schaarse lijst veel minder snel groeit omdat we maar ´e´en item bijhouden met dezelfde hash-waarde. Bij gebruik van de schaarse representatie krijgen we vaak een (quasi) exact resultaat terug, vooral voor zeer kleine kardinaliteiten zoals 31 of 250. Gemiddeld zit het HyperLogLog algoritme 7698 langs het exacte resultaat en het HyperLogLog++ algoritme 5591. Dit getal wordt omhoog getrokken door de uitschieters, toch hebben we slechts een gemiddelde error van ongeveer 4, 1% voor het HyperLogLog algoritme, indien we kijken naar de gemiddelde standaardfout voor alle precisies bedraagt deze 6, 8%. Voor het HyperLogLog++ algoritme hebben we een gemiddelde error van 3, 0%. 99
Figuur 6.6: UserID count voor listID 171
Indien we echter naar de mediaan van de fouten kijken, is deze voor beide algoritmes 0. In Figuur 6.6 en 6.7 zien we de resultaten voor zowel het HyperLogLog als HyperLogLog++ algoritme voor listID 171 en 641. De volledige output voor deze 2 listID’s staat in Bijlage A. We beperken ons hier tot 2 van de 58 resultaten om overzichtelijkheid te behouden. We zien in Figuur 6.8 het gemiddeld aantal unieke gebruikers voor alle verschillende gebruikerslijsten voor zowel het HyperLogLog als het HyperLogLog++ algoritme. Voor lage precisies zijn de schattingen niet altijd accuraat, maar vanaf ongeveer precisie 10 zien we dat de gemiddelde schattingen telkens dicht bij de gemiddelde kardinaliteit liggen. Tenslotte in Figuur 6.9 zien we dat de gemiddelde fout van het HyperLogLog algoritme dat we krijgen per gebruikerslijst per precisie steeds lager ligt dan de berekening die we maken met behulp van de standaardfout, behalve voor precisie 12 en 15. Nu we enkele basiskardinaliteiten hebben bekeken, concluderen we tot nu toe dat het algoritme goed werkt in de praktijk. We bekijken nu enkele use cases die interessant zijn voor Selligent. 100
Figuur 6.7: UserID count voor listID 641
Figuur 6.8: De gemiddelde userID count van alle gebruikerslijsten per precisie
101
Figuur 6.9: Fout HyperLogLog vergeleken met standaardfout voor gemiddelde UserID count per gebruikerslijst
6.3.2
Use case: Per campagne en gebruikerslijst het aantal unieke gebruikers tellen
De eerste use case gaat als volgt: we willen per campagne weten hoeveel gebruikers er per gebruikerslijst een interactie met een e-mail hebben uitgevoerd. We hebben hierboven de eerste stappen gemaakt om deze use case te kunnen oplossen door eerst en vooral te kijken naar het totaal aantal rijen in de dataset, daarna het aantal unieke gebruikers. We hebben dit daarna verfijnd tot het aantal unieke gebruikers per gebruikerslijst. We willen nu echter het aantal unieke gebruikers weten per gebruikerslijst en campagne: s e l e c t l i s t i d , campaignid , count ( d i s t i n c t u s e r i d ) from t a b l e group by l i s t i d , campaignid o r d e r by l i s t i d , campaignid ;
Deze query geeft ons 1006 rijen terug. We weten dat er 58 gebruikerslijsten zijn en met een simpele query kunnen we ook opvragen dat er 755 verschillende campagnes in de dataset gedocumenteerd staan. De meeste van deze campagnes hebben enkel te maken met gebruikerslijst 0 en 9, waarop respectievelijk 219 en 679 e-mailcampagnes werden uitgestuurd. Andere gebruikerslijsten zijn slechts betrokken in minder dan 7 campagnes elk. We werken opnieuw met kleinere kardinaliteiten aangezien het aantal unieke gebruikers per gebruikerslijst (zoals besproken in vorige paragraaf) nu nog meer opgedeeld worden. 102
De kardinaliteiten per gebruikerslijst en campagne zijn altijd minder dan 500.000, de meeste daarvan zijn zelfs minder dan 10.000, met ´e´en uitschieter: lijst 172 met campagne 338 heeft 9 miljoen unieke gebruikers. De gemiddelde kardinaliteit van elk (gebruikerslijst, campagne)-paar is 17.106, de mediaan is 3. Het HyperLogLog algoritme geeft ons 13.078 resulaten voor 13 verschillende precisieparameters en 1006 (gebruikerslijst, campagne)-paren. Van deze resultaten zijn er 8996 exact. Dit betekent dat we 68, 7% van de tijd een exact antwoord als resultaat krijgen. Het HyperLogLog++ algoritme geeft 22.132 resultaten voor 22 verschillende precisieparameters. Indien we zoeken naar exacte antwoorden, vinden we dat 17.492 resulaten de exacte kardinaliteit teruggeven. Met andere woorden, in 79, 0% van de gevallen krijgen we een perfect resultaat. Opnieuw scoort het HyperLogLog++ algoritme veel beter, door het gebruik van de schaarse representatie voor kleine kardinaliteiten. Gemiddeld geven het HyperLogLog en het HyperLogLog++ algoritme ons een resultaat dat respectievelijk 694 en 486 langs het exacte antwoord zit, wat betekent dat we gemiddeld 4, 0% en 2, 8% langs de kardinaliteit zitten. In Figuur 6.10 zien we de gemiddelde geschatte kardinaliteit voor alle (gebruikerslijst, campagne)-paren per precisie voor zowel HyperLogLog als HyperLogLog++. We vergelijken dit met het exacte gemiddelde. We zien dat vooral voor hogere precisies de geschatte kardinaliteit en het exacte aantal unieke gebruikers alsmaar dichter bij elkaar liggen.
6.3.3
Use case: Per campagne, actie, gebruikerslijst en sensor
Opnieuw hebben we nood aan een opdeling per campagne en gebruikerslijst. Dit hebben we al bekeken in de vorige use case. We hebben nu echter ook nood aan het opdelen per actie dat binnen een campagne werd uitgevoerd en per sensor die getriggerd werd tijdens deze actie. Dit betekent dat de gemiddelde kardinaliteit waarmee we te maken hebben nog zal verkleinen. We beginnen opnieuw met het uitvoeren van volgende query: s e l e c t campaignid , a c t i o n i d , l i s t i d , p r o b e i d , count ( d i s t i n c t u s e r i d ) from c o o l b l u e group by campaignid , a c t i o n i d , l i s t i d , p r o b e i d o r d e r by campaignid , a c t i o n i d , l i s t i d , p r o b e i d ; .
Deze query geeft ons 27.832 rijen terug. De gemiddelde kardinaliteit voor alle verschillende 4-tupels is 699. De mediaan is 1. 103
Figuur 6.10: De gemiddelde userID count van alle (gebruikerslijst, campagne)-paren per precisie Indien we opnieuw het HyperLogLog en het HyperLogLog++ algoritme uitvoeren voor elke precisie, cre¨eren we respectievelijk 361.816 en 612.304 resultaten. Het HyperLogLog algoritme geeft resultaten die gemiddeld 28 langs het exacte resultaat liggen. Toch zijn 264.023 van de resultaten, ofwel 72, 9% van de gevallen, exacte kardinaliteiten. Het HyperLogLog++ algoritme geeft resultaten die gemiddeld 20 langs het exacte resultaat liggen. Ondanks dat er 557.705 exacte resultaten worden teruggegeven, dit is 91, 1% van de kardinaliteiten. Tenslotte zien we in Figuur 6.11 de gemiddelde geschatte kardinaliteiten voor elke 4-tupel. We maken opnieuw dezelfde observatie als voorheen: voor lagere precisies is de schatting niet altijd accuraat, maar voor hogere precisies echter wel. We kunnen afleiden dat het HyperLogLog en HyperLogLog++ algoritme zeer goede resultaten geven voor precisies hoger dan ongeveer 10. We hebben echter nog niet besproken hoe Selligent nu het aantal unieke gebruikers bepaalt. We weten dus niet of HyperLogLog en HyperLogLog++ echt wel voordelen kan bieden. Hierin verdiepen we ons in volgende paragraaf.
6.3.4
Toepassing in Selligent
In Selligent wordt er om antwoord te kunnen geven op de use case in Paragraaf 6.3.3 een bestand bijgehouden per (campagne, actie)-paar. In dit 104
Figuur 6.11: De gemiddelde userID count van alle (campagne, actie, gebruikerslijst, sensor)-tupels per precisie
bestand staan alle (gebruikerslijst, sensor)-paren, samen met de kardinaliteit. Deze kardinaliteit wordt opgeslagen als een tabel van integers met de verschillende userID’s tot op een bepaalde treshold, dan wordt er overgestapt op een bitmap die evenveel bits bevat als het maximale userID per (campagne, actie, gebruikerslijst, sensor). In de data die geleverd werden door Selligent is het maximale userID 9.174.034, dit betekent dat de bitmap dus 9.174.034 bits zou bevatten. Indien een gebruiker userID 5 heeft, zal bit 5 van de bitmap op 1 gezet worden indien de gebruiker tot de set van unieke gebruikers hoort voor een bepaalde (campagne, actie, lijst, sensor)tupel. Deze bitmap wordt echter niet exclusief gebruikt, voor kleine kardinaliteiten wordt er gebruik gemaakt van een simpele array waar de unieke userID’s worden opgeslagen, een na¨ıeve manier om kardinaliteiten te tellen. Indien het geheugengebruik echter te groot wordt, schakelen we over op de bitmap. We gebruiken de resultaten van de testen uit vorige paragrafen om na te gaan wanneer HyperLogLog of HyperLogLog++ superieur is en wanneer niet. We vergelijken telkens een na¨ıeve oplossing: simpelweg een lijst van 32-bit userID’s bijhouden, wat Selligent doet voor lage kardinaliteiten, en de bitmap-oplossing met het HyperLogLog en HyperLogLog++ algoritme voor bepaalde precisies. Uit eerdere figuren kunnen we afleiden dat het HyperLogLog en Hyper105
Figuur 6.12: Vergelijking geheugengebruik en accuraatheid voor (campagneID, actionID, listID, probeID)-tupel (2,2,1,-1)
LogLog++ algoritme ongeveer vanaf precisie 10 een accuraat resultaat oplevert. We bekijken geen lage precisies aangezien deze gemiddeld teveel fouten geven om interessant te zijn voor Selligent, vooral bij hogere kardinaliteiten. We bekijken daarom enkel het HyperLogLog algoritme met precisie 10 en 16. We bekijken het HyperLogLog++ algoritme met precisie 10, 15, 25 en soms ook 18. We bekijken 5 (campagneID, actionID, listID, probeID)-tupels, waarvoor we telkens het geheugengebruik van de verschillende oplossingen met elkaar vergelijken. We proberen aan de hand van deze tupels tot een conclusie te komen in verband met de optimale manier waarop Selligent kardinaliteiten kan berekenen. In Figuur 6.12 zien we dat het maximale userID zeer laag ligt. Hierdoor is het gebruik van een bitmap superieur omdat dit betekent dat we zeer weinig bits nodig hebben om deze te construeren. Door de zeer lage kardinaliteit gebruikt zelfs de na¨ıeve manier minder geheugen dan HyperLogLog. Aangezien we een lage kardinaliteit hebben, gebruiken we de schaarse representatie voor HyperLogLog++, de schaarse lijst heeft slechts 3 elementen, waardoor we een minstens even laag geheugengebruik krijgen als voor de na¨ıeve methode, afhankelijk of de waarde van de eerste 1-bit wordt opgeslagen. We gaan er echter in deze analyse vanuit dat we telkens 32 bits nodig hebben per element in de schaarse lijst, omdat we dit op deze manier hebben ge¨ımplementeerd. 106
Figuur 6.13: Vergelijking geheugengebruik en accuraatheid voor (campagneID, actionID, listID, probeID)-tupel (85,2,9,-1)
In Figuur 6.13 ligt het maximale userID redelijk hoog. Dit betekent dat we voor het opslaan van een bitmap veel bits nodig hebben. Doordat de kardinaliteit echter zeer laag ligt, zou Selligent in dit geval enkel een lijst gebruiken van het aantal unieke gebruikers, waardoor we slechts een geheugengebruik van 96 bits hebben. Dit ligt veel lager dan het HyperLogLog algoritme. Opnieuw gebruiken we bij het HyperLogLog++ de schaarse representatie waardoor we ook een zeer laag geheugengebruik krijgen. In Figuur 6.14 zien we dat de maximale userID opnieuw hoog ligt. Deze keer ligt echter ook de kardinaliteit zeer hoog. Dit betekent dat zowel de bitmap als de na¨ıeve methode zeer veel geheugen nodig hebben. HyperLogLog en HyperLogLog++ zijn daardoor superieur in dergelijke gevallen. Indien we het HyperLogLog++ algoritme uitvoeren met behulp van precisie 18 ligt het geheugengebruik zelfs nog lager, indien we echter een hogere precisie kiezen niet meer. Indien we het HyperLogLog++ algoritme gebruiken met precisie 25, zullen we enkel gebruik maken van de schaarse representatie. In de schaarse lijst zitten 283.121 elementen van elk hoogstens 32 bits. In Figuur 6.15 zien we dat de maximale userID nogmaals hoog is. De kardinaliteit ligt echter ook redelijk hoog. Hierdoor gebruikt Selligent mogelijk geen integer-array meer, maar maakt gebruik van een bitmap. Zowel de bitmap als de na¨ıeve manier gebruiken echter meer geheugen dan HyperLogLog en HyperLogLog++ afhankelijk van de precisie die werd meege107
Figuur 6.14: Vergelijking geheugengebruik en accuraatheid voor (campagneID, actionID, listID, probeID)-tupel (171,12,9,-1)
geven. Het HyperLogLog++ algoritme is superieur voor precisie 10 en 15. Het HyperLogLog algoritme verbruikt ook minder geheugen voor precisie 10. Voor precisie 16 is enkel een optimale implementatie, waarbij slechts 5 bits gebruikt worden, voordeliger. De fout die we krijgen bij precisie 15 voor HyperLogLog++ ligt laag: 102 ofwel 0.7%. Indien we het HyperLogLog++ algoritme uitvoeren voor precisie 18 of 25, maken we enkel gebruik van de schaarse representatie. We zien dat we hierdoor een gelijkaardige hoeveelheid geheugen nodig hebben als bij de na¨ıeve methode. In Figuur 6.16 zien we opnieuw een voorbeeld van een zeer lage kardinaliteit ondanks een hoge maximale userID. In dit geval zal Selligent de na¨ıeve manier gebruiken om het aantal unieke gebruikers op te slaan, wat minder bits in beslag zal nemen dan HyperLogLog. We gebruiken voor HyperLogLog++ echter enkel de schaarse representatie, waardoor we een minstens even laag geheugengebruik krijgen als de na¨ıeve manier. Het HyperLogLog of HyperLogLog++ algoritme kan voor Selligent een meerwaarde bieden in gevallen waar de kardinaliteit en de maximale userID beiden redelijk hoog liggen. We weten echter de kardinaliteit van de set niet op voorhand. Selligent beslist nu via geheugengebruik of de na¨ıeve manier of de bitmap gebruikt moet worden, eenzelfde strategie kan toegepast worden voor het HyperLogLog of HyperLogLog++ algoritme. Er moet 108
Figuur 6.15: Vergelijking geheugengebruik en accuraatheid voor (campagneID, actionID, listID, probeID)-tupel (887,2,9,-1)
Figuur 6.16: Vergelijking geheugengebruik en accuraatheid voor (campagneID, actionID, listID, probeID)-tupel (1103,19,9,126)
109
ook een keuze gemaakt worden in verband met de precisie die gebruikt wordt voor het HyperLogLog of HyperLogLog++ algoritme, aangezien het niet mogelijk is te switchen van precisie tenzij we de volledige dataset opnieuw tellen met een nieuwe precisie-parameter. Indien we bijvoorbeeld gebruik zouden maken van √ precisie 11, dan weten we dat we een accuraatheid van ongeveer 1, 04/ 211 ≈ 2, 3% hebben tijdens de uitvoering van het HyperLogLog algoritme. Een precisie kleiner dan 10 is niet aangeraden omdat dit een te grote fout zal geven. Zoals te zien in vorige paragraaf is het ook niet verstandig om een te grote precisie uit te kiezen aangezien dit het geheugengebruik drastisch doet toenemen, waardoor het gebruik van het HyperLogLog of HyperLogLog++ algoritme weinig voordeel zal bieden. We zagen dat vooral het gebruik van precisies hoger dan 16 meestal weinig voordelen biedt voor de kardinaliteiten die Selligent wil schatten. Indien er datasets zijn waar er een veel grotere kardinaliteit moet geschat worden, kan een hogere precisie mogelijk wel voordelen bieden, omdat we dan voor zowel de na¨ıeve als de bitmap-methode ook veel meer geheugen gebruiken. Indien we dan een hogere precisie kiezen, zoals bijvoorbeeld 16, zullen √ we voor het HyperLogLog algoritme een accuraatheid hebben van 1, 04/ 216 ≈ 0, 4%. Vergewis je er wel van dat het resultaat van het HyperLogLog++ algoritme een hogere accuraatheid kan hebben, maar aangezien het algoritme enkel empirisch werd getest, weten we de exacte accuraatheid van dit algoritme niet. HyperLogLog++ is beter in het omgaan met kleine kardinaliteiten dan HyperLogLog. Ook voor het tellen van grotere kardinaliteiten heeft dit als voordeel dat de bias wordt gecorrigeerd indien nodig en dat we gebruik maken van een 64-bit hash-functie. Dit neemt natuurlijk niet weg dat HyperLogLog ook zeer mooie resultaten aflevert, mits een veel eenvoudigere implementatie. HyperLogLog of HyperLogLog++ kunnen dus inderdaad voordelig zijn voor het bedrijf.
6.4
Open-source implementaties
Zoals voor elk bekend algoritme, zijn er online implementaties terug te vinden. Specifiek zijn er twee noemenswaardige open-source implementaties online aan te treffen voor HyperLogLog. De eerste is een implementatie van Clearspring Technologies, en de tweede is van Aggregate Knowledge, een bedrijf dat gekocht werd door Neustar. Clearspring Technologies, vroeger bekend als AddThis, biedt een ‘au110
dience intelligence’ platform aan dat bedrijven toelaat real-time activiteit van miljarden webgebruikers te bekijken. Ze hebben een Java library ge¨ımplementeerd om streams te kunnen samenvatten en kardinaliteiten te kunnen tellen. [36] Onder andere werd zowel het HyperLogLog als het HyperLogLog++ algoritme door hen ge¨ımplementeerd. Buiten kardinaliteit schatten is het ook mogelijk set-lidmaatschap te testen, frequentie en de ‘top k’ elementen te vinden. Als hash-functie werd er voor MurmurHash gekozen. Neustar focust zich op beveiliging, marketing en data services voor bedrijven. Deze implementatie werd ge¨ımplementeerd als extensie voor PostgreSQL om HyperLogLog data structuren in SQL te kunnen manipuleren. [30] In tegenstelling tot de vorige implementatie, is dit ook het enige algoritme dat aangeboden wordt. Ook het HyperLogLog++ algoritme werd niet ge¨ımplementeerd. Als hash-functie werd er voor MurmurHash3 gekozen. Net zoals bij Selligent is het hier de bedoeling dat de extensie gebruikt zal worden om onder andere het aantal unieke gebruikers te tellen.
111
112
Hoofdstuk 7 Conclusie In deze thesis hebben we verscheidene streaming algoritmen bekeken om Big Data te verwerken. We hebben onder andere bekeken hoe we de heavy hitters in een stream kunnen bepalen met behulp van bijvoorbeeld het Count-Min algoritme en hoe we het totaal aantal items in een stream kunnen schatten door bijvoorbeeld gebruik te maken van het Morris algoritme. We bestudeerden dit alles om een goede basis te verwerven zodat we uiteindelijk tot een oplossing konden komen voor de onderzoeksvraag van deze thesis: het tellen van het aantal unieke elementen in een stream. Hiervoor hebben we verscheidene algoritmes bestudeerd. Eerst en vooral begonnen we met het Flajolet-Martin algoritme wat het eerste streaming algoritme was dat ontworpen werd om de kardinaltieit van een multiset te kunnen schatten. In dit algoritme leerden we dat we met behulp van een hash-functie willekeurigheid kunnen introduceren in de data-stream. Door het gebruik van een gepaste hash-functie, mappen we de items in een stream naar ‘emmers’. We zagen dat indien we n het maximaal aantal nullen voorstelt achteraan de gehashte waarden, we konden verwachten dat de kardinaliteit van de stream 2n benadert. We houden dus tijdens de uitvoering van het algoritme enkel het maximaal aantal nullen bij, wat we uiteindelijk gebruiken om de kardinaliteit te schatten. Dit algoritme vormde de basis voor het complexere LogLog en HyperLogLog algoritme. We gebruiken in beide algoritmen opnieuw een hash-functie om willekeurigheid voor te stellen. We introduceerden ook stochastic averaging: we plaatsen de items in de stream in m emmers (of substreams) met behulp van ´e´en hash-functie. We berekenen een schatting van de kardinaliteit voor elk van deze emmers. We voegen uiteindelijk de resultaten samen om een schatting te kunnen krijgen van de totale kardinaliteit. We bootsen hiermee m experimenten met m verschillende hash-functies na om
113
een betere schatting in verband met de kardinaliteit te verkrijgen. In beide algoritmen gebruikten we dezelfde observabele: de positie van de eerste 1-bit. Indien we de eerste 1-bit op positie p begint, kunnen we als ruwe schatting voor de kardinaliteit 2p teruggeven. Aangezien we echter gebruik maken van stochastic averaging gebruiken we in het LogLog algoritme een aritmetisch gemiddelde om een schatting in verband met de kardinaliteit te kunnen geven. In het HyperLogLog algoritme gebruiken we dezelfde observabele, maar we berekenen nu een harmonisch gemiddelde, hierdoor gaan we beter om met uitschieters. Als verbetering op het HyperLogLog algoritme stelde Google het empirisch ge¨evalueerde HyperLogLog++ algoritme voor. Er werden kleine aanpassingen voorgesteld zoals het gebruiken van een schaarse representatie om beter kleine kardinaliteiten te kunnen schatten en het empirisch corrigeren van de bias. Uiteindelijk maakten we een implementatie van zowel het HyperLogLog als het HyperLogLog++ algoritme om testen te kunnen uitvoeren op een dataset van Selligent. Samen met deze dataset werden er ook twee use cases uiteengezet. Deze use cases stelden situaties voor waarin het bedrijf kardinalteiten berekent van grote hoeveelheden data. De resultaten van de testen werden vergeleken met de exacte kardinaliteiten voor de dataset om de correctheid van de uitkomsten te evalueren. Tenslotte bestudeerden we de accuraatheid en het geheugengebruik van zowel HyperLogLog als HyperLogLog++ om dit te vergelijken met de manier waarop Selligent nu het aantal unieke gebruikers telt. We concludeerden dat vooral het HyperLogLog++ algoritme een mooie oplossing zou kunnen zijn voor Selligent.
114
Bibliografie [1] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. 2002. URL: http://www. tau.ac.il/~nogaa/PDFS/amsz4.pdf. [2] Paolo Atzeni, Christian S. Jensen, Giorgio Orsi, Sudha Ram, Letizia Tanca, and Riccardo Torlone. The relational model is dead, SQL is dead, and i don’t feel so good myself. SIGMOD Record, June 2013. URL: http://www.orsigiorgio.net/wp-content/ papercite-data/pdf/ajo*13.pdf. [3] Peter Bailis, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica. HAT, not CAP: Towards highly availability transactions. 2013. URL: http://www.bailis.org/papers/hat-hotos2013.pdf. [4] Philippe Chassaing and Lucas Gerin. Efficient estimation of the cardinality of large data sets. 2011. URL: http://arxiv.org/pdf/math/ 0701347v3.pdf. [5] Couchbase. Why NoSQL? URL: http://www.couchbase.com/ nosql-resources/what-is-no-sql. [6] Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. 2004. URL: http://static.googleusercontent.com/media/research. google.com/nl//archive/mapreduce-osdi04.pdf. [7] Marianne Durand and Philippe Flajolet. LogLog counting of large cardinalities. 2003. URL: http://www.ic.unicamp.br/~celio/ peer2peer/math/bitmap-algorithms/durand03loglog.pdf. ´ [8] Philippe Flajolet, Eric Fusy, Olivier Gandouet, and Fr´ed´eric Meunier. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. 2007. URL: http://algo.inria.fr/flajolet/ Publications/FlFuGaMe07.pdf. 115
[9] Philippe Flajolet and G. Nigel Martin. Probabilistic counting algorithms for data base applications. 1985. URL: http://algo.inria. fr/flajolet/Publications/FlMa85.pdf. [10] An Optimal Algorithm for the Distinct Elements Problem. An optimal algorithm for the distinct problem elements problem. 2010. URL: http://people.seas.harvard.edu/~minilek/papers/f0.pdf. [11] Floris Geerts. Big Data. 2014. [12] Seth Gilbert and Nancy Lynch. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. 2002. URL: http://webpages.cs.luc.edu/~pld/353/gilbert_ lynch_brewer_proof.pdf. [13] Google. Guava library. URL: https://code.google.com/p/guavalibraries/. [14] Georg Gottlob, Giovanni Grasso, Dan Olteanu, and Christian Schallhart. Big Data. 2013. URL: https://books.google.be/books?id= FNO6BQAAQBAJ. [15] Katarina Grolinger, Wilson A Higashino, Abhinav Tiwari, and Miriam AM Capretz. Data management in cloud environments: NoSQL and NewSQL data stores. Journal of Cloud Computing, 2013. URL: http://www.journalofcloudcomputing.com/content/ pdf/2192-113X-2-22.pdf. [16] Stefan Heule, Marc Nunkesser, and Alexander Hall. Appendix to HyperLogLog in Practice: Algorithmic engineering of a state of the art cardinality estimation algorithm. 2013. URL: https://docs.google.com/document/d/1gyjfMHy43U9OWBXxfaeG3MjGzejW1dlpyMwEYAAWEI. [17] Stefan Heule, Marc Nunkesser, and Alexander Hall. HyperLogLog in Practice: Algorithmic engineering of a state of the art cardinality estimation algorithm. 2013. URL: http://stefanheule.com/papers/ edbt13-hyperloglog.pdf. [18] Adam Kirsch and Michael Mitzenmacher. Less hashing, same performance: Building a better bloom filter. 2008. URL: http://www. eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf. [19] Philip N. KLein and Neal E. Young. Approximation algorithms for NP-hard optimization problems, chapter 34. 1999. URL: http://www. cs.ucr.edu/~neal/Papers/CRC_1999_ch34.pdf. 116
[20] Andrew McAfee and Erik Brynjolfsson. Big Data: The management revolution. Harvard Business Review, October 2012. URL: https: //hbr.org/2012/10/big-data-the-management-revolution/ar. [21] Mary Meeker. Internet trends 2014. KPCB, March 2014. URL: http://www.kpcb.com/internet-trends. [22] Michael Mitzenmacher and Eli Upfal. Probability and Computing. [23] Jeff Morris. Top 10 categories for Big Ddata sources and mining technologies. ZDNet, July 2012. URL: http://www.zdnet.com/article/top-10-categories-for-bigdata-sources-and-mining-technologies/. [24] M. Tamer Ozsu and Patrick Valduriez. Principles of Distributed Database Systems. [25] Odysseas Papapetrou, Wolf Siberski, and Wolfgang Nejdl. Cardinality estimation and dynamic length adaptation for bloom filters. 2010. URL: http://www.l3s.de/~papapetrou/publications/ Bloomfilters-DAPD.pdf. [26] Helmut Prodinger. Combinatorics of geometrically distributed random variables: Left-to-right maxima. 1993. URL: http://www. sciencedirect.com/science/article/pii/0012365X9500141I. [27] Lisa Quast. Why knowledge management is so important to the success of your company. Forbes, August 2012. URL: http://www.forbes.com/sites/lisaquast/2012/08/20/whyknowledge-management-is-important-to-the-success-ofyour-company/. [28] April Reeve. Big Data and NoSQL: The problem with relational databases. EMC, September 2012. URL: https: //infocus.emc.com/april_reeve/big-data-and-nosql-theproblem-with-relational-databases/. [29] Neustar Research. Articles tagged with HyperLogLog. URL: http: //research.neustar.biz/tag/hyperloglog/. [30] Neustar Research. PostgreSQL extension adding hyperloglog data structures as a native data type. URL: https://github.com/ aggregateknowledge/postgresql-hll. [31] Paul Roberts. Guest: The slide toward an impulse society, thanks to big data and Amazon.com. The Seattle Times, August 2014. URL: http://www.seattletimes.com/opinion/guest-the117
slide-toward-an-impulse-society-thanks-to-big-data-andamazoncom/. [32] Robert Sedgewick and Kevin Wayne. Algorithms. URL: http:// algs4.cs.princeton.edu/66intractability/. [33] Jonathan Shaw. Why “Big Data” is a big deal. Harvard Magazine, March-April 2014. URL: http://harvardmagazine.com/2014/03/ why-big-data-is-a-big-deal. [34] O’Reilly Strata. Returning transactions to distributed data stores. Radar, March 2012. URL: http://radar.oreilly.com/2013/03/ returning-transactions-to-distributed-data-stores.html. [35] David Talbot. Big Data from cheap phones. MIT Technology Review, May/June 2013. URL: http://www.technologyreview.com/ featuredstory/513721/big-data-from-cheap-phones/. [36] Clearspring Technologies. Stream summarizer and cardinality estimator. URL: https://github.com/addthis/stream-lib. [37] Mark van Rijmenam. Sears became a real-time digital enterprise due to big data. Smart Data Collective, July 2014. URL: http://smartdatacollective.com/bigdatastartups/212091/ sears-became-real-time-digital-enterprise-due-big-data. [38] Marco Vieira, Ant´onio Casimiro Costa, and Henrique Madeira. The relational model is dead, SQL is dead, and i don’t feel so good myself. SIGMOD Record, June 2013. URL: http://www.di.fc.ul.pt/ ~casim/papers/dsn04-fa/dsn04-fa.pdf. [39] Baoying Wang, Ruowang Li, and William Perrizo. Big Data Analytics in Bioinformatics and Healthcare. [40] Kyu-Young Whang, Brad T. Vander-Zanden, and Howard M. Taylor. A linear-time probabilistic counting algorithm for database applications. 1990. URL: http://dblab.kaist.ac.kr/Prof/pdf/ Whang1990%28linear%29.pdf. [41] Alexander Wolfe. Big Data at work: Decline of the HiPPO. Forbes, August 2013. URL: http://www.forbes.com/sites/oracle/2014/ 05/05/6-key-steps-to-customer-centric-modern-marketing/.
118
Bijlage A Resultaten implementatie A.1
Het totaal aantal rijen tellen
Output MySQL query: +----------+ | count(*) | +----------+ | 28660533 | +----------+ Output HyperLogLog algoritme: Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision
p p p p p p p p p p p p p
= = = = = = = = = = = = =
4, result = 26625336 5, result = 28233112 6, result = 27491668 7, result = 28232633 8, result = 26964935 9, result = 26332492 10, result = 25684230 11, result = 28270670 12, result = 27707974 13, result = 27932629 14, result = 28339989 15, result = 28552585 16, result = 28712483
Output HyperLogLog++ algoritme: 119
DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE DENSE
A.2
Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision Precision
p p p p p p p p p p p p p p p p p p p p p p
= = = = = = = = = = = = = = = = = = = = = =
4, result = 21897826 5, result = 29205778 6, result = 22406120 7, result = 25524917 8, result = 24264508 9, result = 26865932 10, result = 27396526 11, result = 28291275 12, result = 29040750 13, result = 29312182 14, result = 29049539 15, result = 28747035 16, result = 28694348 17, result = 28688972 18, result = 28690127 19, result = 28716078 20, result = 28673413 21, result = 28665656 22, result = 28656921 23, result = 28651365 24, result = 28661392 25, result = 28666586
Het totaal aantal unieke gebruikers tellen
Output MySQL query: +------------------------+ | count(distinct userid) | +------------------------+ | 9171857 | +------------------------+ Output HyperLogLog algoritme: Precision Precision Precision Precision
p p p p
= = = =
4, 5, 6, 7,
result result result result
= = = =
7392616 9443509 8871469 9207055 120
Precision Precision Precision Precision Precision Precision Precision Precision Precision
p p p p p p p p p
= = = = = = = = =
8, result = 8806399 9, result = 9223193 10, result = 9455637 11, result = 9373660 12, result = 9412254 13, result = 9252725 14, result = 9243984 15, result = 9252158 16, result = 9176016
Output HyperLogLog++ algoritme:
DENSE Precision p = 4, result = 8188422 DENSE Precision p = 5, result = 8036489 DENSE Precision p = 6, result = 7426019 DENSE Precision p = 7, result = 8497366 DENSE Precision p = 8, result = 8609496 DENSE Precision p = 9, result = 8948422 DENSE Precision p = 10, result = 9201573 DENSE Precision p = 11, result = 9023288 DENSE Precision p = 12, result = 9350969 DENSE Precision p = 13, result = 9189622 DENSE Precision p = 14, result = 9173589 DENSE Precision p = 15, result = 9146470 DENSE Precision p = 16, result = 9173423 DENSE Precision p = 17, result = 9189708 DENSE Precision p = 18, result = 9140369 DENSE Precision p = 19, result = 9148003 DENSE Precision p = 20, result = 9161160 DENSE Precision p = 21, result = 9179035 DENSE Precision p = 22, result = 9166918 DENSE Precision p = 23, result = 9170696 DENSE Precision p = 24, result = 9172265 SPARSE Precision p = 25, result = 9171199
A.3
Het totaal aantal unieke gebruikers per gebruikerslijst tellen
Output MySQL query voor listID 171 en 641: 121
+--------+------------------------+ | listid | count(distinct userid) | +--------+------------------------+ | 171 | 154434 | | 641 | 4604 | +--------+------------------------+ Output HyperLogLog algoritme voor listID 171 en 641: Listid = 171, precision Listid = 171, precision Listid = 171, precision Listid = 171, precision Listid = 171, precision Listid = 171, precision Listid = 171, precision Listid = 171, precision Listid = 171, precision Listid = 171, precision Listid = 171, precision Listid = 171, precision Listid = 171, precision Exact count: 154434 ----------------------Listid = 641, precision Listid = 641, precision Listid = 641, precision Listid = 641, precision Listid = 641, precision Listid = 641, precision Listid = 641, precision Listid = 641, precision Listid = 641, precision Listid = 641, precision Listid = 641, precision Listid = 641, precision Listid = 641, precision Exact count: 4604
p p p p p p p p p p p p p
= = = = = = = = = = = = =
4, result = 196580 5, result = 149980 6, result = 177476 7, result = 158903 8, result = 150502 9, result = 153090 10, result = 158202 11, result = 160724 12, result = 154210 13, result = 154844 14, result = 154072 15, result = 154714 16, result = 154738
p p p p p p p p p p p p p
= = = = = = = = = = = = =
4, result = 4658 5, result = 4227 6, result = 4217 7, result = 4059 8, result = 4312 9, result = 4232 10, result = 4421 11, result = 4408 12, result = 4510 13, result = 4602 14, result = 4640 15, result = 4614 16, result = 4625
Output HyperLogLog++ algoritme: DENSE Listid = 171, precision p = 4, result = 164795 122
DENSE Listid = 171, precision p = 5, result = 126922 DENSE Listid = 171, precision p = 6, result = 139142 DENSE Listid = 171, precision p = 7, result = 137112 DENSE Listid = 171, precision p = 8, result = 148196 DENSE Listid = 171, precision p = 9, result = 154095 DENSE Listid = 171, precision p = 10, result = 155638 DENSE Listid = 171, precision p = 11, result = 152814 DENSE Listid = 171, precision p = 12, result = 154225 DENSE Listid = 171, precision p = 13, result = 153441 DENSE Listid = 171, precision p = 14, result = 154112 DENSE Listid = 171, precision p = 15, result = 154454 DENSE Listid = 171, precision p = 16, result = 154655 DENSE Listid = 171, precision p = 17, result = 154806 DENSE Listid = 171, precision p = 18, result = 154336 SPARSE Listid = 171, precision p = 19, result = 154429 SPARSE Listid = 171, precision p = 20, result = 154429 SPARSE Listid = 171, precision p = 21, result = 154429 SPARSE Listid = 171, precision p = 22, result = 154429 SPARSE Listid = 171, precision p = 23, result = 154429 SPARSE Listid = 171, precision p = 24, result = 154429 SPARSE Listid = 171, precision p = 25, result = 154429 Exact count: 154434 ----------------------DENSE Listid = 641, precision p = 4, result = 3333 DENSE Listid = 641, precision p = 5, result = 4179 DENSE Listid = 641, precision p = 6, result = 4609 DENSE Listid = 641, precision p = 7, result = 4557 DENSE Listid = 641, precision p = 8, result = 4713 DENSE Listid = 641, precision p = 9, result = 4732 DENSE Listid = 641, precision p = 10, result = 4733 DENSE Listid = 641, precision p = 11, result = 4642 DENSE Listid = 641, precision p = 12, result = 4590 DENSE Listid = 641, precision p = 13, result = 4639 DENSE Listid = 641, precision p = 14, result = 4632 SPARSE Listid = 641, precision p = 15, result = 4604 SPARSE Listid = 641, precision p = 16, result = 4604 SPARSE Listid = 641, precision p = 17, result = 4604 SPARSE Listid = 641, precision p = 18, result = 4604 SPARSE Listid = 641, precision p = 19, result = 4604 SPARSE Listid = 641, precision p = 20, result = 4604 SPARSE Listid = 641, precision p = 21, result = 4604 SPARSE Listid = 641, precision p = 22, result = 4604 SPARSE Listid = 641, precision p = 23, result = 4604 123
SPARSE Listid = 641, precision p = 24, result = 4604 SPARSE Listid = 641, precision p = 25, result = 4604 Exact count: 4604
124
Auteursrechtelijke overeenkomst Ik/wij verlenen het wereldwijde auteursrecht voor de ingediende eindverhandeling: Big Data Counting : Hoe kunnen we een zeer groot aantal distincte efficiënt tellen?
objecten
Richting: master in de informatica-databases Jaar: 2015 in alle mogelijke mediaformaten, Universiteit Hasselt.
-
bestaande
en
in
de
toekomst
te
ontwikkelen
-
,
aan
de
Niet tegenstaand deze toekenning van het auteursrecht aan de Universiteit Hasselt behoud ik als auteur het recht om de eindverhandeling, - in zijn geheel of gedeeltelijk -, vrij te reproduceren, (her)publiceren of distribueren zonder de toelating te moeten verkrijgen van de Universiteit Hasselt. Ik bevestig dat de eindverhandeling mijn origineel werk is, en dat ik het recht heb om de rechten te verlenen die in deze overeenkomst worden beschreven. Ik verklaar tevens dat de eindverhandeling, naar mijn weten, het auteursrecht van anderen niet overtreedt. Ik verklaar tevens dat ik voor het materiaal in de eindverhandeling dat beschermd wordt door het auteursrecht, de nodige toelatingen heb verkregen zodat ik deze ook aan de Universiteit Hasselt kan overdragen en dat dit duidelijk in de tekst en inhoud van de eindverhandeling werd genotificeerd. Universiteit Hasselt zal wijzigingen aanbrengen overeenkomst.
Voor akkoord,
Broeckx, Jana Datum: 22/06/2015
mij als auteur(s) van de aan de eindverhandeling,
eindverhandeling identificeren en zal uitgezonderd deze toegelaten door
geen deze
