Olasılıksal Veri Yapılarına (Probabilistic Data Structures) Giriş
İşlenen veri miktarlarının artmasıyla birlikte, geleneksel veri yapıları büyük verinin getirdiği zorluklara karşı yetersiz kalabilmektedir. Bu noktada, olasılıksal veri yapıları, bellek kullanımı ve işlem hızı arasında bir denge sağlayarak, kesin (exact) sonuçlar yerine yaklaşık (approximate) ama yeterince doğru cevaplar sunabilen çözümler olarak karşımıza çıkmaktadır. Hatalı sonuçlara dayalı kayıplar, düşük bellek gereksinimleri, sabit zamanlı ($O(1)$) veya logaritmik zamanlı ($O(\log n)$)sorgu süreleri ve ölçeklenebilirlik ile telafi edilir. Örneğin, bloom filtreleri, bir elemanın kümede olup olmadığını sorgularken yanlış pozitif (false positive) sonuçlar verebilir ancak yanlış negatif (false negative) sonuçlar asla üretmez.
Hash fonksiyonları, verileri daha küçük ve sabit boyutlu bir forma indirgediklerinden, verilerin hızlı ve verimli bir şekilde işlenmesini sağlarlar. Olasılıksal veri yapılarının temelini oluştururlar.
Kriptografik hash fonksiyonlarının aksine, olasılıksal veri yapılarında kullanılan hash fonksiyonlarının kabul edilebilir bir hata olasılığı ile hızlı olması ve düşük çakışma olasılığı (collision probability) gereklidir, bu sayede büyük miktardaki veriler hızlıca hashlenebilir.
Üyelik (Membership) Sorguları
Üyelik sorguları, bir elemanın bir kümede olup olmadığını kontrol eder.
Bloom filtresi, düşük bellek tüketimi ile hızlı bir sorgulama imkanı sağlar. Yanlış negatif sonuçlar üretebilir; yani bir elemanın kümede olduğu yanıtını verirken eleman gerçekte kümede olmayabilir. Yanlış negatif ise mümkün değildir. Dolayısıyla bir elemanın bir küme içindeki yokluğunu garanti eder. Web tarayıcılarında zararlı URL'lerin tespit edilmesi, veritabanlarında hızlı arama yapılması gibi alanlarda sıklıkla kullanılır. Bir web tarayıcısı, bilinen kötü URL'lerin bir listesini tutmak yerine, bu URL'lerin Bloom filtresini kullanır. Bir URL'ye erişilmeye çalışıldığında, Bloom filtresi bu URL'nin listede olup olmadığını kontrol eder. Eğer filtre "yok" derse, tarayıcı URL'ye güvenle erişebilir.
Kardinalite (Cardinality) Tahmini
Büyük verisetlerinde benzersiz (distinct) elemanların sayımı için kullanılır.
HyperLogLog, kardinalite tahmini için kullanılan bir veri yapısıdır. Bu algoritma, çok büyük veri setlerindeki benzersiz eleman sayısını düşük bellek kullanarak tahmin etmeyi sağlar. LogLog algoritmasının geliştirilmiş bir versiyonu olan HyperLogLog, özellikle büyük veri analizlerinde, benzersiz kullanıcı sayısını veya farklı olayların sayısını tahmin etmek için kullanılır. Örneğin, bir web sitesinin günlük ziyaretçi sayısını tahmin etmek için kullanılabilir. Her ziyaretçi için benzersiz bir hash değeri oluşturulur ve HyperLogLog algoritması bu değerleri kullanarak yaklaşık benzersiz ziyaretçi sayısını hesaplar.
Frekans Analizi (Frequency Analysis)
Veri akışlarındaki (data stream) elemanların sıklığını tahmin etmek için kullanılırlar.
Count-min sketch algoritması, gerçek frekansı hiçbir zaman olduğundan düşük tahmin etmez, ancak daha fazla tahmin edebilir (overestimation). Bu algoritma, özellikle veri akışlarında (data stream) en sık görünen öğeleri tespit etmek için kullanılır. Örneğin, bir sosyal medya platformunda en çok bahsedilen hashtag'leri bulmak için kullanılabilir.
Sıralama (Ranking)
Büyük veri setlerinde yüzdelik dilimleri (quantiles) hesaplamak için kullanılırlar. t-digest algoritması bu tip bir algoritmadır. t-digest, büyük veri setlerindeki değerlerin dağılımını özetlemek ve yüzdelik dilimleri hesaplamak için kullanılır. Örneğin, bir e-ticaret sitesindeki ürün fiyatlarının yüzdelik dağılımını belirlemek için kullanılabilir. Bu, satıcıların fiyatlandırma stratejilerini optimize etmelerine yardımcı olabilir.
Benzerlik (Similarity)
İki veri kümesi (metin dökümanı, DNA dizileri vb) arasındaki benzerliği hızlıca hesaplayabilmek için kullanılırlar. Jaccard benzerliği ve Locality Sensitive Hashing (LSH) bu tip algoritmalardır. Jaccard benzerliği, iki küme arasındaki ortak elemanların sayısının, kümelerin birleşimindeki eleman sayısına oranıdır. LSH ise, benzer öğelerin aynı hash değerine sahip olma olasılığını artıran bir hash fonksiyonu ailesidir. Bu teknikler, metin belgelerinin benzerliğini, DNA dizilerinin karşılaştırılmasını veya öneri sistemlerinde benzer öğelerin bulunmasını sağlar. Örneğin, bir arama motoru, benzer web sayfalarını tespit etmek için bu teknikleri kullanabilir.
Kaynaklar
- Probabilistic Data Structures and Algorithms, Andrii Gakhov