Bir çoklu kümedeki benzersiz değerlerin sayısını tahmin eden algoritmalar serisi, state of the art (güncel en iyi) algoritma olan HyperLogLog yazısıyla devam ediyor. Ancak bu algoritmanın arkasındaki bütün fikirler daha önce anlattığımız LogLog algoritmasından geliyor; o yüzden okumaya devam etmek istiyorsan LogLog’u iyi bildiğinden emin ol.

LogLog algoritmasının iki büyük sorunu vardı:

Aykırı Değerler

LogLog’un sonuç tahmini, diğer değerlerden çok uzak olan değerlere, yani aykırı değerlere (outlier) karşı çok hassastır. Tipik olarak her grup için sıfır soneklerinin maksimum uzunluklarının çoğu aşağı yukarı aynıdır, örneğin 12 ile 15 arasında değişir; ama sonra pat — ve bir sıfır sonekinin uzunluğu 27 çıkar. Bu büyük fark, benzersiz değerlerin sayısı için bulunan tahmini bozar, çünkü klasik aritmetik ortalama bununla pek iyi başa çıkamaz. Aslında, birkaç üst düzey yönetici ve genel müdürün yüksek maaşlarıyla ülkedeki ortalama maaşı yukarı çekmesi gibi bir ilke devreye girdi.

Algoritmanın yazarları bunu aykırı değerlerden kurtularak çözmeye çalıştı; ortalamaya en yüksek birkaç maksimumu katmadılar, ama bu pek iyi bir çözüm değildi. Daha sonra başka bir yol denediler — aritmetik ortalama yerine, ortalamadan uzak değerlerimiz olduğunda çok daha iyi özelliklere sahip olan harmonik ortalamayı kullandılar.

Küçük Kardinaliteler İçin Çok Kötü Sonuçlar

LogLog, küçük çoklu kümelerin kardinalitesini tahmin etmesi gerektiğinde berbat sonuçlar verir. Çoklu kümede yalnızca birkaç benzersiz eleman varsa, LogLog bize anlamsız derecede büyük bir tahmin döndürür. Yazarlar bunu kurnazca çözdü — girdide kardinalitesi düşük bir çoklu küme olduğunda LogLog algoritması kullanılmaz, bunun yerine tamamen başka bir algoritma, yani eski dostumuz Linear counting kullanılır. Peki ama kardinaliteyi tam da bilmiyorsak, girdideki çoklu kümenin kardinalitesinin küçük olduğunu nasıl anlarız?

Benzersiz eleman sayısını LogLog’a tahmin ettiririz ve bu tahminin görece düşük olduğunu görürsek tahmini atar, kardinaliteyi Linear counting algoritmasıyla yeniden hesaplarız. Linear counting’in nasıl çalıştığını hızlıca hatırlayalım. Başlangıçta, önceden belirlenmiş bir büyüklükte (tipik olarak ikinin kuvveti) sıfırlardan oluşan bir (bit) dizisi ayırırız. Çoklu kümenin bütün elemanlarını tararız, hash’lerini hesaplarız ve her birini 0 ile dizi uzunluğu eksi 1 arasındaki bir i tam sayısına çeviririz. Sonra dizide i indeksine bir koyarız. Sonunda dizideki sıfırların ve birlerin sayısını hesaplar ve basit bir formülle kardinaliteyi tahmin ederiz.

Ancak LogLog algoritması, hesaplanan hash’leri “saklayacağı” bir bit dizisi kullanmaz. Bunun yerine soneklerin maksimum uzunluklarını tuttuğu bir dizi kullanır. Dizi örneğin şöyle görünebilir:

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

Buradaki her sayı, hesaplanan hash’lerin ilgili grubundaki sıfır sonekinin maksimum uzunluğunu gösterir. i. konumdaki sıfır olmayan bir değer ise, çoklu kümedeki elemanlar arasında (üç bitlik) hash’i i’ye eşit olan bir eleman bulunduğu anlamına gelir. Başka bir deyişle, bu diziyi Linear counting için bir bit dizisine çevirebiliriz: sıfırları olduğu gibi bırakırız, pozitif her sayıyı da bire çeviririz. Önceki diziden şu bit dizisini elde ederiz:

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

Şimdi Linear counting algoritmasını uygulayabilir ve kardinaliteyi onunla tahmin edebiliriz.

Ama bunun bir sorunu var. Diziye maksimum sıfır sonekini koyuyoruz, peki bir gruptaki bütün hash’ler birle bitiyorsa ne olacak? Örneğin hash’in ait olduğu grubun tanımlayıcısı olarak son üç biti kullanırsak, bu hash’in “01001100” sıfır sonekinin uzunluğu sıfır olurdu — çünkü “01001” vektörü birle biter. Yani maksimumlar dizisinde 4 indeksine (100₂=4₁₀) sıfır koyardık. Ama Linear counting algoritmasında bu, hash’i dört olan bir değer bulmadığımız anlamına gelirdi; bu doğru değil.

Bu yüzden algoritmayı, maksimumlar dizisine en uzun sıfır sonekinin uzunluğunu değil, “sağdan ilk birin” indeksini koyacak biçimde değiştiririz (netlik için — indekslemeye birden başlıyoruz); bu, sıfır sonekinin uzunluğuna bir eklemekle aynı şeydir. Böylece i indeksindeki sıfır, hiçbir değerin hash’inin i’ye eşit olmadığı anlamına gelir ve böyle bir diziyi Linear counting için kullanabiliriz.

HyperLogLog’un Uygulanması

Adım adım gidelim:

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

alpha fonksiyonu hesaplanan tahmin için düzeltme değerini döndürür; bunu geçen sefer görmüştük, yalnızca HyperLogLog’da alpha grup sayısına bağlı olarak başka bir değer alır.

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

Bir sayının sonundaki sıfır bitlerinin sayısını döndüren fonksiyon.

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

Bütün değerleri tarayan, onları num_buckets gruba bölen ve her grup için sağdan ilk birin indeksini (en uzun sıfır sonekinin uzunluğu artı bir) hesaplayan fonksiyon.

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

Linear counting algoritmasının hesabı için hafifçe değiştirilmiş fonksiyon.

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

Hepsini bir araya getiren ana fonksiyon. Önce değiştirilmiş LogLog ile tahmini hesaplar; dördüncü satırda aritmetik ortalama yerine harmonik ortalamayı kullanır ve sonunda, hesaplanan tahmin grup sayısının 2,5 katından küçükse (bu durumda standart LogLog tahmininin Linear counting kullanmaktan daha kötü olacağını bekliyoruz) ve maksimumlar dizisinde en az bir sıfır varsa Linear counting biçiminde düzeltmeyi uygular (yalnızca birlerden oluşan diziyi Linear counting’de kullanamayız, bkz. önceki yazı). Peki HyperLogLog’un sonuçları nasıl?

Sırasıyla 10, 100, …, 1.000.000 kardinaliteli kümelerin kardinalitesini tahmin eden test kodunu çalıştıralım:

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)

Sonuçlar:

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

Sonuçların doğru sonuçtan her zaman yüzde birden az saptığını görüyoruz. Bu da iyi!

HyperLogLog’un Diğer İyileştirmeleri

HyperLogLog, birkaç ilginç iyileştirme daha gördü. Geriye kalan sorunlardan biri yüksek bellek ihtiyacı. Geçen sefer bellek ihtiyacını göklere çıkarıp maksimumlar dizisini saklamak için 768 baytın yeteceğini hesapladığımıza göre bu kulağa oldukça tuhaf geliyor. Ancak sorun, tek bir devasa çoklu kümenin değil, birkaç milyon küçük çoklu kümenin kardinalitesini paralel olarak hesaplamak istediğinde ya da hesaplanan maksimum dizilerini daha sonraki işlemler için bir veri tabanında saklamak istediğinde ortaya çıkar.

Örneğin bir milyar çoklu kümenin kardinalitesini aynı anda hesaplayacak olsaydık, mevcut uygulamayla 1.000.000.000 çarpı 768 bayta, yani 768 GB’a ihtiyacımız olurdu. Bir yandan bu fena değil … ama öbür yandan HyperLogLog’u daha iyi uygulayabiliyoruz.

Seyrek (Sparse) Gösterim

k=12 ayarladığımızı, yani grupları tanımlamak için 12 bit kullandığımızı ve dolayısıyla 2¹² farklı hash grubumuz olduğunu düşünelim. Algoritmanın başında 4.096 uzunluğunda bir dizi ayırmamız gerekir (bkz. count_maxims fonksiyonunun 3. satırı). Diyelim ki çoklu kümemizin üç farklı elemanı var. Bu, dizide üç farklı yere bir değer koyacağımız ve dizinin geri kalan 4.093 değerinin sıfır kalacağı anlamına gelir; geri kalan 4.093 değeri hiç kullanmadık. Bu pek verimli değil, değil mi?

Çoğunluğu sıfır olan ve kullanılmayan, ama yine de değerli bir bellek parçası kaplayan bir diziye sahip olmaktan kaçınmak için, başlangıçta değerleri [indeks, değer] çiftleri olarak saklayabiliriz. Daha iyi anlamak için bir örnek. Şu dizi

[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]

iki çift olarak bellek açısından çok daha verimli biçimde gösterilebilir:

[0, 7], [4, 12]

Bellekte bir yığın kullanılmayan yer ayırmak yerine, yalnızca gerçekten ihtiyaç duyduğumuz yeri adım adım ayırabiliriz. Bu gösterime sparse (seyrek) gösterim deriz. Ancak bir noktada bu gösterim, diziye kaydetmekten daha fazla bellek ister — o zaman seyrek gösterimi bilgi kaybı olmadan klasik diziye çevirebiliriz.

Ofsetler

Uygulama, dizideki bütün değerlerin aşağı yukarı aynı olduğunu gösterdi. Maksimumlar dizisi genellikle örneğin şöyle görünür:

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

Bütün değerler 13 sayısının civarında dolaşır. Böyle bir dizinin boyutunu küçültmenin bir başka stratejisi, her elemandan sabit bir değer çıkarmak ve bu değeri hatırlamaktır. Örneğin sekizi çıkarabiliriz:

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

Bu durumda dizideki her değer bellekte daha az yer kaplar — ilk dizide 0’dan 15’e kadar sayıları saklamamız gerekir, bunun için 4 bit gerekir; ikinci dizi için ise 3 bit yeter, çünkü yalnızca 0’dan 7’ye kadar sayıları saklıyoruz. Elbette bu, dizinin tek tek bitler düzeyinde uygulanmasını varsayar. Dizideki değerleri okumak istediğimizde, onlara not ettiğimiz değeri geri eklememiz gerekir.

…ve bir yığın başka iyileştirme. Bu alandaki araştırma hâlâ sürüyor, dolayısıyla yeni ilginç fikirler göreceğimizden eminiz. Bir sonraki yazıda HyperLogLog vektörlerinin birleşimi ve kesişimi hakkında konuşacağız, yakın bir gelecekte de milyarlarca HyperLogLog vektörünü saklamanın neden işimize yarayabileceğini anlatacağız.

Bağlantılar ve Kaynaklar

• Benim uygulamamın tamamını GitHub’da inceleyebilirsin.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] — HyperLogLog’un tanıtıldığı özgün makale.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] — Özgün HyperLogLog’un, örneğin sözünü ettiğimiz seyrek gösterim gibi iyileştirmeler içeren sürümü.