Basit ve Alan Açısından Verimli Minimal Mükemmel Hash Fonksiyonları

Fabiano C. Botelho¹, Rasmus Pagh² ve Nivio Ziviani¹

¹ Bilgisayar Bilimleri Bölümü, Federal Univ. of Minas Gerais, Belo Horizonte, Brezilya
{fbotelho,nivio}@dcc.ufmg.br
² Computational Logic and Algorithms Group, IT Univ. of Copenhagen, Danimarka
pagh@itu.dk

Özet

Bir anahtar kümesi S için mükemmel bir hash fonksiyonu (PHF) h : U → [0, m − 1], S kümesindeki anahtarları benzersiz değerlere eşleyen bir fonksiyondur. Verilen bir S kümesi için bir PHF’yi temsil etmek üzere gereken en düşük alan miktarının yaklaşık olarak 1.44n²/m bit olduğu bilinmektedir; burada n = |S|. Bu makalede, verilen bir küme için (m = n ve m = 1.23n durumları için) PHF’lerin oluşturulması ve değerlendirilmesi için yeni algoritmalar sunuyoruz. Bu algoritmaların özellikleri şunlardır:

1. Bir PHF’nin değerlendirilmesi sabit zaman gerektirir.
2. Algoritmalar açıklanması ve uygulanması açısından basittir ve doğrusal zamanda çalışır.
3. PHF’leri temsil etmek için gereken alan miktarı, bilgi kuramsal minimumun yaklaşık 2 katı civarındadır.

Daha önce bilinen hiçbir algoritma bu özelliklerin tümüne sahip değildir. Bildiğimiz kadarıyla literatürde üçüncü özelliğe sahip herhangi bir algoritma ya:

• Oluşturma ve değerlendirme için üstel zaman gerektirir, ya da
• Yalnızca çok büyük n değerleri için, asimptotik olarak, neredeyse en iyi alan kullanımını sağlar.

Dolayısıyla, temel katkımız gerçekçi n değerleri için düşük alan kullanımı sağlayan bir yöntem sunmaktır. Başlıca teknik bileşen, PHF’leri rastgele hipergraphlar üzerine kurmanın yeni bir yoludur. Daha önce bu yaklaşım, doğrusal üstü alan kullanımı olan basit PHF’ler tasarlamak için kullanılmıştır.

⋆ Bu çalışma kısmen GERINDO Project—hibe MCT/CNPq/CT-INFO 552.087/02-5 ve CNPq hibeleri 30.5237/02-0 (Nivio Ziviani) ve 142786/2006-3 (Fabiano C. Botelho) tarafından desteklenmiştir.

Makalenin bu sürümü, WADS 2007 bildirilerinde yayımlanan sürümle aynıdır. Ne yazık ki, SODA 2004 bildirilerinde yayımlanan Chazelle ve arkadaşlarının The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables başlıklı makalesine referans ve atıf vermemektedir. Bu çalışmada, bizimkine eşdeğer bir PHF oluşturma yöntemi sunulmaktadır. Bu yöntem, Bölüm 3.3’ün sonunda “Bloomier Filter” veri yapısının bir değişikliği olarak açıklanmaktadır; ancak burada bir PHF’nin oluşturulduğu açıkça belirtilmemektedir. Bu nedenle açıklanan basit PHF oluşturma yönteminin Chazelle ve arkadaşlarına atfedilmesi gerekir. Bu makalenin yeni katkısı, uygulama yönlerini de dikkate alarak alan kullanımının sabit katsayısını analiz etmek ve iyileştirmek ile bu PHF’lerden MPHF oluşturmanın bir yolunu sunmaktır.

1 Giriş

Mükemmel hashing, statik bir S kümesinin elemanlarına benzersiz tanımlayıcılar atamanın alan açısından verimli bir yoludur. S kümesinin elemanlarını anahtarlar olarak adlandıracağız. Bir mükemmel hash fonksiyonu (PHF), S ⊆ U kümesini [0, m − 1] aralığındaki benzersiz değerlere eşler. n = |S| ve u = |U| olarak tanımlarız — burada m ≥ n olması gerektiğine dikkat edilmelidir. Minimal mükemmel hash fonksiyonu (MPHF), m = n olan bir PHF’dir. Açıklamayı basitleştirmek amacıyla bu makalede log u ≪ n durumunu ele alıyoruz. Bu varsayım, alan kullanımında u’ya bağlı terimleri göz ardı etmemize olanak tanır.

Bu makalede PHF ve MPHF üretmek için basit, verimli, alana yakın optimal ve pratik bir F algoritma ailesi sunuyoruz. F ailesindeki algoritmalar, S kümesindeki anahtarlar üzerinde r hash fonksiyonunun fonksiyon değerleriyle tanımlanan r-uniform rastgele hipergraphlar kullanır. r-uniform hipergraph, her kenarın r ≥ 2 düğümü bağladığı standart yönsüz grafın bir genellemesidir.

Mükemmel hashing’i rastgele hipergraphlar üzerine kurma fikri yeni değildir, örneğin [14]’e bakınız; ancak biz O(n log n) bit yerine O(n) bit alan kullanımı elde etmek için farklı bir yol izleyeceğiz. (Hipergraphlara dayanan önceki yapımlarda olduğu gibi, kullanılan hash fonksiyonlarının düzgün rastgele dağıldığını ve fonksiyon değerlerinin bağımsız olduğunu varsayıyoruz. Ancak yöntemimizin küçük alan kullanan açıkça tanımlı hash fonksiyonlarıyla da gerçekleştirilebileceğini savunuyoruz.) Ele alınan tüm yöntemlerde değerlendirme süresi sabittir.

r = 2 için bir MPHF’de (3 + ε)n bit alan kullanımı elde ederiz; burada ε > 0 herhangi bir sabittir. r = 3 için bir MPHF’de 2.7n bitten daha az alan kullanımı elde ederiz. Bu değer, yaklaşık 1.4427n bit olan bilgi kuramsal alt sınırın 2 katı içindedir. Daha büyük m değerleri için daha sıkı ve hatta daha basit temsiller elde edilebilir. Örneğin m = 1.23n için 1.95n bit alan kullanımı elde edebiliriz. Bu değer yaklaşık 0.89n bit olan bilgi kuramsal alt sınırın iki katından biraz fazladır.

r = 3 için verilen sınırlar, rastgele bir 3-parçalı hipergraph içinde bir 2-core’un ortaya çıkmasına ilişkin bir varsayıma dayanır; r = 2 için verilen sınırlar ise tamamen kanıtlanmıştır. r > 3 seçilmesi bu sonuçlarda herhangi bir iyileşme sağlamaz.

Yöntemimizin, hem basitliği hem de alan karmaşıklığının sabit katsayısının makul problem boyutları için en yakın rakibinden 6 katından fazla düşük olması nedeniyle, kanıtlanmış alan karmaşıklığına sahip önceki yöntemlerden çok daha pratik olduğunu savunacağız. Bu pratikliği, sezgisel hash fonksiyonları kullanarak ve belirtilen kuramsal sınırların biraz üzerinde alan kullanarak deneysel olarak doğruluyoruz.

Bu bölümde mükemmel hashing üzerine en önemli kuramsal ve pratik sonuçlardan bazılarını gözden geçiriyoruz. Czech, Havas ve Majewski [4] daha kapsamlı bir inceleme sunmaktadır.

2 İlgili Çalışmalar

2.1 Kuramsal Sonuçlar

Fredman ve Komlós [9], u ≥ n^α olacak şekilde α > 2 için (n büyüklüğündeki tüm kümeler üzerinde en kötü durumda) bir MPHF’yi temsil etmek için en az n log e + log log u − O(log n) bit gerektiğini kanıtlamıştır. Logaritmalar taban 2’dir. log u ≪ n varsayımı altında son iki terimin ihmal edilebilir olduğuna dikkat edilmelidir.

Genel olarak m > n için bir PHF’yi temsil etmek üzere gereken alan yaklaşık olarak

(1 + (m/n − 1) ln(1 − n/m)) n log e bit

düzeyindedir.

Bunun daha basit bir kanıtı daha sonra Radhakrishnan [18] tarafından verilmiştir.

Mehlhorn [15], en fazla

n log e + log log u + O(log n) bit

ile temsil edilebilen bir MPHF oluşturan bir algoritma sunarak Fredman–Komlós sınırının neredeyse sıkı olduğunu göstermiştir.

Ancak algoritmasının oluşturma ve değerlendirme süresi n’e göre üstel olduğundan pratikten çok uzaktır.

Schmidt ve Siegel [19], sabit değerlendirme süresine ve O(n + log log u) bit tanım boyutuna sahip bir MPHF oluşturmak için ilk algoritmayı önermiştir. Onların algoritması ve ele alacağımız diğer tüm algoritmalar, hesaplama için Word RAM modelini [10] varsayar. Bu modelde evren U’nun bir elemanı bir makine sözcüğüne sığar ve aritmetik işlemler ile bellek erişimlerinin maliyeti birimdir.

Pratik açıdan Schmidt ve Siegel algoritması çekici değildir. Yöntem uygulanması açısından karmaşıktır ve alan sınırının sabit katsayısı büyüktür: n anahtarlı bir küme için en az 29n bit kullanılır; bu da pratikte O(n log n) bit kullanan en iyi yöntemlere benzer bir alan kullanımı anlamına gelir. [19]’un algoritmik fikirlerini mümkün olduğunca açık biçimde anlatmayı hedeflediği ve sabit katsayıyı iyileştirmeye çalışmadığı görülse de, alan kullanımını önemli ölçüde iyileştirmek zor görünmektedir.

Daha yakın zamanda Hagerup ve Tholey [11], bildiğimiz en iyi kuramsal sonucu sunmuştur. Elde edilen MPHF O(1) zamanda değerlendirilebilir ve

n log e + log log u + O(n (log log n)² / log n + log log log u)

bitte saklanabilir. Oluşturma süresi O(n + log log u) olup O(n) sözcük alan kullanır. Yine u içeren terimler ihmal edilebilir düzeydedir.

Kuramsal önemine rağmen Hagerup ve Tholey [11] algoritması da pratik değildir; çünkü yalnızca asimptotik alan karmaşıklığını vurgular. Ayrıca uygulanması da oldukça karmaşıktır. n < 2^150 için yöntem iyi tanımlı değildir; çünkü anahtar kümesini boyutu

n̂ ≤ log n / (21 log log n)

olan kovalarına bölmeye dayanır.

Bunu kova boyutunu en az 1 olacak şekilde düzelttiğimizi varsayarsak, n < 2^300 için boyutu 1 olan kovalar kullanılacaktır; bu da alan kullanımının en az

(3 log log n + log 7) n bit

olacağı anlamına gelir.

Bir milyar anahtarlı bir küme için bu, eleman başına 17 bitten fazladır. Dolayısıyla Hagerup–Tholey MPHF pratik durumlarda alan açısından verimli değildir. Algoritmalarının açıklama kolaylığı için optimize edildiğine ve sabit katsayıların optimize edilmediğine inansak da, yaklaşımlarına dayanarak alan kullanımını önemli ölçüde azaltmak zor görünmektedir.

Şimdi çalışmamızın dayandığı başlıca “pratik” sonuçlardan bazılarını açıklıyoruz. Bu çalışmalar basitlikleri ve (kanıtlanabilir biçimde) düşük sabit katsayıları ile karakterize edilir.

2.2 Pratik Sonuçlar

İlk iki sonuç, düzgün rastgele hash fonksiyonlarının ücretsiz olarak mevcut olduğunu varsayar. Czech ve arkadaşları [14], r-uniform hipergraphlara (yani kenar boyutu r olan) dayanan MPHF oluşturma algoritmalarından oluşan bir aile önermiştir. Ortaya çıkan fonksiyonlar O(1) zamanda değerlendirilebilir ve O(n log n) bit içinde saklanabilir.

Botelho, Kohayakawa ve Ziviani [3], r = 2 durumunu ele alarak bu ailedeki bir örneğin alan gereksinimini iyileştirmiştir; ancak alan gereksinimi hâlâ O(n log n) bittir. Her iki durumda da MPHF beklenen O(n) zamanda üretilebilir. [3]’te yapılan deneyler, oluşturma prosedürünün pratikte iyi çalıştığını göstermiştir.

Pagh [16], aşağıdaki biçimde MPHF oluşturmak için bir algoritma önermiştir

h(x) = (f(x) + d[g(x)]) mod n,

burada f ve g evrensel hash fonksiyonları ailesinden rastgele seçilir ve d, f fonksiyonunun neden olduğu çakışmaları çözmek için kullanılan “yer değiştirme değerleri”nden oluşan bir vektördür. Yöntem basittir ve fonksiyonların değerlendirilmesi çok hızlıdır; ancak alan kullanımı (2 + ε)n log n bittir ve bu optimal değildir.

Dietzfelbinger ve Hagerup [5], [16]’yı geliştirerek alan kullanımını (1 + ε)n log n bite düşürmüştür; yine basit hash fonksiyonları kullanılmıştır. Woelfel [20], alan kullanımını asimptotik olarak O(n log log n) bite kadar düşürmenin yolunu göstermiştir ve algoritma hâlâ oldukça basittir. Ancak bu yöntemin pratikliğine dair deneysel kanıt yoktur.

Fox ve arkadaşları [7, 8], deneylerde anahtar başına saklama maliyeti 2 ile 8 bit arasında olan MPHF oluşturma algoritmaları sunmuştur. Ancak [4, Bölüm 6.7]’de bu algoritmaların beklenen çalışma sürelerinin üstel olduğu gösterilmiştir. Ayrıca fonksiyonu saklamak için gereken anahtar başına bit sayısının n arttıkça sabit kalacağına dair bir garanti yoktur.

Lefebvre ve Hoppe [13] tarafından yapılan çalışma da aynı probleme sahiptir. Seyrek uzamsal verileri temsil etmek amacıyla özel olarak bir PHF yöntemi tasarlamışlardır ve elde edilen fonksiyonlar saklanmak için anahtar başına 3 bitten fazlasını gerektirir.

3 Minimal Mükemmel Hashing Yöntemlerinden Oluşan Bir Aile

Bu bölümde, alana yakın optimal MPHF’ler oluşturmak için geliştirdiğimiz F algoritma ailesini sunuyoruz. Temel fikir aşağıdaki gibidir.

Eşleme Adımı (Mapping Step) olarak adlandırılan ilk adım, anahtar kümesi S’yi n = |S| kenardan oluşan ve çevrimsiz bir r-parçalı hipergraph Gᵣ = (V, E) oluşturan bir yapıya eşler; burada |E(Gᵣ)| = n, |V(Gᵣ)| = m ve r ≥ 2’dir. S kümesindeki her anahtarın E(Gᵣ)’de bir kenarla ilişkilendirildiğine dikkat edilmelidir.

Eşleme Adımı sırasında ayrıca Gᵣ’nin kenarlarını L adlı bir liste içinde sıralarız; öyle ki her eᵢ kenarı, L’de kendisinden sonra gelen hiçbir kenara komşu olmayan bir düğüm içerir.

Atama Adımı (Assigning Step) olarak adlandırılan bir sonraki adım, her kenarı kendi r düğümünden biriyle benzersiz biçimde ilişkilendirir. Burada “benzersiz” ifadesi, iki kenarın aynı düğüme atanamayacağı anlamına gelir. Böylece Atama Adımı, değer aralığı V(Gᵣ) olan bir PHF bulur.

Daha küçük bir değer aralığına sahip bir PHF istiyorsak (n < |V(Gᵣ)|), daha sonra V(Gᵣ)’nin atanmış düğümlerini [0, n − 1] aralığına eşleriz. Bu eşleme, Sıralama Adımı (Ranking Step) tarafından üretilir ve herhangi bir atanmış düğümün sırasını sabit zamanda hesaplamaya olanak veren bir veri yapısı oluşturur.

Analiz için elimizde aşağıdaki r hash fonksiyonlarının bulunduğunu varsayıyoruz

hᵢ : U → [ i·m/r , (i + 1)·m/r − 1 ], 0 ≤ i < r,

ve bu fonksiyonların değerlerinin bağımsız ve düzgün dağılımlı olduğunu kabul ediyoruz. Bu r fonksiyon ve S kümesi doğal bir şekilde rastgele bir r-parçalı hipergraph tanımlar.

Şu şekilde tanımlarız

Gᵣ = Gᵣ(h₀, h₁, … , hᵣ₋₁)

bu hipergraphın düğüm kümesi

V(Gᵣ) = [0, m − 1]

ve kenar kümesi

E(Gᵣ) = { {h₀(x), h₁(x), … , hᵣ₋₁(x)} | x ∈ S }.

Eşleme Adımı’nın çalışabilmesi için Gᵣ’nin basit ve çevrimsiz olması gerekir; yani Gᵣ çoklu kenarlar ve çevrimler içermemelidir. Eşleme Adımı başarısız olursa r yeni hash fonksiyonu seçilerek bu durum ele alınır.

Atama Adımı tarafından üretilen PHF p : S → V(Gᵣ) aşağıdaki biçimdedir

p(x) = hᵢ(x), burada

i = ( g(h₀(x)) + g(h₁(x)) + ... + g(hᵣ₋₁(x)) ) mod r.
(1)

Fonksiyon g : V(Gᵣ) → {0, 1, … , r}, V(Gᵣ)’nin düğümlerinin bir etiketlemesidir. Gᵣ çevrimsiz olduğunda p’nin S üzerinde bire bir olmasını sağlayacak etiketlemenin nasıl seçileceğini göstereceğiz. Ayrıca g(y) ≠ r olması ancak ve ancak y atanmış bir düğüm ise, yani tam olarak y ∈ p(S) olduğunda geçerlidir.

Bu, S için bir MPHF’yi şu şekilde elde ettiğimiz anlamına gelir:

rank(u) = | { v ∈ V(Gᵣ) | v < u ∧ g(v) ≠ r } |.
(3)

Sıralama Adımı, rank fonksiyonunu sabit zamanda hesaplamayı sağlayan bir veri yapısı üretir.

Şekil 1, minimal mükemmel hashing algoritmalarımızın ailesi için sözde kodu göstermektedir. Üçüncü adımı çıkarırsak bunun yerine m = |V(Gᵣ)| olan PHF’ler oluşturmuş oluruz. Şimdi her adımı ayrıntılı olarak açıklıyoruz.

2.3 Sezgisel Yaklaşımlar

Eşleme Adımı girdi olarak |S| = n olan anahtar kümesi S’yi alır ve çevrimsiz bir rastgele hipergraph Gᵣ ile L adlı bir kenar listesi oluşturur.

Bir hipergraphın çevrimsiz olduğunu, eğer boş grafik ise veya derece 1 olan bir düğüme sahip bir kenarı kaldırabildiğimiz ve bu işlem sonucunda elde edilen graf (tümevarımsal olarak) çevrimsiz kalıyorsa söyleriz. Bu durum, Gᵣ’nin kenarlarını şu şekilde bir listeye sıralayabileceğimiz anlamına gelir

L = e₁, … , eₙ

öyle ki herhangi bir eᵢ kenarı, j > i için hiçbir eⱼ kenarına komşu olmayan bir düğüm içerir. L listesi, Gᵣ’nin çevrimsiz olup olmadığını belirleyen ve O(n) zamanda çalışan bir test sırasında elde edilir (örneğin bkz. [14]).

Pᵣᵃ ile Gᵣ’nin çevrimsiz olma olasılığını gösterelim. Bunun sabit olasılıkla gerçekleşmesini isteriz; yani Pᵣᵃ = Ω(1). m = cn olacak şekilde c’yi tanımlarız.

r = 2 için [12]’de sunulan teknikler kullanılarak

Pᵣᵃ = 1 − (2/c)²

olduğu gösterilebilir.

Örneğin c = 2.09 olduğunda Pᵣᵃ = 0.29 elde edilir. Bu değer, n = 10⁷ anahtar (kenar) içeren 1.000 rastgele iki parçalı 2-graf üretilerek deneysel olarak elde edilen 0.294 değerine oldukça yakındır.

r > 2 için Pᵣᵃ üzerinde sıkı bir sınır elde etmek teknik olarak zor görünmektedir. Ancak [4, Teorem 6.5]’te sunulan sezgisel argüman bizim r-parçalı rastgele hipergraphlarımız için de geçerlidir.

Bu argüman, eğer c = c(r) şu şekilde verilirse

c(r) = min_{x > 0} ( x / (1 − e^(−x))^{r−1} )^{−1}, r > 2 için,

ve

c(r) = 2 + ε, ε > 0, r = 2 için,

çevrimsiz rastgele r-grafların rastgele r-grafların uzayına hâkim olacağını öne sürer. c(3) ≈ 1.23 değeri Denklem (4) için minimum değerdir. Bu, en az düğüm sayısına sahip çevrimsiz r-parçalı hipergraphların r = 3 olduğunda ortaya çıktığını gösterir. Bu durumda, n = 10^7 anahtar (hiperkenar) içeren 1.000 rastgele 3-parçalı hipergraph üreterek deneysel olarak Pᵣᵃ ≈ 1 elde edilmiştir.

r = 2 ve r > 2 için çevrimsiz r-parçalı hipergraflar üretme problemlerinin farklı doğalara sahip olduğunu belirtmek ilginçtir. r = 2 için Pra olasılığı sabit c ile sürekli olarak değişir. Ancak r > 2 için bir faz geçişi vardır. Yani öyle bir c(r) değeri vardır ki c ≤ c(r) ise n → ∞ iken Pra 0'a yaklaşır ve c > c(r) ise Pra 1'e yaklaşır. Bu olgu Majewski ve arkadaşları [14] tarafından genel hipergraflar için de rapor edilmiştir.

Assigning Step, Gr grafının köşeleri için g : V(Gr) → {0, 1, ..., r} etiketlemesini oluşturur. Gr'nin köşelerine değer atamak için kenarları ters sırada en, ..., e1 dolaşırız; böylece her kenarın ilk kez dolaşılan en az bir köşesi bulunur.

Atama şu şekilde yapılır. Visited, bir köşenin ziyaret edilip edilmediğini gösteren m boyutunda bir boolean vektör olsun. Önce g[i] = r (yani her köşe atanmamış) ve Visited[i] = false olacak şekilde başlatırız, 0 ≤ i ≤ m − 1. Ardından, L içindeki her e kenarı için kuyruktan başa doğru ilerlerken, e içinde henüz ziyaret edilmemiş ilk u köşesini ararız. 0 ≤ j ≤ r − 1 olmak üzere j, u'nun e içindeki indeksidir. Daha sonra

g[u] = (j − ∑_{v∈e ∧ Visited[v]=true} g[v]) mod r

değerini atarız.

e kenarından bir u köşesinden her geçtiğimizde, eğer daha önce ziyaret edilmemişse Visited[u] = true yaparız. Her kenar yalnızca bir kez işlendiğinden Assigning Step de doğrusal zamanda çalışır.

3.3 Ranking Step

Ranking Step, Bölüm 3.2'de sunulan PHF'lerden MPHF'ler elde eder. Girdi olarak g etiketlemesini alır ve çıktı olarak rankTable üretir. Eq. (3)'te sunulan rank fonksiyonunun sabit zamanda hesaplanmasına olanak sağlayan bir veri yapısını o(m) ek bit kullanarak kurmak mümkündür. Bu, özlü veri yapılarında iyi incelenmiş bir temel işlemdir (örneğin bkz. [17]).

Implementation

Şimdi doğrusal zamanda rankTable veri yapısını hesaplamak için εm ek bit kullanan pratik bir varyantı açıklıyoruz; burada ε herhangi bir pozitif sayı olarak seçilebilir. Kavramsal olarak yöntem oldukça basittir: rankTable içinde her k'inci indeksin rank değerini açıkça saklarız; burada

k = ⌊log(m) / ε⌋.

Uygulamada k parametresinin kullanıcı tarafından ayarlanmasına izin veririz; böylece kullanıcılar alan ile değerlendirme zamanı arasında karşılıklı bir denge kurabilir. Deneylerde, ortaya çıkan MPHF'leri depolarken daha az alan kullanmak için k değerini 256 olarak ayarladık. Bu, g etiketlemesinde her 256'ncı girişten önce atanmış köşelerin sayısını rankTable içinde sakladığımız anlamına gelir.

Evaluation

Eq. (1) ile verilen u için rank(u) hesaplamak üzere, rankTable içinde u ≤ v koşulunu sağlayan ve önceden hesaplanmış en büyük v indeksinin rank değerine bakarız ve v konumundan u − 1 konumuna kadar atanmış köşelerin sayısını sayarız. Bunu O(1/ε) zamanda yapmak için, Ω(log m) bit içindeki atanmış köşe sayısını sabit zamanda saymamıza izin veren bir lookup tablosu kullanırız. Böyle bir lookup tablosu m^{Ω(1)} bit alan gerektirir.

Deneylerde, 8 bit içindeki atanmış köşelerin sayısını sabit zamanda saymamıza izin veren bir lookup tablosu kullandık. Bu nedenle 256 bit içindeki atanmış köşelerin sayısını hesaplamak için 32 lookup gerekir. Böyle bir lookup tablosu yalnızca 2^8 bayt alan gerektirdiğinden tamamen önbelleğe sığar.

Az önce açıklanan uygulamayı kullanıyoruz çünkü en küçük hipergraflar r = 3 olduğunda elde edilir (bkz. Bölüm 3.1). Dolayısıyla en kompakt ve verimli fonksiyonlar r = 2 ve r = 3 olduğunda elde edilir. Bu nedenle aşağıdaki bölümlerde tartışılmak üzere ailenin bu iki örneğini seçtik.

4 The 2-Uniform Hypergraph Instance

2-grafların kullanımı, Eq. (1)'deki PHF'leri üretmemize olanak sağlar; bu fonksiyonlar [0, m − 1] aralığında değer üretir; burada m = (2 + ε)n ve ε > 0'dır (bkz. Bölüm 3.1). Bir PHF için g etiketlemesindeki anlamlı değerler {0, 1}'dir çünkü sıralamayı hesaplamak için bilgi temsil etmemiz gerekmez (yani r = 2). Bu nedenle her köşeye atanan değeri temsil etmek için yalnızca bir bit kullanabiliriz. Dolayısıyla ortaya çıkan PHF'nin saklanması için m bit gerekir. ε = 0.09 için elde edilen PHF'ler yaklaşık 2.09n bit içinde saklanır.

Eq. (2)'deki MPHF'leri üretmek için sıralama bilgisini de eklememiz gerekir. Bu nedenle atanmış olmayan köşeleri temsil etmek için r = 2 değerini kullanırız ve artık köşelere atanan her değeri kodlamak için iki bit gerekir. Böylece ortaya çıkan MPHF'lerin saklanması için (2 + ε)m bit gerekir (sıralama bilgisinin εm bit gerektirdiğini hatırlayın); bu da herhangi bir ε > 0 için (2 + ε)(2 + ε)n bite karşılık gelir. ε = 0.125 ve ε = 0.09 için elde edilen fonksiyonlar yaklaşık 4.44n bit içinde saklanır.

Köşelere atanan anlamlı değer aralığı açıkça [0, 2]'dir. Dolayısıyla her köşeye atanan değeri kodlamak için log(3) bit gerekir. Kuramsal olarak değer blokları üzerinde aritmetik kodlama kullanırız. Bu nedenle basit bir paketleme tekniği kullanarak ortaya çıkan MPHF'yi (log(3) + ε)(2 + ε)n bit depolama alanına sıkıştırabiliriz.

Pratikte her 5 köşelik grubun atanmış değerlerini tek bir bayta paketleyebiliriz çünkü her atanmış değer 3 büyüklüğünde bir aralıktan gelir ve 3^5 = 243 < 256'dır. Dolayısıyla ε = 0.125 ve ε = 0.09 ise ortaya çıkan fonksiyonlar yaklaşık 3.6n bit içinde saklanır.

4.1 Alanı İyileştirme

Şimdi, şemaya biraz karmaşıklık ekleyerek alanı anahtar başına 3 bitin biraz üzerine düşürmenin başka bir yolunu özetliyoruz. ε > 0 için m = (2 + ε/2)n kullanın. Şimdi atanmış köşeler kümesini ayrı olarak saklayın; böylece rank işlemleri (ε/2)n bit ek alan kullanarak verimli biçimde desteklenir. Son olarak her atanmış köşe v için g(v) bitini saklayın (0 veya 1 olmalıdır). Doğru bit, atanmış köşeler kümesi üzerinde rank kullanılarak bulunabilir. Böylece g(v) değerlerini saklamak için n bit gerekir. Dolayısıyla toplam alan (3 + ε)n olur.

5 The 3-Uniform Hypergraph Instance

3-grafların kullanımı, bir adet ek hash fonksiyonu h2 karşılığında daha kompakt PHF ve MPHF üretmemize olanak tanır. m ≥ c(3)n olduğunda çevrimsiz rastgele bir 3-graf Ω(1) olasılıkla üretilir; burada c(3) ≈ 1.23, c(r) için minimum değerdir (bkz. Bölüm 3.1). Dolayısıyla Eq. (1)'deki PHF'leri herhangi bir ε ≥ 0 için [0, (1.23 + ε)n − 1] aralığında değer üretecek şekilde oluşturabiliriz.

Köşelere atanan değerler {0, 1, 2, 3} kümesinden seçilir ve dolayısıyla her değer temsil edilmek için 2 bit gerektirir. Böylece ortaya çıkan PHF'lerin saklanması için 2(1.23 + ε)n bit gerekir; bu da ε = 0 için 2.46n bite karşılık gelir.

Eq. (2)'deki MPHF'leri, r = 3 özel değerini dikkate alan PHF'lerden elde edebiliriz. Ortaya çıkan MPHF'lerin saklanması için herhangi bir ε > 0 ve ε ≥ 0 için (2 + ε)(1.23 + ε)n bit gerekir; çünkü sıralama bilgisi de dahil edilmelidir. Eğer ε = 0.125 ve ε = 0 ise ortaya çıkan fonksiyonlar yaklaşık 2.62n bit içinde saklanır.

5.1 Alanı İyileştirme

[0, (1.23 + ε)n − 1] aralığına eşleyen PHF'ler için daha da kompakt fonksiyonlar elde edebiliriz. Bunun nedeni, Eq. (1)'i hesaplamak için kullanılan köşelere atanmış anlamlı değerlerin yalnızca {0, 1, 2} olmasıdır. Böylece Bölüm 4.1'de sunulan paketleme tekniğini uygulayarak saklanması için

log(3)(1.23 + ε)n

bit gerektiren PHF'ler elde edebiliriz; bu da ε = 0 için yaklaşık 1.95n bittir. Bunun için özel değer r = 3 yerine 0 kullanılmalıdır.

6 Tam Rastgelelik Varsayımı

Tam rastgelelik varsayımı uygulanabilir değildir çünkü her hash fonksiyonu hi : U → [i·m/r, (i + 1)m/r − 1] (0 ≤ i < r için) saklanmak üzere en az n log(m/r) bit gerektirir ve bu da PHF'ler için gereken alanı aşar.

Kuramsal açıdan bakıldığında tam rastgelelik varsayımı çok zararlı değildir; çünkü Dietzfelbinger ve Weidling [6] tarafından önerilen "split and share" yaklaşımını kullanabiliriz. Ek alan kullanımı bu durumda O(n^{1−Ω(1)}) mertebesinde daha düşük bir terim olur. Özellikle algoritma S kümesini boyutu n^δ olan O(n^{1−δ}) kovaya böler; burada örneğin δ < 1/3 olabilir. Ardından her kova için, boyutu O(n^{2δ}) olan O(r) adet basit hash fonksiyonundan oluşan bir havuz kullanarak bir perfect hash fonksiyonu oluşturur; bu fonksiyonlar yüksek olasılıkla her kovada gerçek rastgele fonksiyonlar gibi davranır. Bu havuzdan her kova için yüksek olasılıkla uygun r fonksiyon bulunabilir. Tümünü birleştirerek S için tek bir perfect hash fonksiyonu oluşturmak O(n^{1−δ}) boyutunda bir ofset tablosu kullanılarak yapılabilir.

Implementation

Pratikte sınırlı rastgelelik çoğu zaman tam rastgelelik kadar iyi sonuç verir [19]. Deneylerimizde hi fonksiyonlarını, Alon, Dietzfelbinger, Miltersen ve Petrank [1] tarafından önerilen evrensel hash fonksiyonları ailesi H içinden seçtik ve yöntemlerin iyi davrandığını deneysel olarak doğruladık (bkz. Bölüm 7).

hi fonksiyonlarının paralel hesaplanabilmesi için H ailesinden bir h′ fonksiyonu kullanırız. Bunun için S kümesindeki anahtarların uzunluklarına bir üst sınır L koyarız. h′ fonksiyonu aşağıdaki biçimdedir:

h′(x) = Ax

burada x ∈ S ⊆ {0,1}^L ve A, elemanları {0,1} kümesinden rastgele seçilmiş bir γ × L matrisidir. Çıktı, önceden tanımlanmış uzunlukta γ bitlik bir bit dizisidir.

Her hi hash fonksiyonu şu şekilde hesaplanır:

hi(x) = h′(x)[a, b] mod (m/r)

burada a = βi, b = a + β − 1 ve β, her hi hesaplamasında h′ çıktısından kullanılan bit sayısıdır. [2]'de h′ fonksiyonunun ve dolayısıyla hi fonksiyonlarının verimli uygulanmasını sağlayan bir tablolama fikri gösterilmiştir. hi hash fonksiyonları için gereken depolama alanı, h′ için gereken alana eşittir ve γ × L bittir.

7 Deneysel Sonuçlar

Bu bölümde algoritmalarımızın performansını değerlendiriyoruz. Literatürde bulunan başlıca pratik minimal perfect hashing algoritmalarıyla karşılaştırma yapıyoruz. Bunlar:

• Botelho, Kohayakawa ve Ziviani [3] (BKZ)
• Fox, Chen ve Heath [7] (FCH)
• Majewski, Wormald, Havas ve Czech [14] (MWHC)
• Pagh [16] (PAGH)

MWHC algoritması için 3-graflara dayalı sürümü kullandık. 2-graf kullanan sürümü dikkate almadık çünkü [3]'te BKZ algoritmasının onu geride bıraktığı gösterilmiştir. Tüm algoritmalar için Bölüm 6'da sunulan doğrusal hash fonksiyonlarını kullandık.

Algoritmalar C dilinde uygulanmıştır ve şu adreste bulunmaktadır:

http://cmph.sf.net

GNU Lesser General Public License (LGPL) altında.

Deneyler, Linux işletim sistemi sürüm 2.6 üzerinde çalışan bir bilgisayarda gerçekleştirilmiştir. Sistem 3.2 gigahertz Intel Xeon işlemciye, 2 megabayt L2 önbelleğe ve 1 gigabayt ana belleğe sahiptir. Her deney 100 tekrar halinde yürütülmüştür.

Deneylerde iki veri kümesi kullandık:

• Rastgele üretilmiş 4 bayt uzunluğunda IP adreslerinden oluşan bir küme
• Web'den toplanmış ortalama 64 bayt uzunluğunda URL'lerden oluşan bir küme

Algoritmaları karşılaştırmak için aşağıdaki ölçütleri kullandık:

• Generation Time: MPHF üretmek için gereken süre
• Storage Space: erişim sırasında ortaya çıkan MPHF tanımının gerektirdiği alan
• Evaluation Time: bir MPHF'nin her erişim için gerektirdiği süre

Tüm deneylerde iki veri kümesi için n = 3,541,615 anahtar kullandık. n için küçük bir değer seçmemizin nedeni, FCH algoritmasının üretim aşamasında n üzerinde üstel zaman karmaşıklığına sahip olmasıdır; anahtar sayısı biraz arttığında süreler hızla büyür.

Tablo 1 — Üretim Süresi ve Depolama Alanı Açısından Karşılaştırma

Evaluation Time

PAGH algoritması tarafından üretilen MPHF'nin erişim sırasında gerçekleştirdiği bellek erişimi sayısı optimal olsa da [16] (yalnızca bir bellek erişimi yapar), değerlendirme süresi FCH ve bizim algoritmalarımız için daha küçüktür çünkü üretilen fonksiyonlar tamamen makinenin L2 önbelleğine sığar.

Örneğin, 6.5 milyon anahtara kadar olan kümeler için algoritmalarımızın ürettiği fonksiyonlar tamamen 2 MB L2 önbelleğe sığar. Ters durumda, yani fonksiyonlar önbelleğe sığmadığında, PAGH algoritması tarafından üretilen MPHF'ler en verimli olanlardır.

Tablo 2 — Değerlendirme Süresi Karşılaştırması

Tablo 3 — PHF'ler ve MPHF'ler (Üretim, Değerlendirme, Depolama)

8 Sonuçlar

Neredeyse alan açısından optimal PHP'ler ve MPHF'ler üretmek için verimli bir algoritma ailesi sunduk. Bu algoritmalar daha basittir ve n < 2^30 için mevcut kuramsal sonuçlara göre çok daha düşük sabit katsayılara sahiptir. Ayrıca üretim süresi ve depolama alanı ölçütleri dikkate alındığında literatürde bulunan başlıca pratik genel amaçlı algoritmalardan daha iyi performans gösterirler.

Teşekkür

Daha kompakt fonksiyonlar üretmek için aritmetik kodlama önerisinde bulunduğu için Djamal Belazzougui'ye ve çevrimsiz r-parçalı rastgele r-graflar konusunda yardım ettiği için Yoshiharu Kohayakawa'ya teşekkür ederiz.

References

1. N. Alon, M. Dietzfelbinger, P. B. Miltersen, E. Petrank ve G. Tardos. Doğrusal hash fonksiyonları. Journal of the ACM, 46(5):667–683, 1999.
2. N. Alon ve M. Naor. Rastgeleliğin ortadan kaldırılması, Boolean matris çarpımı için tanıklar ve mükemmel hash fonksiyonlarının oluşturulması. Algorithmica, 16(4–5):434–449, 1996.
3. F. C. Botelho, Y. Kohayakawa ve N. Ziviani. Pratik bir minimal mükemmel hashleme yöntemi. Proc. of the 4th International Workshop on Efficient and Experimental Algorithms (WEA’05) içinde, sayfa 488–500. Springer LNCS cilt 3503, 2005.
4. Z. J. Czech, G. Havas ve B. S. Majewski. Mükemmel hashleme üzerine temel bir çalışma. Theoretical Computer Science, 182:1–143, 1997.
5. M. Dietzfelbinger ve T. Hagerup. Daha az alanda basit minimal mükemmel hashleme. Proc. of the 9th European Symposium on Algorithms (ESA’01) içinde, sayfa 109–120. Springer LNCS cilt 2161, 2001.
6. M. Dietzfelbinger ve C. Weidling. Dengeli tahsis ve sıkı biçimde paketlenmiş sabit boyutlu kutulara sahip sözlükler. Proc. of the 32nd International Colloquium on Automata, Languages and Programming (ICALP) içinde, sayfa 166–178, 2005.
7. E. A. Fox, Q. F. Chen ve L. S. Heath. Minimal mükemmel hash fonksiyonları geliştirmek için daha hızlı bir algoritma. Proc. of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval içinde, sayfa 266–273, 1992.
8. E. A. Fox, L. S. Heath, Q. Chen ve A. M. Daoud. Büyük veritabanları için pratik minimal mükemmel hash fonksiyonları. Communications of the ACM, 35(1):105–121, 1992.
9. M. L. Fredman ve J. Komlós. Ayırıcı sistemlerin ve mükemmel hash fonksiyonu ailelerinin boyutu üzerine. SIAM Journal on Algebraic and Discrete Methods, 5:61–68, 1984.
10. M. L. Fredman, J. Komlós ve E. Szemerédi. O(1) en kötü durum erişim süresiyle seyrek bir tablonun saklanması. Journal of the ACM, 31(3):538–544, Temmuz 1984.
11. T. Hagerup ve T. Tholey. Neredeyse minimal alanda verimli minimal mükemmel hashleme. Proc. of the 18th Symposium on Theoretical Aspects of Computer Science (STACS’01) içinde, sayfa 317–326. Springer LNCS cilt 2010, 2001.
12. S. Janson. Poisson yakınsaması ve rastgele graflara uygulamalarıyla Poisson süreçleri. Stochastic Processes and their Applications, 26:1–30, 1987.
13. S. Lefebvre ve H. Hoppe. Mükemmel mekânsal hashleme. ACM Transactions on Graphics, 25(3):579–588, 2006.
14. B. S. Majewski, N. C. Wormald, G. Havas ve Z. J. Czech. Bir mükemmel hashleme yöntemleri ailesi. The Computer Journal, 39(6):547–554, 1996.
15. K. Mehlhorn. Veri Yapıları ve Algoritmalar 1: Sıralama ve Arama. Springer-Verlag, 1984.
16. R. Pagh. Hash ve yer değiştirme: Minimal mükemmel hash fonksiyonlarının verimli değerlendirilmesi. Workshop on Algorithms and Data Structures (WADS’99) içinde, sayfa 49–54, 1999.
17. R. Pagh. Sabit sorgu süresine sahip statik sözlüklerde düşük fazlalık. SIAM Journal on Computing, 31(2):353–363, 2001.
18. J. Radhakrishnan. Tam düzgün hiperografların örtülmesi için iyileştirilmiş sınırlar. Information Processing Letters, 41:203–207, 1992.
19. J. P. Schmidt ve A. Siegel. Oblivious k-probe hash fonksiyonlarının mekânsal karmaşıklığı. SIAM Journal on Computing, 19(5):775–786, Ekim 1990.
20. Philipp Woelfel. Harici bellek için verimli hash tablolarının sürdürülmesi. Proc. of the 10th International Workshop on Randomization and Computation (RANDOM’06) içinde, sayfa 508–519. Springer LNCS cilt 4110, 2006.