Bagaimana cara mengimplementasikan Count-Min Sketch untuk estimasi frekuensi streaming?

1. Pertanyaan

Sebuah platform pencatatan log menerima kunci peristiwa seperti URL atau ID produk, yang berpotensi mencapai miliaran peristiwa. Implementasikan add(key) dan estimate(key) dengan memori tetap. Kembalikan perkiraan jumlah kemunculan dan diskusikan galat, penggabungan shard, luapan pencacah (counter overflow), dan kapan struktur eksak diperlukan.

2. Batasan dan klarifikasi

• Setiap peristiwa dilihat sekali; semua kunci tidak dapat dimuat dalam tabel hash.
• Estimasi berlebih (overestimation) dapat diterima, dengan parameter yang mengontrol probabilitas galat.
• Mulailah dengan pembaruan non-negatif; penghapusan, bobot negatif, dan kedaluwarsa berbasis waktu memerlukan batasan tambahan.
• Shard hanya dapat digabungkan secara langsung jika lebar, kedalaman, seed hash, dan pengodean pencacah cocok.

3. Pendekatan utama

Count-Min Sketch (CMS) menyimpan d baris dari w pencacah non-negatif. Setiap baris memiliki fungsi hash independen yang memetakan kunci ke satu kolom. Sebuah pembaruan menaikkan nilai setiap pencacah yang dipilih; sebuah kueri mengembalikan nilai minimum dari pencacah yang dipilih. Jumlah sebenarnya muncul di setiap baris yang dipilih, sementara tabrakan (collisions) dari kunci lain hanya dapat menambah nilai pencacah, sehingga nilai minimumnya adalah batas atas yang tidak pernah menghitung kurang (undercount).

Menggunakan galat epsilon dan probabilitas kegagalan delta, pilihan umumnya adalah w = ceil(e / epsilon) dan d = ceil(ln(1 / delta)). Dengan total bobot pembaruan N, estimasinya paling banyak adalah jumlah sebenarnya ditambah epsilon * N dengan probabilitas setidaknya 1 - delta. Ini adalah batas galat probabilistik, bukan jaminan mutlak untuk setiap kueri.

4. Implementasi referensi

init(epsilon, delta):
  w = ceil(e / epsilon)
  d = ceil(ln(1 / delta))
  table = array(d, w, fill=0)
  seeds = choose_d_independent_seeds()

add(key, weight=1):
  require weight >= 0
  for row in 0..d-1:
    col = hash(key, seeds[row]) mod w
    table[row][col] += weight
  total += weight

estimate(key):
  values = []
  for row in 0..d-1:
    col = hash(key, seeds[row]) mod w
    values.append(table[row][col])
  return min(values)

merge(other):
  require same w, d, seeds, counter encoding
  for each cell (r, c):
    table[r][c] += other.table[r][c]
  total += other.total

5. Kompleksitas dan kebenaran

Setiap pembaruan dan kueri menyentuh d sel, sehingga waktunya adalah O(d). Ruang memori adalah O(d * w), tidak bergantung pada jumlah kunci yang berbeda (distinct keys). Dengan pembaruan non-negatif, nilai minimum tetap setidaknya sebesar frekuensi sebenarnya. Menambah lebar mengurangi bias tabrakan; menambah kedalaman menurunkan probabilitas melampaui batas galat, sementara keduanya meningkatkan memori dan kerja hash secara linier.

Pencacah membutuhkan lebar bilangan bulat yang memadai atau kebijakan saturasi eksplisit; wraparound tak bertanda akan membatalkan sifat tidak menghitung kurang (no-undercount). Penggabungan shard menjumlahkan sel-sel yang bersesuaian, dan semua pemetaan hash harus cocok. Menggabungkan tata letak yang berbeda menghasilkan hasil yang tidak dapat diinterpretasikan.

6. Tindak lanjut dan jebakan

• CMS menjawab perkiraan jumlah dari kunci yang diketahui; CMS tidak mengenumerasi Top-K. Simpan kumpulan kandidat atau gunakan struktur heavy-hitter untuk hal tersebut.
• Tabrakan hanya menghasilkan estimasi berlebih, sehingga estimasi tersebut tidak dapat memulihkan frekuensi eksak atau himpunan unik yang eksak.
• Pembaruan negatif merusak monotonisitas dan bukti sederhananya; penghapusan dan sliding window biasanya memerlukan time bucket atau struktur yang meluruh (decaying structure).
• Jendela waktu (time window) tidak dapat dipertahankan dengan mengurangi total lama kecuali status bucket yang mendukung rollback dipertahankan.

7. Bacaan lebih lanjut

Bandingkan CMS dengan hash map eksak, Bloom filter, HyperLogLog, dan Frequent Items Sketch: mereka masing-masing menargetkan kueri frekuensi, keanggotaan, kardinalitas, dan identifikasi heavy-hitter. Pilihlah berdasarkan jenis kueri, batas toleransi galat, kebutuhan penghapusan, dan apakah kunci kandidat harus dikeluarkan.

8. Poin penilaian wawancara

Mampu menjelaskan matriks pencacah

Kandidat harus mendeskripsikan hash baris independen, pembaruan pada setiap baris, pengambilan nilai minimum, dan mengapa tabrakan hanya dapat menaikkan nilai pencacah.

Mampu menyatakan parameter galat

Mereka harus menghubungkan epsilon, delta, w, d, dan total bobot N, membedakan batas probabilitas dari jaminan eksak yang mutlak.

Mampu menangani batasan rekayasa

Mereka harus mencakup luapan pencacah (counter overflow), kompatibilitas parameter shard, penambahan per sel, dan rancangan tambahan untuk bobot negatif atau sliding window.

Mampu memilih struktur yang cocok

Mereka harus menyadari bahwa CMS tidak menyediakan Top-K, daftar keanggotaan eksak, atau kardinalitas eksak, dan beralih ke map eksak, HLL, atau struktur heavy-hitter saat kebutuhan berubah.