HyperLogLog

Penghitung nilai berbeda yang tidak menyimpan satu pun di antaranya. Ia menjawab “berapa banyak yang berbeda?” dengan ketelitian sekitar satu persen, memakai memory yang tidak ikut membesar bersama jawabannya.

Di mana ini benar-benar dipakai

Redis menyediakannya sebagai tipe bawaan, dan Google, Presto, serta Elasticsearch semuanya memakainya. Menghitung pengunjung unik dengan set exact memakan memory sebanding dengan jumlah pengunjungnya; HyperLogLog menghitungnya dalam sekitar 12 KB, entah ada sepuluh ribu atau sepuluh miliar.

Jaminannya

Standard error ≈ 1.04/√m. Nilai register tidak pernah turun.

Cara kerjanya

Ia tidak menyimpan item. Ia menyimpan runtun nol terpanjang yang terlihat di setiap register, beralasan bahwa runtun panjang itu langka, lalu menghitung nilai distinct dari situ.

Flajolet, Fusy, Gandouet & Meunier, AofA 2007

Mulai dari siniKalikan panjang stream dengan sepuluh dan perhatikan dua angka: estimasinya ikut naik mengejar count sebenarnya, dan angka memory-nya tidak bergerak sama sekali. Itulah seluruh triknya.

Stream

Distribusiseberapa sering item berulang — data nyata tidak pernah uniformItem distinct tanpa pengulangan. Kasus terburuk untuk fill ratio pada m tertentu.

Item distinctberapa banyak item berbeda yang tersedia untuk diambilPanjang streamberapa banyak item yang melewati struktur iniSeedmengubah hash, dan karenanya item mana yang kebetulan bertabrakan

Tautan ini membawa stream dan seluruh parameter. Tanpa server, tanpa akun — state-nya ikut di dalam URL.

Parameter

seluruh biaya memory-nya, satu byte per register, berapa pun item yang datang

m — registerp=12 · m=4,096 · 4.0 KiB

Register selalu pangkat dua, karena indeksnya diambil dari p bit teratas hash. Register empat kali lipat memangkas error menjadi separuh.