q-digest
q-digest algoritması, büyük veri akışlarında yüzdelikleri (quantile) yaklaşık olarak hesaplamak için kullanılan bir olasılıksal veri yapısıdır. Sınırlı bellek kullanımı ile verilerin dağılımının özetini tutar.
Algoritmanın çalışabilmesi için öncelikle işlenecek verilerin bulunacağı aralığın (universe) tanımlanması gerekir:
$$ U = [\sigma_{min},\sigma_{max}] $$
Bu aralık, veri kümesindeki olası en küçük ve en büyük değerleri belirtir. Özetlenmek istenen veri kümesi $S$ ise şu şekilde tanımlanır:
$$ S={(v_1,w_1),(v_2,w_2),\ldots,(v_m,w_m)} $$
Burada $v$ bir elemanı (değeri) , $w$ ise o öğrenin ağırlığını veya frekansını (kaç defa tekrarlandığını) ifade eder.
q-digest, mantıksal olarak bir tam ikili ağaç (complete binary tree) yapısı üzerine kuruludur. Ancak, bellek verimliliği sağlamak amacıyla bu ağacın tamamı değil, yalnızca veri içeren düğümleri (node) saklanır. Bu ağacın özellikleri :
- Ağacın en alt seviyesindeki yaprak düğümler, $U$ veri aralığındaki tekil değerlere karşılık gelir.
- İç düğümler, belirli bir değer aralığını $[i,j]$ temsil eder.
- Ağaçtaki her düğüm (hem yaprak hem de iç düğümler), kendi temsil ettiği değere veya aralığa düşen toplam veri frekansını (ağırlığını) tutan bir sayım (count) değerine sahiptir.
q-digest'in en önemli avantajlarından biri, bellek kullanımını optimize etmesidir. Bu, özellikle düşük frekanslı (az tekrarlanan) öğelerin bilgilerini birleştirerek sağlanır. Örneğin, {3:1, 4:1} (3 değeri 1 kez, 4 değeri 1 kez geçmiş) gibi ayrı ayrı tutulan bilgiler, {[3,4]: 2} (3 ile 4 arasındaki değerler toplam 2 kez geçmiş) şeklinde birleştirilebilir. Bu birleştirme işlemi, birebir öğe bilgisi yerine aralık bilgisi sunduğu için bir miktar bilgi kaybına yol açsa da, genel dağılım hakkında kabul edilebilir bir doğrulukla özet sunar.
Sıkıştırma işlemi, veri yapısının boyutunu kontrol altında tutmak için belirli kurallara göre yapılır:
- Kural 1 (iç düğümler için): Bir v iç düğümünün sayım değeri $count(v)$, toplam frekansın (n) sıkıştırma parametresine (k) bölümünden küçük veya eşit olmalıdır:
$$ count(v) \leq \frac{n}{k} $$
- Kural 2 (her iç düğüm ve kardeşleri için): Bir v iç düğümü için, eğer v'nin bir kardeşi (sibling) varsa, v'nin sayımı, kardeşinin sayımı ve ebeveynlerinin (parent) sayımının toplamı, n/k'dan büyük olmalıdır:
$$ count(v) + count(sibling) + count(parent) > \frac{n}{k} $$
Bu kurallar, düşük frekanslı yaprakların bilgilerinin üst düğümlerde toplanarak veri yapısının sıkıştırılmasını ve yönetilebilir boyutta kalmasını sağlar. k parametresi, sıkıştırma seviyesini ve dolayısıyla doğruluk ile bellek kullanımı arasındaki dengeyi ayarlar.
q-digest algoritmasının temel çalışma adımları şu şekilde özetlenebilir:
- Başlatma: Boş bir q-digest (yani kök düğümü dışında hiçbir düğümü olmayan bir ikili ağaç) oluşturulur. Sıkıştırma parametresi $k$ belirlenir. Veri aralığı $U$ tanımlanır.
- Veri Ekleme (Update): Yeni bir $(v,w)$ veri öğesi geldiğinde, ağaç üzerinde $v$ değerine karşılık gelen yaprak düğüm (veya $v$'yi içeren en dar aralığa sahip düğüm) bulunur. Bu düğümün ve ebeveynlerinin count değerleri $w$ kadar artırılır.
- Sıkıştırma (Compress): Sayım değerleri güncellendikten sonra, ağaç üzerinde sıkıştırma kuralları (Kural 1 ve Kural 2) kontrol edilir. Sıkıştırma kurallarına göre, birleştirilebilecek düğümler belirlenir. Sayımlar ebeveyn düğümlere aktarılır, çocuk düğümler silinir.
- Yüzdelik Sorgulama (Query): Belirli bir q yüzdeliğine karşılık gelen değeri bulmak için:
- İstenen yüzdelik $q$ için, toplam frekansın $n$ ile çarpımı $n \cdot q$ hesaplanır.
- Ağaç üzerinde dolaşarak, bu değere ulaşan en küçük düğüm bulunur. Bu düğümün aralığı, istenen yüzdelik değeri temsil eder.
t-Digest algoritması, q-digest'in bazı sınırlamalarını aşmak için Ted Dunning tarafından geliştirilmiş modern bir alternatiftir. q-digest algoritması veri aralığının önceden bilindiği durumlarda ve uniform doğruluk (tüm yüzdeliklerde aynı hata oranı) gerektiğinde tercih edilir. t-digest algoritması ise veri aralığının bilinmediği ve ekstrem yüzdeliklerde (%99.9, %99.99 gibi) yüksek doğruluk gerektiği durumlarda tercih edilir.
Bir sonraki yazıda görüşmek üzere.