Monoton Minimal Mükemmel Hashleme: O(1) Erişim ile Sıralı Bir Tabloda Arama

Djamal Belazzougui*
Paolo Boldi†
Rasmus Pagh‡
Sebastiano Vigna†

Özet

Minimal mükemmel bir hash fonksiyonu, S kümesindeki n anahtarı {0, 1, ..., n − 1} kümesine birebir eşler. Klasik sonuçlar, minimal mükemmel hashlemenin sabit zamanda ve eleman başına log e bitlik alt sınıra yakın yer kaplayan bir yapı kullanılarak mümkün olduğunu belirtir. Burada monoton minimal mükemmel hashleme problemini ele alıyoruz; bu durumda birebir eşlemenin anahtarların sözlüksel sıralamasını koruması gerekir.

Bir monoton minimal mükemmel hash fonksiyonu, yalnızca S kümesi üzerinde sıralama sağlayan (ve S dışında rastgele yanıtlar döndüren) çok zayıf bir indeks biçimi olarak görülebilir. Amacımız hash fonksiyonunun tanım boyutunu en aza indirmektir: 2^w elemanlı bir evrenden n eleman içeren bir S kümesi için O(n log log w) bitin O(log w) değerlendirme süresiyle monoton hashleme için yeterli olduğunu gösteriyoruz. Alternatif olarak, O(1) sorgu süresiyle O(n log w) bitlik alan elde edilebilir. Bu veri yapılarının her ikisi de O(n log w) alan ve O(log w) sorgu süresine sahip basit bir yapıyı geliştirir.

Bunun bir sonucu olarak, sıralı bir tabloda O(1) tablo erişimiyle arama yapmak mümkündür (ek olarak O(n log log w) bit kullanarak). Sonuçlarımız, bir trie yapısını oldukça kompakt biçimde temsil eden ancak hata kabul edebilen bir yapıya (bağımsız olarak da ilgi çekici) dayanmaktadır.

Aynı yapının ek bir uygulaması olarak, rastgele bir elemanın öncülünü (S’nin sıralı düzeninde) nasıl hesaplayacağımızı gösteriyoruz; bunun için beklenen değerde O(1) erişim ve O(n log w) bitlik bir indeks kullanılır; bu da O(nw) bitlik basit sonucu geliştirir. Bu durum, bloklanmış bellekte arama için verimli bir indeks anlamına gelir.

Bu makale, iki araştırma akımının kesişiminde yer alan bir dizi problemi ele almaktadır: minimal mükemmel hash fonksiyonlarının incelenmesi ve indeksleme yapılarının analizi.

1 Giriş

Minimal mükemmel bir hash fonksiyonu, S kümesindeki n anahtarı {0, 1, ..., n − 1} kümesine birebir eşler. Bu tür fonksiyonların oluşturulması son yıllarda geniş biçimde incelenmiş ve [12, 13, 15] gibi temel kuramsal sonuçlara ulaşılmıştır.

Uygulama odaklı bir bakış açısından, sıralamayı koruyan minimal mükemmel hash fonksiyonları bir anahtarın belirli bir anahtar listesi içindeki konumunu elde etmek için kullanılmıştır [11, 20]. Bu görev için mevcut tüm tekniklerin anahtarların herhangi bir sırada verilebileceğini varsaydığını gözlemleyerek başlıyoruz; bu durum fonksiyonun saklanması için gerekli bit sayısında kaçınılmaz bir Ω(n log n) alt sınırına yol açar.

Ancak çok sık olarak hashlenmesi gereken anahtarlar kendi içsel (yani sözlüksel) sıralarına göre zaten sıralıdır. Bu durum genellikle arama motorlarının sözlükleri, web grafiklerinin URL listeleri vb. için geçerlidir. Sözlüksel olarak sıralı bir kümenin her anahtarını sıra numarasına eşleme problemine monoton minimal mükemmel hashleme adını veriyoruz.

Bu problem, bildiğimiz kadarıyla literatürde herhangi bir ilgi görmemiştir. Ancak kısa süre içinde açıklayacağımız gibi, diğer klasik problemlerle sıkı bir ilişkiye sahiptir. Bir bakıma sıralama işleminin çok zayıf bir biçimidir: örneğin S kümesi üzerinde kısmi sıralama, S içindeki bir x elemanının sözlüksel konumunu döndüren fakat x S içinde değilse −1 döndüren bir fonksiyonla verilir. Buna karşılık monoton minimal mükemmel hash fonksiyonu, S içinde olmayan elemanlar için herhangi bir sonuç döndürebilir.

Klasik bir makalede Yao [27], eğer sıralı bir evrenden gelen n > 2 anahtarlı bir tabloya ek alan kullanılmazsa ve evren u yeterince büyükse, tablonun herhangi bir düzenlenmesinin en kötü durumda log(n + 1) arama süresi gerektirdiğini göstermiştir. Özellikle tabloyu sıralamak mümkün olan en iyi arama süresini verir. Bu alt sınır yalnızca üyelik sorgularıyla (“x tabloda var mı?”) ilgilenildiğinde bile geçerlidir ve işaretçiler ile tekrar eden anahtarların bulunduğu n^{O(1)} alanlı daha genel veri yapılarına da genişletilebilir.

Bir dizi araştırmacı, Yao’nun alt sınırını aşmak için gereken ek alan miktarını incelemiş ve üyelik sorgularını O(1) tablo erişimiyle sağlayan hashleme teknikleri kullanmıştır [9, 10, 25]. Ancak bu şemalar aralık sorgularını (“[ℓ .. r] aralığındaki anahtarlar hangileridir?”) desteklemez; yalnızca üyelik sorgularına indirgenen ve aralık boyutunda doğrusal zaman gerektiren basit yöntem kullanılabilir.

Burada tablonun sıralı olduğu senaryoyu ele alıyor ve şu soruyu soruyoruz: beklenen değerde O(1) erişimle tabloda arama yapmayı mümkün kılan indeks yapılarının alan kullanımı nedir? Bir anahtar x için iki tür arama ele alıyoruz:

1. x’in tablodaki konumunun bulunması veya tabloda olmadığının bildirilmesi gereken üyelik aramaları.

İkinci tür arama, verimli aralık sorgularını doğrudan mümkün kılar: ℓ’nin öncülünü bul ve r’den büyük bir anahtar bulunana kadar tabloyu tara. Bu tür tarama disklerde ve modern bloklu bellek mimarilerinde oldukça verimlidir. Nitekim aralık sorgularına ilişkin son çalışmaların birçoğu, anahtarları normal bir arama ağacı yerine (boşluklar içeren) sıralı bir tabloda tutmayı önermektedir; bunun nedeni tam olarak budur [24, 2, 1]. (Bu çalışmaların anahtar kümesinin değiştiği dinamik durumla ilgilendiğini, bizim ise yalnızca statik durumu ele aldığımızı belirtelim.)

Birinci tür arama nokta sorgularına izin verir, fakat aynı zamanda özel bir tür aralık sorgusunu da mümkün kılar: aralık içinde herhangi bir elemanı biliyorsak, onun konumu O(1) erişimle bulunabilir ve ardından aralıktaki tüm elemanları raporlamak kolaydır. Bu durum örneğin veritabanı uygulamalarında anlamlı olabilir; burada referans bütünlüğü kısıtları bir ilişkideki elemanların başka bir ilişkide de bulunduğunu garanti eder.

Sonuçlarımız

Evrensel kümenin boyutunun 2^w olduğunu ve n ≥ log w olduğunu varsayalım. Genelliği bozmadan w’nin iki kuvveti olduğunu kabul ediyoruz (değilse yukarı yuvarlanır). Hesaplama modelimiz kelime boyutu w olan birim maliyetli word RAM modelidir.

Boyutu O(n log log w) bit ve sorgu süresi O(log w) olan bir monoton minimal mükemmel hash fonksiyonu ve boyutu O(n log w) bit olup sabit sorgu süresine sahip bir başka fonksiyon tanımlıyoruz. Her iki durumda da bu, sıralı bir tabloda bir elemanı yalnızca tek bir tablo erişimiyle bulabileceğimiz anlamına gelir.

Her iki yapı da anahtar kümesini O(k) boyutlu O(n/k) adet sıralı gruba ayırmanın yeni yollarına dayanır. Bu yaklaşım, her k’inci anahtarı açıkça bir öncül veri yapısında saklayan klasik çözümün (ör. [26]) alan ve zaman maliyetlerini iyileştirir. Kümenin sıralı biçimde saklanması gerekmese bile Ω(n) bitin bir alt sınır olduğu bilinmektedir [21]; dolayısıyla bu sonuçlar (en azından) en iyi olası sonuçlara yakındır.

Üyelik araması için daha alan verimli çözümdeki ana araç, yaklaşık bir trie temsilidir. Bu yapı, n anahtarlı bir S kümesini O(n log w) alanda saklamamızı sağlar; öyle ki herhangi bir y elemanı için S’ye göre sırası yaklaşık olarak şu anlamda belirlenebilir: veri yapısı {0, 1, ..., n} kümesinden iki tamsayı döndürür ve olasılığı 1 − 1/w olacak şekilde bunlardan biri y’nin öncülünün konumudur.

Bu veri yapısı, z-fast trie adını verdiğimiz yeni bir van Emde Boas ağacı benzeri veri yapısının yaklaşık bir sürümüdür (adı, y-fast trie’lerle [26] olan ilişkisine gönderme yapar).

Yaklaşık trie sonucumuzun bağımsız olarak da ilgi çekici olduğuna inanıyoruz ve iki olası öncülün paralel olarak aranabildiği ortamlarda potansiyel uygulamalar bulabilir (örneğin yönlendirme için donanımsal çözümlerde ve paralel disk sistemlerindeki B-ağaçlarında).

Ayrıca yaklaşık trie temsilinin aşağıdaki anlamda en iyiye yakın olduğunu gösteren bir alt sınır da sunuyoruz: evrendeki her elemanın doğru sırasını olasılığı 1/2’den büyük olacak şekilde belirleyen her veri yapısı, S’nin kendisini saklamak için gereken alana yakın bir alan kullanmak zorundadır. Bizim veri yapımız sıralamayı 1/2’nin biraz altında bir olasılıkla belirlemeye izin verir.

Bu makalede sunulan veri yapılarının bir uygulaması Sux4J projesinin bir parçası olarak GNU LGPL altında dağıtılmaktadır (http://sux4j.dsi.unimi.it/). Yaklaşan bir makalede uygulama sorunlarını ve algoritmalarımızın pratik davranışını ayrıntılı biçimde inceliyoruz.

İlgili Çalışmalar

Mehlhorn [21], minimal mükemmel hashlemenin Ω(n + log w) bit alan gerektirdiğini göstermiştir. Bu alt sınır, fonksiyon aralığının tam olarak n yerine O(n) boyutunda olduğu ve h’nin birebir olmasının gerektiği daha genel durumda da geçerlidir.

Minimal mükemmel bir hash fonksiyonunu temsil eden ve O(1) değerlendirme süresine sahip özlü bir veri yapısı Hagerup ve Tholey [15] tarafından geliştirilmiştir.

Schmidt ve Siegel [25], hash fonksiyonu h’nin {0, ..., n − 1} kümesinden en fazla k değer içeren bir küme döndürdüğü mükemmel hashlemenin bir genellemesini ele almıştır. Gereksinim, S ile {0, ..., n − 1} arasında bir eşleme bulunmasıdır; öyle ki her x ∈ S anahtarı h(x)’in bir elemanıyla eşleşsin. k sabit olduğunda bile bu durum hâlâ Ω(n) bit alan gerektirir. Özellikle O(n e^{-k} + log log m) ve Ω((n/k^2)e^{-k} + log log m) bitlik üst ve alt sınırlar gösterilmiştir.

Mairson [18, 19], minimal mükemmel hashlemenin ilgili bir genellemesini incelemiştir; burada aralık k boyutlu “sayfalara” bölünür ve bir anahtar için k olası konum her zaman tek bir sayfanın konumlarıdır. Başka bir deyişle, S kümesindeki en fazla k anahtar tek bir sayfaya eşlenmelidir. Mairson, bu problem için Ω(n log(k)/k) bitin hem gerekli hem yeterli olduğunu göstermiştir.

Ortalama olarak yalnızca Θ(k) anahtar içeren sayfalara izin vermek de yardımcı olmaz: bu durumda da Ω(n log(k)/k) alt sınırı vardır [19]. Tüm bu sonuçlar n’in k’nin bir fonksiyonuyla sınırlı olmadığı durum içindir; gerçekten de k = ω(log n) olduğunda “sayfalı” bir mükemmel hash fonksiyonu yalnızca O(log n + log w) bit alan gerektirir.

Fiat ve arkadaşları [10], S kümesinin herhangi bir permütasyonu olarak düzenlenebilen bir tabloda arama problemini incelemiştir. Sabit zamanlı üyelik araması elde etmek için O(log n + log w) bit ek depolamanın yeterli olduğunu göstermişlerdir. Yazarların bir alt kümesi daha sonra [9], yapıcı olmayan bir argümanla teoride O(log w) ek bitin yeterli olduğunu göstermiştir. Bu yöntemler bilgilerin eleman permütasyonları olarak kodlanabilmesi gerçeğinden yararlanır; bu ise bizim bağlamımızda mümkün değildir.

Kümeler ve Tamsayılar

Doğal sayılar için von Neumann’ın tanımını ve gösterimini kullanıyoruz: n = {0, 1, ..., n − 1}. Bu nedenle m ilk doğal sayısından n ilk doğal sayısına bir fonksiyon için serbestçe f : m → n yazabiliriz. Gerçek sayılar için de aynı yaklaşımı, küçük bir gösterim esnekliğiyle ve tavan operatörünün anlaşılacağı varsayımıyla kullanıyoruz.

Aşağıda, bir evren elemanı x’in x’ten büyük olmayan en büyük anahtarın konumunu döndürdüğünü varsayacağız.

Şekil 1

Bir oyuncak örnek: S = {s0, ..., s10} kümesi üç elemanlı üç kovaya ayrılmıştır (son kova yalnızca iki eleman içerir); ayraçları D = {s2, s5, s8} olan elemanlar kalın yazılmıştır.

u = 2^w sabittir.

u kümesinin doğal bir sıralaması vardır; bu sıralama w bitlik sola sıfır doldurulmuş ikili gösterimin dizge sözlüksel sırasına karşılık gelir. Basitlik adına w’nin iki kuvveti olduğunu varsayıyoruz.

|S| = n olan S ⊆ u verildiğinde ve m verildiğinde, S için m-kovalı bir hash fonksiyonu h : S → m olan herhangi bir fonksiyondur. h’nin mükemmel olduğunu, eğer birebir ise; minimal mükemmel olduğunu, eğer birebir ve n = m ise; monoton olduğunu ise S içindeki tüm x, y için x ≤ y ise h(x) ≤ h(y) olduğunda söyleriz.

Rank ve Select

Birçok özlü veri yapısının iki temel yapı taşını — rank ve select — yoğun biçimde kullanacağız.

b ∈ {0, 1}^n olan bir bit dizisi (veya bit dizgesi) verildiğinde ve konumlar 0’dan başlayarak numaralandırıldığında:

• rank_b(p), p konumuna kadar (hariç) olan birlerin sayısıdır (0 ≤ p ≤ n).
• select_b(r), b içindeki r’inci bir bitin konumudur; bitler 0’dan başlayarak numaralandırılır (0 ≤ r < rank_b(n)).

Bu işlemler, n bitlik bir dizge üzerinde ek o(n) bit kullanılarak sabit zamanda gerçekleştirilebilir [16, 6]. Bağlamdan b açıkça anlaşılıyorsa alt simgeyi kullanmayacağız.

Fonksiyonların Saklanması

Makalenin geri kalanında sık sık bir anahtar kümesi S ile değerler ilişkilendirmemiz gerekecektir; daha açık ifadeyle r bitlik bir f : S → 2^r fonksiyonunu statik olarak saklamamız gerekecektir.

Bu problem yakın zamanda yeniden ilgi görmüştür [8, 5, 23]. Ancak bu makalenin amaçları doğrultusunda klasik çözümü kullanıyoruz: S üzerinde minimal mükemmel bir hash fonksiyonu saklamak ve elde edilen değeri bir tabloyu indekslemek için kullanmak.

Örneğin Hagerup ve Tholey’in [15] mükemmel hash fonksiyonunu kullanarak r bitlik bir fonksiyonu rn + O(n + log w) bit alanda ve sabit zamanlı erişimle saklayabiliyoruz.

Bucketing

Şimdi bu makalede kullanacağımız ve bucketing olarak adlandıracağımız monoton minimal mükemmel hashleme için genel bir yaklaşımı kısaca tartışıyoruz. Aynı fikir monoton olmayan mükemmel hashleme için yaygın biçimde kullanılmıştır ve genişletilmesi verimli sonuçlar verir.

S kümesi için minimal mükemmel monoton bir hash fonksiyonu oluşturmak istediğinizi varsayalım; başlangıçta:

• S’yi m kovaya eşleyen monoton bir hash fonksiyonu d : S → m bulunur; buna distributor denir.

Daha sonra

h(x) = s(d(x)) + g_{d(x)}(x)

şeklinde tanımlanan h : S → n fonksiyonu, S için monoton minimal mükemmel bir hash fonksiyonudur.

Bucketing fikrinin arkasındaki düşünce şudur: dağıtıcı az alan kullanacaktır (çünkü minimal olma veya mükemmel olma şartı yoktur) ve her kovadaki elemanları monoton biçimde hashleyen fonksiyonlar, kova boyutu yeterince küçükse az alan kullanacaktır. Eğer d^{-1}(i) kümeleri aynı boyuttaysa s fonksiyonu elbette atlanabilir.

3 En Uzun Ortak Öneklerle Bucketing

İlk monoton minimal mükemmel hash fonksiyonumuz (makalenin geri kalanında da bir yapı taşı olarak kullanılacaktır) en uzun ortak önekler üzerine kuruludur. Bu tekniğin avantajı sabit sayıda hash fonksiyonunun değerlendirilmesini gerektirmesidir; buna karşılık tartıştığımız algoritmalar arasında en yüksek bellek kullanımına sahiptir.

Bölüm 2’de açıklanan bucketing yaklaşımını kullanıyoruz. b pozitif bir tamsayı olsun ve S kümesini sıralamayı koruyarak b boyutlu kovalar hâlinde bölelim.

Başka bir deyişle B₀, B₁, …, B_{m−1} kümeleri aşağıdaki koşulları sağlayan S’nin tekil bölünmesidir:

• m = ⌈n/b⌉
• |B_i| = b tüm i = 0, …, m − 2 için
• eğer x ∈ B_i ve y ∈ B_j ve i < j ise, x < y

Basit bir lemma ile başlıyoruz.

LEMMA 3.1. i = 0, …, m − 1 için p_i, B_i’nin en uzun ortak öneki olsun. O hâlde tüm p_i değerleri birbirinden farklıdır.

Kanıt. Çelişki yoluyla iki en uzun ortak önek p_i ve p_j’nin, j > i olmak üzere, eşit olduğunu varsayalım. Eğer |B_i| = 1 veya |B_j| = 1 ise iki önek açıkça farklıdır.

Aksi takdirde i kovasının ilk ve son anahtarlarını inceleriz. p = p_i = p_j olsun. i kovasının son anahtarının p1 dizgesiyle başladığını ve j kovasının ilk anahtarının p0 dizgesiyle başladığını biliyoruz. Bunun nedeni iki anahtarın en uzun ortak önekten hemen sonraki bitte farklı olması ve son anahtarın sözlüksel olarak ilk anahtardan daha büyük olmasıdır.

Şimdi j kovası da aynı en uzun ortak öneke sahip olduğundan, onun ilk anahtarı da p0 ile başlar. Bu da j kovasının ilk anahtarının, i kovasının son anahtarından (p1 ile başlayan) leksikografik olarak daha küçük olduğu anlamına gelir ve bu bir çelişkiye yol açar.

Dolayısıyla her kovayı, içindeki dizgelerin en uzun ortak öneki ile temsil ederiz. Her dizgeyi ilgili kovasının en uzun ortak öneki ile ilişkilendirmek için şu fonksiyonu saklarız:

d₀ : S → w

Bu fonksiyon, x ∈ S için x’i içeren kovadaki en uzun ortak önekin uzunluğunu atar.

Daha sonra şu fonksiyonu saklarız:

d₁ : {p₀, p₁, …, p_{m−1}} → m

Bu fonksiyon p_i’yi i’ye eşler.

Verilen x ∈ S için d(x) değerini hesaplamak amacıyla önce d₀ uygulanır ve kovasının en uzun ortak önekinin uzunluğu ℓ elde edilir; ℓ değerinden önek hesaplanabilir (x’in ilk ℓ bitinden oluşur) ve son olarak d₁ uygulanarak d(x) elde edilir.

Şekil 2, b = 3 olduğunda Şekil 1’deki örnek için d₀ ve d₁ fonksiyonlarını göstermektedir.

d₀ fonksiyonu O(n log w) bit gerektirir; buna karşılık d₁ fonksiyonu O((n/b) log(n/b) + log w) bit gerektirir; tüm g_i fonksiyonları birlikte O(n log b + log w) bit gerektirir. b = log n seçilirse şu alan sınırı elde edilir:

O(n(log log n + log w)) = O(n log w)

bit ve değerlendirme açıkça sabit zamandadır.

TEOREM 3.1. O(n log w) bit yer kaplayan ve sorgulara sabit zamanda yanıt veren monoton minimal mükemmel bir hash fonksiyonu vardır.

4 Göreli Sıralama ile Kovaya Ayırma

Daha iyi bir alan sınırı ararken, kovaya ayırma probleminin açık bir yaklaşımının sıralama olduğunu fark ederiz. X dizge kümesi verildiğinde, bir sıralama veri yapısı her s ∈ u dizgesi için X içinde s’ten küçük olan dizgelerin sayısını sağlar; yani:

|{ x ∈ X | x < s }|.

Ayırıcılar kümesi D’yi ele alalım; bu küme her kovadaki leksikografik olarak en büyük dizgeden oluşur. Açıkça, herhangi bir dizgenin D’ye göre sırası tam olarak bulunduğu kovanın indeksidir.

Örneğin bu tür sıra bilgisini elde etmenin basit bir yolu, D içindeki dizgeleri içeren bir sıkıştırılmış trie [17] kurmaktır (bkz. Şekil 3). Günümüzde çok daha gelişmiş veri yapıları da mevcuttur (örn. [14]), ancak bizim durumumuzda amaçlarını yerine getiremezler: çok fazla alan kaplarlar ve aslında tüm olası dizgeleri sıralamamız gerekmez — yalnızca S içindeki dizgeleri sıralamamız gerekir.

Bu problemi göreli sıralama problemi olarak adlandırırız: D ⊆ S ⊆ u kümeleri verildiğinde, s ∈ S olduğu koşulu altında bir s dizgesini D’ye göre sıralamak isteriz.

Bu problemi çözmek için kullandığımız fikir, trie tabanlı bir dağıtıcının davranışını taklit etmektir: bilmemiz gereken tek şey, her düğüm ve her anahtar için

• arama sırasında ulaşılan son düğümün hangisi olduğu (çıkış düğümü),
• çıkış düğümünde hangi davranışın gerçekleştiği (soldan mı sağdan mı çıkıldığı), ve
• belirli bir çıkış düğümü ve çıkış davranışı için hangi sıranın karşılık geldiğidir.

Göreceğimiz gibi, bu bilgi çok az alan kullanılarak kodlanabilir.

4.1 Olasılıksal Trie

Bu bölümde hatalara izin veren bir trie’yi çok sıkı biçimde temsil eden bir Monte-Carlo rastgeleleştirilmiş veri yapısı tanıtıyoruz. Bu yapının nasıl çalıştığını açıklamak için önce sıkıştırılmış trie’lerle ilgili bazı gösterimler ve tanımlar sunarız.

Sıkıştırılmış Trie’ler için Gösterim

D ⊆ u kümesi için oluşturulmuş sıkıştırılmış trie’yi ele alalım. Bir α düğümünün temsil ettiği dizge, α kökünden başlayan alt ağaçta saklanan tüm anahtarların en uzun ortak öneki olarak tanımlanır.

Düğümler ile dizgeler arasındaki eşleme bire birdir: bu nedenle bazen bir dizgenin bir düğüm tarafından temsil edildiğini, bazen de düğümün dizgeyi temsil ettiğini söyleyeceğiz.

p dizgesini temsil eden bir α düğümünün atlama aralığı şu şekilde tanımlanır:

• aksi halde, α’nın atlama aralığı [|q| .. |p|) şeklindedir; burada q, α’nın ebeveyninin temsil ettiği dizgedir.

α düğümüne giden yol kök için ε, p’yi temsil eden bir düğümün sol ve sağ çocukları için sırasıyla p0 ve p1 olarak tanımlanır. α’ya giden yolun her zaman α’nın temsil ettiği dizgenin bir öneki olduğuna dikkat edin.

Bir z-fast trie’nin arkasındaki temel fikir şudur: sıkıştırılmış yollar içeren ikili ağaç yapısını açıkça temsil etmek yerine, verilen bir x girdisi için trie’nin bir iç düğümü tarafından temsil edilen ve x’in öneki olan en uzun p dizgesini sağlarız.

Bu p dizgesi, x’in çıkış düğümünün ebeveyni tarafından temsil edilir. Bu noktada x’in |p| indeksindeki bitine bakarak x’in çıkış düğümüne giden kenarı belirleyebiliriz.

TEOREM 4.1. D ⊆ u kümesi için oluşturulmuş sıkıştırılmış trie’yi ele alalım, |D| = m. x ∈ u verildiğinde aşağıdaki özelliklere sahip tek iç düğüm tarafından temsil edilen p dizgesinin uzunluğunu hata olasılığı ε ile döndüren olasılıksal bir veri yapısı vardır:

• p, x’in bir önekidir;
• iç düğümler tarafından temsil edilen diğer her q dizgesi için, q da x’in öneki ise |q| < |p|.

Bu yapı O(m(log w + log(1/ε))) bit alan gerektirir ve sorgu süresi O(log w)’dir.

2-En Şişkin Sayılar

Boş olmayan bir pozitif tam sayı aralığındaki 2-en şişkin sayı, ikili gösteriminde en fazla sondan sıfır bulunan sayıdır.

Olasılıksal trie’yi tanımlamak için 2-en şişkin sayılarla ilgili bazı basit özelliklere ihtiyaç duyarız.

LEMMA 4.1. [x .. y] aralığında pozitif tam sayılar verildiğinde:

1. 2^i b ∈ [x, y] olacak şekilde bir b tam sayısı bulunan en büyük i sayısı olsun. Bu durumda b tektir ve 2^i b sayısı [x .. y] aralığındaki 2-en şişkin sayıdır.

2. Eğer y − x < 2^i ise, 2^i b ∈ [x .. y] olacak en fazla tek bir b değeri vardır.

Olasılıksal bir z-fast trie, aşağıdaki eşlemeyi sağlayan bir T fonksiyonu ile verilir (bkz. Bölüm 2). D üzerinde kurulu sıkıştırılmış trie’nin her α düğümü için:

• p, α tarafından temsil edilen dizge olsun,
• [α_ℓ .. α_r) α’nın atlama aralığı olsun,
• f ise (α_ℓ .. α_r] aralığındaki 2-en şişkin sayı olsun.

Aralık boşsa (bu yalnızca kökte olabilir), f = 0 alınır. Ardından T, p’nin uzunluğu f olan önekini aşağıdaki verilere eşler:

1. p’nin uzunluğu (log w bit);
2. evrensel hashing [3] kullanılarak hesaplanan, uzunluğu log log w + log(1/ε) olan p imzası.

Yukarıdaki fonksiyon O(m(log w + log(1/ε))) bit kullanır. İmzanın özdeşlik fonksiyonu olduğu kesin sürüme z-fast trie adını veririz.

Veri yapısı Algorithm 1’deki gibi sorgulanır. Fikir, x’in trie’den çıktığı noktayı bulmak için bir tür ikili arama gerçekleştirmektir. Geleneksel ikili aramada olduğu gibi aralık uçlarının aritmetik ortalamasına karşı test etmek yerine, aralıktaki 2-en şişkin sayıya karşı test ederiz (şişkin ikili arama). Bu, T’nin aramayı uygun şekilde yönlendirecek bilgiyi içermesini sağlar.

Arama aralığındaki 2-en şişkin sayı uzunluğuna sahip x öneki q’yu T’ye girdi olarak kullanırız. Eğer q, S içindeki bir anahtarın öneki ise, q’nun altındaki dallanma düğümüne karşılık gelen x ile eşleşen daha uzun bir önek olup olmadığını kontrol ederiz. Her iki koşul da sağlanıyorsa alt sınır ℓ güncellenir; aksi halde (imzada yanlış eşleşme olmadığını varsayarak) üst sınır r güncellenir.

Örneğin, Şekil 4’te gösterilen yapıyı Şekil 1’deki s₁ dizgesi ile sorguladığımızda önce T(00100101) hesaplanır; çünkü (0 .. 13) aralığındaki 2-en şişkin sayı 8’dir. İmzanın sorguyu doğru biçimde başarısız olarak tanımladığını varsayarsak, bu kez T(0010) denenir. Bu sefer imza eşleşir ve bize s₁’in çıkış düğümünün ebeveyninin 001001 dizgesini temsil ettiğini söyler. s₁’in bir bitini daha ekleyerek 0010010 dizgesinin s₁’in çıkış düğümüne giden yol olduğunu çıkarırız.

Algoritmanın doğruluğunu ve karmaşıklığını belirlemek için önce bazı ek lemmalara ihtiyaç duyarız.

Lemma 4.2

Algorithm 1 içindeki döngünün her yinelemesinden önce ve sonra aşağıdaki değişmezler geçerlidir:

1. (2^i b ∈ (\ell..r)) olacak en fazla tek bir (b) vardır.
2. (2^{i+1} b ∈ (\ell..r)) olacak hiçbir (b) yoktur.
3. ((\ell..r)) aralığının uzunluğu (2^i)’den küçüktür.

Algorithm 1 — Olasılıksal z-fast trie’nin sorgulanması

((T) fonksiyonu ile temsil edilir)

((2^i b), ((\ell..r)) aralığındaki 2‑en şişkin sayıdır)

girdi x ∈ u
i ← ⌈log w⌉ − 1
ℓ, r ← 0, w

while r − ℓ > 1 do

    if ∃ b such that 2^i b ∈ (ℓ..r) then
        q ← x’in uzunluğu 2^i b olan öneki
        ⟨g, s⟩ ← T(q)

        if g ≤ |x| and s is the signature of the prefix of x of length g then
            ℓ ← g
            { (ℓ..r) aralığından (g..r) aralığına geç }
        else
            r ← 2^i b
            { (ℓ..r) aralığından (ℓ..2^i b) aralığına geç }
        end if
    end if

    i ← i − 1

end while

return ℓ

İspat

(1) Başlangıçta, (i = \log w − 1) iken ((\ell..r) = (0..w)) olur ve bu aralık (2^i b) biçiminde tek bir değer içerir; bu da (w/2)’dir. Şimdi bir yinelemeden sonra (2^i b ∈ (\ell..r)) olacak en fazla tek bir (b) olduğunu varsayalım. İki durum vardır:

• Hiçbir (b) değeri (2^i b ∈ (\ell..r)) koşulunu sağlamaz.
  Bu durumda aralık değişmeden kalır ve Lemma 4.1 (3)’e göre (2^{i−1} b) biçiminde en fazla tek bir değer içerir.

• Tek bir (b) değeri (2^i b ∈ (\ell..r)) koşulunu sağlar. Aralık iki şekilde güncellenebilir: ya aralığı (g ≥ 2^i b) olacak bir (g) için ((g..r)) yaparız ya da ((\ell..2^i b)) yaparız. Her iki durumda da yeni aralık artık (2^i b) değerini içermez. Lemma 4.1’in 3. değişmezine göre yeni aralık (2^{i−1} b) biçiminde en fazla tek bir değer içerir.

(2) Başlangıçta bu açıkça doğrudur çünkü ((0..w)) aralığı (b_w) biçiminde hiçbir değer içermez. (1)’e göre yinelemenin başında ((\ell..r)) aralığında (2^j b) biçiminde en fazla tek bir değer vardır ve bu tek değer yinelemenin sonunda aralıktan kaldırılır.

(3) (1)’dekiyle aynı argümanla aralık (2^i b) biçiminde bir değer içermez. Lemma 4.1 (3) uygulanarak aralığın uzunluğunun en fazla (2^{i−1}) olduğu sonucu çıkar.

Üçüncü değişmez, algoritmanın (i = 0) olduğunda sona ereceğini gösterir. Başlangıçta (i) değeri (\log w − 1) (bir tam sayı) olduğundan ve her yinelemede 1 azaldığından, algoritma hiçbir zaman (\log w − 1) yinelemeden fazla çalışmaz.

Lemma 4.3

Şu küme tanımlansın:

[ X = {x_0 = ε, x_1, …, x_t} ]

Burada (x_1, x_2, …, x_t) trie’deki düğümler tarafından temsil edilen ve (x)’in önekleri olan dizgelerdir; artan uzunluk sırasına göre düzenlenmiştir.

İmza karşılaştırmasında yanlış pozitif olmadığını varsayalım (yani iki dizgenin imzaları eşleşiyorsa dizgeler de eşittir). Algoritma tarafından tutulan aralık ((\ell..r)) olsun.

Her yinelemeden önce ve sonra şu değişmez sağlanır:

[ \ell = |x_j| \text{ olacak şekilde bir } j, \quad \ell ≤ |x_t| < r ]

İspat

Başlangıçta değişmez açıkça doğrudur çünkü başlangıç aralığı ((0..w))’dir. Lemma 4.1 ve Lemma 4.2 (1)’e göre her adımda ya hiçbir şey yapılmaz ya da ((\ell..r)) aralığındaki 2‑en şişkin sayı (g) seçilerek aralık değiştirilir.

İki durum vardır (Algorithm 1’deki gösterime göre):

• Eğer (T(q)) pozitif sonuç verirse, mevcut aralığı ((g..r)) olarak değiştiririz. Uzunluğu (g) olan ve (x)’in öneki olan en az bir dizge bulunduğunu biliriz; dolayısıyla (g = |x_j|) olacak bir (j) vardır ve (g ≤ |x_t|). Değişmez korunur.

• Eğer (T(q)) negatif sonuç verirse, (x)’in (2^i b − 1)’den daha uzun hiçbir önekinin trie’de bir düğüm tarafından temsil edilmediğini biliriz. Aksi halde (2^i b), (X) içindeki bir öğeyi temsil eden bir (α) düğümünün atlama aralığı ([α_ℓ..α_r)) içinde yer alırdı ve ((α_ℓ..α_r]) tamamen ((\ell..r)) içinde olurdu. Böylece (2^i b), ((\ell..r)) içinde 2‑en şişkin olduğundan ((α_ℓ..α_r]) içinde de 2‑en şişkin olurdu ve (T(q)) pozitif sonuç döndürürdü — bu bir çelişkidir.

Dolayısıyla yanlış pozitif yoksa algoritma doğrudur, çünkü sonunda (\ell = |x_t|) elde edilir.

Şimdi algoritmanın hata olasılığının (ε) ile sınırlı olduğunu gösteririz. (T)’yi mükemmel hashing kullanarak sakladığımızdan, (T) tarafından döndürülen imza (T)’nin tanımlı olduğu alandaki bir (p) dizgesinin imzasıdır. Dolayısıyla yanlış eşleşme olasılığı

[ 2^{-\log \log w - \log(1/ε)} = ε / \log w ]

olur.

Algoritma en fazla (\log w) imza karşılaştırması yapar; bu nedenle bir veya daha fazla yanlış pozitif oluşma olasılığı toplamda (ε) ile sınırlıdır. Böylece Teorem 4.1 ispatlanmış olur.

Değişken Uzunluklu Anahtarlar

Algoritmamız değişken uzunluklu anahtarlar için de çalışır. Ancak anahtar uzunluğuna bağlı sorgu süresinin mümkün olan en iyi değeri alması için dikkat edilmelidir.

Sorun şudur: uzunluğu (l) bit olan bir anahtarın hashing işlemi naif şekilde yapılırsa (O(1 + l/w)) zaman alır.

Çözümümüz, her sorguya sorgu anahtarının kelime hizalı her öneki için (O(\log n)) bitlik bir hash değeri hesaplayarak başlamaktır. Bu işlem

[ O(1 + l/w) ]

zamanda yapılabilir; örneğin [7, Bölüm 5]’te açıklanan artımlı hashing yöntemi kullanılarak. Yüksek olasılıkla çakışma olmaz. Önceden hesaplanmış tablo kullanıldığında sonraki hash fonksiyonu değerlendirmeleri sabit zamanda yapılabilir; bu da aramanın kendisinin (O(\log l)) zaman kullanması anlamına gelir.

4.2 Olasılıksal Trie Kullanarak Hatalı Sıralama

Teorem 4.2

D ⊆ u (|D| = m) ve ε > 0 olsun. Her x ∈ u için hata olasılığı ε ile ⟨i, j⟩ biçiminde bir tam sayı çifti döndüren bir veri yapısı vardır; bu iki sayıdan biri x’in D içindeki sırasıdır (yani (|{t ∈ D \mid t < x}| ∈ {i, j})).

Bu veri yapısı

[ O(m(\log w + \log(1/ε))) ]

bit alan kullanır ve sorgu süresi (O(\log w))’dir.

İspat

D üzerinde olasılıksal bir z‑fast trie kurarız ve P kümesini şu şekilde tanımlarız: D için sıkıştırılmış trie’deki her iç düğüme karşılık gelen p dizgesi için P kümesi aşağıdaki uzunluğu w olan bit dizgelerini içerir:

• p0 0^{w-|p|-1}
• p1 0^{w-|p|-1}
• p1 0^{w-|p|-1} + 0^{|p|}1 0^{w-|p|-1} (yalnızca p ≠ 1^w ise)

P üzerinde sabit zamanlı monoton minimal mükemmel bir hash fonksiyonu f kurarız (bkz. Bölüm 3) ve

[ |P| = O(m) ]

boyutunda, sıralama yapısı ile donatılmış bir bit vektörü b tanımlarız; P içindeki ve bir yaprağa giden her x için f(x) konumunda bir bit ayarlanır.

Bu düzen altında, p dizgesi bir iç düğüm α tarafından temsil ediliyorsa:

• b içinde f(p0 0^{w-|p|-1}) değerinin sıralaması, p0 ile başlayan her dizgeden küçük olan D elemanlarının sayısını verir;
• f(p1 0^{w-|p|-1}) değerinin sıralaması, p1 ile başlayan her dizgeden küçük olan D elemanlarının sayısını verir;
• p1 0^{w-|p|-1} + 0^{|p|}1 0^{w-|p|-1} değerinin sıralaması, p1 ile başlayan veya p1’den küçük olan D elemanlarının sayısını verir.

Dolayısıyla x ∈ u girdisi için doğru sonucu döndürmek amacıyla önce olasılıksal trie’yi sorgular ve bir p dizgesinin uzunluğunu elde ederiz. Daha sonra x’in |p| indeksindeki bitine bakarız:

• Eğer 0 ise şu değeri döndürürüz

  [ ⟨rank_b(f(p0 0^{w-|p|-1})), rank_b(f(p1 0^{w-|p|}))⟩ ]

• Eğer 1 ise ve p ≠ 1^w ise, döndürürüz

[ ⟨rank_b(f(p1 0^{w-|p|-1})), rank_b(f(p1 0^{w-|p|-1} + 0^{|p|}1 0^{w-|p|-1}))⟩ ]

• Aksi halde döndür

  [ ⟨rank_b(f(p1 0^{w-|p|-1})), m⟩ ]

Her iki durumda da, ilk veya ikinci cevap, (x)’in (α)’nın solundan mı yoksa sağından mı çıktığına bağlı olarak doğrudur.

4.3 Hatalarla Sıralama için Bir Alt Sınır

Teorem 4.2, (m) elemanlı bir kümeye göre sıralama yapabilen ve başarı olasılığı (1/2 − ε) olan bir veri yapısının var olduğunu, bunun da

[ O(m(\log w + \log(1/ε))) ]

bit alan gerektirdiğini ve çalışma süresinin (O(\log w)) olduğunu ifade edecek şekilde yorumlanabilir.

Bu durum, aşağıdaki alt sınır ile karşılaştırılmalıdır.

Teorem 4.3

(D ⊆ u) ve (|D| = m ≤ 2^w / 3) olsun ve (ε < 1/2 − Ω(1)) olsun. (D)’yi sıralayan (yani (x ∈ u) verildiğinde (|{s ∈ D \mid s < x}|) değerini hesaplayan) hata olasılığı (ε) ile sınırlı her olasılıksal veri yapısı, beklenen değerde en az

[ \frac{m \log(2^w / m)}{1 + \log(w)/\log(1/ε)} ]

bit gerektirir.

Göreli Trie'ler

Teorem 4.1’deki olasılıksal trie, doğru düğümü geri getirmede belirli bir başarısızlık olasılığına sahiptir. Yapı yalnızca önceden belirlenmiş bir (S ⊇ D) kümesindeki anahtarlar için sorgulandığında bu durum önlenebilir. Bu durumda göreli trie kavramından söz edilir.

Bir göreli trie gerçekleştirmek için önce göreli üyelik problemini çözeriz.

Teorem 5.1

(E ⊆ S ⊆ u) kümeleri verilsin ve (|E| = t) ile (|S| = n) olsun. (S) kümesinin elemanları için (E)’de sabit zamanlı üyelik testi

[ t \log(n/t) + O(t + \log w) ]

bit içinde gerçekleştirilebilir.

Teorem 5.2

(|D| = m) ve (|S| = n) olacak şekilde (D ⊆ S ⊆ u) kümesi için sıkıştırılmış trie’yi ele alalım. (x ∈ S) anahtarı verildiğinde, aşağıdaki koşulları sağlayan bir iç düğüm tarafından temsil edilen (p) dizgesinin uzunluğunu döndüren bir veri yapısı vardır:

• (p), (x)’in bir önekidir;
• Bir iç düğüm tarafından temsil edilen her (q) dizgesi için, eğer (q) (x)’in bir önekiyse o zaman (|q| ≤ |p|).

Bu yapı

[ O(m(\log(n/m) + \log w)) ]

bit alan gerektirir ve sorgu süresi (O(\log w))’dir.

5.1 Hatasız Göreli Sıralama

Teorem 5.2’de tanımlanan yapı, olasılıksal trie’yi kesin hale getirir; ancak bunun bedeli, doğru sonucun yalnızca (S) kümesinin elemanları için verilmesidir.

Bunu Teorem 4.2’nin ispatında tanımlanan sıralama yapısıyla birleştirerek, (S) kümesinin bir elemanının sırası için deterministik olarak iki olası değer sağlayan bir yapı elde ederiz.

Daha sonra, çiftteki ilk tam sayının doğru olduğu (L ⊆ S) alt kümesini kaydederiz (özünde, hangi dizgelerin soldan çıktığını belirtir). Bu, göreli üyelik veri yapısı kullanılarak gerçekleştirilebilir.

Teorem 5.3

(D ⊆ S ⊆ u) ve (|D| = m), (|S| = n) olsun. Her (x ∈ S) için (x)’in (D) içindeki sırasını döndüren bir veri yapısı vardır ve bu yapı

[ O(m(\log(n/m) + \log w) + n) ]

bit alan gerektirir ve sorgu süresi (O(\log w))’dir.

Son olarak, monoton minimal mükemmel bir hash fonksiyonu yalnızca

[ O(n \log \log w) ]

bit kullanılarak ve (O(\log w)) sorgu süresiyle elde edilebilir. Boyutu (b = \log w) olan kovalar kullanıldığında, (n / \log w) ayırıcı üzerinde kurulan göreli trie yalnızca (O(n)) bit yer kaplar. (g_i) fonksiyonları tarafından kullanılan alanın eklenmesi ((O(n \log \log w)) bit) nihai sonucu verir.

5. Bir Göreli Trie

TEOREM 6.1. Alan olarak (O(n \log \log w)) bit kullanan ve sorgulara (O(\log w)) sürede cevap veren monoton minimal mükemmel bir hash fonksiyonu vardır.

Monoton minimal mükemmel hashleme üzerine kanıtladığımız sonuçlar, sıralı bir tabloda bir elemanı yalnızca tek bir erişimle bulabileceğimizi ima eder. Bu bölümde indeksleme problemi üzerine ek sonuçlar sunuyoruz.

7. Sıralı Bir Tabloyu İndeksleme

7.1 Beklenen Değerde (O(1)) Erişim ile Sıralı Bir Tablonun Sıralanması

Sıralı bir anahtar kümesi (S) içeren çevrimdışı bir depolamamız olduğunu varsayalım. Amacımız, (x \in u) elemanının sırasını, (S) kümesine beklenen sabit sayıda erişim kullanarak ve mümkün olan en az ek alanla belirlemektir. Fikir, (S)’ye göre hatalı olabilen göreli sıralama sağlayan bir yapı kullanmak ve hataları (S) üzerinde yapılan yoklamalarla kontrol etmektir.

Hata olasılığı (o(1/w)) olmalıdır; bu da asimptotik alan kullanımında herhangi bir maliyet olmadan mümkündür. Bu, (1 - o(1/w)) olasılığıyla (i) ve (j) olmak üzere iki olası değer elde ettiğimiz anlamına gelir; burada (i < j) olup, (S)’teki sırası (i - 1) olan eleman veya sırası (j - 1) olan eleman (x)’in öncülüdür (eğer (i = 0) veya (j = 0) ise (x), (S)’teki tüm dizgelerden önce gelir).

En fazla 3 yoklama kullanarak (x)’in öncülünün gerçekten (i - 1) mi yoksa (j - 1) mi sırasındaki eleman olduğunu belirleyebiliriz: önce (i). elemanı yoklarız ve (x) ile olan ilişkisine bağlı olarak ya (i - 1) konumunu ya da ({j - 1, j}) konumlarını yoklarız. Eğer bu yöntem öncülü belirleyemezse, basitçe (S) üzerinde ikili arama yaparız; bu da

[\log(n + 1) = O(w)]

yoklama gerektirir. İkili arama (o(1/w)) olasılıkla gerçekleştiğinden, bunun toplam değere beklenen katkısı (o(1))’dir.

TEOREM 7.1. (n) elemanlı saklanmış sıralı bir (S) tablosu verildiğinde, ek olarak (O(n \log w)) alan kullanan ve (x ∈ u) elemanının (S) içindeki sırasını beklenen değerde (S)’e (3 + o(1)) erişim kullanarak hesaplayan bir yapı vardır.

7.2 Bloklu Depolamada Bir Elemanı En Fazla İki Erişimle Bulma

Bu durumda sıralı tablomuz (S), boyutu (b) olan bloklara bölünmüştür ve (x ∈ S) anahtarının bulunduğu bloğu mümkün olan en az sayıda blok okuyarak bulmak isteriz.

Bölüm 5.1’in başında yapıldığı gibi, ayırıcı kümesi (D) üzerinde (her zamanki gibi her bloğun son anahtarını içeren) bir göreli trie yapısı kurabilir ve bunu (x)’in ait olabileceği iki olası bloğu belirleyen bir düğüm‑sıralama yapısıyla eşleştirebiliriz.

Bu yapı

[O\left(\frac{n}{b}(\log b + \log w) + \frac{n}{b}\right)]

bit alan kullanacaktır; bu da (b = O(w^c)) için (O((n/b) \log w))’dir (ayırıcıları saklamak için gerekli olan bilgi‑kuramsal alt sınır olan

[\Theta\left((n/b)(w - \log(n/b))\right)]

bit ile karşılaştırılmalıdır).

Yapıya erişildikten sonra en fazla iki olası aday elde ederiz ve beklenen değerde doğru olanı 1.5 denemede tespit ederiz.

Aramaları yönlendirmek için olasılıksal trie kullanan bir dış bellek arama ağacı için Bee-tree adını öneriyoruz. Bazı parametreler için Bee-tree’lerin derinliği, klasik B-tree’lerden asimptotik olarak daha küçüktür.

Kaynaklar

1. M. A. Bender, Z. Duan, J. Iacono ve J. Wu. Yerellik koruyan cache-oblivious dinamik sözlük. J. Algorithms, 53(2):115–136, 2004.
2. G. S. Brodal, R. Fagerberg ve R. Jacob. Küçük yükseklikli ikili ağaçlar aracılığıyla cache oblivious arama ağaçları. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA-02), sayfa 39–48, New York, 6–8 Ocak 2002. ACM Press.
3. J. L. Carter ve M. N. Wegman. Evrensel hash fonksiyonu sınıfları. J. Comput. Syst. Sci., 18:143–154, 1979.
4. L. Carter, R. Floyd, J. Gill, G. Markowsky ve M. Wegman. Kesin ve yaklaşık üyelik test edicileri. In Proceedings of Symposium on Theory of Computation (STOC '78), sayfa 59–65. ACM Press, 1978.
5. D. Charles ve K. Chellapilla. Bloomier filtreleri: ikinci bir inceleme. In Proc. ESA 2008, 2008.
6. D. R. Clark ve J. I. Munro. İkincil depolamada verimli suffix ağaçları (genişletilmiş özet). In SODA, sayfa 383–391, 1996.
7. M. Dietzfelbinger, J. Gil, Y. Matias ve N. Pippenger. Polinom hash fonksiyonları güvenilirdir (genişletilmiş özet). In 19th International Colloquium on Automata, Languages and Programming (ICALP '92), Lecture Notes in Computer Science, cilt 623, sayfa 235–246. Springer, 1992.
8. M. Dietzfelbinger ve R. Pagh. Erişim ve yaklaşık üyelik için özlü veri yapıları (genişletilmiş özet). In L. Aceto et al., editörler, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, 7–11 Temmuz 2008. Lecture Notes in Computer Science, cilt 5125, sayfa 385–396. Springer, 2008.
9. A. Fiat ve M. Naor. Örtük O(1) yoklama araması. SIAM Journal of Computing, 22(1):1–10, 1993.
10. A. Fiat, M. Naor, J. P. Schmidt ve A. Siegel. Bilinçli hashleme. Journal of the ACM, 39(4):764–782, 1992.
11. E. A. Fox, Q. F. Chen, A. M. Daoud ve L. S. Heath. Sıra koruyan minimal mükemmel hash fonksiyonları ve bilgi erişimi. ACM Trans. Inf. Sys., 9(3):281–308, 1991.
12. M. L. Fredman ve J. Komlós. Ayırıcı sistemlerin ve mükemmel hash fonksiyonu ailelerinin boyutu üzerine. SIAM J. Algebraic Discrete Methods, 5(1):61–68, 1984.
13. M. L. Fredman, J. Komlós ve E. Szemerédi. O(1) en kötü durum erişim süresi ile seyrek bir tabloyu saklama. J. Assoc. Comput. Mach., 31(3):538–544, Temmuz 1984.
14. A. Gupta, W.-K. Hon, R. Shah ve J. S. Vitter. Sıkıştırılmış veri yapıları: sözlükler ve veri farkındalıklı ölçüler. Theoret. Comput. Sci., 387(3):313–331, 2007.
15. T. Hagerup ve T. Tholey. Neredeyse minimal alanda verimli minimal mükemmel hashleme. In Proceedings of the 18th Symposium on Theoretical Aspects of Computer Science (STACS '01), Lecture Notes in Computer Science, cilt 2010, sayfa 317–326. Springer–Verlag, 2001.
16. G. Jacobson. Alan açısından verimli statik ağaçlar ve grafikler. In Proc. 30th Annual Symposium on Foundations of Computer Science, sayfa 549–554, 1989.
17. D. E. Knuth. Sorting and Searching, cilt 3, The Art of Computer Programming. Addison-Wesley, ikinci baskı, 1997.
18. H. G. Mairson. Bir tabloda aramanın program karmaşıklığı. In 24th Annual Symposium on Foundations of Computer Science, sayfa 40–47, Tucson, Arizona, 7–9 Kasım 1983. IEEE.
19. H. G. Mairson. Tablo genişlemesinin mükemmel hash fonksiyonlarının program karmaşıklığı üzerindeki etkisi. BIT, 32(3):430–440, Eylül 1992.
20. B. S. Majewski, N. C. Wormald, G. Havas ve Z. J. Czech. Bir mükemmel hashleme yöntemleri ailesi. Comput. J., 39(6):547–554, 1996.
21. K. Mehlhorn. Mükemmel ve evrensel hash fonksiyonlarının program boyutu üzerine. In 23rd Annual Symposium on Foundations of Computer Science (FOCS 1982), sayfa 170–175, Chicago, Illinois, ABD, 1982. IEEE.
22. R. Pagh. Sabit sorgu süresi olan statik sözlüklerde düşük fazlalık. SIAM J. Comput., 31(2):353–363, 2001.
23. E. Porat. Matris çözümüne dayalı optimal bir Bloom filtre yerine geçen yöntem, 2008. arXiv:0804.1845v1.
24. V. Raman. Yerellik koruyan sözlükler: teori ve veritabanlarında kümelendirmeye uygulama. In PODS '99: Proceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, sayfa 337–345, New York, NY, ABD, 1999. ACM.
25. J. P. Schmidt ve A. Siegel. Örtük k-yoklama hash fonksiyonlarının uzamsal karmaşıklığı. SIAM Journal of Computing, 19(5):775–786, 1990.
26. D. E. Willard. En kötü durumda log-logaritmik aralık sorguları theta(n) alan içinde mümkündür. Inf. Process. Lett., 17(2):81–84, 1983.
27. A. C.-C. Yao. Tablolar sıralı olmalı mı? J. Assoc. Comput. Mach., 28(3):615–628, 1981.