✖

HyperLogLog: cara menaksir banyaknya nilai unik dengan sangat akurat

Seri tentang algoritma untuk menaksir banyaknya nilai unik dalam multihimpunan berlanjut dengan artikel tentang algoritma state of the art HyperLogLog. Namun, semua ide di balik algoritma ini berasal dari LogLog yang sudah dijelaskan sebelumnya. Jadi, jika ingin melanjutkan membaca, pastikan kamu sudah memahami LogLog dengan baik.

Algoritma LogLog memiliki dua masalah utama:

Pencilan

Taksiran akhir LogLog sangat rentan terhadap pencilan (outlier), yaitu nilai yang sangat jauh dari nilai-nilai lainnya. Biasanya, sebagian besar panjang maksimum sufiks nol untuk setiap kelompok kira-kira sama, misalnya berkisar antara 12 dan 15, tetapi tiba-tiba — satu sufiks nol memiliki panjang 27. Perbedaan besar ini mengacaukan taksiran akhir banyaknya nilai unik, karena rata-rata aritmetika biasa tidak dapat menanganinya dengan baik. Pada dasarnya, prinsipnya sama seperti ketika segelintir manajer puncak dan direktur dengan gaji tinggi mereka menaikkan rata-rata gaji di seluruh negeri.

Penulis algoritma ini mencoba mengatasinya dengan membuang pencilan, yaitu tidak memasukkan beberapa nilai maksimum tertinggi ke dalam rata-rata, tetapi solusi itu kurang baik. Kemudian mereka mencoba cara lain — alih-alih rata-rata aritmetika, mereka menggunakan rata-rata harmonik, yang memiliki sifat jauh lebih baik jika ada nilai-nilai yang jauh dari rata-rata.

Hasil yang sangat buruk untuk kardinalitas kecil

LogLog memberikan hasil yang sangat buruk jika harus menaksir kardinalitas multihimpunan kecil. Jika multihimpunan hanya memuat sedikit elemen unik, LogLog mengembalikan taksiran yang besarnya tidak masuk akal. Penulisnya mengatasi hal ini dengan cerdik — jika inputnya multihimpunan berkardinalitas rendah, yang digunakan bukan algoritma LogLog, melainkan algoritma yang sama sekali berbeda, yaitu Linear counting yang sudah kita kenal. Baiklah, tetapi bagaimana kita tahu bahwa inputnya multihimpunan berkardinalitas kecil, padahal kardinalitas itulah yang tidak kita ketahui?

Kita biarkan LogLog menaksir banyaknya elemen unik, dan jika ternyata taksirannya relatif rendah, taksiran tersebut kita buang dan kita hitung ulang dengan algoritma Linear counting. Kita ingat lagi secara singkat cara kerja Linear counting. Pada awalnya, kita mengalokasikan larik (bit) berisi nol dengan ukuran tertentu yang sudah ditetapkan sebelumnya, biasanya berupa pangkat dari dua. Kita telusuri semua elemen multihimpunan, kita hitung nilai hash-nya, lalu nilai hash tersebut kita ubah menjadi bilangan bulat i dari 0 sampai panjang larik dikurangi 1. Pada indeks i dalam larik, kita simpan angka satu. Terakhir, kita hitung banyaknya nol dan satu dalam larik, lalu dengan rumus sederhana kita taksir kardinalitasnya.

Namun, algoritma LogLog tidak memakai larik bit untuk “menyimpan” nilai hash yang sudah dihitung. Sebagai gantinya, LogLog memakai larik yang menyimpan panjang sufiks maksimum. Lariknya bisa terlihat, misalnya, seperti ini:

[2, 5, 9, 0, 5, 4, 4, 0]

dengan setiap bilangan menyatakan panjang maksimum sufiks nol dalam kelompok nilai hash yang bersangkutan. Nilai tak nol pada posisi ke-i berarti bahwa di antara nilai-nilai dalam multihimpunan pasti ada elemen yang nilai hash-nya (tiga bit) sama dengan i. Dengan kata lain, larik ini dapat kita ubah menjadi larik bit untuk linear counting dengan membiarkan nol tetap nol dan mengubah setiap bilangan positif menjadi satu. Dari larik sebelumnya, kita memperoleh larik bit:

[1, 1, 1, 0, 1, 1, 1, 0]

Sekarang kita dapat menerapkan algoritma Linear counting dan menaksir kardinalitas dengannya.

Namun, ada satu masalah. Kita menyimpan sufiks nol maksimum ke dalam larik, tetapi bagaimana jika dalam suatu kelompok semua nilai hash diakhiri angka satu? Misalnya, jika kita menggunakan tiga bit terakhir sebagai penanda kelompok nilai hash, panjang sufiks nol dari nilai hash “01001100” adalah nol — karena vektor “01001” diakhiri angka satu. Jadi, ke dalam larik maksimum pada indeks 4 (1002=410) kita simpan nol. Dalam algoritma linear counting, hal ini akan terbaca seolah-olah kita tidak menemukan nilai yang nilai hash-nya empat, padahal itu tidak benar.

Karena itu, algoritmanya kita ubah sehingga yang disimpan dalam larik maksimum bukan panjang sufiks nol terpanjang, melainkan indeks “angka satu pertama dari kanan” (sebagai catatan — indeksnya dimulai dari satu). Hal ini sama dengan menambahkan satu ke panjang sufiks nol. Dengan begitu, nol pada indeks i berarti tidak ada nilai yang nilai hash-nya sama dengan i, dan larik seperti itu dapat dipakai untuk linear counting.

Implementasi HyperLogLog

Kita bahas satu per satu:

def alpha(num_buckets):
    return (0.7213 / (1 + 1.079 / num_buckets))

Fungsi alpha mengembalikan koreksi untuk taksiran yang dihitung. Hal ini sudah kita kenal dari artikel sebelumnya, hanya saja pada HyperLogLog nilai alpha berbeda-beda bergantung pada banyaknya kelompok.

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

Fungsi yang mengembalikan banyaknya bit nol di akhir bilangan.

def count_maxims(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) + 1
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)

    return max_zeroes

Fungsi yang menelusuri semua nilai, membaginya menjadi num_buckets kelompok, dan untuk setiap kelompok menghitung indeks angka satu pertama dari kanan (panjang sufiks nol maksimum ditambah satu).

def linear_counting(number_of_ones, num_buckets):
    number_of_zeros = num_buckets - number_of_ones
    Z = float(number_of_zeros) / num_buckets
    p = (-num_buckets) * log(Z)
    return p

Fungsi algoritma Linear counting yang sedikit dimodifikasi.

def estimate_cardinality(values, k): 
    num_buckets = 2 ** k   
    max_zeroes = count_maxims(values, k)
    estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes)
    number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes)

    if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets):
        return linear_counting(number_of_ones, num_buckets)
    else:
        return estimate

Fungsi utama yang menyatukan semuanya. Pertama, fungsi ini menghitung taksiran dengan LogLog yang sudah dimodifikasi; pada baris keempat, alih-alih rata-rata aritmetika, digunakan rata-rata harmonik. Terakhir, fungsi ini menerapkan koreksi berupa Linear counting jika taksiran yang dihitung lebih kecil daripada 2,5 kali banyaknya kelompok (pada kondisi ini, kita menduga taksiran standar LogLog lebih buruk daripada Linear counting) dan jika larik maksimum memuat setidaknya satu nol (larik yang seluruhnya berisi angka satu tidak dapat dipakai dalam Linear counting, lihat artikel sebelumnya). Lalu, bagaimana hasil HyperLogLog?

Kita jalankan kode uji yang menaksir kardinalitas himpunan dengan kardinalitas berturut-turut 10, 100, …, 1.000.000:

for x in range(1, 7):
    num_values = 10**x
    values = (str(uuid4()) for _ in xrange(num_values))
    cardinality = estimate_cardinality(values, 14)
    print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)

Hasilnya:

Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408

Terlihat bahwa hasilnya selalu menyimpang kurang dari satu persen dari hasil yang benar. Ini bagus!

Perbaikan lain pada HyperLogLog

HyperLogLog telah mendapat beberapa perbaikan menarik lainnya. Salah satu masalah yang tersisa adalah kebutuhan memori yang tinggi. Kedengarannya aneh, karena di artikel sebelumnya kita memuji-muji kebutuhan memorinya setinggi langit dan menghitung bahwa untuk menyimpan larik maksimum cukup 768 byte. Namun, masalahnya muncul jika kamu ingin menghitung kardinalitas bukan satu multihimpunan raksasa, melainkan beberapa juta multihimpunan kecil secara paralel, atau jika kamu ingin menyimpan larik maksimum yang sudah dihitung di basis data untuk diolah macam-macam di kemudian hari.

Misalnya, jika kita menghitung kardinalitas satu miliar multihimpunan sekaligus, dengan implementasi saat ini kita memerlukan 1.000.000.000 kali 768 byte, yaitu 768 GB. Di satu sisi itu tidak buruk… tetapi di sisi lain, HyperLogLog dapat kita implementasikan dengan lebih baik.

Representasi sparse

Bayangkan kita menetapkan k=12, artinya kita memakai 12 bit untuk menandai kelompok, sehingga diperoleh 212 kelompok nilai hash yang berbeda. Pada awal algoritma, kita harus mengalokasikan larik dengan panjang 4.096 (lihat baris 3 fungsi count_maxims). Misalkan multihimpunan kita memiliki tiga elemen berbeda. Artinya, kita mengisi nilai pada tiga tempat berbeda dalam larik, sedangkan 4.093 nilai sisanya tetap nol; 4.093 tempat tersebut sama sekali tidak terpakai. Kurang efisien, bukan?

Agar kita tidak memiliki larik yang sebagian besar berisi nol dan tidak terpakai, tetapi tetap memakan memori yang berharga, pada awalnya kita dapat menyimpan nilai-nilainya sebagai pasangan [indeks, nilai]. Contoh agar lebih jelas. Larik ini

[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

dapat direpresentasikan dengan jauh lebih hemat memori sebagai dua pasangan:

[0, 7], [4, 12]

Alih-alih mengalokasikan banyak ruang yang tidak terpakai di memori, kita dapat mengalokasikan secara bertahap hanya ruang yang benar-benar kita perlukan. Representasi ini disebut sparse (jarang). Namun, pada suatu saat representasi ini akan memakan memori lebih banyak daripada penyimpanan dalam larik — pada saat itu, representasi sparse dapat kita ubah menjadi larik biasa tanpa kehilangan informasi.

Offset

Praktik menunjukkan bahwa semua nilai dalam larik kira-kira sama. Larik maksimum biasanya terlihat, misalnya, seperti ini:

[12, 13, 11, 13, 15, 12, 14, 11, 12, ...,  13, 14, 11]

Semua nilainya berkisar di sekitar bilangan 13. Strategi lain untuk memperkecil ukuran larik seperti ini adalah mengurangi setiap elemen dengan suatu nilai tetap dan mengingat nilai tersebut. Misalnya, kita dapat mengurangi dengan delapan:

[4, 5, 3, 5, 7, 4, 6, 3, 4, ..., 5, 6, 3]

Sekarang setiap nilai dalam larik memakai lebih sedikit memori — pada larik pertama kita perlu menyimpan bilangan dari 0 sampai 15, yang memerlukan 4 bit, sedangkan untuk larik kedua cukup 3 bit, karena kita hanya menyimpan bilangan dari 0 sampai 7. Tentu saja hal ini mengandaikan implementasi larik pada tingkat bit. Ketika ingin membaca nilai dari larik, kita harus menambahkan kembali nilai yang sudah kita catat.

…dan masih banyak perbaikan lainnya. Penelitian di bidang ini masih terus berjalan, jadi kita tentu bisa menantikan ide-ide menarik lainnya. Lain kali, kita akan membahas gabungan dan irisan vektor HyperLogLog, dan dalam waktu dekat kita akan membahas mengapa menyimpan miliaran vektor HyperLogLog bisa berguna.

Tautan dan sumber

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