Çok Büyük Veritabanları İçin Minimal Perfect Hash Fonksiyonlarına Bir Yaklaşım

Fabiano C. Botelho
Bilgisayar Bilimleri Bölümü
Federal Univ. of Minas Gerais
Belo Horizonte, Brezilya
fbotelho@dcc.ufmg.br

Yoshiharu Kohayakawa
Bilgisayar Bilimleri Bölümü
Univ. of São Paulo
São Paulo, Brezilya
yoshi@ime.usp.br

Nivio Ziviani
Bilgisayar Bilimleri Bölümü
Federal Univ. of Minas Gerais
Belo Horizonte, Brezilya
nivio@dcc.ufmg.br

ÖZET

Devasa anahtar kümeleri için minimal perfect hash fonksiyonları h oluşturmak amacıyla dış bellek tabanlı yeni bir algoritma öneriyoruz. n anahtardan oluşan bir küme için algoritmamız h fonksiyonunu O(n) zamanda üretir. Algoritma, h fonksiyonunu oluşturmak için ana bellekte bir baytlık girişlerden oluşan küçük bir vektöre ihtiyaç duyar. Herhangi bir x anahtarı için h(x) değerinin hesaplanması üç bellek erişimi gerektirir. h fonksiyonunun tanımı, her anahtar için en fazla 9 bit olmak üzere sabit sayıda bit kaplar; bu değer optimaldir ve teorik alt sınıra oldukça yakındır, yani anahtar başına yaklaşık 2 bit civarındadır.

Deneylerimizde, web’den toplanmış 1 milyar URL içeren bir koleksiyon kullandık; her URL ortalama 64 karakter uzunluğundadır. Bu koleksiyon için algoritmamız:

• sıradan bir PC kullanarak yaklaşık 3 saat içinde minimal perfect hash fonksiyonu bulur,
• h fonksiyonunu üretmek için yalnızca 5.45 megabayt iç bellek gerektirir ve
• h fonksiyonunun tanımı için anahtar başına 8.1 bit kullanır.

Kategoriler ve Konu Tanımlayıcıları

Minimal Perfect Hash Fonksiyonları, Büyük Veritabanları

1. GİRİŞ

Bir perfect hash fonksiyonu, n anahtardan oluşan statik bir kümeyi çakışma olmadan m adet tamsayıdan oluşan bir kümeye eşler; burada m, n’e eşit veya daha büyüktür. Eğer m, n’e eşitse fonksiyon minimal olarak adlandırılır. Şekil 1(a) bir perfect hash fonksiyonunu, Şekil 1(b) ise bir minimal perfect hash fonksiyonunu (MPHF) göstermektedir.

Minimal perfect hash fonksiyonları, doğal dillerdeki kelimeler, programlama dillerindeki ayrılmış kelimeler veya etkileşimli sistemler, web arama motorlarındaki evrensel kaynak konumları (URL'ler) ya da veri madenciliği tekniklerindeki öğe kümeleri gibi statik kümelerden öğelerin bellek açısından verimli biçimde saklanması ve hızlı biçimde geri alınması için yaygın şekilde kullanılır.

Günümüzde arama motorları on milyarlarca sayfayı indekslemektedir ve web sayfalarının popülerliğini ölçmek için web bağlantı yapısını kullanan PageRank [3] gibi algoritmalar, URL’lerin saklanması ve geri alınması için bir MPHF kullanmaktan fayda sağlayabilir.

MPHF’ler için bir diğer ilginç uygulama, veritabanları için indeksleme yapısı olarak kullanılmalarıdır. B+ ağacı, kayıtların sık eklenip silindiği dinamik uygulamalar için bir indeksleme yapısı olarak oldukça popülerdir. Ancak nadiren değişiklik yapılan ve çok büyük sayıda sorgunun bulunduğu uygulamalarda B+ ağacı en iyi seçenek değildir; çünkü yeni veritabanı uygulamalarının gerektirdiği çok büyük anahtar kümeleriyle çalışırken zayıf performans gösterir [19].

Bu nedenle MPHF’lerin; bilgi erişim sistemleri, veritabanı sistemleri, dil çeviri sistemleri, elektronik ticaret sistemleri, derleyiciler, işletim sistemleri ve benzeri alanlarda uygulamaları vardır.

Şu ana kadar mevcut algoritmaların sınırlamaları nedeniyle MPHF kullanımı, hash işlemi uygulanacak anahtar kümesinin küçük olduğu senaryolarla sınırlı kalmıştır. Ancak birçok durumda çok büyük anahtar kümeleriyle verimli şekilde çalışmak kritik öneme sahiptir. Bilgi erişim (IR) topluluğunda devasa koleksiyonlarla çalışmak günlük bir görevdir. Örneğin, bir koleksiyondaki web sayfalarına sayısal kimlikler atamak bile zorlu bir görev olabilir.

Geleneksel veritabanları, URL çalışma kümesi artık ana belleğe sığmadığında daha fazla trafiği yönetemezken, burada MPHF oluşturmak için önerdiğimiz algoritma milyarlarca girdiye kolayca ölçeklenebilir.

MPHF’lerin pek çok uygulaması bulunduğundan, bu tür fonksiyonların oluşturulması için zaman ve alan açısından verimli algoritmalar tasarlamak ve uygulamak önemlidir. MPHF kullanımının cazibesi aşağıdaki konulara bağlıdır:

1. MPHF oluşturma algoritmalarının gerektirdiği CPU zamanı.
2. MPHF oluşturma algoritmalarının alan gereksinimleri.
3. Her geri alma işlemi için bir MPHF’nin gerektirdiği CPU zamanı.
4. Geri alma sırasında kullanılacak MPHF tanımının alan gereksinimleri.

Bu makale, yukarıda belirtilen dört gereksinim açısından oldukça verimli olan, dış bellek tabanlı yeni bir MPHF oluşturma algoritması sunmaktadır.

Birincisi, algoritma bir MPHF oluşturmak için anahtar kümesinin büyüklüğüne göre doğrusal karmaşıklığa sahiptir; bu optimaldir. Örneğin, web’den toplanmış ve her biri ortalama 64 karakter uzunluğunda olan 1 milyar URL’den oluşan bir koleksiyon için, 2.4 gigahertz işlemcili ve 500 megabayt kullanılabilir ana belleğe sahip bir PC kullanılarak bir MPHF oluşturma süresi yaklaşık 3 saattir.

İkincisi, algoritma bir MPHF oluşturmak için ana bellekte ⌈n/b⌉ adet bir baytlık girişten oluşan, önceden tanımlanmış küçük bir vektöre ihtiyaç duyar. 1 milyar URL içeren koleksiyon ve b = 175 kullanıldığında, algoritma yalnızca 5.45 megabayt iç bellek gerektirir.

Üçüncüsü, her geri alma işlemi için MPHF’nin değerlendirilmesi üç bellek erişimi ve üç evrensel hash fonksiyonunun hesaplanmasını gerektirir. Bu optimal değildir; çünkü herhangi bir MPHF en az bir bellek erişimi ve iki evrensel hash fonksiyonunun hesaplanmasını gerektirir.

Dördüncüsü, bir MPHF’nin tanımı her anahtar için sabit sayıda bit gerektirir; bu da optimaldir. 1 milyar URL’den oluşan koleksiyon için anahtar başına 8.1 bit gerektirir ve bu değer teorik alt sınıra yakındır:

1 / ln 2 ≈ 1.4427 bit / anahtar [15].

2. GÖSTERİM VE TERİMLER

Bu makale boyunca kullanılan temel gösterim ve terimler aşağıdaki gibidir:

• h : U → M, anahtarları bir evren U içinden alıp verilen bir M = {0, 1, ..., m − 1} tamsayı aralığına eşleyen bir hash fonksiyonudur.
• h, S üzerinde bire bir ise perfect hash fonksiyonudur; yani S kümesinden tüm k₁ ≠ k₂ için h(k₁) ≠ h(k₂) koşulu sağlanır.
• h, S üzerinde bire bir ve n = m ise minimal perfect hash fonksiyonu (MPHF) olarak adlandırılır.

3. İLGİLİ ÇALIŞMALAR

Czech, Havas ve Majewski [5], perfect hashing üzerine en önemli teorik ve pratik sonuçların kapsamlı bir incelemesini sunmaktadır. Bu bölümde en önemli sonuçlardan bazılarını gözden geçiriyoruz.

Fredman, Komlós ve Szemerédi [10], tablo boyutlarının anahtar sayısına doğrusal olarak bağlı olduğu (m = O(n)) ve sabit zamanda değerlendirilebilen alan açısından verimli perfect hash fonksiyonlarının geliştirilebileceğini göstermiştir.

Onların hesaplama modelinde, evren U’nun bir elemanı tek bir makine kelimesine sığar ve aritmetik işlemler ile bellek erişimleri birim maliyetlidir. FKS modelindeki rastgeleleştirilmiş algoritmalar, beklenen O(n) zamanda bir perfect hash fonksiyonu geliştirebilir. Bu durum bizim algoritmamız ve [4,16]’daki çalışmalar için de geçerlidir.

Mehlhorn [15], bir MPHF’yi temsil etmek için en az Ω((1/ln 2)n + ln ln u) bit gerektiğini göstermiştir (yani anahtar başına en az 1.4427 bit saklanmalıdır). Bildiğimiz kadarıyla, algoritmamız milyarlar mertebesinde anahtar içeren kümeler için MPHF üretebilen ilk algoritmadır ve üretilen fonksiyonların saklanması için anahtar başına 9 bitten az alan gerektirir.

Minimal perfect hashing üzerine bazı çalışmalar, algoritmanın gerçekten rastgele fonksiyonlar seçip saklayabileceği varsayımı altında yapılmıştır [2,4,16]. Gerçekten rastgele fonksiyonların alan gereksinimleri uygulama açısından uygun olmadığından, pratikte sözde rastgele fonksiyonlarla yetinmek gerekir. Deneysel çalışmalar, sınırlı rastgelelik özelliklerinin çoğu zaman tam rastgelelik kadar iyi sonuç verdiğini göstermektedir.

Deneylerimizde Jenkins [13] tarafından önerilen evrensel hash fonksiyonunu kullanarak bu olguyu doğruladık. Bu fonksiyon geri alma sırasında zaman açısından verimlidir ve rastgele tohum olarak kullanılmak üzere yalnızca bir tamsayı gerektirir (fonksiyon tamamen bu tohum tarafından belirlenir).

Pagh [16], elde edilen fonksiyonun şu biçime sahip olduğu MPHF oluşturma için bir rastgeleleştirilmiş algoritma ailesi önermiştir:

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

burada f ve g evrensel hash fonksiyonlarıdır ve d, f fonksiyonunun neden olduğu çakışmaları çözmek için kullanılan bir yer değiştirme değerleri kümesidir.

Pagh, f ve g ile ilgili bir dizi koşul belirlemiş ve bu koşullar sağlandığında minimal perfect hash fonksiyonunun beklenen O(n) zamanda hesaplanabileceğini ve (2 + ε)n log₂ n bit içinde saklanabileceğini göstermiştir.

Dietzfelbinger ve Hagerup [6], [16]’yı geliştirerek depolama gereksinimini (2 + ε)n log₂ n bitten (1 + ε)n log₂ n bite düşürmüştür; ancak onların yaklaşımında f ve g ek gereksinimleri karşılayan bir hash fonksiyonu sınıfından seçilmelidir.

Fox ve diğerleri [8,9], depolama gereksinimini anahtar başına 2 ile 4 bit arasına düşüren MPHF’leri incelemiştir. Ancak [5, Bölüm 6.7]’de bu algoritmaların çalışma sürelerinin üstel olduğu gösterilmiştir.

Önceki çalışmamız [2], Czech, Havas ve Majewski [4] tarafından önerilen algoritmayı geliştirmektedir. Daha kısa sürede daha kompakt fonksiyonlar elde ettik. Bildiğimiz en hızlı algoritma olmasına rağmen, elde edilen fonksiyonlar O(n log n) bit içinde saklanır ve üretim sırasında ana bellekte n kenar ve cn tepe noktası içeren rastgele bir graf tutulması gerekir; burada c ∈ [0.93, 1.15].

İyi bilinen böl-ve-yönet yaklaşımını kullanarak, bu algoritmayı burada sunulan yeni algoritmanın yapı taşı olarak kullanıyoruz.

4. ALGORİTMA

Algoritmamızı destekleyen temel fikir klasik böl-ve-yönet tekniğidir. Algoritma, S kümesinde bulunan n anahtar için bir MPHF h geliştiren iki aşamalı, dış bellek tabanlı bir algoritmadır.

Şekil 2 algoritmanın iki adımını göstermektedir:

• bölümlendirme adımı
• arama adımı

Bölümlendirme adımı, S anahtar kümesini alır ve Jenkins [13] tarafından önerilen evrensel hash fonksiyonu h₀’ı kullanarak her k ∈ S anahtarını bir tamsayıya h₀(k) dönüştürür. h₀(k) değeri ⌈n/b⌉ moduna indirgenerek, S kümesi her kovada en fazla 256 anahtar bulunacak şekilde (yüksek olasılıkla) ⌈n/b⌉ kovaya ayrılır.

Arama adımı her kova i için bir MPHFᵢ geliştirir.

Belirli bir anahtarın hangi kovaya ait olduğunu bulmak için evrensel hash fonksiyonu h₀(k) [13] kullanılır. k anahtarı şu kovaya gider:

i = h₀(k) mod ⌈n/b⌉

Ortaya çıkan MPHF h(k), k ∈ S için şu şekilde verilir:

h(k) = MPHFᵢ(k) + offset[i]

burada i = h₀(k) mod ⌈n/b⌉.

Yer değiştirme vektörü offset’in i-inci girdisi offset[i], 0 ≤ i < ⌈n/b⌉ olmak üzere, 0’dan i − 1’e kadar olan kovaların içerdiği toplam anahtar sayısını tutar. Başka bir deyişle, MPHFᵢ tarafından adreslenen hash tablosundaki anahtarların aralığını verir.

Aşağıda her adımı ayrıntılı biçimde açıklıyoruz.

4.1 Bölümlendirme Adımı

n anahtardan oluşan S kümesi ⌈n/b⌉ kovaya ayrılır; burada b, her kovada yüksek olasılıkla en fazla 256 anahtar bulunmasını garanti edecek uygun bir parametredir.

Bölümlendirme adımı şu şekilde çalışır:

• β, S kümesinin bayt cinsinden boyutu olsun.
• μ, önceden ayrılmış iç bellek alanının bayt cinsinden boyutu olsun.
• N = ⌈β/μ⌉, diskten iç belleğe okunacak anahtar bloklarının sayısı olsun.
• size, her kovanın boyutunu saklayan bir vektör olsun.

Algoritma:

1. j = 1’den N’e kadar:
   • Diskten anahtarların bulunduğu Bⱼ bloğunu oku.
   • Bir bucket sort algoritması kullanarak Bⱼ bloğunu ⌈n/b⌉ kovaya ayır ve size vektöründeki girdileri güncelle.
   • Bⱼ bloğunu diskte j dosyasına yaz.
2. offset vektörünü hesapla ve diske yaz.

İfade 1.1, Bⱼ bloğundaki tüm anahtarları diskten μ boyutundaki iç alana sıralı biçimde okur.

İfade 1.2, size vektöründeki girdileri güncellerken Bⱼ bloğundaki anahtarların dolaylı bir bucket sort işlemini gerçekleştirir.

⌈n/b⌉ sayıda sayaçtan oluşan yerel bir dizi, Bⱼ içindeki kaç anahtarın her kovaya ait olduğunu saklar. i kovasındaki anahtarlara ait işaretçiler (0 ≤ i < ⌈n/b⌉) bir dizide bitişik konumlarda saklanır. Önce sayaç dizisindeki bilgi kullanılarak gerekli giriş sayısı ayrılır. Daha sonra anahtarlara ait işaretçiler ayrılan alanlara yerleştirilir.

Bölümlendirme adımının sonunda kovalar mantıksal olarak düzenlenmiş olur ancak fiziksel olarak birkaç disk dosyasına dağılmış durumdadır.

Son olarak offset vektörü, size vektörü kullanılarak hesaplanır. Her offset[i] girdisi 0, 1, ..., i − 1 kovalarındaki anahtar sayısını içerir.

Bu vektör daha sonra diske yazılır ve nihai minimal perfect hash fonksiyonunun hesaplanmasında kullanılır.

4.2 Arama Adımı

Arama adımı her kova için bir MPHF geliştirmekten sorumludur. Şekil 5 arama adımı algoritmasını göstermektedir.

Şekil 5’teki ifade 1, disk üzerindeki her dosyadan bir anahtarı N boyutlu minimum yığın H içine ekler. H içindeki sıralama ilişkisi, Denklem (2) ile verilen kova adresi i tarafından belirlenir.

İfade 2 iki önemli adıma sahiptir:

• 2.1 ifadesinde, bir kova diskten okunur; bu işlem Bölüm 4.2.1’de açıklanmıştır.
• 2.2 ifadesinde, her i kovası için bir MPHF geliştirilir; bu işlem Bölüm 4.2.2’de açıklanmıştır.

MPHFᵢ’nin tanımı 8 bitlik tamsayılardan oluşan gᵢ vektörüdür. Son olarak 2.3 ifadesi MPHFᵢ’nin tanımı olan gᵢ’yi diske yazar.

Arama Adımı Algoritması

H, boyutu N olan bir minimum yığın olsun ve H içindeki sıralama ilişkisi Denklem (2) tarafından verilsin; yani remove işlemi en küçük i değerine sahip öğeyi çıkarır.

1. j = 1’den N’e kadar {Yığın oluşturma}

   1. Diskteki j dosyasından k anahtarını oku
   2. H içine (i, j, k) ekle

2. i = 0’dan ⌈n/b⌉ − 1’e kadar

   1. Yığın H tarafından yönlendirilerek i kovasını diskten oku
   2. i kovası için bir MPHF geliştir
   3. MPHFᵢ’nin tanımını diske yaz

Şekil 5: Arama adımı

4.2.1 Diskten Bir Kova Okuma

Bu bölümde Şekil 5’teki 2.1 ifadesinin ayrıntılı biçimini sunuyoruz. Diskten i kovasını okuma algoritması Şekil 6’da verilmiştir.

Algoritma

1. i kovası dolu değilken do
   1. H’den (i, j, k) çıkar
   2. k anahtarını i kovasına ekle
   3. Diskteki j dosyasından aynı i değerine sahip tüm k anahtarlarını sıralı olarak oku ve i kovasına ekle
   4. H içine (i, j, x) üçlüsünü ekle; burada x, j dosyasından okunan ve i ile aynı kova indeksine sahip olmayan ilk anahtardır

i kovası birçok dosyaya dağılmış durumdadır ve H yığını çok yollu bir birleştirme işlemini yönlendirmek için kullanılır.

Şekil 6’da ifade 1.1, H’den (i, j, k) üçlüsünü çıkarır ve kaldırır; burada i, H içindeki en küçük değerdir. İfade 1.2, k anahtarını i kovasına ekler. (i, j, k) üçlüsündeki k’nın aslında, karakterlerden oluşan bir dizide bitişik konumlarda saklanan anahtarın ilk baytına işaret eden bir işaretçi olduğuna dikkat edilmelidir. Anahtarları içeren bu dizi, Şekil 5’teki ifade 1’de yığın oluşturulurken başlatılır.

İfade 1.3, ilk okuma işlemi için disk üzerindeki j dosyasında bir seek işlemi gerçekleştirir ve ardından aynı i değerine sahip tüm k anahtarlarını sıralı olarak okuyarak i kovasına ekler. Son olarak ifade 1.4, H içine (i, j, x) üçlüsünü ekler; burada x, j dosyasından (ifade 1.3’te) okunan ve önceki anahtarlarla aynı kova adresine sahip olmayan ilk anahtardır.

Disk üzerinde 1.3 ifadesinde gerçekleştirilen arama (seek) işlemlerinin sayısı, arama işlemleri için harcanan süreyi azaltan bir arabelleğe alma tekniğini sunduğumuz Bölüm 5.1'de tartışılmaktadır.

Şekil 6: Bir bucket'ın okunması

4.2.2 Her Bucket için bir MPHF Oluşturma

Bildiğimiz kadarıyla, önceki çalışmamızda [2] tasarladığımız algoritma MPHFs oluşturmak için yayımlanmış en hızlı algoritmadır. Bu nedenle burada sunulan algoritma için bir yapı taşı olarak bu algoritmayı kullanıyoruz.

Önceki algoritmamız, rastgele graflara dayanan ve bir MPHF üreten üç adımlı, iç bellek tabanlı bir algoritmadır. n anahtardan oluşan bir küme için algoritma, ortaya çıkan MPHF'yi beklenen O(n) zamanda üretir.

Verilen bir i bucket'ı için, burada 0 ≤ i < ⌈n/b⌉, karşılık gelen MPHFᵢ aşağıdaki biçime sahiptir:

MPHFᵢ(k) = gᵢ[a] + gᵢ[b]

burada:

• a = hᵢ₁(k) mod t
• b = hᵢ₂(k) mod t
• t = c × size[i]

hᵢ₁(k) ve hᵢ₂(k) fonksiyonları, Bölüm 4.1'de açıklanan bölümlendirme adımında kullanılan ve Jenkins [13] tarafından önerilen aynı evrensel fonksiyonlardır.

Yukarıdaki fonksiyonu üretmek için algoritma, aşağıdaki özelliklere sahip basit rastgele grafların Gᵢ = (Vᵢ, Eᵢ) oluşturulmasını içerir:

• |Vᵢ| = t = c × size[i]
• |Eᵢ| = size[i]
• c ∈ [0.93, 1.15]

Yüksek olasılıkla¹ basit bir rastgele graf üretmek için, bucket i içindeki her anahtar k için iki köşe a ve b hesaplanır. Böylece her bucket i için karşılık gelen bir graf vardır:

• Gᵢ = (Vᵢ, Eᵢ)
• Vᵢ = {0, 1, ..., t − 1}
• Eᵢ = {{a, b} : k ∈ bucket i}

Basit bir graf elde etmek için algoritma, karşılık gelen graf basit olana kadar evrensel hash fonksiyonları ailesinden hᵢ₁ ve hᵢ₂ fonksiyonlarını tekrar tekrar seçer.

Basit bir graf elde etme olasılığı:

p = e^(−1/c²)

c = 1 için bu olasılık yaklaşık p ≃ 0.368'dir ve basit bir graf elde etmek için beklenen yineleme sayısı 1/p ≃ 2.72'dir.

MPHFᵢ'nin oluşturulması, Gᵢ grafındaki köşelerin uygun bir etiketlemesinin hesaplanmasıyla sona erer. Bu etiketleme gᵢ vektöründe saklanır. v ∈ Vᵢ olan her v için gᵢ[v] değerini, Denklem (3)'ün bucket i için bir MPHF olacağı şekilde seçeriz.

gᵢ içindeki her girişin değerini hesaplamak için önce Gᵢ grafının 2‑çekirdeği üzerinde bir genişlik öncelikli arama (breadth‑first search) çalıştırırız; yani minimum derecesi en az 2 olan Gᵢ'nin en büyük altgrafı (bkz. örn. [1, 12, 17]), ardından Gᵢ'nin çevrimsiz kısmı üzerinde bir derinlik öncelikli arama (depth‑first search) çalıştırırız (ayrıntılar için bkz. [2]).

¹Yüksek olasılıkla terimini n → ∞ iken olasılığın 1'e yaklaşması anlamında kullanıyoruz.

4.3 b'nin Belirlenmesi

Bölümlendirme adımı, iyi bilinen "topların kutulara atılması" (balls into bins) problemi [18, 7] olarak görülebilir; burada n anahtar (toplar) bağımsız ve eşit olasılıkla ⌈n/b⌉ bucket'a (kutulara) yerleştirilir.

İlgilenilen temel soru şudur: herhangi bir bucket içindeki maksimum anahtar sayısı nedir?

Herhangi bir bucket içindeki maksimum anahtar sayısının yüksek olasılıkla 256'dan büyük olmamasını sağlayan b için mümkün olan en büyük değeri elde etmek istiyoruz. Bu önemlidir çünkü her MPHFᵢ için gᵢ vektöründe giriş başına 8 bit kullanmak istiyoruz; burada 0 ≤ i < ⌈n/b⌉.

Herhangi bir bucket içindeki maksimum anahtar sayısını BS_max olarak tanımlayalım.

Açıkça, BS_max, her biri parametreleri:

• n
• p = 1 / ⌈n/b⌉

olan binom dağılımına Bᵢ(n, p) sahip ⌈n/b⌉ adet rastgele değişken Zᵢ'nin maksimumudur.

Ancak Zᵢ değişkenleri bağımsız değildir. Bᵢ(n, p) dağılımının ortalaması ve varyansının yaklaşık b olduğunu unutmayın.

BS_max ≥ γ olayının olasılığı için bir üst tahmin elde etmek amacıyla, sabit bir i için Zᵢ ≥ γ olasılığını tahmin eder ve ardından bu tahminleri tüm i değerleri üzerinde toplarız.

Tanımlayalım:

γ = b + σ √(2 b ln(n/b))

Bᵢ(n, p) dağılımını ortalaması ve varyansı b olan normal dağılım ile yaklaşıklaştırarak, Zᵢ ≥ γ olayının gerçekleşme olasılığı için şu tahmini elde ederiz:

(σ √(2π ln(n/b)))⁻¹ × exp(−(1/2) σ² ln(n/b))

Bu tahminleri tüm i değerleri için topladığımızda, BS_max ≥ γ olayının gerçekleşme olasılığı en fazla:

1 / (σ √(2π ln(n/b)))

olur ve bu değer n → ∞ iken 0'a yaklaşır.

Dolayısıyla yüksek olasılıkla:

BS_max ≤ b + √(2b ln(n/b)) (4)

Tablo 1: BS_max için Değerler

Deneylerde elde edilen en kötü durum ve ortalama durum değerleri ile Denklem (4) kullanılarak elde edilen değerler; S kümesindeki farklı n anahtar sayıları için b = 128 ve b = 175 dikkate alınmıştır.

Denklem (4) ile verilen tahmin, deneysel sonuçlara oldukça yakındır.

Tablo 2: Algoritmanın Çözebileceği En Büyük Problem Boyutu

Denklem (4)'ten elde edilen değerler; b = 128 ve b = 175 için BS_max ≤ 256 koşulu uygulanmıştır.

5 Analitik Sonuçlar

Bu bölümün amacı dört yönlüdür:

1. Algoritmamızın beklenen O(n) zamanda çalıştığını göstermek.
2. MPHF'nin oluşturulması için gereken ana bellek gereksinimlerini sunmak.
3. Elde edilen MPHF'nin değerlendirme maliyetini tartışmak.
4. Ortaya çıkan MPHF'yi depolamak için gereken alanı sunmak.

5.1 Doğrusal Zaman Karmaşıklığı

Öncelikle, Şekil 3'te sunulan bölümlendirme adımının O(n) zamanda çalıştığını gösteriyoruz.

1 ifadesindeki for döngüsünün her yinelemesi O(|Bⱼ|) zamanda çalışır; burada 1 ≤ j ≤ N ve |Bⱼ|, μ boyutundaki Bⱼ bloğuna sığan anahtar sayısını ifade eder.

• 1.1 ifadesi diskten |Bⱼ| anahtar okur.
• 1.2 ifadesi, sıraladığı anahtar sayısına göre doğrusal çalışan bucket‑sort benzeri bir algoritma çalıştırır.
• 1.3 ifadesi |Bⱼ| anahtarı diske File j dosyasına yazar.

Dolayısıyla döngü şu sürede çalışır:

O(Σ |Bⱼ|) = O(n)

çünkü:

Σ |Bⱼ| = n

Bu nedenle bölümlendirme adımı O(n) zamanda çalışır.

İkinci olarak, Şekil 5'te sunulan arama adımının da O(n) zamanda çalıştığını gösteriyoruz.

1 ifadesindeki heap oluşturma işlemi O(N) zamanda çalışır; burada N ≪ n. N genellikle n'den çok daha küçük olduğundan, heap'e ekleme ve heap'ten silme işlemlerinin O(1) maliyetli olduğunu varsayıyoruz.

2 ifadesi şu sürede çalışır:

O(Σ size[i])

burada size[i], i bucket'ındaki anahtar sayısını saklar. Çünkü:

Σ size[i] = n

2 ifadesi, 2.1, 2.2 ve 2.3 ifadeleri O(size[i]) zamanda çalıştığı sürece O(n) zamanda çalışır.

2.1 ifadesi bucket i'den O(size[i]) anahtar okur (bkz. Şekil 6). Her disk okuma/yazma ve heap işleminin O(1) maliyetli olduğu varsayılır.

Ancak bucket i'nin anahtarları en fazla BS_max dosyaya dağılmış olabilir. Kritik adım, Şekil 6'daki 1.3 ifadesinde ortaya çıkar; burada ilk okuma sırasında bir seek işlemi gerçekleşebilir.

Seek işlemlerini amortize etmek için bir arabelleğe alma tekniği kullanırız [14].

Her j dosyası için boyutu:

β = μ / N

olan bir j arabelleği oluştururuz; burada 1 ≤ j ≤ N.

Dosya j için yapılan bir okuma isteği arabellek tarafından karşılanamazsa, dosyadan arabelleğe β bayt okunur.

Böylece en kötü durumdaki seek sayısı:

β / ℓ

olur; burada β, S kümesinin bayt cinsinden toplam boyutudur. Her URL'nin ortalama 64 bayt uzunluğunda olduğunu varsayarsak seek sayısı 64n / ℓ olur; bu değer n ile doğrusal büyür ve ℓ ile amortize edilir.

İki önemli gözlem vardır:

• İşletim sistemleri zaten seek sayısını ve maliyetini azaltan teknikler uygular.
• Ana belleğin neredeyse tamamı dosya arabellekleri olarak kullanılabilir çünkü ana bellekte yalnızca ⌈n/b⌉ adet tek baytlık girişten oluşan küçük bir vektör tutulmalıdır (bkz. Bölüm 5.2).

2.2 ifadesi her bucket için bir MPHF üretmek amacıyla iç bellek algoritmasını çalıştırır. Algoritma doğrusal olduğundan ve size[i] anahtara sahip bucket'lara uygulandığından, bu adım O(size[i]) zamanda çalışır.

2.3 ifadesi de O(size[i]) zamanda çalışır çünkü MPHF tanımını diske yazar ve her tanım c × size[i] + O(1) bayt yer kaplar; burada c ∈ [0.93, 1.15].

Sonuç olarak algoritma O(n) zamanda çalışır çünkü hem bölümlendirme hem de arama adımları doğrusal zamandadır.

Tablo 3: İç Bellek Tabanlı Algoritmanın Performansı

Bir MPHF oluşturmak için ortalama süre.

Tablo, ortalama oluşturma süresini, standart sapmayı (SD) ve %95 güven düzeyi dikkate alınarak hesaplanan güven aralıklarını sunmaktadır.

Örneğin, 1 milyar anahtardan oluşan bir küme ve b = 175 için vektör boyutu ana bellekte 5.45 megabayt gerektirir.

Bölümlendirme adımında ve arama adımında kullanılmak üzere µ bayt boyutunda bir iç bellek alanına ihtiyaç vardır. µ boyutu önceden sabitlenir ve yalnızca algoritmayı çalıştırmak için mevcut iç bellek miktarına bağlıdır (yani problemin n boyutuna bağlı değildir).

Arama adımında gereken ek alan sabittir; çünkü problem birkaç küçük probleme (en fazla 256 anahtar) ayrılmıştır ve heap boyutunun n'den çok daha küçük olduğu varsayılır (N ≪ n). Örneğin, 1 milyar anahtar içeren bir küme ve µ = 250 megabayt iç bellek alanı için dosya sayısı N = 248 olur.

5.3 MPHF'nin Değerlendirme Maliyeti

Şimdi, elde edilen MPHF'nin erişim sırasında gerektirdiği CPU zamanı miktarını ele alıyoruz. MPHF, her anahtar için üç evrensel hash fonksiyonunun hesaplanmasını ve üç bellek erişimini gerektirir (bkz. Denklem (1), (2) ve (3)). Bu optimal değildir.

Pagh [16], herhangi bir MPHF'nin en az iki evrensel hash fonksiyonunun hesaplanmasını ve bir bellek erişimini gerektirdiğini göstermiştir. Bununla birlikte, algoritmamız literatürde milyarlar mertebesindeki anahtarlarla problemleri çözebilen ilk algoritmadır.

5.4 MPHF Tanımının Boyutu

Algoritma tarafından üretilen MPHF'yi depolamak için gereken bit sayısı Denklem (5) ile hesaplanır. Denklem (3)'te sunulan gᵢ vektörlerinin her birini saklamamız gerekir; burada 0 ≤ i < ⌈n/b⌉. Her bucket en fazla 256 anahtar içerdiğinden, bir gᵢ vektöründeki her giriş 8 bittir.

Her gᵢ vektöründe c × size[i] adet giriş vardır (hatırlayalım ki c ∈ [0.93, 1.15]). ⌈n/b⌉ adet gᵢ vektöründeki giriş sayısını topladığımızda:

c ∑_{i=0}^{⌈n/b⌉−1} size[i] = cn

giriş elde ederiz.

Ayrıca ⌈n/b⌉ adet size vektörü için 8 bitlik girişleri saklamamız gerekir. Bunun yanında, sırasıyla offset vektörünü ve h₁ᵢ ile h₂ᵢ'nin iki rastgele tohumunu ifade eden log₂ n bit uzunluğunda 3⌈n/b⌉ adet tam sayı saklamamız gerekir.

Dolayısıyla:

Required Space = 8cn + (n / b)(3 log₂ n + 8) bits.
(5)

c = 0.93 ve b = 175 dikkate alındığında, 1 milyar anahtar içeren bir küme için ortaya çıkan MPHF'nin tanımını saklamak için anahtar başına bit sayısı 8.1'dir. b = 128 seçilirse, anahtar başına bit oranı 8.3'e yükselir.

Teorik olarak, Denklem (5)'te MPHF'yi saklamak için gereken bit sayısı n → ∞ iken O(n log n) olur. Ancak boyutu 2^{b/3} anahtara kadar olan kümeler için anahtar başına bit sayısı 9 bit'ten küçüktür (dikkat edin ki b = 175 için 2^{b/3} > 2^{58} > 10^{17}). Dolayısıyla pratikte ortaya çıkan fonksiyon O(n) bit içinde saklanır.

6 Deneysel Sonuçlar

Bu bölümde deneysel sonuçları sunuyoruz. Önce deneysel kurulum açıklanır. Ardından iç bellek tabanlı algoritma [2] ve bizim algoritmamız için deneysel sonuçlar sunulur. Son olarak, mevcut iç bellek miktarının algoritmamızın çalışma süresini nasıl etkilediği tartışılır.

6.1 Veri ve Deneysel Kurulum

Algoritmalar C dili ile gerçekleştirilmiştir ve şu adreste mevcuttur:

http://cmph.sf.net

GNU Lesser General Public License (LGPL) altında yayımlanmıştır.

Tüm deneyler Linux işletim sistemi (sürüm 2.6) çalıştıran, 2.4 gigahertz işlemciye ve 1 gigabayt ana belleğe sahip bir bilgisayarda gerçekleştirilmiştir. Yeni algoritmayla ilgili deneylerde ana bellek 500 megabayt ile sınırlandırılmıştır.

Verilerimiz, Web'den toplanmış 1 milyar URL içeren bir koleksiyondan oluşmaktadır; her URL'nin ortalama uzunluğu 64 karakterdir. Koleksiyon disk üzerinde 60.5 gigabayt yer kaplamaktadır.

6.2 İç Bellek Tabanlı Algoritmanın Performansı

[2]'de sunulan üç adımlı iç bellek tabanlı algoritmamız, her bucket için bir MPHF oluşturmak amacıyla kullanılır. İlk adımında basit bir rastgele graf üretmesi gerektiğinden rastgeleleştirilmiş bir algoritmadır. Graf elde edildikten sonra diğer iki adım deterministiktir.

Dolayısıyla algoritmanın çalışma süresini n anahtar içeren bir girdi için αnZ biçiminde düşünebiliriz; burada α, anahtar uzunluğuna da bağlı olan makineye özgü bir sabittir ve Z, ortalaması şu olan geometrik dağılımlı bir rastgele değişkendir:

1/p = e^{1/c²}

(bkz. Bölüm 4.2.2).

Deneylerimizde tüm sonuçlar c = 1 alınarak elde edilmiştir; aslında c ∈ [0.93, 1.15] aralığındaki c değerinin çalışma süresi üzerinde çok az etkisi vardır; bu durum [2]'de gösterilmiştir.

n için seçilen değerler 1, 2, 4, 8, 16 ve 32 milyondur.

1 milyar URL içeren bir veri kümemiz olmasına rağmen, 1 gigabayt ana belleğe sahip bir PC üzerinde algoritma en fazla 32 milyon anahtar içeren bir girdiyle çalışabilir. Bunun temel nedeni ana bellekte tutmamız gereken graf yapısıdır.

Algoritma bir MPHF oluşturmak için 25n + O(1) bayt gerektirir (algoritma tarafından kullanılan veri yapılarıyla ilgili ayrıntılar http://cmph.sf.net adresinde bulunabilir).

Her n değeri için deneme sayısını tahmin etmek amacıyla uygun örneklem büyüklüğünü belirleyen istatistiksel bir yöntem kullandık (bkz. örn. [11, Bölüm 13]). Her n için farklı değerler elde ettiğimizden, %95 güven düzeyi sağlamak için elde edilen en büyük değeri, yani 300 denemeyi, kullandık.

Tablo 3, her n için ortalama çalışma süresini, karşılık gelen standart sapmaları ve %95 güven düzeyi dikkate alınarak ortalama süre ± ortalamadan uzaklık şeklinde verilen güven aralıklarını göstermektedir.

Çalışma süresi ortalamalarına bakıldığında algoritmanın [2]'de gösterildiği gibi beklenen doğrusal zamanda çalıştığı görülür.

Şekil 7 her deneme için çalışma süresini göstermektedir. Ayrıca düz çizgi, deneysel ölçümlerden elde edilen bir doğrusal regresyon modelini temsil eder. Görüldüğü gibi belirli bir n için çalışma süresinde önemli dalgalanmalar vardır. Ancak bu dalgalanma da n ile doğrusal olarak artar.

Çalışma sürelerindeki gözlenen dalgalanma beklendiği gibidir. Bu çalışma süresinin Z ortalaması 1/p = e olan geometrik dağılımlı bir rastgele değişken olmak üzere αnZ biçiminde olduğunu hatırlayın. Dolayısıyla çalışma süresinin ortalaması αn/p = αen olur ve standart sapması:

αn √((1 − p) / p²) = αn √(e(e − 1))

şeklindedir.

Dolayısıyla standart sapma da n ile doğrusal olarak artar; bu durum Tablo 3 ve Şekil 7'de deneysel olarak doğrulanmıştır.

6.3 Yeni Algoritmanın Performansı

Algoritmamızın çalışma süresi de bir rastgele değişkendir, ancak şimdi bu süre (yüksek derecede yoğunlaşmış) normal dağılımı izlemektedir; bunu bu bölümün sonunda ele alıyoruz.

Yine, Bölüm 5.1’de ortaya konan doğrusallık iddiasını doğrulamakla ilgileniyoruz. Bu nedenle, S içindeki anahtar sayısı n için çeşitli değerlerle algoritmayı çalıştırdık.

n için seçilen değerler 1, 2, 4, 8, 16, 32, 64, 128, 512 ve 1000 milyon idi.

Deneyler için ana belleği 500 megabayt ile sınırladık. A priori olarak ayrılan iç bellek alanının boyutu µ 250 megabayt olarak ayarlandı, b parametresi 175 olarak belirlendi ve yapı taşı algoritma parametresi c yine 1 olarak ayarlandı.

Bölüm 6.4’te µ’nün algoritmanın çalışma süresini nasıl etkilediğini gösteriyoruz. Diğer iki parametrenin çalışma süresi üzerinde önemsiz bir etkisi vardır.

Her n değeri için çalıştırılacak deneme sayısını tahmin etmek amacıyla uygun bir örneklem büyüklüğünü belirlemek için yine istatistiksel bir yöntem kullandık. %95 güven düzeyi ile her n için yalnızca bir denemenin yeterli olacağını elde ettik. Bununla birlikte, 10 deneme yaptık.

Bu deneme sayısı oldukça küçük görünebilir; ancak aşağıda gösterildiği gibi algoritmamızın davranışı çok kararlıdır ve çalışma süresi neredeyse deterministiktir (yani standart sapma çok küçüktür).

Tablo 4, her n için ortalama çalışma süresini, ilgili standart sapmaları ve %95 güven düzeyi dikkate alınarak ortalama süre ± ortalama süreden sapma mesafesi olarak verilen güven aralıklarını sunmaktadır.

Çalışma süresi ortalamalarını gözlemlediğimizde algoritmanın, Bölüm 5.1’de gösterildiği gibi beklenen doğrusal zamanda çalıştığını fark ettik. Daha da iyisi, yalnızca iç bellek tabanlı algoritmamızdan yaklaşık %60 daha yavaştır.

Bu değeri elde etmek için iç bellek tabanlı algoritmanın çalışma süresi için elde edilen doğrusal regresyon modelini kullandık ve 1 milyar anahtardan oluşan bir küme için bir MPHF oluşturmanın ne kadar zaman gerektireceğini tahmin ettik. İç bellek tabanlı algoritma için 2.3 saat elde ettik ve algoritmamız için ortalama 3.67 saat ölçtük.

İç bellek alanının boyutunu 250 megabayttan 600 megabayta çıkardığımızda (bkz. Bölüm 6.4), süreyi 3.09 saate düşürdük. Bu durumda algoritmamız bu kurulumda yalnızca %34 daha yavaştır.

Şekil 8, her deneme için çalışma süresini sunmaktadır. Düz çizgi, deneysel ölçümlerden elde edilen bir doğrusal regresyon modeline karşılık gelmektedir. Beklendiği gibi, belirli bir n için çalışma süresinde neredeyse hiçbir değişim yoktur.

İlginç bir gözlem, yapı taşı olarak çalışma süresinde önemli dalgalanmalar bulunan bir algoritma kullanmasına rağmen algoritmanın çalışma süresinin neredeyse deterministik olmasıdır.

Belirli bir i kovası, 0 ≤ i < ⌈n/b⌉, küçük bir anahtar kümesidir (en fazla 256 anahtar) ve Bölüm 6.2’de tartışıldığı gibi yapı taşı algoritmanın çalışma süresi yüksek dalgalanmaya sahip bir Xᵢ rastgele değişkenidir.

Bununla birlikte algoritmamızın arama adımının çalışma süresi Y şu şekilde verilir:

Y = ∑_{0 ≤ i < ⌈n/b⌉} Xᵢ

Xᵢ değişkenlerinin bağımsız ve sınırlı olduğu varsayımı altında, büyük sayılar yasası (bkz. örn. [11]) rastgele değişken Y / ⌈n/b⌉’nin n → ∞ iken bir sabite yakınsadığını ifade eder.

Bu durum, algoritmamızın çalışma süresinin neden neredeyse deterministik olduğunu açıklar.

6.4 Disk Erişimlerinin Kontrolü

Disk üzerindeki arama (seek) işlemlerinin sayısını azaltmak için algoritmamızın ana belleğin neredeyse tamamını disk G/Ç tamponu olarak kullanılabilir bırakmasından yararlanıyoruz.

Bu bölümde µ parametresinin algoritmamızın çalışma süresini ne ölçüde etkilediğini değerlendiriyoruz. Bunun için n = 1 milyar URL sabitlendi, deneylerde kullanılan makinenin ana belleği 1 gigabayt olarak ayarlandı ve µ = 100, 200, 300, 400, 500 ve 600 megabayt değerleri kullanıldı.

Tablo 5 aşağıdakileri sunmaktadır:

• dosya sayısı N
• tüm dosyalar için kullanılan tampon boyutu
• en kötü durumda arama (seek) sayısı (Bölüm 5.1’de belirtilen kötümser varsayım dikkate alınarak)
• mevcut iç bellek miktarının bir fonksiyonu olarak 1 milyar anahtar için bir MPHF üretme süresi

Tablo 5 incelendiğinde µ değeri arttıkça oluşturma süresinin azaldığını fark ettik. Ancak µ > 400 için süre değişimi, µ ≤ 400 durumuna kıyasla o kadar belirgin değildir.

Bu durum, Linux 2.6 çekirdeği G/Ç zamanlayıcısının arama işlemlerini önlemek ve ortalama arama süresini azaltmak için akıllı politikalara sahip olmasıyla açıklanabilir.

7. Sonuç Notları

Bu makale, milyarlarca anahtar mertebesindeki kümeler için çalışan, MPHF oluşturmak amacıyla kullanılan yeni bir dış bellek tabanlı algoritma sunmuştur.

Algoritma ortaya çıkan fonksiyonu O(n) zamanında üretir ve ayrıca literatürde MPHF oluşturmak için mevcut en hızlı algoritmadan [2] (kurulumumuzda) yalnızca %34 daha yavaş çalışacak şekilde ayarlanabilir.

Buna ek olarak, elde edilen MPHF’nin alan gereksinimi anahtar başına en fazla 9 bit olup 2⁵⁸ ≈ 10¹⁷·⁴ anahtara kadar olan veri kümeleri için geçerlidir.

Algoritma basittir ve ortalama 64 bayt uzunluğunda olan 1 milyar URL’den oluşan bir koleksiyon için bir MPHF oluşturmak amacıyla ana bellekte yalnızca yaklaşık 5.45 megabayt boyutunda küçük bir vektöre ihtiyaç duyar. Dolayısıyla ana belleğin neredeyse tamamı disk G/Ç tamponu olarak kullanılabilir.

Böyle bir tamponlama düzeninden yararlanarak algoritmamız sıradan bir kişisel bilgisayar kullanarak yaklaşık 3 saat içinde 1 milyar anahtardan oluşan bir küme için bir MPHF üretebilir.

Herhangi bir anahtar için ortaya çıkan MPHF’nin değerlendirilmesi üç bellek erişimi ve üç evrensel hash fonksiyonunun hesaplanmasını gerektirir.

Gelecekteki çalışmalarda arama adımının özünde yüksek derecede paralellik barındırdığı ve oluşturma süresinin %73’ünü gerektirdiği gerçeğinden yararlanacağız. Bu nedenle algoritmamızın paralel bir uygulaması, ortaya çıkan fonksiyonun paralel olarak değerlendirilmesine olanak tanıyacak ve aynı zamanda yüzlerce milyar anahtardan oluşan kümelere ölçeklenebilecektir.

Kaynaklar

[7] E. Drinea, A. Frieze ve M. Mitzenmacher. Balls and bins models with feedback. Symposium on Discrete Algorithms (ACM SODA), sayfalar 308–315, 2002.

[8] E. Fox, Q. Chen ve L. Heath. Minimal perfect hash fonksiyonları oluşturmak için daha hızlı bir algoritma. Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, sayfalar 266–273, 1992.

[9] E. Fox, L. S. Heath, Q. Chen ve A. Daoud. Büyük veritabanları için pratik minimal perfect hash fonksiyonları. Communications of the ACM, 35(1):105–121, 1992.

[10] M. L. Fredman, J. Komlós ve E. Szemerédi. O(1) en kötü durum erişim süresi ile seyrek bir tabloyu saklamak. Journal of the ACM, 31(3):538–544, Temmuz 1984.

[11] R. Jain. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. John Wiley, birinci baskı, 1991.

[12] S. Janson, T. Łuczak ve A. Ruciński. Random Graphs. Wiley‑Inter., 2000.

[13] B. Jenkins. Algorithm alley: Hash functions. Dr. Dobb’s Journal of Software Tools, 22(9), Eylül 1997.

[14] D. E. Knuth. The Art of Computer Programming: Sorting and Searching, Cilt 3. Addison‑Wesley, ikinci baskı, 1973.

[15] K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. Springer‑Verlag, 1984.

[16] R. Pagh. Hash and displace: Minimal perfect hash fonksiyonlarının verimli değerlendirilmesi. Workshop on Algorithms and Data Structures, sayfalar 49–54, 1999.

[17] B. Pittel ve N. C. Wormald. Counting connected graphs inside‑out. Journal of Combinatorial Theory Series B, 93(2):127–172, 2005.

[18] M. Raab ve A. Steger. "Balls into bins" — Basit ve sıkı bir analiz. Lecture Notes in Computer Science, 1518:159–170, 1998.

[19] M. Seltzer. İlişkisel veritabanlarının ötesi. ACM Queue, 3(3), Nisan 2005.

8. Kaynaklar

1. B. Bollobás. Random Graphs, Cambridge Studies in Advanced Mathematics serisinin 73. cildi. Cambridge University Press, Cambridge, ikinci baskı, 2001.

2. F. Botelho, Y. Kohayakawa ve N. Ziviani. Pratik bir minimal perfect hashing yöntemi. 4th International Workshop on Efficient and Experimental Algorithms içinde, sayfalar 488–500. Springer Lecture Notes in Computer Science, cilt 3503, 2005.

3. S. Brin ve L. Page. Büyük ölçekli hiper metinsel bir web arama motorunun anatomisi. Proceedings of the 7th International World Wide Web Conference içinde, sayfalar 107–117, Nisan 1998.

4. Z. Czech, G. Havas ve B. Majewski. Minimal perfect hash fonksiyonları üretmek için optimal bir algoritma. Information Processing Letters, 43(5):257–264, 1992.

5. Z. Czech, G. Havas ve B. Majewski. Perfect hashing üzerine temel bir çalışma. Theoretical Computer Science, 182:1–143, 1997.

6. M. Dietzfelbinger ve T. Hagerup. Daha az alan kullanarak basit minimal perfect hashing. The 9th European Symposium on Algorithms (ESA) içinde, cilt 2161