🔢 HyperLogLog: Probabilistic Cardinality Estimation

Büyük Veri Analitiğinde Olasılıksal Veri Yapıları: HyperLogLog (HLL) Tasarımı ve Analizi

Cardinality Estimation problemini çözen HyperLogLog algoritmasının harici kütüphane bağımlılığı olmadan sıfırdan Python implementasyonu, teorik hata analizi ve kapsamlı test süiti.

---

📋 İçindekiler

• Proje Hakkında
• Algoritma: HyperLogLog Nedir?
• Mimari ve Bileşenler
• Matematiksel Temel
• Kurulum ve Çalıştırma
• Kullanım Örnekleri
• Test Sonuçları
• Hata Analizi
• Proje Yapısı
• Referanslar

---

Proje Hakkında

Bu proje, Kardinalite Tahmini (Cardinality Estimation) problemini olasılıksal yöntemlerle çözen HyperLogLog (HLL) algoritmasının:

• Sıfırdan (from scratch) Python implementasyonu — hyperloglog paketi veya benzeri hazır kütüphaneler kullanılmamıştır.
• Teorik hata analizinin matematiksel olarak doğrulanması.
• Birleştirilebilirlik (mergeability) özelliğinin veri kayıpsız olarak gösterilmesi.

Neden HyperLogLog?

Yöntem	Bellek	Hata	Ölçeklenebilirlik
Tam sayım (HashSet)	O(n)	%0	❌ Milyarlarca elemanda imkansız
Linear Counting	O(n/log n)	Düşük	⚠️ Büyük n'de yetersiz
HyperLogLog	O(log log n)	~%1–3	✅ Milyarlarda çalışır

Redis, Google BigQuery, Amazon Redshift ve Elasticsearch gibi üretim sistemleri HLL kullanır.

---

Algoritma: HyperLogLog Nedir?

HyperLogLog, Philippe Flajolet ve arkadaşları (2007) tarafından geliştirilen, olasılıksal bit gözlemi temelli bir kardinalite tahmincisidir.

Temel Fikir

Bir kümedeki benzersiz eleman sayısını bulmak için her elemanı hash'leyip hash değerinin başındaki sıfır dizisinin uzunluğuna bakılır. İstatistiksel olarak:

• Eğer maksimum gözlemlenen baştaki sıfır sayısı k ise, kardinalite tahminimiz 2^k'dır.
• Birden fazla kova (bucket) kullanarak varyans düşürülür.
• Kovalar üzerinde harmonik ortalama alınarak sapma azaltılır.

Adım Adım Çalışma Prensibi

Eleman gelir  →  Hash'le (MurmurHash3 / SHA-256)
                      ↓
               [ b1 b2 ... bp | bp+1 ... b32 ]
                    ↑                ↑
              İlk p bit:        Kalan (32-p) bit:
              Kova indeksi j    ρ = baştaki sıfır sayısı + 1
                      ↓
               registers[j] = max(registers[j], ρ)
                      ↓
               E = α_m · m² · (Σ 2^{-M[j]})⁻¹
                      ↓
               Düzeltme faktörleri (küçük/büyük aralık)
                      ↓
               Kardinalite tahmini

---

Mimari ve Bileşenler

1. Hash Katmanı — MurmurHash3

class MurmurHash3:
    """Austin Appleby'ın MurmurHash3 algoritması, sıfırdan bit manipülasyonu."""

Neden MurmurHash3?

• Kriptografik hash'lere (SHA-256) kıyasla 10–20x daha hızlı
• Düşük çarpışma oranı ve uniform dağılım
• HLL için ideal: hız kritik, güvenlik değil
• 32-bit çıktı → p ≤ 16 için yeterli bit uzayı

2. Bucketing Mekanizması

def _get_bucket_and_rho(self, hash_val: int):
    j = hash_val >> (self.b - self.p)      # İlk p bit → kova indeksi
    w = hash_val & ((1 << remaining) - 1)  # Kalan bitler
    rho = remaining - w.bit_length() + 1   # Baştaki sıfır sayısı + 1

• m = 2^p kova, p ∈ [4, 16] hassasiyet parametresi
• Her kova bağımsız maksimum ρ değerini tutar

3. Register Yapısı

self.registers: List[int] = [0] * self.m
# Güncelleme: yalnızca yeni ρ daha büyükse yaz
if rho > self.registers[j]:
    self.registers[j] = rho

• Boyut: m adet integer (pratikte 5-6 bit yeterli)
• p=10 için yalnızca 640 byte bellek

4. Harmonik Ortalama Tahmini

harmonic_sum = sum(2.0 ** (-r) for r in self.registers)
E = self._alpha * (self.m ** 2) / harmonic_sum

Neden Harmonik Ortalama?
Aritmetik ortalama büyük ρ değerlerine aşırı duyarlı (sağa çarpık dağılım). Harmonik ortalama bu outlier etkisini bastırır.

5. Düzeltme Faktörleri (Correction Factors)

# α_m sabiti (Flajolet et al., 2007)
_ALPHA = {16: 0.673, 32: 0.697, 64: 0.709}
_ALPHA_DEFAULT_LARGE = 0.7213  # m ≥ 128 için

# Küçük aralık: Linear Counting
if E <= 2.5 * self.m and zero_count > 0:
    E = self.m * math.log(self.m / zero_count)

# Büyük aralık düzeltmesi
if E > 2^b / 30:
    E = -2^b * log(1 - E / 2^b)

Aralık	Koşul	Yöntem
Küçük	E < 2.5·m ve sıfır register var	Linear Counting
Orta	2.5·m ≤ E ≤ 2^b/30	Ham HLL tahmini
Büyük	E > 2^b/30	Log-tabanlı düzeltme

6. Merge (Birleştirme)

def merge(self, other: "HyperLogLog") -> "HyperLogLog":
    merged.registers = [max(a, b) for a, b in zip(self.registers, other.registers)]

Özellik: merge(HLL_A, HLL_B) → |A ∪ B| tahmini, orijinal veriye erişim gerektirmez.
Bu özellik dağıtık sistemlerde (farklı sunuculardan gelen HLL'lerin merkezi toplanması) kritik öneme sahiptir.

---

Matematiksel Temel

Standart Hata Formülü

$$\sigma \approx \frac{1.04}{\sqrt{m}}$$

p	m = 2^p	σ (Teorik)	Bellek
4	16	%26.00	10 B
8	256	%6.50	160 B
10	1,024	%3.25	640 B
12	4,096	%1.63	2.5 KB
14	16,384	%0.81	10 KB
16	65,536	%0.41	40 KB

Sonuç: m her 4 katına çıktığında hata yarıya düşer — O(1/√m) karmaşıklığı.

---

Kurulum ve Çalıştırma

Gereksinimler

Python >= 3.8
matplotlib  # yalnızca grafik üretimi için

Kurulum

git clone https://github.com/KULLANICI_ADI/hyperloglog-hll.git
cd hyperloglog-hll
pip install matplotlib   # opsiyonel, analiz grafikleri için

Testleri Çalıştır

python tests/test_hyperloglog.py

Analiz Grafiklerini Üret

python analysis/analysis.py
# Çıktı: docs/hll_analysis.png

---

Kullanım Örnekleri

Temel Kullanım

from src.hyperloglog import HyperLogLog

# p=10 → m=1024 kova, teorik hata ≈ %3.25
hll = HyperLogLog(p=10)

# Eleman ekleme
for user_id in range(1_000_000):
    hll.add(f"user_{user_id}")

print(f"Tahmin: {hll.count():,.0f}")   # ≈ 1,000,000
print(f"Teorik hata: ±{hll.error_bound()*100:.2f}%")
print(f"Bellek: {hll.memory_bytes()} byte")

Merge (Birleştirme)

hll_server_1 = HyperLogLog(p=10)
hll_server_2 = HyperLogLog(p=10)

# Her sunucu kendi verisini işler
hll_server_1.add_batch([f"event_{i}" for i in range(50_000)])
hll_server_2.add_batch([f"event_{i}" for i in range(30_000, 80_000)])

# Orijinal veriye gerek kalmadan birleştir
hll_union = hll_server_1.merge(hll_server_2)
print(f"Toplam benzersiz event tahmini: {hll_union.count():,.0f}")
# Gerçek: 80,000 → Tahmin: ~78,000–82,000

SHA-256 Tabanlı Hash

# Daha geniş bit uzayı gerekiyorsa (büyük kardinaliteler)
hll = HyperLogLog(p=12, use_sha256=True)

---

Test Sonuçları

TEST 1: Hash Fonksiyonu Kalitesi        ✓ Uniform dağılım doğrulandı
TEST 2: Kardinalite Doğruluğu           ✓ 100 → 1,000,000 arası tüm PASS
TEST 3: m vs Hata Analizi               ✓ p=4..16, monoton azalma doğrulandı
TEST 4: Merge Özelliği                  ✓ 5 senaryo, tüm PASS
TEST 5: Belirleyicilik (Determinism)    ✓ 5 çalıştırma = özdeş sonuç
TEST 6: Teorik Formül Doğrulaması       ✓ σ ≈ 1.04/√m tablo üretildi
TEST 7: Farklı Veri Tipleri             ✓ int, float, str, UUID — tüm PASS

---

Hata Analizi

Grafikler şunları göstermektedir:

1. Teorik vs Ampirik hata — formülün ampirik olarak doğrulanması
2. Kardinalite sweep — LC ↔ HLL ↔ Büyük aralık geçiş noktaları
3. Bellek-Doğruluk takas eğrisi — log-log ölçekte doğrusal ilişki
4. σ = 1.04/√m formülü — p değerlerine göre görselleştirme

---

Proje Yapısı

hyperloglog/
├── src/
│   └── hyperloglog.py        # Çekirdek HLL implementasyonu
│       ├── MurmurHash3       # 32-bit hash fonksiyonu
│       ├── sha256_hash()     # 64-bit alternatif hash
│       └── HyperLogLog       # Ana sınıf
├── tests/
│   └── test_hyperloglog.py   # 7 test kategorisi
├── analysis/
│   └── analysis.py           # Hata analizi + matplotlib grafikleri
├── docs/
│   └── hll_analysis.png      # Üretilen analiz grafikleri
└── README.md

---

Referanslar

1. Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007). HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. DMTCS Proceedings, AH, 137–156.
2. Heule, S., Nunkesser, M., & Hall, A. (2013). HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm. EDBT/ICDT.
3. Appleby, A. MurmurHash3. https://github.com/aappleby/smhasher

---

Lisans

MIT License — Detaylar için LICENSE dosyasına bakınız.