Perkirakan kardinalitas dan item teratas

Pertanyaan

Bagaimana menghitung jumlah item berbeda dan item terpopuler pada aliran besar tanpa menyimpan semuanya?

Setelah baca ini, kamu bisa memilih set eksak, HyperLogLog, Count-Min Sketch, atau algoritma top-k untuk satu pertanyaan, dan menyebut arah serta besar galatnya.

Prasyarat dan contoh

Kamu sudah membaca M12.03 (Bloom filter) dan paham hash. Kamu juga tahu bahwa ukuran struktur eksak tumbuh mengikuti jumlah item.

Dua pertanyaan yang sering dicampur:

• Kardinalitas: berapa pengunjung unik hari ini?
• Frekuensi: berapa kali tiap tautan diklik, dan mana 10 teratas?

Contoh: 200 juta event klik per hari dari sekitar 50 juta pengunjung unik dan 20 juta tautan. Set eksak untuk pengunjung unik, dengan 16 byte per ID, sekitar 800 MB per hari per dimensi. Kalau dasbor ingin unik per tautan, per negara, per jam, jumlah set meledak. Di titik itu, galat 1-2% yang dinyatakan jelas lebih berguna daripada angka eksak yang tidak sanggup dihitung.

Mekanisme

Set eksak. Hash set atau tabel. Jawaban pasti, memori sebanding dengan jumlah unik. Pakai kalau jumlahnya kecil (jutaan) atau kalau angka dipakai untuk penagihan dan audit.

HyperLogLog (HLL), untuk kardinalitas. Hash tiap item, pakai sebagian bit untuk memilih register, dan di tiap register simpan posisi 1 terdepan terpanjang yang pernah terlihat. Estimasi dihitung dari semua register. Dengan m = 2^14 = 16.384 register, memorinya sekitar 12 KB dan galat standarnya sekitar 1,04/√m ≈ 0,8%, berapa pun jumlah item unik (miliaran tetap 12 KB). Dua HLL digabung dengan mengambil maksimum per register, hasilnya sama seperti kalau satu HLL melihat kedua aliran. Dengan begitu unik per jam bisa digabung jadi unik per hari tanpa dihitung ulang. Yang tidak bisa dilakukan: mengeluarkan item, atau mengetahui item mana yang sudah ada.

Count-Min Sketch (CMS), untuk frekuensi. Matriks d baris × w kolom. Tiap item menambah satu counter per baris (kolom dipilih hash berbeda tiap baris). Estimasi frekuensi adalah minimum dari d counter itu. Karena tabrakan hanya menambah, estimasi tidak pernah lebih kecil dari nilai sebenarnya: galatnya selalu ke atas. Dengan w = ⌈e/ε⌉ dan d = ⌈ln(1/δ)⌉, estimasi melebihi nilai sebenarnya paling banyak ε × N dengan probabilitas 1 - δ, dengan N total event. Contoh: ε = 0,001 dan δ = 0,01 memberi w = 2.719, d = 5, sekitar 13.600 counter, kurang dari 60 KB pada 4 byte per counter. Dua CMS berukuran sama digabung dengan menjumlahkan counter.

Top-k. CMS menjawab "berapa kali item X?", bukan "item apa yang teratas?", karena ia tidak menyimpan daftar item. Cara umumnya: simpan CMS untuk estimasi ditambah heap kecil berisi k kandidat. Alternatif tanpa CMS adalah Space-Saving atau Misra-Gries: simpan k counter beserta item-nya, dan item baru menggantikan counter terkecil. Galat kecil untuk item berat dan besar untuk item di sekitar batas.

Saat rancangan ini gagal

• Galat relatif pada angka kecil. HLL 0,8% pada 10 juta unik berarti sekitar 80.000. Itu bagus. Tapi pada 50 unik, library yang bagus memakai mode eksak atau koreksi untuk jumlah kecil. Pastikan implementasimu melakukannya, jangan asumsikan.
• CMS dan ekor panjang. Galat tambahan ε × N itu absolut. Dengan N = 200 juta dan ε = 0,001, kamu bisa melebihkan sampai 200.000. Untuk tautan yang diklik 300 kali, estimasinya bisa kacau. CMS bagus untuk item berat, buruk untuk item jarang.
• Menggabungkan sketch yang parameternya beda. HLL dengan jumlah register berbeda atau CMS dengan lebar atau seed hash berbeda tidak bisa digabung dengan benar. Tulis parameter di samping data yang tersimpan.
• Irisan dari HLL. Gabungan itu mudah. Irisan (pengunjung yang ada di A dan B) harus diturunkan lewat inklusi-eksklusi dan galatnya melebar tajam kalau irisan kecil dibanding himpunannya.
• Memakai estimasi untuk uang. Angka penagihan atau kuota harus eksak, atau galatnya harus disepakati secara tertulis dengan pihak yang terdampak.

Latihan

Dasbor perlu: (a) pengunjung unik per tautan per jam untuk 20 juta tautan, (b) 10 tautan teratas per hari secara global, (c) jumlah klik tepat untuk satu tautan yang sedang ditagih ke pengiklan.

1. Pilih struktur untuk masing-masing dan sebutkan galatnya.
2. Berapa memori HLL untuk (a) dengan 12 KB per HLL, kalau hanya 2% tautan yang aktif per jam?
3. Bagaimana menghitung unik per hari dari 24 HLL per jam?

Lihat pembahasan+

1. (a) HLL per tautan: galat standar sekitar 0,8%, bisa lebih besar di unik kecil. (b) Space-Saving dengan misalnya k = 1.000 counter, atau CMS plus heap: tautan teratas yang berat akurat, tautan di batas peringkat ke-10 bisa tertukar. (c) Counter eksak dari event ber-ID, karena ini uang: tidak ada galat yang boleh diterima.
2. 2% dari 20 juta = 400.000 HLL aktif. 400.000 × 12 KB = sekitar 4,8 GB per jam. Masih berat kalau semua disimpan. Karena itu simpan HLL hanya untuk tautan aktif, atau pakai representasi sparse HLL untuk tautan dengan sedikit unik (library yang baik mengecilkan HLL kecil jadi beberapa ratus byte).
3. Ambil maksimum per register dari 24 HLL, lalu estimasi dari hasilnya. Hasilnya setara satu HLL yang melihat seluruh hari, jadi pengunjung yang datang di dua jam berbeda tidak dihitung dua kali. Menjumlahkan 24 estimasi per jam akan menghitung ganda.

Terkait

• Sebelumnya: M12.03 Gunakan pemeriksaan keanggotaan aproksimatif.
• Lanjut ke M12.05 Perkirakan distribusi.
• Proyek B09 (satu cardinality sketch dan tes merge) belum tersedia.
• Rancangan D13 belum tersedia.

Catatan

• Asumsi: hash seragam, dan sketch dengan parameter yang sama dipakai di semua node.
• Yang nggak dibahas: HLL++ dan koreksi bias, sketch untuk irisan (theta sketch), dan sliding window.
• Rumus galat adalah hasil standar. Implementasi nyata punya koreksi untuk nilai kecil.
• Terakhir ditinjau: 26 Oktober 2026.