✖

HyperLogLog: Cara menganggar bilangan nilai unik dengan sangat tepat

Siri tentang algoritma untuk menganggar bilangan nilai unik dalam multiset diteruskan dengan artikel tentang algoritma state of the art HyperLogLog. Namun, semua idea di sebalik algoritma ini berasal daripada LogLog yang telah diterangkan sebelum ini, jadi jika anda mahu terus membaca, pastikan anda memahami LogLog dengan baik.

Algoritma LogLog mempunyai dua masalah utama:

Pencilan

Anggaran akhir LogLog sangat terdedah kepada pencilan (outlier), iaitu nilai yang sangat jauh daripada nilai-nilai lain. Lazimnya, kebanyakan panjang maksimum akhiran sifar bagi setiap kumpulan lebih kurang sama, misalnya antara 12 hingga 15, tetapi tiba-tiba — satu akhiran sifar mempunyai panjang 27. Perbezaan yang besar ini mengacaukan anggaran akhir bilangan nilai unik kerana min aritmetik biasa tidak dapat menanganinya dengan baik. Pada dasarnya prinsipnya sama seperti apabila segelintir pengurus atasan dan pengarah menaikkan min gaji negara dengan gaji mereka yang tinggi.

Pencipta algoritma ini cuba menyelesaikan masalah ini dengan membuang pencilan dan tidak memasukkan beberapa nilai maksimum yang tertinggi ke dalam min, tetapi penyelesaian itu kurang baik. Kemudian mereka mencuba cara lain — daripada min aritmetik, mereka menggunakan min harmonik, yang mempunyai sifat yang jauh lebih baik apabila terdapat nilai yang jauh daripada min.

Hasil yang sangat teruk bagi kekardinalan yang kecil

LogLog memberikan hasil yang teruk apabila menganggar kekardinalan multiset yang kecil. Jika multiset hanya mengandungi beberapa unsur unik, LogLog memberikan anggaran yang terlalu besar dan tidak masuk akal. Pencipta algoritma menyelesaikan masalah ini dengan bijak — apabila input ialah multiset yang kekardinalannya rendah, algoritma LogLog tidak digunakan, sebaliknya algoritma lain sama sekali digunakan, iaitu Linear counting yang sudah kita kenali. Baiklah, tetapi bagaimanakah kita tahu bahawa input ialah multiset yang kekardinalannya kecil, sedangkan kekardinalan itulah yang tidak kita ketahui?

Kita biarkan LogLog menganggar bilangan unsur unik, dan jika kita dapati anggaran ini agak rendah, kita membuang anggaran itu dan mengiranya semula dengan algoritma Linear counting. Mari kita ingat semula secara ringkas cara Linear counting berfungsi. Pada mulanya kita memperuntukkan tatasusunan (bit) sifar dengan saiz yang ditetapkan lebih awal, lazimnya kuasa bagi dua. Kita meneliti semua unsur multiset, mengira nilai cincang setiap satu dan menukarkannya kepada integer i dari 0 hingga panjang tatasusunan tolak 1. Kemudian kita menyimpan digit satu pada indeks i dalam tatasusunan. Akhirnya kita mengira bilangan sifar dan satu dalam tatasusunan dan menganggar kekardinalan dengan rumus yang mudah.

Namun, algoritma LogLog tidak menggunakan sebarang tatasusunan bit untuk “menyimpan” nilai cincang yang dikira. Sebaliknya, algoritma ini menggunakan tatasusunan yang menyimpan panjang maksimum akhiran. Tatasusunan itu boleh kelihatan, misalnya, seperti berikut:

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

dengan setiap nombor ialah panjang maksimum akhiran sifar dalam kumpulan nilai cincang yang berkenaan. Nilai bukan sifar pada kedudukan ke-i semestinya bermakna bahawa dalam multiset itu wujud unsur yang nilai cincang (tiga bit)nya sama dengan i. Dengan kata lain, tatasusunan ini boleh ditukarkan kepada tatasusunan bit untuk linear counting dengan mengekalkan sifar dan menukarkan setiap nombor positif kepada satu. Daripada tatasusunan tadi kita memperoleh tatasusunan bit:

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

Sekarang kita boleh menggunakan algoritma Linear counting dan menganggar kekardinalan dengannya.

Namun, ada satu masalah. Kita menyimpan akhiran sifar maksimum dalam tatasusunan, tetapi bagaimana jika dalam suatu kumpulan nilai, semua nilai cincang berakhir dengan digit satu? Contohnya, jika kita menggunakan tiga bit terakhir sebagai pengecam kumpulan bagi nilai cincang, panjang akhiran sifar bagi nilai cincang “01001100” ialah sifar — kerana vektor “01001” berakhir dengan satu. Jadi, kita menyimpan sifar dalam tatasusunan maksimum pada indeks 4 (1002=410). Dalam algoritma linear counting, hal ini bermakna kita tidak menemui nilai yang nilai cincangnya empat, sedangkan hal itu tidak benar.

Oleh itu, kita mengubah suai algoritma supaya tatasusunan maksimum tidak menyimpan panjang akhiran sifar yang terpanjang, sebaliknya menyimpan indeks “digit satu pertama dari kanan” (untuk ketepatan — kita mengindeks bermula dari satu). Hal ini sama seperti menambahkan satu kepada panjang akhiran sifar. Dengan itu, sifar pada indeks i bermakna tiada nilai yang nilai cincangnya sama dengan i, dan tatasusunan sebegini boleh digunakan untuk linear counting.

Pelaksanaan HyperLogLog

Langkah demi langkah:

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

Fungsi alpha memulangkan pembetulan bagi anggaran yang dikira; kita sudah mengenalinya daripada bahagian lalu, cuma dalam HyperLogLog nilai alpha berbeza bergantung pada bilangan kumpulan.

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

Fungsi yang memulangkan bilangan bit sifar di hujung suatu nombor.

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 meneliti semua nilai, membahagikannya kepada num_buckets kumpulan dan bagi setiap kumpulan mengira indeks digit satu pertama dari kanan (panjang akhiran sifar maksimum tambah 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 yang sedikit diubah suai untuk mengira algoritma Linear counting.

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 menggabungkan semuanya. Mula-mula fungsi ini mengira anggaran dengan LogLog yang telah diubah suai; daripada min aritmetik, fungsi ini menggunakan min harmonik pada baris keempat. Akhirnya fungsi ini menggunakan pembetulan dalam bentuk Linear counting jika anggaran yang dikira lebih kecil daripada 2.5 kali bilangan kumpulan (dalam keadaan ini kita menjangkakan anggaran LogLog standard lebih teruk berbanding Linear counting) dan jika tatasusunan maksimum mengandungi sekurang-kurangnya satu sifar (tatasusunan yang mengandungi digit satu sahaja tidak boleh digunakan dalam Linear counting, lihat artikel sebelum ini). Jadi, apakah hasil HyperLogLog?

Kita jalankan kod ujian yang menganggar kekardinalan set yang kekardinalannya masing-masing 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

Kita lihat bahawa hasilnya sentiasa menyimpang kurang daripada satu peratus daripada hasil yang betul. Dan itu bagus!

Penambahbaikan lain bagi HyperLogLog

HyperLogLog telah menerima beberapa penambahbaikan lain yang menarik. Salah satu masalah yang masih tinggal ialah keperluan ingatan yang tinggi. Hal ini kedengaran agak pelik kerana dalam bahagian lalu kita memuji keperluan ingatannya setinggi langit dan mengira bahawa tatasusunan maksimum hanya memerlukan 768 bait. Namun, masalah timbul jika anda mahu mengira kekardinalan bukan bagi satu multiset yang sangat besar, tetapi bagi beberapa juta multiset kecil secara selari, atau jika anda mahu menyimpan tatasusunan maksimum yang dikira itu dalam pangkalan data untuk pelbagai kegunaan kemudian.

Contohnya, jika kita mengira kekardinalan satu bilion multiset serentak, dengan pelaksanaan sekarang kita memerlukan 1 000 000 000 kali 768 bait, iaitu 768 GB. Dari satu sudut, jumlah itu tidaklah teruk … tetapi dari sudut lain, kita boleh melaksanakan HyperLogLog dengan lebih baik.

Perwakilan jarang (sparse)

Bayangkan kita menetapkan k=12, iaitu kita menggunakan 12 bit untuk mengenal pasti kumpulan, jadi kita memperoleh 212 kumpulan nilai cincang yang berbeza. Pada awal algoritma, kita perlu memperuntukkan tatasusunan sepanjang 4096 (lihat baris 3 fungsi count_maxims). Katakan multiset kita mempunyai tiga unsur yang berbeza. Ini bermakna kita menetapkan nilai pada tiga tempat berbeza dalam tatasusunan, dan baki 4093 nilai dalam tatasusunan kekal sifar; ringkasnya, baki 4093 tempat itu langsung tidak digunakan. Cara ini tidak begitu cekap, bukan?

Untuk mengelakkan tatasusunan yang sebahagian besarnya sifar dan tidak digunakan tetapi tetap menggunakan ingatan yang berharga, pada mulanya kita boleh menyimpan nilai sebagai pasangan [indeks, nilai]. Contoh untuk kefahaman yang lebih baik. Tatasusunan 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]

boleh diwakili dengan jauh lebih jimat ingatan sebagai dua pasangan:

[0, 7], [4, 12]

Daripada memperuntukkan ruang besar yang tidak digunakan dalam ingatan, kita boleh memperuntukkan ruang yang benar-benar diperlukan sahaja, sedikit demi sedikit. Perwakilan ini dipanggil jarang (sparse). Namun, pada suatu ketika perwakilan ini akan menggunakan lebih banyak ingatan berbanding penyimpanan dalam tatasusunan — pada masa itu kita boleh menukarkan perwakilan jarang kepada tatasusunan biasa tanpa kehilangan maklumat.

Ofset

Amalan menunjukkan bahawa semua nilai dalam tatasusunan lebih kurang sama. Tatasusunan maksimum biasanya kelihatan, misalnya, seperti berikut:

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

Semua nilai berada sekitar nombor 13. Satu lagi strategi untuk mengecilkan saiz tatasusunan sebegini ialah menolak suatu nilai tetap daripada setiap unsur dan mengingati nilai itu. Contohnya, kita boleh menolak lapan:

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

Sekarang setiap nilai dalam tatasusunan menggunakan ruang ingatan yang lebih kecil — dalam tatasusunan pertama kita perlu menyimpan nombor dari 0 hingga 15, yang memerlukan 4 bit, manakala bagi tatasusunan kedua cukup 3 bit kerana kita hanya menyimpan nombor dari 0 hingga 7. Sudah tentu hal ini mengandaikan bahawa tatasusunan dilaksanakan pada peringkat bit. Apabila kita mahu membaca nilai daripada tatasusunan, kita perlu menambahkan semula nilai yang dicatat itu.

…dan banyak lagi penambahbaikan lain. Penyelidikan dalam bidang ini masih berjalan, jadi kita pasti boleh menantikan idea menarik yang lain. Dalam bahagian seterusnya kita akan membincangkan kesatuan dan persilangan vektor HyperLogLog, dan pada masa akan datang kita akan melihat sebab menyimpan berbilion-bilion vektor HyperLogLog boleh berguna.

Pautan dan sumber

Kandungan: Linear counting: Cara menganggar bilangan nilai unik, Min Value: Cara menganggar bilangan nilai unik, LogLog: Cara menganggar bilangan nilai unik, HyperLogLog: Cara menganggar bilangan nilai unik dengan sangat tepat