Bloomier Filtresi: Statik Destekli Arama Tabloları İçin Verimli Bir Veri Yapısı

Bernard Chazelle†
Joe Kilian‡
Ronitt Rubinfeld‡
Ayellet Tal§

Özet

Yaklaşık değerlendirme sorgularını desteklemek amacıyla, statik destekli bir fonksiyonu kompakt biçimde kodlamak için kullanılan bir veri yapısı olan Bloomier filtresini tanıtıyoruz. Önerdiğimiz yapı, ağlar ve veritabanlarında yoğun biçimde kullanılan ustaca bir karma (hash) şeması olan klasik Bloom filtresini genelleştirir. Bloom filtresinin temel özelliği olan alan verimliliği, çok küçük bir yanlış-pozitif oranı pahasına elde edilir.

Bloom filtreleri yalnızca küme üyeliği sorgularını ele alabilirken, Bloomier filtreleri keyfi fonksiyonlarla çalışabilir. Basitlik ve optimalite açısından farklılık gösteren çeşitli tasarımlar sunuyor ve geliştirdiğimiz yapıların (neredeyse) optimal olduğunu göstermek için alt sınırlar sağlıyoruz.

Geniş biçimde rapor edilen bir haber¹, David Nelson adlı hava yolu yolcularının karşı karşıya olduğu güncel durumu anlatmaktadır; bu isimdeki pek çok kişi Amerika Birleşik Devletleri genelindeki havaalanlarında ek güvenlik kontrolleri için işaretlenmektedir:

“Havaalanlarındaki güvenliğin zaten yeterince sıkı olduğunu düşünüyorsanız, adınızın havayolu bilgisayarlarında olası bir terörist olarak kırmızı bayrakla belirdiğini hayal edin. Ülke genelindeki David Nelsonların başına gelen tam olarak bu.”

Sorun o kadar büyüktür ki birçok David Nelson artık tamamen uçmayı bırakmıştır. David Nelson adı kırmızı bayrak kaldırsa da güvenlik yetkilileri bu isimde bir terör şüphelisi olup olmadığını söylememektedir.

“Transportation Security Administration sözcüsü Nico Melendez, sorunun havayolları tarafından kullanılan isim eşleştirme teknolojisinden kaynaklandığını söyledi.”

Bu hikâye, yanlış negatifler ve yanlış pozitifler arasında denge kurulmaya çalışıldığında ortaya çıkan yaygın bir problemi göstermektedir: eğer kişi hiçbir yanlış negatifi kabul etmek istemezse, bunun bedeli çoğu zaman yüksek bir yanlış-pozitif oranı olur. İdeal olarak kişi, özellikle sorunlu yanlış pozitifleri düzeltecek şekilde sistemi ayarlamak isterken aynı zamanda yanlış negatif olasılığından da kaçınmak ister (örneğin dünyadaki David Nelsonların hayatını kolaylaştırırken Osama Bin Laden’in hayatını kolaylaştırmadan). Bu çalışmada bu meseleleri aşağıda açıklanan Bloom filtrelerinin daha sıradan örneği üzerinden ele alıyoruz.

Tarihsel Arka Plan

Bloom filtreleri, bir küme için üyelik sorgularını destekleyen son derece kompakt bir veri yapısı sağlar [1]. Alan gereksinimleri, hatasız veri yapıları için bilgi kuramsal alt sınırların önemli ölçüde altına düşer. Verimliliklerini küçük bir yanlış-pozitif oranı pahasına elde ederler (kümede bulunmayan öğelerin küçük bir sabit olasılıkla kümede varmış gibi rapor edilmesi), ancak yanlış negatif üretmezler (kümede bulunan öğeler her zaman kümede oldukları şekilde tanınır).

Bloom filtreleri, depolama alanının sınırlı olduğu ve ara sıra yanlış pozitiflerin kabul edilebilir olduğu durumlarda pratikte yaygın biçimde kullanılır. Ağlarda birçok kullanım alanı vardır [2]:

• örtüşmeli ve eşler arası ağlarda işbirliği [5, 8, 17]
• kaynak yönlendirme [15, 26]
• paket yönlendirme [12, 30]
• ölçüm altyapıları [9, 29]

Bloom filtreleri, dağıtık veritabanlarında iceberg sorgularını desteklemek, diferansiyel dosya erişimi sağlamak ve join ile semijoin işlemlerini hesaplamak için kullanılır [7, 11, 14, 18, 20, 24]. Ayrıca parola veri yapılarında üyelik kontrolünü yaklaşık olarak yapmak için [21], web önbellekleme için [10, 27] ve yazım denetimi için [22] de kullanılır.

Bloom filtrelerinin çeşitli varyantları önerilmiştir:

• Zayıflatılmış Bloom filtreleri (Attenuated Bloom filters) [26], en kısa yol uzaklığı bilgilerini depolamak için Bloom filtrelerinden oluşan diziler kullanır.
• Spektral Bloom filtreleri (Spectral Bloom filters) [7], veri yapısını frekans tahminlerini destekleyecek şekilde genişletir.
• Sayma Bloom filtreleri (Counting Bloom filters) [10], her girişin tek bir bit yerine küçük bir sayaç olmasına izin verir; ekleme ve silme işlemleri sayaçları artırır veya azaltır.
• Sıkıştırılmış Bloom filtreleri (Compressed Bloom filters) [23], filtre bir mesaj olarak iletildiğinde kullanışlıdır; parametreler boyut ile yanlış-pozitif oranı arasında denge kurulacak şekilde ayarlanabilir.

“Aman Tanrım, işte yine bir David Nelson”
— Bilet Görevlisi, Los Angeles Havaalanı (Kaynak: BBC News)

1 Giriş

Çok az sayıdaki sorunlu yanlış pozitifi ortadan kaldırmak için kullanılan standart bir tekniğin istisna listesi tutmak olduğunu belirtelim. Ancak bu çözüm, liste büyüdüğünde (örneğin gerçek pozitiflerin sayısıyla karşılaştırılabilir olduğunda) hem arama süresi hem de depolama açısından iyi ölçeklenmez.

Bu Çalışma

Bir Bloom filtresi, bir küme için —ya da eşdeğer biçimde kümenin Boole karakteristik fonksiyonu için— kayıplı bir kodlama şemasıdır. Bloom filtreleri bir küme üzerinde üyelik sorgularına izin verirken, biz bu yaklaşımı Bloomier filtresi adı verilen ve keyfi fonksiyonları kodlayabilen bir veri yapısına genelleştiriyoruz.

Başka bir deyişle, Bloomier filtreleri alanın elemanlarının bir alt kümesiyle değerler ilişkilendirmeye olanak tanır. Fonksiyonun yalnızca alanın küçük bir bölümünde tanımlı olduğu durumlarda yöntem oldukça iyi performans gösterir; bu durum pratikte sık görülür.

Bizim (hayali) terörist tespit örneğimizde, şüpheli isimler suspect değerine, popüler fakat şüpheli olmayan isimler (örneğin David Nelson) sounds-suspicious-but-really-ok değerine eşlenir. Bu sırada neredeyse tüm diğer isimler ok değerine eşlenir. Bu üçüncü kategori tek hata kaynağıdır.

Dolayısıyla Bloomier filtreleri, Bloom filtrelerini fonksiyonlara genelleyerek aynı zamanda depolama alanının ekonomik kullanımını korur. Ayrıca fonksiyonun destek kümesi değişmediği sürece fonksiyon üzerinde dinamik güncellemelere de izin verir.

Bloomier filtrelerinin bir diğer uygulaması meta-veritabanı oluşturmaktır; yani küçük bir veritabanı koleksiyonunun birleşimi için bir dizin. Bloomier filtresi her girdiye ilişkin bilginin hangi veritabanında bulunduğunu takip eder; böylece kullanıcı doğrudan ilgili veritabanlarına geçebilir ve alakasız olanları atlayabilir.

Bu tür meta-veritabanı örnekleri Web üzerinde zaten bulunmaktadır:

• BibFinder (Bilgisayar Bilimi bibliyografyası için bir aracı)
• Debriefing (diğer arama motorlarının sonuçlarını kullanan bir meta arama motoru)
• dünya genelindeki posta kodları için meta siteler

Veri veya kod birden fazla konuma dağıtıldığında Bloomier filtreleri dizinin yerel kopyalarını tutabilir.

Sonuçlarımız

f aşağıdaki biçimde bir fonksiyon olsun

D = {0, ..., N − 1}

den

R = {⊥, 1, ..., 2^r − 1}

kümesine, öyle ki f(x) = ⊥ değeri S ⊆ D sabit alt kümesinin (boyutu n) dışındaki tüm x değerleri için geçerlidir.

(⊥ sembolünü ya 0’ı göstermek için kullanırız (bu durumda fonksiyonun destek kümesi S olur) ya da f fonksiyonunun S dışında tanımlı olmadığını belirtmek için kullanırız.)

Bloomier filtreleri f fonksiyonu için sorguya izin verir:

• S içindeki herhangi bir nokta için her zaman doğru
• D \ S içindeki herhangi bir nokta için neredeyse her zaman doğru

Özellikle rastgele bir x ∈ D \ S için çıktı f(x) = ⊥ değerini olasılığı 1’e keyfi derecede yakın olacak şekilde döndürür.

Bloomier filtreleri özellikle alan boyutu N, n değerinden çok büyük olduğunda (yani N / n oranı çok büyük olduğunda) oldukça etkilidir.

Yapının özellikleri:

• Sorgu süresi: sabit
• Alan gereksinimi: O(nr)

Bu sonuçlar şu yöntemlerle karşılaştırıldığında oldukça avantajlıdır:

• saf sınır O(Nr)
• tüm değerlerin listelenmesiyle elde edilen O(nr log N) sınırı
• mükemmel karma (perfect hashing) ile elde edilen O(n log(N/n)) sınırı [3]

(Bloomier filtrelerinden farklı olarak bu yöntemler hata üretmez.)

Bloomier filtreleri ayrıca O(nr) alanı korurken dinamik güncellemeleri de destekleyebilir. x ∈ S için f(x) değeri değiştirilebilir; ancak destek kümesi S değiştirilemez.

Ayrıca sonuçlarımızın özünde optimal olduğunu gösteren alt sınırlar da kanıtlıyoruz:

• Rastgeleleştirme gereklidir: deterministik Bloomier filtreleri büyük alanlar için doğrusal alan elde edemez.
• Destek kümesini değiştiren güncellemelere (S’ye eleman ekleme/çıkarma) izin vermek süperdoğrusal alan gerektirir.

Tekniklerimiz

İlk uygulama yaklaşımımız, birden fazla Bloom filtresini kademeli bir boru hattı şeklinde birleştirir ve pratik, neredeyse optimal bir çözüm sağlar.

Yapıyı daha da iyileştirmek için [4, 6, 19, 28] çalışmalarından esinlenen, rastgele karma fonksiyonlarının genişletici benzeri özelliklerine dayanan cebirsel bir yaklaşım izliyoruz.

Bloom filtrelerinde olduğu gibi ideal karma fonksiyonlarına erişim varsayılır. Algoritmalarımız bu model altında analiz edilir; ancak pratikte sezgisel olarak gerçek karma fonksiyonları kullanılabilir.

2 Bir Isınma: Bloom Filtresi Kademesi

Bloom filtrelerinden oluşan kademeli bir boru hattına dayalı basit ve neredeyse optimal bir Bloomier filtresi tasarımını açıklıyoruz.

Örnek amacıyla şu duruma kendimizi sınırlıyoruz:

R = {⊥, 1, 2}

Tanımlar:

• A, S içinde 1 değerine eşlenen alt küme
• B, S içinde 2 değerine eşlenen alt küme

Açık çözüm — bir arama anahtarı x’i A için bir Bloom filtresi ve B için başka bir Bloom filtresi olmak üzere iki filtreden geçirmek — işe yaramaz. Her iki filtre de pozitif dönerse sonuç belirsiz olur.

Olası bir çözüm anahtarı Bloom filtresi çiftlerinden oluşan bir dizi üzerinden geçirmektir:

(F(A_i), F(B_i)), i = 0, 1, ..., α

İlk çift şu kümelere karşılık gelir:

A₀ = A, B₀ = B

İdeal durumda hiçbir anahtar her iki testi de geçmez; ancak yanlış pozitifler oluştuğundan ek çiftler gerekir.

Tanımlar:

• A_i = A_{i−1} içinde olup F(B_{i−1}) filtresini geçen anahtarlar
• B_i = B_{i−1} içinde olup F(A_{i−1}) filtresini geçen anahtarlar

Eşdeğer biçimde:

A_i = A_{i−1} ∩ B*_{i−1}
B_i = B_{i−1} ∩ A*_{i−1}

burada A*_i ve B*_i ilgili filtrelerin yanlış pozitiflerini gösterir.

Sorgu Prosedürü

x ∈ D verildiğinde:

1. F(A₀) ve F(B₀) test edilir.
2. Tam olarak biri başarılıysa 1 veya 2 döndürülür.
3. İkisi de başarısızsa ⊥ döndürülür.
4. İkisi de başarılıysa (F(A₁), F(B₁)) ile yinelemeli olarak devam edilir.

Yineleme giderek küçülen aday kümeleri üzerinde devam eder.

|A| = |B| = n olduğunu varsayalım. n_i = max{|A_i|, |B_i|} olsun. Tüm filtreler k adet karma fonksiyonu kullanır.

Her F(A_i) ve F(B_i) filtresi şu büyüklükte bir dizi alır:

2 k_i k n_i

Çift sayısı α, n_i = 0 olacak en küçük i değeridir.

A_i içindeki bir anahtar, F(B_i) içinde yanlış pozitif üretirse A_{i+1} kümesine girer; bunun olasılığı en fazla:

2^{−k_i + 1}

olur.

Bu şu sonucu verir:

E[n_i] ≤ n · 2^{−(k_i + 1 − k)/(k − 1)}

ve

E[α] ≤ 2 log log n / log k

Bir arama anahtarının i‑inci filtreye ulaşma olasılığı 2^{−k_i}’den küçüktür; dolayısıyla beklenen arama süresi sabittir.

Beklenen depolama miktarı:

∑{i=0}^{α} 2 k_i k n_i = k n ∑{i=0}^{α} 2^{−(k_i − k)/(k − 1)} = O(k n)

Eğer N, n’in bir polinomuysa, yinelemeyi n_i ≈ n / log n olduğunda sonlandırabilir ve mükemmel karma (perfect hashing) [3, 13] kullanabiliriz; bu yöntem sabit zaman ve O(n) ek bit gerektirir.

Yüksek olasılıkla, rastgele bir karma fonksiyonu kümesi aşağıdaki özelliklere sahip bir Bloomier filtresi sağlar:

• Depolama: O(k n) bit
• Yanlış pozitifler: D kümesinin en fazla O(2^{−k}) oranı
• Arama süresi: en kötü durumda O(log log n), ortalamada sabit

3 Optimal Bir Bloomier Filtresi

Verilenler:

• alan D = {0, ..., N − 1}
• değer kümesi R = {⊥, 1, ..., |R| − 1}
• alt küme S = {t₁, ..., t_n} ⊆ D

şu fonksiyonu kodluyoruz:

f : D → R

öyle ki:

• f(t_i) = v_i (1 ≤ i ≤ n için)
• f(x) = ⊥ (x ∈ D \ S için)

Fonksiyon şu atama ile belirtilir:

A = {(t₁, v₁), ..., (t_n, v_n)}

R içindeki fonksiyon değerleri, aşağıdaki toplamsal grubun elemanları olarak kodlanır:

Q = {0,1}^q

burada toplama işlemi bit düzeyinde mod 2 olarak tanımlanır. Yanlış-pozitif oranı 2^{−q} ile orantılıdır; bu nedenle q yeterince büyük olmalıdır.

R içindeki herhangi bir x, encode(x) adlı q bitlik ikili kodlamasıyla temsil edilir. Tersine y ∈ Q verildiğinde decode(y), eğer |R|’den küçükse karşılık gelen sayıyı, aksi halde ⊥ değerini döndürür.

Tanımlayalım:

r = ⌈log |R|⌉

Bir A ataması verildiğinde A(t) ile t’ye atanan değeri gösteririz.

Π, S üzerinde tam bir sıralama olsun. Eğer a sıralamada b’den sonra geliyorsa a >_Π b yazarız. Π(i), bu sıralamaya göre S’nin i‑inci elemanını gösterir.

Her (D, m, k) üçlüsü için şu rastgele karma fonksiyonuna erişim olduğunu varsayarız:

hash : D → {1, ..., m}^k

bu fonksiyon k adet rastgele tablo konumu sağlar.

Tanım 3.1

Böyle bir karma fonksiyonu için:

hash(t) = (h₁, ..., h_k)

{h₁, ..., h_k} kümesine t’nin komşuluğu denir ve N(t) ile gösterilir.

Bloomier filtre tabloları A atamasını saklar ve şu çağrı ile oluşturulur:

create(A)[m, k, q]

burada (m, k, q) uygulamayı optimize etmek için seçilen parametrelerdir.

Amacımız tek taraflı hataya sahip, doğrusal alanlı bir veri yapısı geliştirmek ve sabit zamanda tablo sorgularını desteklemektir.

İşlemler şunlardır:

• create(A): veri yapısı Table’ı oluşturur. {t₁, ..., t_n} alt alanı S olarak gösterilir.
• set_value(t, v, Table): t ∈ D ve v ∈ R için t ile v değerini ilişkilendirir.

† Princeton University ve NEC Laboratories America — chazelle@cs.princeton.edu
‡ NEC Laboratories America — {joe | ronitt}@nec-labs.com
§ Technion ve Princeton University — ayellet@ee.technion.ac.il

¹ http://news.bbc.co.uk/2/hi/americas/2995288.stm
http://www.kgun9.com/story.asp?TitleID=3201&ProgramOption=News

• create (A): Bir atama verildiğinde, alan elemanı t için Table içinde kayıt oluşturur. t’nin S içinde olması gerekir.

• lookup (t, Table): t ∈ S için lookup(t, Table) işlemi t ile ilişkilendirilmiş son değer v’yi döndürür. D \ S kümesinin ε oranından daha azı hariç tüm elemanlar için lookup(t, Table) ⊥ döndürür (yani t’nin S içinde olmadığını doğrular). D \ S’nin geri kalan elemanları için lookup(t, Table) R kümesinden keyfi bir eleman döndürür.

Yalnızca create ve lookup işlemlerini destekleyen bir veri yapısına değişmez veri yapısı (immutable data structure) denir. S içindeki elemanların yeniden atanması set value ile yapılabilse de S üzerinde herhangi bir değişikliğe izin verilmediğine dikkat edin. Alt sınır sonuçlarımız, eğer S’nin değiştirilmesine izin verilirse (bit cinsinden ölçülen) doğrusal boyuta ulaşmanın sorgu süresinden bağımsız olarak imkânsız olduğunu göstermektedir. Başka bir deyişle Bloomier filtreleri, tamamen dinamik işlemleri kuramsal olarak dışlar.

Yapılarımızda üç parametre önemlidir: her işlemin çalışma süresi, alan gereksinimleri ve yanlış-pozitif oranı ε. create işlemi beklenen O(n log n) sürede (hatta modele bağlı olarak O(n) sürede) çalışır ve O(n(r + log(1/ε))) alan kullanır. set value ve lookup işlemleri O(1) sürede çalışır.

3.1 Genel Bakış

Önce değişmez veri yapısını açıklıyoruz; daha sonra aynı ilkeleri kullanarak değiştirilebilir bir sürümün nasıl kurulacağını gösteriyoruz.

Tablo, m adet q bitlik elemandan oluşur; burada m ve q uygulama parametreleridir. Table[i] ∈ {0,1}^q ifadesi Table içindeki i’inci q bitlik değeri gösterir.

t ile ilişkilendirilen v değerini bulmak için hash adlı bir karma fonksiyonu kullanarak k adet konum (h1, …, hk) hesaplarız; burada 1 ≤ hi ≤ m. Ayrıca yanlış pozitifleri azaltmak için kullanılan q bitlik bir maskeleme değeri M hesaplanır. Daha sonra şu değeri hesaplarız:

x = M ⊕ ⨁(i=1..k) Table[hi]

burada ⊕ bit düzeyinde özel-veya (exclusive-or) işlemini gösterir.

Ele alınması gereken iki temel konu vardır.

Birincisi, Table[i] değerlerini (i = 1, …, m için) öyle ayarlamamız gerekir ki çözümleme (decode) işlemleri tüm t ∈ S için doğru değerleri versin. Uygun parametre ayarları altında “rastgele” bir çözümün yüksek olasılıkla çalıştığını göstermemiz gerekir; ayrıca bu atamayı verimli biçimde hesaplamak isteriz ve bunu basit bir açgözlü algoritma ile yaparız.

İkincisi, t ∈ D \ S elemanlarının beklenen ε oranı dışındaki tümü için hesaplanan “görüntünün” Q içinde ⊥ değerine çözümlenmesini sağlamamız gerekir.

Tablo değerlerini aşağıdaki temel teknikle ayarlarız. m ve k için uygun bir seçim verildiğinde, yüksek olasılıkla S üzerinde bir sıralama Π ve aşağıda tanımlanan şekilde sıralamaya saygı gösteren bir eşleşme bulunduğunu gösteririz.

Tanım 3.2. S bir küme olsun ve her t ∈ S için bir komşuluk N(t) tanımlı olsun. Π, S'nin elemanları üzerinde tam bir sıralama olsun. Bir τ eşleşmesinin (S, Π, N)'ye saygı gösterdiğini şu durumlarda söyleriz:

1. Tüm t ∈ S için, τ(t) ∈ N(t).
2. Eğer ti >_Π tj ise, τ(ti) ∉ N(tj).

hash fonksiyonu (dolayısıyla N) bağlamdan anlaşılabiliyorsa, τ'nun S üzerinde Π'ye saygı gösterdiğini söyleriz.

Π ve τ verildiğinde, t = Π(1), …, Π(n) için, t ile ilişkilendirilmiş v değerini Table[τ(t)] ayarlayarak belirleyebiliriz. τ'nun sıralamaya saygı gösteren yapısı nedeniyle bu atama daha önce ayarlanmış hiçbir değeri etkileyemez.

İyi (Π, τ) çiftlerinin varlığını kayıpsız genişleyiciler (lossless expanders) kavramını kullanarak gösteririz. Analizimiz, (hash üzerinde) yüksek olasılıkla, açgözlü bir algoritma kullanarak (Π, τ) çiftini neredeyse doğrusal zamanda bulabileceğimizi ima eder.

Yanlış pozitiflerin sayısını sınırlamak için hash(t) tarafından üretilen rastgele maske M'yi kullanırız. M, Table içinde saklanan değerlerin hiçbirinden bağımsız ve düzgün biçimde dağıtılmış olduğundan, t ∉ S için arama yaptığımızda elde edilen sonuç {0,1}^q üzerinde düzgün ve bağımsız dağıtılır. Eğer R'nin boyutu {0,1}^q ile karşılaştırıldığında küçükse, yüksek olasılıkla bu değer R'nin geçerli bir değerini kodlamayacaktır ve t ∉ S olduğunu tespit ederiz.

Bir iki tablo yapısı (two-table construction) kullanarak değiştirilebilir bir yapı elde ederiz. İlk tabloyu, Table1, her t ∈ S için τ(t)'yi kodlamak amacıyla kullanırız. N(t) yalnızca hash(t)'ten hesaplanabilen k değere sahip olduğundan, τ(t) ∈ N(t) değeri {1, …, k} aralığında bir sayı ile kompakt biçimde temsil edilebilir.

Tanımlardan şu sonuç çıkar: t ≠ t′ olacak şekilde t, t′ ∈ S ise, τ(t) ≠ τ(t′). Dolayısıyla t ile ilişkili değeri basitçe Table2[τ(t)] konumunda saklayabiliriz; bu konumlar hiçbir zaman çakışmaz.

3.2 İyi Bir Sıralama ve Eşleşme Bulma

• S* ve hash verildiğinde, S üzerinde Π'ye saygı gösteren bir τ olacak şekilde (Π, τ) çiftini hesaplayan açgözlü bir algoritma sunarız.

Öncelikle τ'yu nasıl kompakt biçimde temsil edeceğimizi ele alırız. Hatırlayın ki hash(t), t'nin k komşusunu (h1, …, hk) olarak tanımlar. Dolayısıyla hash verildiğinde, τ(t) ∈ N(t) değeri {1, …, k} kümesinin bir elemanı olarak temsil edilebilir.

Böylece ι(t)'yi şu şekilde tanımlarız:

τ(t) = h_{ι(t)}

S = {t1, …, tn} için ayrıca ιi = ι(ti) kısaltmasını kullanırız; buradan:

τ = {ι1, …, ιn}

Algoritmamız kolay eşleşmelerin bolluğuna dayanır.

Tanım 3.3. m, k, hash sabit olsun ve t ∈ D için N(t) tanımlansın; ayrıca S ⊆ D olsun. h ∈ {1, …, m} konumunun S için bir singleton olduğunu şu durumda söyleriz: h ∈ N(t) yalnızca bir tane t ∈ S için geçerlidir.

tweak(t, S, hash) değerini, N(t) = (h1, …, hk) olacak şekilde S için singleton olan en küçük j değeri olarak tanımlarız; yani hj bir singleton ise. Böyle bir j yoksa tweak(t, S, hash) = ⊥ olur.

Eğer tweak(t, S, hash) tanımlıysa, bu ι(t) değerini belirler ve t kolay eşleşebilir hale gelir. Bu seçim, S içindeki farklı herhangi bir t′ için komşuluk yapısını bozmaz.

Bu tür “kolay eşleşmelere” sahip S alt kümesini E ile gösterelim ve H = S \ E olsun. (Π′, τ′) çiftini H üzerinde özyinelemeli olarak bulur ve (Π′, τ′) çiftini aşağıdaki şekilde (Π, τ)'ya genişletiriz.

Önce E elemanlarını, H elemanlarının sıralamasının sonuna yerleştiririz; böylece t ∈ E ve t′ ∈ H ise t >_Π t′ olur (E içindeki sıralama keyfi olabilir). Ardından τ(t) değerini H ve E için eşleşmelerin birleşimi olarak tanımlarız. Böylece τ'nun S üzerinde Π'ye saygı gösterdiği hemen görülür.

Algoritmayı Şekil 1'de veriyoruz. find match için önerdiğimiz algoritmanın başarılı olacağı hiç de açık değildir. m ve k yeterince büyük seçildiğinde ve hash rastgele seçildiğinde, find match fonksiyonunun yüksek olasılıkla başarılı olacağını gösteriyoruz.

3.3 Değiştirilebilir Bir Bloomier Filter Oluşturma

S üzerinde bir Π sıralaması ve hash tarafından tanımlanan komşuluklara göre S üzerinde Π'ye saygı gösteren bir τ eşleşmesi verildiğinde, herhangi bir t ∈ S ile ilişkili değerleri aşağıdaki şekilde saklarız.

t ∈ S verildiğinde, τ bize N(t) içinde bir L konumu verir; bu konum Π içinde t'den önce gelen hiçbir t′ elemanının komşuluğunda değildir. Ayrıca hash(t) verildiğinde L, {1, …, k} içinden bir ℓ elemanı olarak kompakt biçimde tanımlanabilir. Son olarak, S içindeki başka hiçbir t′ (önce ya da sonra) aynı L değerine sahip değildir.

Aşağıdaki şekilde değiştirilemez bir tablo kurabiliriz:

t = Π[1], …, Π[n] için:

• hash(t) kullanarak komşuluk N(t) = {h1, …, hk} ve maske M'yi hesapla.
• τ(t)'den N(t) içindeki L konumunu elde et.
• Table[L] değerini şu koşulu sağlayacak şekilde ayarla:

M ⊕ ⨁(i=1..k) Table[hi]

ifadesi t ile ilişkili v değerini kodlasın.

L'nin özellikleri nedeniyle Table[L] değerini değiştirmek daha önce saklanan hiçbir değeri etkileyemez.

t ile ilişkili değeri elde etmek için aynı ifadeyi hesaplar ve sonucun geçerli bir v ∈ R kodlayıp kodlamadığını kontrol ederiz. Eğer kodlamıyorsa t ∉ S olduğunu bildiririz. M rastgele olduğundan, t ∉ S durumunda değer rastgele olur; dolayısıyla yalnızca |R| / 2^q olasılıkla geçerli olur.

Yapıyı değiştirilebilir yapmak için, her t ∈ S'nin {1, …, k} içinde kısa bir gösterime sahip farklı bir eşleşme değeri L'ye sahip olduğu gerçeğini kullanırız. Yukarıdaki tekniği kullanarak her t için ℓ değerini saklayan değiştirilemez bir tablo oluştururuz. Daha sonra t ile ilişkili değeri ikinci bir tablonun L'inci konumunda saklarız.

Son algoritmalar Şekil 2 ve Şekil 3'te gösterilmiştir.

4 Algoritmanın Analizi

Analizimizin teknik açıdan en zor kısmı, rastgele bir hash ve yeterince büyük k ve m için find match yordamının yüksek olasılıkla τ'nun S üzerinde Π'ye saygı gösterdiği bir (Π, τ) çifti bulacağını göstermektir. Böyle bir çift elde edildiğinde geri kalan analiz oldukça basittir.

Lemma 4.1. create içinde find match başarılı olmuşsa, t ∈ S için lookup(t, Table) tarafından döndürülen değer, create veya set value tarafından t'ye atanmış en son v değeri olacaktır.

Kanıt. t için atama ilk kez tabloya yazıldığında, τ(t) {1, …, k} içinde ℓ temsiline sahip L ∈ N(t) konumunu üretir. Yapı gereği Table1[L], çözümleme formülünün ℓ döndürmesini sağlayacak şekilde ayarlanır.

Aynı ℓ değeri (dolayısıyla L) hem lookup hem de set value tarafından yeniden elde edilir. Bu yordamlar aynı formülü kullanır ve Table1'i değiştirmez. create tarafından daha sonra değiştirilen Table1 indeksleri yalnızca t′ >_Π t olacak şekilde τ(t′) biçimindedir. τ'nun özellikleri nedeniyle τ(t′) ∉ N(t) olur; dolayısıyla bu değişiklikler elde edilen ℓ değerini etkileyemez.

Son olarak tüm L değerleri birbirinden farklıdır. t1, t2 ∈ S ve t1 ≠ t2 olduğunu varsayalım. Genelliği bozmadan t1 >_Π t2 olsun. O halde τ(t1) ∉ N(t2) fakat τ(t2) ∈ N(t2) olduğundan τ(t1) ≠ τ(t2) olur. Dolayısıyla Table2[L] yalnızca create veya set value t için bir değer atadığında değiştirilir.

♦

Lemma 4.2. Table, destek kümesi S olan bir atama kullanılarak oluşturulmuş olsun. Eğer t ∉ S ise:

Pr[lookup(t, Table) = ⊥] ≥ 1 − k / 2^q

buradaki olasılık hash'in gerçekten rastgele bir hash fonksiyonu olduğu varsayımı altında create içindeki rastgelelik üzerindedir.

Kanıt. t ∉ S olduğundan veri yapısı hash(t)'ten bağımsız olarak üretilmiştir. Özellikle M, {0,1}^q üzerinde düzgün dağıtılmıştır. Dolayısıyla

x = M ⊕ ⨁(i=1..k) Table[hi]

ifadesi {0,1}^q üzerinde düzgün dağılır. Bu değerlerden yalnızca k tanesi {1, …, k} içindeki geçerli indeks ℓ değerlerini kodlar. ♦

Analizde Kullanılan Grafik Özelliği

G, aşağıdaki şekilde tanımlanan n × m iki parçalı bir graf olsun:

• Sol taraf: S elemanlarına karşılık gelen L1, …, Ln düğümleri.
• Sağ taraf: {1, …, m} değerlerine karşılık gelen R1, …, Rm düğümleri.

Her ti ∈ S için hash, {1, …, m} içinde h1, …, hk değerlerini tanımlar ve Li ile Rhj arasında kenarlar eklenir.

Tanım 4.1 (Singleton Özelliği).

G grafının singleton özelliğine sahip olduğunu şu durumda söyleriz: boş olmayan her A ⊆ L için, A içindeki tam olarak bir düğüme komşu olan bir Ri ∈ R düğümü vardır.

G singleton özelliğine sahipse, find match hiçbir zaman tıkanmaz; çünkü her özyinelemeli çağrı boş olmayan bir kolay küme bulacaktır.

Bunu iyi bilinen bir genişleme özelliğine indirgeriz.

Tanım 4.2 (Kayıpsız Genişleme Özelliği).

N(v), v ∈ L düğümünün komşular kümesi olsun ve A ⊆ L için N(A) bu komşuların birleşimi olsun. G grafının kayıpsız genişleme özelliğine sahip olduğunu şu durumda söyleriz: boş olmayan tüm A ⊆ L için

|N(A)| > k|A| / 2

4.1 find match Analizi

find match'in sonlanacağını göstermek için, herhangi bir A ⊆ S alt kümesi için algoritmanın boş olmayan bir EA kolay kümesi bulduğunu göstermeliyiz. Bu durum her özyinelemeli adımda ilerleme sağlar.

Kanıt. Aksini varsayalım: N(A) içindeki her düğümün derecesi en az 2 olsun. O halde graf en az 2|N(A)| kenar içerir. Ancak kayıpsız genişleme özelliğine göre |N(A)| > k|A|/2 olduğundan kenar sayısı k|A|'dan fazladır. Bu, |A| düğümünün her birinin tam olarak k kenara sahip olmasıyla çelişir.

Dolayısıyla bir singleton komşu bulunmak zorundadır.

Yanlış pozitif oranı ε elde etmek için

q = ⌈ log₂(k / ε) ⌉

değerini seçeriz.

Pratikte hash sezgisel olarak üretilir ve yalnızca sözde rastgeledir. Eğer hash kriptografik olarak güçlü bir sözde rastgele fonksiyon ise, veri yapısının davranışı hesaplama açısından gerçekten rastgele bir hash kullanımından ayırt edilemez; ancak bu tür fonksiyonlar pratik kullanım için fazla maliyetli olabilir.

Şekil 1: hash ve S verildiğinde, find match S üzerinde bir Π sıralaması ve Π'ye saygı gösteren bir τ eşleşmesi bulur.

Şekil 2: Bir atama A ve parametreler (m, k, q) verildiğinde, create A'ya karşılık gelen değiştirilebilir bir veri yapısı kurar.

Şekil 3:

• lookup(t, Table = (Table1, Table2)) t ile ilişkili değeri elde eder.
• set value(t, v, Table = (Table1, Table2)) t ∈ S ile ilişkili değeri v olarak ayarlar.

set value için t, ilk create çağrısı tarafından belirlenen S kümesinin bir elemanı olmalıdır.

Şimdi hash'i rastgele seçmek, G grafını şu dağılıma göre seçmeye karşılık gelir: Her v ∈ L, komşu olmak üzere R içinden (tekrar seçime izin verilerek) rastgele r1, ..., rk olmak üzere k düğüm seçer. Bu tür rastgele graflar iyi incelenmiştir; Lemma 4.4 standart bir sayma argümanından elde edilir.

Lemma 4.4. G yukarıdaki şekilde seçilsin; k sabit ve m = ckn olsun. Herhangi bir c > 2 sabiti için ve k, n yeterince büyük olduğunda, G yüksek olasılıkla kayıpsız genişleme özelliğine sahiptir.

Alt Sınırlar

R = {⊥, 1, 2} durumunu ele alırız. S kümesi sırasıyla 1 ve 2'ye eşlenen A ve B alt kümelerine ayrılır. Tüm A, B çiftleri için tek bir hash fonksiyonları kümesinin yeterli olup olmayacağı doğal bir sorudur. Başka bir deyişle, yalnızca O(n) bit depolama ile deterministik Bloomier filtreleme mümkün müdür?

Bu soruya olumsuz bir yanıt veriyoruz. Alt sınırımız, tekdüze olmayan algoritmalar için de geçerlidir; yani Bloomier filtre tablolarının dışında keyfi büyüklükte depolama kullanılabilir, yeter ki kodlama yalnızca n ve N'e bağlı olsun.

Teorem 5.1. Deterministik Bloomier filtreleme Ω(n + log log N) bit depolama gerektirir.

Kanıt. G grafını şu şekilde ele alalım:

C(N, 2n) · C(2n, n)

düğüm içersin ve her düğüm, tam olarak n koordinatı 1 ve diğer n koordinatı −1 olan {−1, 0, 1}^N vektörlerinden birine karşılık gelsin.

G içindeki iki düğüm, en az bir koordinat konumu 1 ≤ i ≤ N için karşılık gelen vektörleri (x1, ..., xN) ve (y1, ..., yN) şu koşulu sağlıyorsa komşudur:

x_i y_i = −1.

Sezgisel olarak her düğüm A (1 olan koordinatlar) ve B (−1 olan koordinatlar) seçimlerine karşılık gelir. Bir düğümün A kümesi diğer düğümün B kümesiyle kesişiyorsa bu iki düğüm arasında kenar bulunur.

Tablo T, A ve B hakkında tek bilgi kaynağı olduğundan, komşu iki düğüm aynı tablo atamasına karşılık gelmemelidir; dolayısıyla dizinin boyutu m en az log χ(G) olmalıdır. Burada χ(G), G grafının kromatik sayısıdır.

Teorem 5.1 aşağıdaki lemmadan doğrudan elde edilir.

Lemma 5.1. G grafının kromatik sayısı Ω(2^n log N) ile O(4^n ln N) arasındadır.

Kanıt. G için minimum renklendirmeyi ele alalım. Herhangi bir w ∈ {−1, 1}^n vektörü ve

1 ≤ i1 < ... < in ≤ N

şeklindeki n indeks dizisi için, şu koşulu sağlayan bir renk c vardır:

w = (z^c_{i1}, ..., z^c_{in}).

Bunun nedenini görmek için, w vektörünün koordinatlarıyla i1, ..., in konumlarında eşleşen bir A, B seçimini düşünelim. Tüm −1 değerlerini 0'a dönüştürdüğümüzde elde edilen vektör kümesi z^c, (N, n)-evrenseldir (yani vektörlerin herhangi bir n koordinat konumuna kısıtlanması tüm olası 2^n desenlerini üretir).

Kleitman ve Spencer [16]'ya göre bu tür vektörlerin sayısı Ω(2^n log N) olarak bilinir. Üst sınır için, yine [16]'da gösterilen O(n 2^n log N) büyüklüğünde bir (N, 2n)-evrensel vektör kümesinin varlığını kullanır ve tüm sıfırları −1'e çeviririz. (Alternatif olarak Razborov'un ayırıcı kümelerin boyutu üzerine verdiği sınır da kullanılabilir [25].)

Her düğüm, evrensel kümeden o düğümle ilişkili vektörün 1 ve −1 değerleriyle eşleşen bir vektör seçilerek renklendirilir.

♦

Rastgeleleştirilmiş Bloomier filtreleme modeline geri dönersek, S kümesini değiştirmeye çalıştığımızda ne olacağını ele alırız. Yine olumsuz bir sonuç elde ederiz; ancak bu kez evren boyutunun n'den yalnızca polinomsal olarak daha büyük olması şemanın bozulması için yeterlidir. Sezgisel olarak bu durum, f fonksiyonunun doğrusal bit büyüklüğünde bir kodlamasında S kümesinde değişikliklere izin verecek kadar bilginin korunmadığını gösterir.

Teorem 5.2. Eğer N = 2^{n^{O(1)}} ve depolama bit sayısı m

n ≤ m ≤ n / (c log log(N / c n^3))

koşulunu sağlıyorsa (yeterince büyük bir c sabiti için), Bloomier filtreleme S kümesi üzerinde dinamik güncellemeleri destekleyemez.

Kanıt. Yine S kümesini 1'e eşlenen bir A kümesi ve 2'ye eşlenen bir B kümesinin ayrık birleşimi olarak ele alırız. Başlangıçtaki B kümesini sabit tutalım ve çeşitli A seçimlerine karşılık gelen tablo T atamalarını inceleyelim.

T'nin her atamasıyla, D içinde belirli bir n-elemanlı A kümeleri ailesi ilişkilidir. Bu ailelerin en büyüğünü F ile gösterelim; açıkça

|F| ≥ C(N, n) · 2^{−m}.

k > 0 tam sayısı verildiğinde, L_k, F içindeki en az k kümeye ait olan U elemanlarının kümesi olsun. L_k'nin çok küçük olamayacağını görmek kolaydır.

Gerçekten, F_k, F içinde L_k'nin alt kümeleri olan kümelerden oluşan alt aile olsun. Açıkça

|F \ F_k| ≤ (k − 1)N.

Teoremin varsayımları N > c n^3 olduğunu ima eder; dolayısıyla

k = ⌊|F| / (2N)⌋

seçimi k > c olmasını sağlar ve

2|F| ≥ C(N, n) · 2^{−m−1}.

Çünkü

C(|L_k|, n) ≥ |F_k|,

şu sonuç elde edilir:

|L_k| ≥ 2^{−m+1} · (n / N).
(5.1)

D içinden rastgele seçilen bir elemanın F içindeki kaç kümeyle kesiştiğinin beklenen değeri

(n / N) |F|

değeridir.

n-elemanlı bir B ⊆ D verildiğinde, F_B, B ile kesişen F alt ailesi olsun. Rastgele bir B için

E[ |{S : S ∈ F_B}| ] ≤ (n^3 / N) |F|.

Tanımlayalım:

F_B^c = F \ F_B
ve
L_B^k = { S ∩ L_k | S ∈ F_B^c }.

Her x ∈ L_k en az k tane F kümesiyle kesiştiğinden, B'nin yeni seçimi ortaya çıktığında tablo güncellenir. A hakkında mevcut tek bilgi önceki tablo atamasında kodlanmıştır. Dolayısıyla algoritma F_B^c içindeki herhangi iki A kümesini birbirinden ayırt edemez.

Özetlemek gerekirse, rastgele bir B verildiğinde algoritma, L_B^k içindeki herhangi bir arama anahtarı için “A içinde” yanıtını vermelidir; ayrıca

Prob(|L_B^k| ≥ |L_k| − 6n^3) ≥ 1/2.
(5.2)

Daha sonra, n elemanlı B kümeleri ailesini, her birinin karşılık geldiği T atamasına göre bölümlere ayırırız. Bu işlem bize en fazla 2^m adet {G_i} alt ailesi verir ve

Σ_i |G_i| = C(N, n).

Eğer

M_i = ⋃{ S ∩ L_k | S ∈ G_i }

ise, G_i içindeki herhangi bir yeni B seçimi verildiğinde algoritma M_i içindeki herhangi bir arama anahtarı için “B içinde” yanıtını vermek zorundadır. Önceki gözlemimize göre, bu nedenle M_i kümesinin L_B^k ile ayrık olması zorunludur.

m çok küçük olduğunda, B rastgele seçildiğinde her iki kümenin de yüksek olasılıkla kesiştiğini gösteriyoruz.

Bir parametre sabitleyelim

λ = ⌊|L_k| · 2^{−c m / n}⌋.

B ∈ G_j olacak şekilde j indeksini i(B) ile gösterelim ve

τ = ⌈|L_k| n / (2N)⌉.

Rastgele bir B verildiğinde, Chernoff sınırına göre |B ∩ L_k| < τ olma olasılığı o(1)’dir. Öte yandan, |B ∩ L_k| ≥ τ olduğu koşulu altında |M_{i(B)}| ≤ λ olmasının koşullu olasılığı en fazla

( C(|L_k|, s) / C(|L_k|, τ) ) · |L_k|^τ = o(1).

Dolayısıyla |M_{i(B)}| > λ olasılığı 1 − o(1)’dir. λ > 6n^3 olduğundan, en az 1/2 − o(1) olasılıkla M_{i(B)} kümesi L_B^k ile kesişir ve algoritma başarısız olur.

♦

Teşekkür

Hesaplamalarımızdan birindeki hatayı işaret ettiği için David Talbot’a teşekkür ederiz.

Kaynaklar

1. Bloom, B. İzin verilebilir hatalarla hash kodlamasında alan/zaman ödünleşimleri, CACM 13 (1970), 422–426.
2. Broder, A., Mitzenmacher, M. Bloom filtrelerinin ağ uygulamaları: bir inceleme, Allerton 2002.
3. Brodnik, A., Munro, J. I. Sabit zamanda ve neredeyse en az alan kullanımıyla üyelik testi, SIAM J. Comput. 28 (1999), 1628–1640.
4. Buhrman, H., Miltersen, P. B., Radhakrishnan, J., Venkatesh, S. Bit vektörleri en iyi çözüm müdür? Proc. 32nd STOC (2000), 449–458.
5. Byers, J., Considine, J., Mitzenmacher, M. Uyarlanabilir üst katman ağları üzerinde bilgilendirilmiş içerik dağıtımı, Proc. ACM SIGCOMM 2002, Vol. 32:4, Computer Communication Review (2002), 47–60.
6. Capalbo, M., Reingold, O., Vadhan, S., Wigderson, A. Rastgelelik iletkenleri ve derece/2 engelinin ötesinde sabit dereceli genişleme, Proc. 34th STOC (2002), 659–668.
7. Cohen, S., Matias, Y. Spektral Bloom filtreleri, SIGMOD 2003.
8. Cuena-Acuna, F. M., Peery, C., Martin, R. P., Nguyen, T. D. PlanetP: İçerik adreslenebilir eşler arası bilgi paylaşım toplulukları oluşturmak için dedikodu tabanlı iletişim kullanımı, Rutgers Technical Report DCS-TR-487, 2002.
9. Estan, C., Varghese, G. Trafik ölçümü ve muhasebesinde yeni yönelimler, Proc. ACM SIGCOMM 2002, Vol. 32:4 (2002), 323–336.
10. Fan, L., Cao, P., Almeida, J., Broder, A. Summary cache: ölçeklenebilir geniş alan web önbellek paylaşım protokolü, IEEE/ACM Transactions on Networking 8 (2000), 281–293.
11. Fang, M., Shivakumar, N., Garcia-Molina, H., Motwani, R., Ullman, J. Iceberg sorgularını verimli biçimde hesaplama, Proc. 24th Int. Conf. on VLDB (1998), 299–310.
12. Feng, W.-C., Shin, K. G., Kandlur, D., Saha, D. Stochastic fair blue: adaleti sağlamak için bir kuyruk yönetimi algoritması, INFOCOM '01 (2001), 1520–1529.
13. Fredman, M. L., Komlós, J., Szemerédi, E. O(1) en kötü durum erişim süresiyle seyrek bir tabloyu saklama, J. ACM 31 (1984), 538–544.
14. Gremillion, L. L. Farklılaştırılmış dosya erişimi için Bloom filtresi tasarımı, Comm. ACM 25 (1982), 600–604.
15. Hsiao, P. Coğrafi yönlendirme için coğrafi bölge özet hizmeti, Mobile Computing and Communications Review 5 (2001), 25–39.
16. Kleitman, D. J., Spencer, J. k-bağımsız küme aileleri, Discrete Math 6 (1973), 255–262.
17. Ledlie, J., Taylor, J., Serban, L., Seltzer, M. Eşler arası sistemlerde kendi kendine örgütlenme, Proc. 10th European SIGOPS Workshop, September 2002.
18. Li, Z., Ross, K. A. PERF join: iki yönlü semijoin ve bloomjoin’e bir alternatif, CIKM '95, Proc. 1995 International Conference on Information and Knowledge Management, 137–144.
19. Luby, M. LT kodları, Proc. 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002.
20. Mackert, L., Lohman, G. Dağıtık sorgular için R iyileştiricisinin doğrulanması ve performansı*, Proc. Int’l Conf. on VLDB (1986), 149–159.
21. Manber, U., Wu, S. Parola güvenliğine uygulaması olan yaklaşık üyelik denetimi için bir algoritma, Information Processing Letters 50 (1994), 191–197.
22. McIlroy, M. D. Bir yazım listesi geliştirilmesi, IEEE Trans. on Communications, COM-30 (1982), 91–99.
23. Mitzenmacher, M. Sıkıştırılmış Bloom filtreleri, IEEE Transactions on Networking 10 (2002).
24. Mullin, J. K. Dağıtık veritabanı sistemleri için en iyi semijoin yöntemleri, IEEE Transactions on Software Engineering 16 (1990).
25. Razborov, A. A. Hesaplama karmaşıklığında alt sınırlar kuramına matris yöntemlerinin uygulamaları, Combinatorica 10 (1990), 81–93.
26. Rhea, S. C., Kubiatowicz, J. Olasılıksal konum belirleme ve yönlendirme, Proceedings of INFOCOM 2002.
27. Rousskov, A., Wessels, D. Önbellek özetleri (Cache digests), Computer Networks and ISDN Systems 30(22–23), 2155–2168, 1998.
28. Sipser, M., Spielman, D. A. Genişleyici kodlar, IEEE Trans. Inform. Theory 42 (1996), 1710–1722.
29. Snoeren, A. C., Partridge, C., Sanchez, L. A., Jones, C. E., Tchakountio, F., Kent, S. T., Strayer, W. T. Hash tabanlı IP izleme (traceback), Proc. ACM SIGCOMM 2001, Vol. 31:4, Computer Communication Review, 3–14, August 2001.
30. Whitaker, A., Wetherall, D. Icarus içinde döngüsüz iletme, Proc. 5th OPENARCH (2002), 63–75.