Video: Black Holes Explained – From Birth to Death 2024
Meskipun filter Bloom dapat melacak objek yang tiba dari sungai, tidak dapat diketahui berapa banyak benda yang ada di sana. Vektor bit yang diisi oleh yang dapat (tergantung pada jumlah hash dan probabilitas tabrakan) menyembunyikan jumlah sebenarnya objek yang digabung pada alamat yang sama.
Mengetahui jumlah objek yang berbeda berguna dalam berbagai situasi, seperti kapan Anda ingin mengetahui berapa banyak pengguna yang berbeda telah melihat halaman situs web tertentu atau jumlah permintaan mesin pencari yang berbeda. Menyimpan semua elemen dan menemukan duplikat di antara mereka tidak dapat bekerja dengan jutaan elemen, terutama yang berasal dari arus. Bila Anda ingin mengetahui jumlah objek yang berbeda dalam arus, Anda tetap harus bergantung pada fungsi hash, namun pendekatannya melibatkan pengambilan sketsa numerik.
Membuat sketsa berarti mengambil perkiraan, itu adalah nilai yang tidak tepat namun tidak sepenuhnya salah sebagai jawaban. Perkiraan bisa diterima karena nilai sebenarnya tidak terlalu jauh dari itu. Dalam algoritma cerdas ini, HyperLogLog, yang didasarkan pada probabilitas dan aproksimasi, Anda mengamati karakteristik angka yang dihasilkan dari arus. HyperLogLog berasal dari studi ilmuwan komputer Nigel Martin dan Philippe Flajolet. Flajolet memperbaiki algoritma awal mereka, Flajolet-Martin (atau algoritma LogLog), ke versi HyperLogLog yang lebih kuat, yang bekerja seperti ini:
- Sebuah hash mengubah setiap elemen yang diterima dari arus menjadi sebuah angka.
- Algoritma mengubah bilangan menjadi biner, basis standar numerik 2 yang digunakan komputer.
- Algoritma menghitung jumlah angka nol awal pada bilangan biner dan lintasan dari jumlah maksimum yang dilihatnya, yaitu n.
- Algoritma memperkirakan jumlah elemen yang berbeda yang dilewatkan dalam arus menggunakan n. Jumlah elemen yang berbeda adalah 2 ^ n.
Misalnya, elemen pertama dalam string adalah anjing kata. Algoritma menggabungkannya menjadi nilai integer dan mengubahnya menjadi biner, dengan hasil 01101010. Hanya satu nol yang muncul di awal nomor, jadi algoritma mencatatnya sebagai jumlah maksimum angka nol yang terlihat. Algoritma kemudian melihat kata-kata burung beo dan serigala, yang setara binernya adalah 11101011 dan 01101110, sehingga n tidak berubah. Namun, ketika kata kucing berlalu, hasilnya adalah 00101110, jadi n menjadi 2. Untuk memperkirakan jumlah elemen yang berbeda, algoritma menghitung 2 ^ n, yaitu 2 ^ 2 = 4. Angka tersebut menunjukkan proses ini.
Trik dari algoritma ini adalah jika hash Anda menghasilkan hasil acak, didistribusikan secara merata (seperti pada filter Bloom), dengan melihat representasi biner, Anda dapat menghitung probabilitas bahwa rangkaian angka nol muncul. Karena probabilitas bilangan biner tunggal menjadi 0 adalah satu dari dua, untuk menghitung probabilitas urutan nol, Anda hanya mengalikan probabilitas 1/2 sebanyak itu sebanyak panjang dari nol:
- 50 persen (1/2) probabilitas untuk angka yang dimulai dengan 0
- 25 persen (1/2 * 1/2) probabilitas untuk bilangan yang dimulai dengan 00
- 12. 5 persen (1/2 * 1/2 * 1/2) probabilitas untuk angka yang dimulai dengan kemungkinan 000
- (1/2) untuk bilangan yang dimulai dengan k nol (Anda menggunakan kekuatan untuk perhitungan lebih cepat dari banyak perkalian dari nomor yang sama)
Semakin sedikit angka yang dilihat HyperLogLog, semakin besar ketidaktepatannya. Akurasi meningkat ketika Anda menggunakan perhitungan HyperLogLog berkali-kali menggunakan fungsi hash yang berbeda dan rata-rata bersama jawaban dari setiap perhitungan, namun hashing berkali-kali membutuhkan waktu, dan arusnya cepat. Sebagai alternatif, Anda dapat menggunakan hash yang sama namun membagi arus menjadi beberapa kelompok (seperti dengan memisahkan elemen menjadi beberapa kelompok saat mereka tiba berdasarkan pesanan kedatangan mereka) dan untuk setiap grup, Anda melacak jumlah maksimum angka nol yang tertinggal. Pada akhirnya, Anda menghitung taksiran elemen yang berbeda untuk setiap kelompok dan menghitung rata-rata aritmatika semua taksiran. Pendekatan ini adalah stochastic averaging dan memberikan perkiraan yang lebih tepat daripada menerapkan algoritma ke keseluruhan aliran.
