Count-Min sketch

Penghitung frekuensi yang tidak menyimpan key. Tanyakan sudah berapa kali ia melihat sesuatu, dan jawabannya tidak pernah terlalu rendah — kadang terlalu tinggi, sebanyak yang Anda tentukan di muka.

Di mana ini benar-benar dipakai

Perangkat jaringan dan platform iklan memakainya untuk menemukan lalu lintas yang penting selagi ia masih mengalir lewat. Menyimpan satu counter per alamat IP pada kecepatan penuh itu mustahil; menyimpan grid counter berukuran tetap tidak — dan segelintir sumber yang mengirim paling banyak tetap menonjol di dalamnya.

Jaminannya

selaluTidak pernah underestimate: setiap estimasi sama dengan atau di atas count sebenarnya.
terbatasOverestimate paling banyak ε·N.dengan probabilitas 1−δ · w = ⌈e/ε⌉, d = ⌈ln 1/δ⌉

Estimasi tidak pernah di bawah count sebenarnya. Setiap baris hanya bisa melebihi, jadi mengambil minimum berarti seluruh d baris harus melebihi agar jawabannya salah — itulah sebabnya depth membeli confidence dan width membeli presisi.

Cara kerjanya

d baris × w kolom counter. Update menambah satu sel per baris. Estimasi adalah minimum di antara baris.

Cormode & Muthukrishnan, J. Algorithms 55(1), 2005

Mulai dari siniUbah stream ke Zipfian — data nyata itu miring, dan heavy hitter hanya ada di sana. Lalu baca tabel heavy hitter: setiap estimasi berada pada atau di atas count sebenarnya, tidak pernah di bawah.

Parameter

ε — faktor errorseberapa jauh estimasi boleh di atas kebenaran, sebagai bagian dari seluruh streamw = ⌈e/ε⌉δ — probabilitas gagalseberapa sering ia boleh lebih salah daripada itud = ⌈ln(1/δ)⌉

w — width

2,719

counter per baris — makin banyak kolom, makin ketat estimasinya

d — depth

baris independen — makin banyak baris, makin jarang estimasinya longgar

Stream

Distribusiseberapa sering item berulang — data nyata tidak pernah uniformRank r muncul dengan probabilitas ∝ 1/rˢ. Data nyata itu miring, dan heavy hitter hanya ada di sini.

Item distinctberapa banyak item berbeda yang tersedia untuk diambilPanjang streamberapa banyak item yang melewati struktur iniKemiringan (s)Seedmengubah 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.

Hasil bacaan

Berjalan…