HyperLogLograkenteita

HyperLogLog-rakenteet ovat probabilistisia tietorakenteita, joita käytetään suurten tietojoukkojen erilaisten alkioiden lukumäärän estimointiin. Ne tarjoavat tilatehokkaan tavan arvioida, kuinka monia eri arvoja joukossa esiintyy, ilman että kaikki alkiot tallennetaan erikseen. HyperLogLog-rakenteet soveltuvat erityisesti virta- ja suurdataprojekteihin, joissa nopeus ja muistitehokkuus ovat tärkeitä.

Toimintaperiaate: Jokainen alkio hajautetaan ja hajautusarvo jaetaan m rekisteriin. Rekisteriindeksi j valitaan hajautusarvon etuosi bitin perusteella, ja rekisteri M[j] päivitetään arvon maksimaalisen ρ(h) mukaan, missä ρ(h) on vasemmanpuoleisen ensimmäisen ykkösen sijainti binääriesityksessä. Kun kaikki alkiot on käsitelty, kartin lukumäärä estimoidaan kaavalla hat{n} = α_m m^2 / Σ_j 2^{-M[j]}, jossa α_m on m:stä riippuva vakio. Suhteellinen virhe on noin 1.04 / sqrt(m), ja m on rekisterien määrä (usein m = 2^b).

Parannukset ja variaatiot: HyperLogLog on kehitetty LogLog-rakenteesta parantamaan tarkkuutta ja muistinkäyttöä. HyperLogLog++ lisää pienille kartinileille tehtävää virhekorjausta ja käyttää tiiviimpää tallennusta sekä lineaarista laskentaa pienille arvoille. Näin saavutetaan parempi tarkkuus suurilla ja keskisuurilla datamäärillä sekä parempi skaalautuvuus.

Käyttökohteet ja rajoitukset: Käytetään laajasti verkkosivujen analytiikassa, verkkoliikenteen monitoroinnissa, tietovarastoinnissa ja massadatan deduplicointiongelmissa. Se tarjoaa nopean ja muistitehokkaan arvion, mutta ei ole tarkka; virhe riippuu rekisterien määrästä ja hajautusfunktiosta, eikä sitä voi pitää aukottomana korvauksena todelliselle kartinilteelle.