LogLog: cara menaksir banyaknya nilai unik

Setelah bagian-bagian sebelumnya tentang Linear Counting dan Min Value, akhirnya kita sampai pada algoritma probabilistik yang hampir paling top untuk menaksir banyaknya nilai unik dalam suatu kumpulan data, yaitu LogLog. Yang lebih baik lagi hanyalah saudaranya, HyperLogLog, yang dikembangkan dari LogLog, tetapi itu akan dibahas lain kali.

Kita ulangi rumusan masalahnya. Inputnya adalah suatu kumpulan data/multihimpunan, misalnya larik/generator berisi ID. Dalam larik ini, beberapa nilai muncul lebih dari sekali, dan kita ingin menghitung banyaknya nilai unik dalam larik tersebut. Banyaknya ini kita sebut kardinalitas. Kita mengharapkan kardinalitas ini benar-benar besar; jika tidak, kita bisa memakai algoritma konvensional.

Ide algoritma LogLog

Bayangkan kita punya sekumpulan vektor biner. Jangan takut, misalnya 0001011001001100 adalah vektor biner dengan panjang 16. Misalkan kita punya vektor biner dengan panjang 32, seluruhnya satu juta buah, dan semuanya dibangkitkan secara benar-benar acak. Berapa banyak vektor yang diakhiri angka nol?

Tentu saja kita tidak bisa tahu persis, tetapi jika vektor-vektor tersebut memang dibangkitkan secara acak, kira-kira setengahnya akan diakhiri nol, yaitu 500 ribu. Berapa banyak vektor yang diakhiri 00? Seperempatnya. Yang diakhiri 000? Seperdelapannya. Dan seterusnya. Secara kasar, hal ini dapat digambarkan seperti ini:

pola vektor       proporsi dari semua vektor
...xxxxxx0        50%
...xxxxx00        25%
...xxxx000        12,5%
...xxx0000        6,25%
     ...          ...

Jika kita mencari sufiks (sufiks adalah string yang menjadi akhir string lain — kebalikan prefiks) dengan panjang d, kita berharap menemukan v vektor yang diakhiri sufiks tersebut. Nilai v dihitung sebagai:

$v = \frac{1}{2^{d}} \cdot N$

dengan N banyaknya semua vektor dalam kumpulan. Sufiks dengan panjang 3 (misalnya …010) seharusnya muncul pada 1/2^3 N = 1/8 N vektor, yaitu 12,5% dari semua vektor.

Sekarang kita lakukan sedikit trik yang memutarbalikkan cara berpikir. Misalkan ada multihimpunan berisi 1.024 vektor unik. Berapa banyak vektor yang seharusnya diakhiri sufiks 0000000000 (sepuluh nol)? Kita substitusikan ke rumus dan memperoleh

$v = \frac{1}{2^{10}} \cdot 1024 = \frac{1}{1024} \cdot 1024 = 1$

Wah, satu! Di antara seribu vektor biner yang dibangkitkan secara acak, seharusnya ada tepat satu vektor yang diakhiri sepuluh nol. Lalu, bagaimana informasi ini dapat dipakai untuk menaksir banyaknya elemen unik? Kita dapat menempuh arah sebaliknya. Bagaimana jika kita menelusuri semua vektor biner pada input dan mendapati bahwa dalam kumpulan tersebut hanya ada satu vektor yang diakhiri sepuluh nol? Tentu kita dapat menaksir bahwa kumpulan tersebut berisi 1.024 vektor!

Memperumum dan menyusun algoritma

Tujuannya adalah mencari sufiks yang hanya dimuat oleh satu vektor, dan sufiks tersebut sependek mungkin. Namun, hal ini sangat sulit, karena untuk benar-benar menemukan vektor seperti itu kita harus menyimpan semua sufiks. Kita tidak menginginkannya, karena memakan terlalu banyak memori. Sebagai gantinya, kita puas dengan mencari rangkaian nol terpanjang di akhir vektor.

Jadi, kita telusuri semua vektor, dan untuk setiap vektor kita hitung berapa banyak nol di akhirnya. Dalam satu variabel, kita simpan nilai maksimum dari nilai-nilai tersebut. Setelah semua vektor ditelusuri, kita tahu panjang sufiks terpanjang yang hanya terdiri atas nol. Panjang ini kita lambangkan dengan huruf d. Sekarang rumus sebelumnya kita ubah sehingga variabel N terisolasi, artinya N menjadi output algoritma, bukan input. Di tempat v kita substitusikan satu, karena kita berharap menemukan tepat satu vektor seperti itu, yaitu kita berharap berlaku v=1.

$\begin{array}{rcl} v & = & \frac{N}{2^{d}} \\ v \cdot 2^{d} & = & N \\ 2^{d} & = & N \end{array}$

Jadi, jika kita menemukan panjang d dari sufiks nol terpanjang, kardinalitas kita taksir dengan rumus N=2^d.

Bagaimana memperoleh vektor biner acak?

Dengan vektor biner acak, algoritma kita sudah bekerja, tetapi bagaimana menerapkan cara ini pada data nyata? Seperti biasa, kita juga menggunakan fungsi hash yang sesuai. Jika inputnya berupa kumpulan data, misalnya ID (string), data tersebut kita hash terlebih dahulu. Output fungsi hash n-bit adalah n bit, yang dari sudut pandang praktis terlihat seperti vektor biner yang dibangkitkan secara acak.

Sekarang kita sudah dapat menuliskan algoritmanya:

def trailing_zeroes(number):
    if number == 0: 
        return 0

    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def count_unique(values):
    max_zero_suffix_length = 0
    for value in values:
        zeroes_length = trailing_zeroes(hash(value))
        max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
    return 2 ** max_zero_suffix_length

Fungsi trailing_zeroes mengembalikan banyaknya nol di akhir bilangan. Bagaimana caranya? Kalau kodenya belum menjelaskan, lebih baik jangan tanya. Lalu, seberapa berhasil fungsi ini? Untuk himpunan berisi seratus ribu elemen unik, fungsi ini mengembalikan taksiran 524.288.

Hmm…

Yah, tidak terlalu bagus, ya? Tapi tidak apa-apa! Kita coba memperbaiki algoritmanya dengan cara yang persis sama seperti pada Min Value sebelumnya. Data input kita bagi menjadi beberapa kelompok yang saling lepas. Untuk setiap kelompok, kita hitung sufiks nol maksimum, lalu kita hitung rata-rata panjang sufiks nol dan menggunakannya untuk menaksir banyaknya nilai unik.

Misalnya, kita dapat menetapkan bahwa dua bit terakhir setiap vektor menentukan nomor kelompok vektor tersebut. Keenam vektor berikut

1101110111111011     1110110010100101
1011001111110010     1111101100000011
1010101000100000     0110010110011000

dapat kita bagi menjadi empat kelompok berdasarkan akhirannya:

00                   01              
1010101000100000     1110110010100101
0110010110011000                     

10                   11
1011001111110010     1101110111111011
                     1111101100000011

Selanjutnya, kita hitung panjang sufiks nol terpanjang di setiap vektor, tetapi bit-bit yang kita pakai sebagai nomor kelompok kita lewati. “Sufiks” nol kita tandai dengan warna hijau:

00                   01                     
1010101000100000     1110110010100101    
0110010110011000

10                   11
1011001111110010     1101110111111011
                     1111101100000011

00: 3                01: 0
10: 2                11: 6

Di bagian akhir tertulis panjang sufiks nol terpanjang dari setiap kelompok. Dari panjang-panjang sufiks ini, kita dapat menghitung rata-rata aritmetika, yang hasilnya 2,75. Nilai ini kita substitusikan ke rumus dan memperoleh

$2^{2, 75} \approx 6,727$

Hasilnya adalah rata-rata banyaknya elemen unik di setiap kelompok. Tentu saja hasil ini sama sekali tidak cocok, tetapi tidak usah dipikirkan: untuk himpunan kecil, algoritma LogLog memberikan hasil yang sangat buruk.

Untuk menaksir kardinalitas seluruh himpunan, nilai ini masih harus kita kalikan dengan banyaknya kelompok: 6,727 · 4 = 26,908. Algoritma menghitung bahwa kumpulan tersebut berisi kira-kira 27 nilai unik. Padahal isinya enam, jadi hasilnya meleset jauh, tetapi untuk saat ini hal itu benar-benar tidak masalah.

Implementasi algoritma

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def estimate_cardinality(values, k):
    num_buckets = 2 ** k
    max_zeroes = [0] * num_buckets
    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash)
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
    average_max_zeros = float(sum(max_zeroes)) / num_buckets
    return (2 ** average_max_zeros) * num_buckets

Parameter k menentukan berapa bit yang diambil sebagai indeks kelompok. Parameter ini menentukan akurasi algoritma — makin tinggi k, makin tinggi akurasinya. Variabel bucket_index menyimpan nomor kelompok. Bagaimana cara kerja keajaiban di ruas kanan tanda sama dengan?

Variabel num_buckets berisi banyaknya kelompok, yang selalu berupa pangkat dari dua. Misalnya, jika k = 3, maka num_buckets=8. Dalam sistem biner, bilangan 8 berbentuk 1000. Jika dikurangi satu, kita memperoleh bilangan 7, yang berbentuk 0111. Setelah num_buckets dikurangi satu, kita selalu memperoleh bilangan yang di akhirnya memiliki k angka satu dan sebelumnya hanya nol. Selanjutnya, kita lakukan operasi AND logika (itulah operator &). Untuk vektor 1110110010100101, operasi ini terlihat seperti ini:

  1110110010100101
& 0000000000000111
------------------
  0000000000000101

Tujuan seluruh keajaiban ini adalah memperoleh bilangan yang di awalnya hanya berisi nol, sedangkan k bit terakhirnya sama dengan nilai hash h.

Selanjutnya, kita hitung bucket_hash, yaitu nilai hash semula yang k bit terakhirnya kita buang dengan menggeser seluruh nilai hash sejauh k bit ke kanan. Pergeseran bit ini memindahkan semua bit dalam bilangan sejauh k bit ke kanan, lalu bagian kiri bilangan diisi dengan nol. (Pergeseran bit ke kanan sejauh satu sama dengan membagi bilangan dengan dua dan membuang sisanya.) Dari vektor 1110110010100101, setelah digeser sejauh tiga kita memperoleh 0001110110010100. Vektor ini disimpan dalam variabel bucket_hash.

Selanjutnya, kita hitung banyaknya nol di akhir vektor ini. Jika nilai ini lebih besar daripada nilai maksimum saat ini yang tersimpan dalam larik max_zeroes pada indeks bucket_index, nilai tersebut kita timpa.

Terakhir, kita tinggal menghitung rata-rata banyaknya nol di semua kelompok dan menghitung rata-rata banyaknya elemen unik di setiap kelompok (2 ** average_max_zeros). Karena seluruhnya ada num_buckets kelompok, nilai ini kita kalikan dengan banyaknya kelompok, sehingga diperoleh taksiran akhir banyaknya elemen unik. Fiuh, ternyata tidak sakit. Hasil untuk beberapa kumpulan data yang berisi 250.000 nilai unik dan k=10:

331774.56203
323349.39265
307343.444439
309430.914045
294512.379123

Tidaaak, masih salah :-(. Tetapi tenang, kita sudah cukup dekat. Perhatikan bahwa semua hasilnya lebih besar daripada hasil yang benar. Selama algoritma berjalan, berbagai galat menumpuk, sehingga taksirannya jelas lebih besar daripada hasil yang benar. Namun, galat-galat ini cukup stabil, dan besarnya galat dapat ditaksir. Jika taksiran kita kalikan dengan konstanta koreksi 0,79402, kita memperoleh hasil yang jauh lebih baik:

263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445

Saya juga mencoba multihimpunan dengan kardinalitas satu juta. Hasilnya:

Hasil                 Galat
1017297.17411         1.01729717411
1022820.99717         1.02282099717
984108.725487         0.984108725487
1018675.32683         1.01867532683
1007020.2853          1.0070202853

Bagus sekali! Galatnya di bawah 2,5%, hasil yang lumayan. Dan inilah, hadirin sekalian, algoritma LogLog. Implementasi akhirnya, lengkap dengan konstanta koreksi tadi, terlihat seperti ini:

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def estimate_cardinality(values, k):
    num_buckets = 2 ** k
    max_zeroes = [0] * num_buckets
    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash)
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
    average_max_zeros = float(sum(max_zeroes)) / num_buckets
    return (2 ** average_max_zeros) * num_buckets * 0.79402

Bagaimana mengubah algoritma ini untuk memperoleh HyperLogLog yang legendaris dan paling top akan kita bahas lain kali. Untuk sementara, kita lihat seberapa besar kebutuhan memori algoritma ini.

Kebutuhan memori

Algoritma ini sangat efisien dalam hal pemakaian memori. Satu-satunya yang harus kita ingat adalah larik yang menyimpan nilai-nilai maksimum. Panjang larik ini dipengaruhi oleh nilai k, yaitu banyaknya bit dari vektor yang kita ambil sebagai indeks kelompok. Untuk k tertentu, ada 2^k kelompok yang berbeda, sehingga larik maksimum memiliki panjang 2^k. Dalam implementasi, nilai ini kita namai num_buckets.

Seberapa besar satu sel larik? Ke dalamnya kita simpan panjang sufiks nol. Saya bisa membocorkan sejak awal bahwa nilai hash 64-bit kemungkinan besar sudah cukup untuk semua multihimpunan yang dapat dibayangkan di dunia ini, sehingga larik ini harus dapat menyimpan bilangan dari 0 (vektor yang seluruhnya angka satu) sampai 64 (vektor yang seluruhnya nol). Selain itu, jika kita asumsikan bahwa k selalu lebih besar daripada nol, kita cukup menyimpan bilangan dari 0 sampai 63. Untuk itu, cukup 6 bit saja, karena 2⁶ = 64.

Ya, kita cukup memakai “larik” yang satu selnya berukuran 6 bit. Saya juga bisa membocorkan bahwa nilai k=10 sudah cukup untuk menaksir kardinalitas dengan cukup baik hingga orde ratusan juta. Algoritma dengan pengaturan ini membuat larik berukuran 2¹⁰ = 1024, dan setiap selnya memakai 6 bit. Seluruhnya, larik ini memakai 6.144 bit, yaitu 768 byte. Bahkan tidak sampai satu kilobyte.

Dan hanya itu.

Kita tidak perlu menyimpan apa pun lagi. Nilai hash yang sudah dihitung dapat langsung dibuang; kita cukup tahu banyaknya nol di akhir vektor.

Perhatikan bahwa jika kamu menggunakan fungsi hash yang lebih besar, misalnya yang mengembalikan 128 bit, kebutuhan memorinya hampir tidak berubah. Kita hanya perlu menyimpan bilangan dari 0 sampai 127, yang cukup dengan 7 bit. Jadi, kebutuhan memori terutama ditentukan oleh parameter k, yaitu banyaknya kelompok.

LogLog terutama cocok untuk menghitung multihimpunan dengan kardinalitas yang benar-benar besar. Seperti terlihat juga pada contoh sederhana di atas, LogLog kurang baik dalam menangani multihimpunan berkardinalitas kecil. Namun, hal ini dapat diatasi, misalnya, dengan menggunakan algoritma lain untuk menaksir jika kita mendapati bahwa multihimpunan berkardinalitas rendah, misalnya Linear Counting yang sudah dijelaskan sebelumnya. Hal ini juga akan dibahas lain kali.

Sumber:

Loglog Counting of Large Cardinalities [PDF]
Damn Cool Algorithms: Cardinality Estimation (kode LogLog di sini kurang lebih diambil dari sana)

Daftar isi: Linear counting: cara menaksir banyaknya nilai unik, Min Value: cara menaksir banyaknya nilai unik, LogLog: cara menaksir banyaknya nilai unik, HyperLogLog: cara menaksir banyaknya nilai unik dengan sangat akurat

« Artikel sebelumnya: Min Value: cara menaksir banyaknya nilai unik

Artikel berikutnya: HyperLogLog: cara menaksir banyaknya nilai unik dengan sangat akurat »