Algoritme Baru untuk Menghitung Jumlah Item Unik secara Efisien

• Algoritme CVM memperkirakan jumlah item berbeda dalam stream data yang panjang, sehingga dapat mengestimasi jumlah item unik tanpa menyimpan seluruh daftar
• Berfokus pada masalah elemen berbeda (distinct elements problem), ketika seluruh input melebihi memori, dan dapat diterapkan pada log skala besar atau stream peristiwa yang memiliki banyak input duplikat
• Dengan hanya menyisakan sebagian item dalam memori terbatas dan berulang kali melakukan penghapusan acak setiap kali ruang penuh, algoritme ini menyamakan probabilitas tiap item untuk tetap tersimpan
• Dalam contoh Hamlet, dengan memori 100 kata, rata-rata dari 5 kali percobaan mengestimasi 3.955 kata, mendekati jumlah kata unik sebenarnya yaitu 3.967; dengan memori 1.000 kata, rata-ratanya membaik menjadi 3.964
• Semakin besar memori, semakin tinggi akurasinya; jika cukup untuk menampung semua item unik, akurasi 100% juga memungkinkan

---

Menghitung Item Unik dalam Stream Data Panjang

• Tujuannya adalah mengestimasi secara efisien jumlah item unik setelah duplikat dihapus dari daftar panjang yang itemnya masuk satu per satu
• Cara paling sederhana adalah menyimpan semua item yang sudah dilihat sejauh ini, lalu membandingkan setiap item baru dengan daftar yang ada
  • Dalam survei satwa liar, perlu terus memeriksa daftar foto hewan yang sudah pernah dilihat
  • Jika daftarnya mencapai miliaran, seperti jumlah pengguna login harian Facebook, penyimpanan dan perbandingannya menjadi sulit
• CVM adalah algoritme yang namanya diambil dari Sourav Chakraborty, Vinodchandran Variyam, dan Kuldeep Meel
• Algoritme ini dapat diterapkan pada daftar item yang masuk secara berurutan, seperti kata, produk di ban berjalan, atau kendaraan di jalan raya

Ide Inti Algoritme CVM

• CVM tidak menyimpan semua item, melainkan hanya mempertahankan sebagian item yang muat dalam memori terbatas
• Algoritme ini menggunakan keacakan untuk mengendalikan probabilitas tiap item unik tetap berada di daftar akhir
• Andrew McGregor menilai algoritme ini sangat sederhana dan mudah diimplementasikan, sehingga bisa menjadi pendekatan dasar untuk masalah item unik di dunia nyata

Cara Kerjanya dalam Contoh Hamlet

• Hamlet memiliki total 30.557 kata, dan algoritme ini mengestimasi jumlah kata unik di antaranya
• Jika memorinya diasumsikan sebagai papan tulis berkapasitas 100 kata, pada awalnya algoritme melewati kata yang berulang dan menuliskan 100 kata unik pertama
• Ketika ruang penuh, algoritme melempar koin untuk setiap kata
  • Jika sisi depan, kata dipertahankan
  • Jika sisi belakang, kata dihapus
  • Setelah tahap awal ini, sekitar 50 kata unik tersisa

Syarat Bertahan yang Makin Ketat di Tiap Putaran

• Pada Round 1, kata baru terus ditambahkan, dan jika kata yang sudah ada di daftar muncul lagi, koin dilempar lalu kata dihapus jika hasilnya sisi belakang
• Ketika daftar kembali berisi 100 kata, sekitar separuhnya dihapus berdasarkan hasil 100 lemparan koin, dan Round 1 berakhir
• Mulai Round 2, kata menjadi lebih sulit untuk bertahan
  • Jika kata berulang muncul, kata dihapus jika hasil lemparan koin sisi belakang
  • Jika hasilnya sisi depan, koin dilempar sekali lagi, dan kata hanya dipertahankan jika lemparan kedua juga sisi depan
• Pada putaran ketiga, diperlukan sisi depan 3 kali berturut-turut; pada putaran keempat, diperlukan 4 kali berturut-turut
• Secara umum, ketika putaran ke-k berakhir, probabilitas tiap kata tetap tersimpan menjadi 1/2^k

Perhitungan Estimasi dan Hasil Eksperimen

• Jumlah kata yang tersisa di daftar akhir dibagi dengan probabilitasnya untuk tetap tersimpan, sehingga jumlah total kata unik dapat diestimasi
• Misalnya, jika setelah 6 putaran tersisa 61 kata, dengan membaginya menggunakan probabilitas 1/2^6, diperoleh estimasi 3.904 kata
• Jumlah kata unik sebenarnya dalam Hamlet adalah 3.967
• Semakin besar ukuran memori, estimasinya semakin mendekati nilai sebenarnya
  • Dengan memori 100 kata, nilai estimasi rata-rata dari 5 kali eksekusi adalah 3.955
  • Dengan memori 1.000 kata, nilai estimasi rata-ratanya adalah 3.964
• Variyam dan rekan-rekannya membuktikan secara matematis bahwa akurasi teknik ini meningkat seiring ukuran memori

Solusi Sederhana tetapi Tidak Sepele

• CVM dinilai sebagai kemajuan penting dalam masalah item unik yang telah diteliti selama lebih dari 40 tahun
• William Kuszmaul menilai bahwa bahkan untuk masalah yang sangat mendasar dan telah banyak diteliti, masih bisa ada solusi yang sederhana tetapi sulit terpikirkan

[GN⁺]

Komentar Hacker News

• Saya ikut bekerja dengan para penulis pada implementasi versi penghitungan volume DNF dari algoritme ini. Tulisan terkait ada di sini: https://www.msoos.org/2023/09/pepin-our-probabilistic-approx...
  Kodenya ada di sini: https://github.com/meelgroup/pepin
  Algoritmenya sangat cepat sampai-sampai kadang 30% dari total waktu habis untuk I/O pembacaan file. Sebagai referensi, Knuth juga berkontribusi pada algoritme ini, dan catatannya ada di sini: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
  Ia mengambil sebulan penuh dari pekerjaannya di TAOCP untuk mengerjakan ini, dan dia benar-benar sehebat yang bisa dibayangkan

  • Sangat menarik, dan saya sangat tertarik pada orang-orang yang berbakat luar biasa. Saya penasaran kenapa Knuth terasa begitu hebat. Apakah ada momen khusus, apakah karena kecepatan memahami ide, atau karena kemampuannya menjelaskan dengan mudah
  • Ini terlihat bodoh. Sangat bodoh, apakah saya melewatkan sesuatu? Ini bukan menghitung melainkan hanya sampling, dan jika Anda benar-benar ingin menghitung semua kata yang berbeda, tampaknya penggunaan memorinya tidak berbeda dibanding sekadar menghitungnya
  • Mungkin Anda tahu, tapi saya penasaran kenapa tidak memilih pendekatan mengurutkan agar hitungan yang lebih besar diprioritaskan lalu membuang separuh bawah saat penuh. Mungkin bagi orang lain ini obvious, tapi saya ingin tahu alasannya
  • Saya penasaran apa kasus penggunaan utama algoritme ini
  • Nah, sekarang ada seseorang yang bisa disalahkan atas tertundanya terbitan buku Knuth berikutnya :)

• Algoritme ini tampak mirip dengan HyperLogLog yang juga dikutip dalam makalahnya. Ia memakai wawasan yang sama untuk melacak kemunculan beruntun sisi depan/belakang koin guna memperoleh estimasi, tetapi idenya dibalik menjadi algoritme yang lebih sederhana dengan membuang nilai yang diingat berdasarkan rangkaian hasil lemparan koin
  Ini bekerja sangat efisien terutama dalam konteks streaming, sehingga Anda bisa mempertahankan semacam “counter” untuk menghitung jumlah elemen unik meski ada tingkat galat
  Kelebihan HyperLogLog adalah dalam beberapa hal ia bertindak seperti himpunan hash. Anda bisa menambahkan item, menghitung jumlah item unik, dan yang penting, menggabungkan dua HLL untuk membentuk union, sambil menjaga penggunaan memori tetap beberapa KB meski pada himpunan berisi miliaran item. Penyimpanan data terdistribusi memakai trik ini pada cardinality agg di Elasticsearch/OpenSearch, serta PFADD/PFMERGE/PFCOUNT di Redis/Redict
  Saya tidak benar-benar tahu bagaimana tepatnya algoritme CVM dibandingkan dengan HLL, tetapi karena sudah ditinjau oleh Knuth dan katanya mudah diimplementasikan bahkan oleh mahasiswa S1, sepertinya ini algoritme yang cukup bagus

  • HLL bisa mengestimasi baik union maupun intersection dari dua HLL, jadi bisa juga dipakai untuk estimasi kardinalitas join
    http://oertl.github.io/hyperloglog-sketch-estimation-paper/
  • Struktur data ini juga bisa digabungkan. Jika “round” dari dua instans yang akan digabung berbeda, Anda cukup memajukan yang berada di round lebih awal sebanyak selisih round-nya. Artinya, membuang separuh secara acak. Setelah itu, masukkan nilai dari satu daftar ke daftar lain dan abaikan duplikat. Jika hasilnya terlalu besar, Anda bisa membuang separuh secara acak dan menaikkan nomor round
    Di pekerjaan saya sebelumnya, saya mengimplementasikan algoritme ini persis seperti itu, tetapi juga menyimpan estimasi berapa kali tiap nilai muncul di samping nilainya. Berkat itu, kami bisa membuat daftar perkiraan nilai yang paling sering muncul beserta estimasi hitungannya untuk masing-masing nilai
  • Dari ingatan lama waktu kuliah, saya jadi penasaran, apa hubungan HLL dan CVM yang dibahas di sini dengan reservoir sampling yang pernah saya pelajari dulu?
    Saat dulu bekerja di rumah sakit, saya pernah memakai reservoir sampling untuk membuat subset kecil dari record yang disimpan di tape DAT

• Membaca makalah ini memakan waktu hampir sama seperti membaca tulisan blognya, dan makalahnya lebih bermanfaat.
  https://arxiv.org/pdf/2301.10191
  Isinya tentang memperkirakan kardinalitas himpunan elemen yang muncul dari sebuah stream. Algoritmenya begitu sederhana sehingga sambil membaca makalahnya kita bisa langsung mencoba mengodingnya dan memainkannya.
  Para penulis dengan jelas menyatakan bahwa pembaca sasaran dan tujuan algoritme ini adalah mahasiswa S1 dan buku teks.

  • Subjudul makalah, “An Algorithm for the (Text) Book”, tampaknya merujuk pada ungkapan terkenal Paul Erdős tentang pembuktian yang “berasal dari The Book” karena kesederhanaan dan keindahannya begitu anggun.
    Karena Knuth meninjaunya sendiri, mungkin ia juga menilai algoritme ini termasuk jenis seperti itu. Kalau begitu, memasukkannya ke judul memang terdengar seperti sesumbar yang tidak rendah hati, tetapi memang pantas untuk dibanggakan.
    Awalnya saya ingat ungkapan itu berasal dari Knuth, tetapi ingatan saya salah.
  • Tulisan blognya lebih dari separuh isinya hanya padding. Tapi justru itu hal yang baik: algoritmenya terlalu sederhana untuk dijadikan tulisan blog yang panjang.
  • Saya setuju bahwa makalahnya lebih baik daripada tulisan blog, tetapi satu kritik saya terhadap makalah CVM adalah bahwa ia punya kondisi terminasi. Catatan Knuth tentang CVM yang disebut di thread lain hanya memakai loop agar ruang tambahan muncul pada tahap mengurangi reservoir menjadi setengah.
    Menulis loop tampaknya tidak serumit menjelaskan https://en.wikipedia.org/wiki/Up_tack. [1]
    [1] https://news.ycombinator.com/item?id=40388878
  • Dulu saya belajar ilmu komputer, tetapi entah karena otak saya sudah menipis, ini terasa lebih membingungkan dari yang perlu.
    Pertama, penanganan contradiction itu tampaknya cuma error atau panic biasa, jadi saya tidak paham kenapa ditulis seperti itu. Lalu asumsi 1..m juga membingungkan. Saya sempat tidak yakin apakah ukuran harus diketahui sebelumnya atau tidak, tetapi setelah dibaca lagi tampaknya tidak. Kita memilih ambang batas dan probabilitasnya berubah sesuai ukuran stream, tetapi penjelasan algoritmenya ditulis seolah-olah hanya punya satu keluaran, jadi membingungkan.
    Batas Chernoff dan delta/epsilon juga sama sekali tidak dijelaskan di makalah, jadi makin membingungkan. Kode Go yang saya buat ada di sini: https://github.com/betamos/distinct
    Jauh lebih masuk akal jika bagian terkait ambang batas dipisahkan ke helper, daripada tidak sengaja mengalokasikan memori terlalu banyak. Sepertinya juga perlu ada metode untuk memperkirakan tingkat kepercayaan atau laju galat. Karena tidak ada yang tahu ukuran stream sebelumnya, terasa lebih alami kalau nilai ini diperbarui sambil berjalan.
  • Kalau ungkapan “untuk mahasiswa S1 dan buku teks” bukan berarti cukup sederhana untuk mereka gunakan, melainkan benar-benar hanya berguna di sana, saya ingin ada penjelasan mengapa itu tidak berguna bagi para ahli tetapi berguna bagi mahasiswa S1.

• Mengingat topik makalahnya, catatan kakinya terasa sangat menarik.
  Para penulis memilih urutan acak alih-alih kebiasaan lama mengurutkan nama penulis secara alfabetis, dan menandainya dengan r⃝. Catatan yang dapat diverifikasi secara publik tentang pengacakan itu ada di sini: https://www.aeaweb.org/journals/policies/random-author-order...
  [0]: https://arxiv.org/pdf/2301.10191

• Bukankah penjelasan algoritmenya salah?
  Jika kita mengimplementasikan sesuai penjelasan “saat menemukan kata yang sudah ada dalam daftar, lempar koin lagi, dan jika sisi belakang muncul, hapus kata itu”, yaitu “cek apakah ada di daftar lalu hapus”, hasilnya setelah sekitar 20 iterasi menjadi estimasi aneh seperti 772800512.
  Sebaliknya, jika kata itu disimpan terlebih dahulu lalu kata yang sama dihapus, hasilnya menjadi 7240, dekat dengan jumlah kata unik sebenarnya yaitu 7233. Jadi urutannya penting dalam penjelasan, tetapi tampaknya tersampaikan secara keliru.

  • Saya mengalami masalah yang sama. Jika diimplementasikan hanya dari penjelasan Quanta Magazine tanpa melihat makalah arxiv-nya, saya selalu mendapatkan estimasi seperti 461746372167462146216468796214962164.
    Setelah membaca makalahnya, saya mendapatkan estimasi yang benar, dan masalahnya hanyalah satu else kecil. Penjelasan Quanta terbaca seperti “jika tidak ada di daftar, tambahkan; jika tidak, hapus dengan probabilitas tertentu”, tetapi implementasi yang benar adalah menerapkan kondisi probabilitas itu sesudahnya tanpa peduli apakah ditambahkan atau tidak.
  • Saya baru saja mencoba memecahkannya lalu datang ke sini untuk melihat apakah orang lain mengalami masalah yang sama, dan ternyata iya. Jika mengikuti penjelasannya, hasilnya salah; implementasinya harus menambahkan nilai baru di setiap ronde, lalu memangkas secara probabilistik, dan ketika memori mencapai batas, menghapus separuh acak dari seluruh himpunan.

• Memperkirakan jumlah elemen unik dalam sebuah himpunan dan menghitung jumlah elemen unik dalam sebuah himpunan adalah dua hal yang sangat berbeda. Metodenya keren, tetapi judulnya kurang bagus.

  • Tidak sebegitu berbeda. Semua cara menghitung di dunia nyata memiliki tingkat galat yang tidak nol, jadi dalam kebanyakan konteks kedua istilah itu dipakai bergantian.
    Misalnya, dalam pemilu kita berkata “menghitung suara”, tetapi kalau hasilnya ketat kita melakukan “penghitungan ulang”, dan orang sangat wajar mengharapkan angka yang sedikit berbeda dari hitungan awal. Kalau begitu, penghitungan suara sebenarnya juga merupakan estimasi, dan penghitungan ulang hanyalah estimasi dengan batas galat yang lebih sempit.
    Mitos “countless stones” (https://en.wikipedia.org/wiki/Countless_stones) juga terasa seperti pengingat folkloris agar kita tidak terlalu yakin bahwa bahkan sesuatu yang besar, keras, dan statis seperti batu tegak pun sudah benar-benar dihitung dengan tepat.
    Kasus ketika menghitung bukan estimasi kurang lebih terbatas pada situasi matematis: ketika kita bisa menjamin bahwa semua item telah ditangani tanpa ada yang terlewat, dan identitas item mana pun tidak tertukar dengan yang lain.
  • Untuk bilangan yang relatif kecil, itu benar. Tetapi untuk bilangan yang sangat besar, biasanya estimasi diperlakukan setara dengan penghitungan, dan hasilnya pun sering dinyatakan bukan sebagai bilangan bulat melainkan dalam notasi ilmiah, yaitu seperti bilangan floating-point.
    Misalnya, mol adalah bilangan bulat, tetapi nilainya hanya diketahui secara hampiran, dan tidak ada yang peduli pada nilai tepatnya.
  • Ini bukan estimation, melainkan approximation.

• Saya sangat suka contoh berpikir di luar kebiasaan seperti ini. Mungkin juga karena secara profesional ini memang bukan bagian yang paling saya kuasai. Penting bukan hanya mempelajari cara yang benar untuk menyelesaikan masalah, tetapi juga proses menemukan pertanyaan yang membuat masalah yang kita miliki menjadi lebih mudah, atau kadang bahkan memungkinkan untuk diselesaikan
  Di sini, inti pertanyaannya adalah, “kita tidak membutuhkan angka yang persis, cukup menetapkan rentang probabilistik dalam parameter yang sudah didefinisikan.” Untuk masalah lain, mungkin ada pertanyaan yang berbeda. Saya berharap dengan melihat cukup banyak contoh seperti ini, kita bisa menginternalisasi proses berpikirnya lalu menerapkannya dengan tepat

  • Kalau mau adil, ini adalah pekerjaan tim peneliti universitas. Secara harfiah, mereka adalah tim orang-orang yang bisa menghabiskan sepanjang hari meninjau satu topik dengan metode ilmiah berulang-ulang
    Jika di perusahaan besar ada insinyur-insinyur yang sama cerdasnya dan dibayar untuk duduk di depan whiteboard sepanjang hari, mereka pasti juga bisa menghasilkan sesuatu yang bagi kebanyakan orang tampak seperti “solusi di luar kebiasaan”
    Namun kebanyakan dari kita dibayar untuk bekerja di lini pabrik JIRA, jadi waktu untuk bereksperimen pada satu masalah saja memang terbatas
  • Sepertinya ini biasanya disebut berpikir lateral. Edward de Bono menulis beberapa buku tentang ini, dan mungkin menarik untuk dibaca

• Contoh “bagaimana jika Anda ingin menghitung jumlah pengguna berbeda yang login setiap hari di Facebook, dan sebagian pengguna login dari banyak perangkat pada banyak waktu?” rasanya bukan contoh situasi nyata yang terlalu berguna untuk algoritma ini
  Jika saat merancang proses login Anda sudah tahu informasi ini akan dibutuhkan, caranya sederhana. Simpan tanggal login terakhir untuk tiap akun, lalu tingkatkan penghitung pengguna unik hanya ketika nilai yang tersimpan berbeda dari tanggal saat ini
  Bahkan jika tidak begitu pun, nanti Anda tetap bisa menganalisisnya dengan “memutar ulang” aliran event login dari database. Mungkin berbeda ceritanya jika data selama bertahun-tahun sudah telanjur menumpuk

  • Pendekatan itu harus melacak “tanggal login terakhir tiap akun”, jadi membutuhkan memori sebesar jumlah pengguna. Inti algoritma ini adalah melakukannya dengan memori yang jauh lebih kecil dan tetap

• Soal penghitungan, saya ingin menyebut algoritma yang efisien dan juga mudah diimplementasikan untuk menemukan k item teratas dalam sebuah stream. Sepertinya algoritma ini kurang dikenal dibanding yang semestinya
  A Simple Algorithm for Finding Frequent Elements in Streams and Bags
  Karp, Shenker & Papadimitriou
  https://www.cs.umd.edu/~samir/498/karp.pdf

  • Frasa “k item teratas dalam stream” terdengar berbeda dari penjelasan di abstraknya. Abstraknya mengatakan bahwa algoritma ini menemukan simbol yang frekuensinya lebih tinggi dari ambang tertentu dalam deretan simbol yang sangat panjang dari alfabet besar
    Penjelasan Anda terdengar seperti mencari sejumlah item tetap sebanyak k dan seolah memberi jaminan bahwa item-item itu memang yang paling atas. Sementara abstraknya terdengar seperti mencari item-item yang memenuhi kondisi lebih besar dari nilai k tertentu, dengan jumlah item yang tidak diketahui sebelumnya
    Ini terasa seperti perbedaan antara “mencari 100 pengguna tertua” dan “mencari semua pengguna yang berusia di atas 30 tahun”; apakah saya salah memahami ucapan Anda atau abstraknya? Bahasa Inggris bukan bahasa ibu saya, jadi saya agak bingung

• Jadi para ilmuwan komputer menemukan cara untuk mengestimasi ukuran subset secara hemat memori

  • Jika estimasinya bisa didapat hanya dengan lebih sedikit putaran lempar koin, ini juga tampak lebih cepat. Untuk memperkirakan jumlah kata yang berbeda, mungkin kita tidak perlu menyisir seluruh “buku” sampai habis
  • Kata subset penting di sini. Tepatnya, ini adalah subset dari elemen unik