Flajolet–Martin algoritm

Flajolet -Martin-algoritmen är en algoritm för att approximera antalet distinkta element i en ström med en enda passage och logaritm för utrymmesförbrukning i det maximala antalet möjliga distinkta element i strömmen (det antal distinkta problemet) . Algoritmen introducerades av Philippe Flajolet och G. Nigel Martin i deras 1984 artikel "Probabilistic Counting Algorithms for Data Base Applications". Senare har det förfinats i "LogLog counting of large cardinalities" av Marianne Durand och Philippe Flajolet , och " HyperLogLog : The analysis of a near-optimal cardinality estimation algorithm" av Philippe Flajolet et al.

I sin artikel från 2010 "An optimal algorithm for the distinct elements problem" ger Daniel M. Kane, Jelani Nelson och David P. Woodruff en förbättrad algoritm, som använder nästan optimalt utrymme och har optimala O (1) uppdaterings- och rapporteringstider.

Algoritmen

Antag att vi får en hashfunktion $\mathrm {hash} (x)$ som mappar indata $x$ till heltal i intervallet $[0;2^{L}-1]$ , och där utsignalerna är tillräckligt jämnt fördelade . Observera att uppsättningen av heltal från 0 till $2^{L}-1$ motsvarar uppsättningen av binära strängar med längden $L$ . För alla icke-negativa heltal $y$ , definiera $\mathrm {bit} (y,k)$ till $k$ -th biten i binär representation av $y$ , så att:

y=\sum _{k\geq 0}\mathrm {bit} (y,k)2^{k}.

Vi definierar sedan en funktion $\rho (y)$ som matar ut positionen för den minst signifikanta setbiten i den binära representationen av $y$ , och $L$ om nej sådan set bit kan hittas eftersom alla bitar är noll:

$\rho (y)={\begin{cases}\min\{k\geq 0\ mitten av \mathrm {bit} (y,k)\neq 0\}&y>0\\L&y=0\end{fall}}$

Observera att med ovanstående definition använder vi 0-indexering för positionerna, med början från den minst signifikanta biten. Till exempel, ${\displaystyle \rho (13)=\rho (1101_{2})=0} ,$ eftersom den minst signifikanta biten är en 1 (0:e position), och ${\displaystyle \rho (8)=\rho (1000_{2})=3},$ eftersom den minst signifikanta setbiten är på den tredje positionen. Notera nu att under antagandet att utdata från vår hashfunktion är likformigt fördelad, då är sannolikheten att observera en hashutgång som slutar med $2^{k}$ (en etta, följt av ${\ displaystyle k}$ nollor) är $2^{-(k+1)}$ , eftersom detta motsvarar att vända $k$ huvuden och sedan en svans med ett rättvist mynt.

Nu är Flajolet–Martin-algoritmen för att uppskatta kardinaliteten för en multiset $M$ som följer:

Initiera en bit-vektor BITMAP så att den har längden $L$ och innehåller alla nollor.
För varje element $x$ $x$ i $M$ $M$ :
1. Beräkna indexet $i=\rho (\mathrm {hash} (x))$ .
2. Sätt $\mathrm {BITMAP} [i]=1$ .
Låt $R$ beteckna det minsta indexet $i$ så att $\mathrm {BITMAP} [i]=0$ .
Uppskatta kardinaliteten för $M$ som $2^{R}/\phi$ , där $\phi \approx 0,77351$ .

Tanken är att om $n$ är antalet distinkta element i multiuppsättningen $M$ , så kommer $\mathrm {BITMAP} [0]$ åtkomst ungefär $n/2$ gånger, $\mathrm {BITMAP} [1]$ nås ungefär $n/4$ gånger och så på. Följaktligen, om $i\gg \log _{2}n$ så är $\mathrm {BITMAP} [i]$ nästan säkert 0 , och om $i\ll \log _{2}n$ så är $\mathrm {BITMAP} [i]$ nästan säkert 1 . Om $i\approx \log _{2}n$ , då kan $\mathrm {BITMAP} [i]$ förväntas vara antingen 1 eller 0.

Korrektionsfaktorn $\phi \approx 0,77351$ hittas genom beräkningar, som finns i originalartikeln.

Förbättrar noggrannheten

Ett problem med Flajolet–Martin-algoritmen i ovanstående form är att resultaten varierar avsevärt. En vanlig lösning har varit att köra algoritmen flera gånger med $k$ olika hashfunktioner och kombinera resultaten från de olika körningarna. En idé är att ta medelvärdet av $k$ -resultaten tillsammans från varje hashfunktion och erhålla en enda uppskattning av kardinaliteten. Problemet med detta är att medelvärdesberäkning är mycket känsligt för extremvärden (vilket är troligt här). En annan idé är att använda medianen , som är mindre benägen att påverkas av extremvärden. Problemet med detta är att resultaten bara kan ta formen ${\displaystyle 2^{R}/\phi } ,$ där $R$ är heltal. En vanlig lösning är att kombinera både medelvärdet och medianen: Skapa $k\cdot l$ hashfunktioner och dela upp dem i $k$ distinkta grupper (var och en av storleken $l$ ) . Inom varje grupp använd medelvärdet för att aggregera samman $l$ -resultaten, och ta slutligen medianen för $k$ -gruppens uppskattningar som den slutliga uppskattningen.

2007 års HyperLogLog -algoritm delar upp multiuppsättningen i delmängder och uppskattar deras kardinaliteter, sedan använder den det harmoniska medelvärdet för att kombinera dem till en uppskattning för den ursprungliga kardinaliteten.

Se även

Ytterligare källor

Rajaraman, Anand; Ullman, Jeffrey David (2011-10-27). Utvinning av massiva datamängder . Cambridge University Press . sid. 119. ISBN 9781139505345 . Hämtad 2014-11-09 .