Bagaimanakah anda melaksanakan Count-Min Sketch untuk anggaran kekerapan penstriman?

1. Soalan

Platform pengelogan menerima kunci peristiwa seperti URL atau ID produk, yang berpotensi mencecah berbilion-bilion peristiwa. Laksanakan add(key) dan estimate(key) dengan memori tetap. Kembalikan anggaran bilangan kemunculan dan bincangkan ralat, penggabungan shard, limpahan pembilang, serta masa struktur tepat diperlukan.

2. Kekangan dan penjelasan

• Setiap peristiwa dilihat sekali; semua kunci tidak dapat dimuatkan dalam jadual cincangan.
• Anggaran berlebihan boleh diterima, dengan parameter yang mengawal kebarangkalian ralat.
• Mulakan dengan kemas kini bukan negatif; pemadaman, pemberat negatif, dan luput berasaskan masa memerlukan kekangan tambahan.
• Shard boleh digabungkan secara langsung hanya apabila lebar, kedalaman, benih cincangan, dan pengekodan pembilang adalah sepadan.

3. Pendekatan teras

Count-Min Sketch (CMS) mengekalkan d baris pembilang bukan negatif w. Setiap baris mempunyai fungsi cincangan bebas yang memetakan kunci kepada satu lajur. Sesuatu kemas kini meningkatkan setiap pembilang yang dipilih; pertanyaan mengembalikan pembilang terpilih yang minimum. Kiraan sebenar muncul dalam setiap baris yang dipilih, manakala perlanggaran daripada kunci lain hanya boleh menambah kepada pembilang, jadi nilai minimum ialah batas atas yang tidak terkurang kira.

Menggunakan ralat epsilon dan kebarangkalian kegagalan delta, pilihan biasa ialah w = ceil(e / epsilon) dan d = ceil(ln(1 / delta)). Dengan jumlah pemberat kemas kini N, anggaran adalah paling banyak kiraan sebenar ditambah epsilon * N dengan kebarangkalian sekurang-kurangnya 1 - delta. Ini ialah batas ralat kebarangkalian, bukan jaminan mutlak untuk setiap pertanyaan.

4. Pelaksanaan rujukan

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. Kerumitan dan ketepatan

Setiap kemas kini dan pertanyaan menyentuh sel d, jadi masa ialah O(d). Ruang ialah O(d * w), tidak bergantung pada bilangan kunci yang berbeza. Dengan kemas kini bukan negatif, nilai minimum kekal sekurang-kurangnya kekerapan sebenar. Menambah lebar mengurangkan bias perlanggaran; menambah kedalaman mengurangkan kebarangkalian melebihi batas ralat, manakala kedua-duanya meningkatkan memori dan kerja cincangan secara linear.

Pembilang memerlukan lebar integer yang mencukupi atau dasar ketepuan eksplisit; lilitan tak bertanda (unsigned wraparound) akan membatalkan sifat tiada pengurangan kiraan. Penggabungan shard menambah sel yang sepadan, dan semua pemetaan cincangan mesti sepadan. Menggabungkan reka letak yang berbeza menghasilkan keputusan yang tidak boleh ditafsirkan.

6. Tindakan susulan dan perangkap

• CMS menjawab anggaran kiraan kunci yang diketahui; ia tidak menyenaraikan K Teratas (Top-K). Simpan set calon atau gunakan struktur item kerap (heavy-hitter) untuk tujuan itu.
• Perlanggaran hanya melebihkan anggaran, jadi anggaran tersebut tidak boleh mendapatkan semula kekerapan tepat atau set berbeza yang tepat.
• Kemas kini negatif memecahkan kemonotonan dan pembuktian mudah; pemadaman dan tetingkap gelongsor biasanya memerlukan baldi masa atau struktur yang menyusut (decaying).
• Tetingkap masa tidak boleh dikekalkan dengan menolak jumlah lama melainkan keadaan baldi yang mampu undur balik (rollback) dikekalkan.

7. Bacaan lanjut

Bandingkan CMS dengan peta cincangan tepat, penapis Bloom, HyperLogLog, dan Frequent Items Sketch: masing-masing disasarkan untuk pertanyaan kekerapan, keahlian, kekardinalan, dan pengenalpastian item kerap. Pilih berdasarkan pertanyaan, belanjawan ralat, keperluan pemadaman, dan sama ada kunci calon mesti dikeluarkan.

8. Mata pemarkahan temu duga

Boleh menerangkan matriks pembilang

Calon harus menerangkan cincangan baris bebas, mengemas kini setiap baris, mengambil nilai minimum, dan sebab perlanggaran hanya boleh menaikkan pembilang.

Boleh menyatakan parameter ralat

Mereka harus menghubungkan epsilon, delta, w, d, dan jumlah pemberat N, membezakan batas kebarangkalian daripada jaminan tepat yang mutlak.

Boleh mengendalikan batasan kejuruteraan

Mereka harus merangkumi limpahan pembilang, keserasian parameter shard, penambahan mengikut sel, dan reka bentuk tambahan untuk pemberat negatif atau tetingkap gelongsor.

Boleh memilih struktur yang sepadan

Mereka harus menyedari bahawa CMS tidak menyediakan Top-K, senarai keahlian yang tepat, atau kekardinalan yang tepat, dan beralih kepada peta tepat, HLL, atau struktur item kerap apabila keperluan berubah.