İki Bellek Erişiminde Arama ile Verimli Hashleme

Rina Panigrahy*

22 Ağustos 2018

Özet

Hashleme çalışmaları, toplar ve kutular analizine yakından bağlıdır. Azar ve ark. [1], tek bir hash fonksiyonu kullanmak yerine bir topu rastgele iki kutuya hashleyip onu bu ikisinden daha az dolu olana yerleştirmenin, kutular üzerindeki maksimum yükü dramatik biçimde azalttığını göstermiştir. Bu durum, en büyük kovada yüksek olasılıkla (O(\log \log n)) top bulunmasına yol açan iki yönlü hashleme kavramına götürür. Hash araması artık bir öğenin hashlendiği her iki kovada da arama yapacaktır.

Bir öğe iki kovadan birine yerleştirilebildiğinden, maksimum yükü azaltmak için başlangıçta yerleştirildikten sonra bir öğeyi potansiyel olarak taşıyabiliriz. Eklemeler sırasında taşımalar gerçekleştirerek, hash güncelleme işlemlerini desteklerken maksimum yükün çevrimiçi olarak yüksek olasılıkla 2 seviyesinde tutulabileceğini gösteriyoruz. Hatta (n) kova ile, kova başına iki öğe için alan önceden ayrılmış olsa bile — donanım uygulamalarında arzu edilebileceği gibi — (n)'den fazla öğe depolanabilir ve bu da yüksek bellek kullanım oranı sağlar.

Bu, aşağıdaki özelliklere sahip basit ve pratik bir hashleme yöntemi sunar:

• Her ekleme işlemi yüksek olasılıkla (O(\log n)) zaman ve en fazla (\log \log n + O(1)) taşıma gerektirir ve beklenen durumda sabit zamandadır.
• Her arama iki rastgele bellek erişimi alır ve erişim başına en fazla iki öğe okur.
• Eklemeler sırasında dinamik bellek ayırma gerektirmeden %83.75 bellek kullanım oranını korur.

Ayrıca eklemeler sırasında gerçekleştirilen taşıma sayısı ile bir kovadaki maksimum yük arasındaki dengeyi de analiz ediyoruz. En fazla (h) taşıma gerçekleştirerek aşağıdaki maksimum yük korunabilir:

[ O\left( \frac{\log \log n}{h \log(\log \log n / h)} \right). ]

Dolayısıyla yalnızca bir taşıma gerçekleştirerek bile hiç taşıma yapılmayan duruma göre daha iyi bir üst sınır elde ederiz.

Hashleme çalışmaları toplar ve kutular analizine yakından bağlıdır. Bu alandaki klasik sonuçlardan biri şudur: asimptotik olarak, (n) top bağımsız ve rastgele biçimde (n) kutuya atılırsa, en büyük kutu yüksek olasılıkla ((1 + o(1)) \frac{\ln n}{\ln \ln n}) top içerir. Azar ve ark. [1], tek bir hash fonksiyonu kullanmak yerine bir topu rastgele iki kutuya hashleyip onu bu ikisinden daha az dolu olana yerleştirmenin, kutular üzerindeki maksimum yükü dramatik biçimde azalttığını göstermiştir. Bu durum iki yönlü hash fonksiyonları kavramına yol açar; burada en büyük kova (O(\log \log n)) top içerir.

Hash araması artık bir öğenin hashlendiği her iki kovada da arama yapacaktır. Bu iyileşme o kadar çarpıcıdır ki pratikte paket yönlendirme donanımında hash aramalarını verimli biçimde gerçekleştirmek için kullanılabilir [3]. İki hash araması, iki farklı hash tablosu ayrı bellek bileşenlerine yerleştirilerek paralel hâle getirilebilir.

1. Giriş

Bir öğe iki kovadan birine yerleştirilebildiği için, maksimum yükü azaltmak amacıyla bir öğeyi başlangıçta yerleştirildikten sonra taşıyabiliriz. Tüm rastgele seçimler önceden verilmişse topların yüksek olasılıkla maksimum yükü 2 olacak şekilde kutulara atanabileceği biliniyordu [6]; ancak bunun hash güncelleme işlemlerini desteklerken çevrimiçi olarak da başarılabileceğini gösteriyoruz.

Hatta (n)'den daha fazla, en fazla 1.67n öğe, (n) kovada maksimum iki öğelik yük ile depolanabilir ve bu eklemeler sırasında yüksek olasılıkla en fazla (\log \log n + O(1)) taşıma gerektirir. Her kova için iki öğelik alan önceden ayrılmış olsa bile — dinamik bellek ayırmayı önlemek için donanım uygulamalarında arzu edildiği gibi — bu yalnızca %16.25 alan kaybı, yani %83.75'in üzerinde kullanım anlamına gelir.

Bellek kullanım oranı birçok hash uygulamasında kritik bir konudur; özellikle çok sayıda bellek bileşeninin kart alanı, ASIC pin sayısı ve güç gibi önemli kaynakları tükettiği donanım uygulamalarında.

Algoritmamız yüksek olasılıkla en fazla (O(\log n)) düğümü inceleyen ve beklenen durumda sabit olan bir BFS (breadth-first search) gerektirir. Alternatif olarak BFS kullanmaktan kaçınmak için, (m < 0.65n) olduğu sürece maksimum yükü iki olarak korumak amacıyla yalnızca (O(\log n)) uzunluğunda bir rastgele yürüyüş yapılabileceğini gösteriyoruz. Daha büyük (m) değerleri için ise, (m = O(n)) olduğu sürece bu yöntem sabit bir yük sağlar.

Ayrıca eklemeler sırasında yapılan taşıma sayısı ile kovadaki maksimum yük arasındaki dengeyi de analiz ediyoruz. Daha az taşıma gerektiren bir çözüm pratikte daha cazip olabilir çünkü taşıma işlemleri pahalı olabilir. Ayrıca donanım uygulamalarında mümkün olmayabilecek BFS taramasından kaçınmak da arzu edilebilir.

Eklemeler sırasında en fazla (h) taşıma gerçekleştirerek aşağıdaki maksimum yük korunabilir:

[ O\left( \frac{\log \log n}{h \log(\log \log n / h)} \right). ]

Dolayısıyla yalnızca bir taşıma gerçekleştirerek bile hiç taşıma yapılmayan duruma göre daha iyi bir üst sınır elde ederiz.

Öğeleri taşıma fikri daha önce cuckoo hashing [17] yönteminde kullanılmıştır; ancak bu yöntem kova başına yalnızca bir öğeye izin verir. İki hash tablosu ile bu durum %100 bellek ek yükü gerektirir. Bu hashleme yönteminin olasılıksal analizi [9]'da yapılmış ve amortize ekleme süresinin sabit olduğu gösterilmiştir.

Fotakis ve ark. [14] yöntemi d-ary hashing biçimine genelleştirerek (d) hash tablosu kullanmış ancak yine kova başına yalnızca bir öğeye izin vermiştir. (\epsilon) bellek ek yükü ile hash aramalarının (O(\ln^2 (1/\epsilon))) yoklama sayısında gerçekleştirilebileceğini ve amortize ekleme süresinin sabit olduğunu göstermişlerdir. Ancak önceki çalışmalarda ekleme süresi için yüksek olasılıklı üst sınırlar veya maksimum kova boyutu ile eklemeler sırasında gerekli taşıma sayısı arasındaki bir denge analiz edilmemiştir.

Pratikte daha fazla rastgele erişim gerektiren bellek işlemleri, aynı miktarda belleği daha az erişim ve daha büyük veri bloklarıyla okumaya göre daha pahalıdır. İlk rastgele erişimin gecikmesi, sonraki konumlardan veri getirmeye göre çok daha yüksektir. Donanım uygulamalarında çok sayıda tabloyu yoklamak, paralel olarak verimli biçimde erişilebilmesi için aynı sayıda bellek bileşeni gerektirir.

Yöntemimiz iki bellek erişimi içerir ve %83.75 bellek kullanım oranı sağlar. Bu kullanım oranının ispatlanabilir bir değer olduğunu ve sıkı bir sınır olmadığını belirtmek gerekir; algoritmamız için %93 üst sınırı gösterilebilir.

Diğer ilgili çalışmalar arasında Fredman, Komlós ve Szemerédi [13] tarafından geliştirilen sabit arama zamanına sahip ilk statik sözlük veri yapısı yer alır; daha sonra Dietzfelbinger ve ark. tarafından [8] ve [10]'da dinamik bir veri yapısına genelleştirilmiştir. Ancak pratikte bu algoritmaların uygulanması cuckoo hashing'e göre daha karmaşıktır.

Ayrıca paralel toplar ve kutular [2] alanında ve paylaşımlı bellek makinelerini (örneğin PRAM'ler) dağıtık bellek makineleri (DMM'ler) üzerinde taklit eden algoritmaların incelenmesinde [11][5][16][19] kapsamlı çalışmalar yapılmıştır. Bu ortamda, tüm (n) topların kutulara atanmak için paralel girişim turlarına katıldığı bir paralel yerleştirme oyunu ( collision game ) söz konusudur.

Her turda henüz yerleştirilmemiş her topun iki konumu da test edilir. Eğer bir topun test edilen konumu en fazla sabit sayıda başka top tarafından test ediliyorsa, top yerleştirilir. (\log \log n + O(1)) turun tüm (n) topu yüksek olasılıkla yerleştirmek için yeterli olduğu gösterilmiştir [11][5]. Ancak bu durum (\log \log n + O(1)) taşımanın maksimum yükü 2 olarak korumaya yeterli olduğunu doğrudan göstermez çünkü ortam farklıdır.

2. Tekniklerin Genel Görünümü

Kovaları kutular ve öğeleri toplar olarak düşünürsek, hashleme sürecini (m) topun (n) kutuya atanması olarak görebiliriz. Her top için rastgele iki kutu seçilir.

Kutular bir grafın köşeleri olarak düşünülürse, bir top için seçilen iki kutu bir kenar ile temsil edilebilir. Bu da (n) köşeli ve (m) kenarlı bir rastgele grafik (G) oluşturur.

Bu graf yönlü hâle getirilerek bir kenarın yönü, topu iki kutudan hangisinin aldığı bilgisini göstermek için kullanılabilir. Her kenarın yönü çevrimiçi bir prosedür tarafından belirlenir. Bir köşenin (kova) yükü onun iç derece değerine eşittir.

Her kenar (öğe) eklemesi için iki yönlü hash algoritması kenarı iç derecesi daha küçük olan köşeye yönlendirir.

Hash süreci sırasında bir topun hashlendiği köşelerden birinin (U) olduğunu varsayalım. Eğer (VU) yönlü bir kenar ise ve (V)'nin yükü belirgin biçimde daha düşükse, (U)'dan (V)'ye bir taşıma gerçekleştirerek (U)'da bir yer açılabileceğini gözlemleyebiliriz. Temelde yeni top (U) veya (V)'den hangisinin yükü daha düşükse oraya eklenebilir.

Bu ilke (V)'den (U)'ya yönlü bir yol bulunduğu duruma genellenebilir. Bu yol boyunca taşıma yapılması, yol üzerindeki tüm kenarların yönlerini tersine çevirir. Eğer kökü (U) olan ve tüm kenarları köke doğru yönelen bir yönlü alt ağaç varsa, bu ağaçtaki en az yüklü köşe yeni topu almak üzere seçilebilir.

Eğer (XW) yönlü bir kenarsa, (W)'nin (X)'in çocuğu olduğunu söyleriz.

Hash ekleme algoritması şu şekilde çalışır:

• Yeni öğenin hashlendiği iki kutu (U_1) ve (U_2) hesaplanır.
• (U_1) veya (U_2)'den ters yönde yönlü kenarlar boyunca ilerlenerek erişilebilen köşeler incelenir.
• Bu köşeler arasından (örneğin) (U_1)'den erişilebilen ve düşük yüke sahip bir (V) köşesi bulunur.
• Yeni öğe (U_1)'e eklenir ve (U_1)'den (V)'ye kadar olan yol boyunca taşıma işlemleri gerçekleştirilir; böylece yalnızca (V)'nin yükü bir artar.

[ s = \frac{2m}{n} ]

ifadesi, yönsüz rastgele grafik (G)'nin ortalama derecesi olsun. Aynı grafın hem yönlü hem yönsüz olarak görülebileceğini unutmayın. Makale boyunca aksi belirtilmedikçe (G) grafı yönsüz sürümü ifade eder.

(s)'nin sabit olduğu varsayılır. Algoritmamızın maksimum yükü düşük tutma başarısı, bu rastgele graf içinde yoğun alt grafiklerin bulunmamasına bağlıdır.

(s < 3.35) olduğunda böyle yoğun alt grafiklerin bulunmadığını gösteriyoruz; bu da kova boyutu en fazla 2 olan ve eklemeler için yüksek olasılıkla en fazla (\log \log n + O(1)) taşıma gerektiren bir algoritma verir (Bölüm 3). 3.35 sınırı kesin olmayabilir ancak ispatlanabilir biçimde 3.72'den büyük değildir.

Daha sonra eklemeler sırasında yapılan taşıma sayısı ile maksimum kova boyutu arasındaki dengeyi tanık ağaçları (witness trees) tekniğini [5][16][2] kullanarak ve problemimize önemli uyarlamalar yaparak analiz ediyoruz (Bölüm 4).

Bu bölümde (s < 3.35) için en fazla (\log \log n + O(1)) taşıma gerçekleştirerek yüksek olasılıkla hiçbir kovaya 2'den fazla öğe gelmemesinin sağlanabileceğini gösteriyoruz.

Bir ekleme işlemi için, verilen bir düğümden BFS sırasıyla geriye doğru arama yaparız; yönlü kenarları ters yönde takip ederek yükü en fazla bir olan bir düğüm ararız. Analizi basitleştirmek için geriye doğru arama sırasında algoritmanın her düğüm için yalnızca iki çocuğu ziyaret ettiğini varsayıyoruz; gerçekte daha fazla çocuk bulunabilir.

(\log \log n + O(1)) derinliğe kadar arama yapıldığında yüksek olasılıkla yükü en fazla bir olan bir düğüm bulunacağını göstereceğiz. Öncelikle geriye doğru aramanın sınırsız derinliğe kadar ilerlemesine izin verilirse algoritmanın başarısının rastgele grafik (G)'nin bir özelliği ile ilişkili olduğunu gösteriyoruz.

Lemma 3.1

Eğer eklemeler sırasında geriye doğru aramanın herhangi bir derinliğe kadar ilerlemesine izin verilirse, algoritma tüm (m) öğeyi maksimum yükü 2 olacak şekilde yerleştirmeyi ancak ve ancak grafik (G) yoğunluğu 2'den büyük bir alt grafik içermiyorsa başarır.

Burada yoğunluk, alt grafikteki kenar sayısının köşe sayısına oranı olarak tanımlanır.

İspat.

Böyle bir alt grafik varsa, kenarları her köşenin iç derecesi en fazla 2 olacak şekilde yönlendirmek imkânsızdır. Dolayısıyla tüm öğeler yük ≤ 2 korunarak yerleştirilemez.

Tersine, bir ekleme başarısız olursa geriye doğru arama yükü 2'den küçük olan bir düğüm bulamaz. Arama derinliği sınırsız olduğundan, arama her biri en az iki yüke sahip ve ters kenarlar aracılığıyla birbirine ulaşabilen bir düğüm kümesi içinde sıkışmış olmalıdır. Bu küme yoğunluğu en az 2 olan bir alt grafik oluşturur.

Rastgele grafiklerde yoğun alt grafiklerin varlığı kritik eşik davranışı gösterir. Kenar yoğunluğu bu değerin üzerinde olan neredeyse tüm rastgele grafikler böyle bir alt grafik içerirken, bu değerin altındakilerin neredeyse hiçbiri içermez. Bunun nedeni yoğun alt grafiğin varlığının monoton bir özellik olmasıdır ve bu tür özelliklerin keskin eşiklere sahip olduğu Friedgut ve Kalai [12] tarafından gösterilmiştir.

Yakından ilişkili bir özellik, rastgele grafiklerde k-core varlığıdır. Bir k-core, her düğümün derecesi en az (k) olan en büyük boş olmayan alt grafiktir. Pittel ve ark. [18], 3-core varlığı için kritik değerin yaklaşık 3.35 olduğunu göstermiştir.

Yoğunluğu 2'den büyük bir alt grafiğin varlığı, bir 3-core varlığını ima eder. Derecesi en fazla 2 olan düğümleri yinelemeli olarak silersek, sonunda boş olmayan bir 3-core elde edilmelidir; çünkü kaldırılan kenar sayısı kaldırılan köşe sayısının en fazla iki katıdır ve dolayısıyla toplam kenar sayısından küçüktür.

Dolayısıyla yoğunluğu 2 olan bir alt grafiğin varlığı için eşik değeri en az 3.35'tir. Bunun 3.35 ile 3.71 arasında olduğunu gösteriyoruz.

Ayrıca (s \le 3.35) için yalnızca ekleme işlemi yüksek olasılıkla başarılı olmakla kalmaz, aynı zamanda (\log \log n + O(1))'den daha az taşıma gerektirir.

Stratejimiz yükü en fazla bir olan bir düğüm aradığı için, önce aramanın (o(n)) düğüm keşfedilmişken, her biri en az 2 yüke sahip ve birbirine yönelmiş durumda olup ziyaret edilecek yeni düğüm kalmayan bir durumda sıkışmasının olası olmadığını gösteriyoruz.

Lemma 3.2

Yüksek olasılıkla (1 - O(1/n^2)), (G) içinde her düğümün iç derecesinin en az 2 olduğu (o(n)) boyutunda bir indüklenmiş alt grafik yoktur. Bu, geriye doğru aramanın keyfi derinliğe ilerlemesine izin verildiğinde yüksek olasılıkla sıkışamayacağını gösterir.

İspat.

Böyle bir alt grafik (x) düğüm içeriyorsa, en az (2x) kenar içermelidir. Bu olayın olasılığı ihmal edilebilir düzeydedir.

(x) köşe ve (m) kenar arasından (2x) kenar seçmenin yollarının sayısı

[ \binom{n}{x} \binom{sn/2}{2x}. ]

Verilen bir kenarın bu alt grafik içinde bulunma olasılığı en fazla

[ \frac{x^2}{n^2}. ]

Dolayısıyla toplam olasılık

[ \binom{n}{x} \left( \frac{x^2}{n^2} \right)^{2x} ]

ile sınırlanır ve ilgili (x) aralıkları için ihmal edilebilir düzeydedir.

Belirli bir (V) düğümünden başlayarak yönsüz grafik (G) üzerinde (h) derinliğine kadar bir BFS gerçekleştirelim. Bunun aynı düğümden (h) derinliğine kadar yapılan geriye doğru aramadan farklı olduğunu unutmayın; çünkü geriye doğru arama yönlü kenarlar boyunca ters yönde yapılan bir BFS içerir. Bu ikisini ayırt etmek için birincisine yönsüz grafik üzerinde BFS, ikincisine ise geriye doğru arama diyeceğiz.

(\mathrm{BFS}_h(V)), yönsüz grafik üzerinde (h) derinliğine kadar yapılan BFS tarafından ziyaret edilen alt grafiği göstersin. Açıkça görülür ki (h) derinliğine kadar yapılan geriye doğru aramada ziyaret edilen düğümler, (\mathrm{BFS}_h(V)) içinde (h) derinliğine kadar ziyaret edilen düğümlerin bir alt kümesi olacaktır.

Bunu, rastgele yönsüz grafik (G) üzerindeki bu BFS’i bir dallanma süreciyle karşılaştıracağız. (n) düğüm içeren grafik (G)’ye rastgele (sn/2) kenar atıldığından, bu kenarların toplam (sn) uç noktasının her biri rastgele seçilir. Öz‑döngü oluşma olasılığını göz ardı eder ve bu uç noktaları birbirinden bağımsız seçersek, bir düğümün üzerinde (k) kenarın sonlanma olasılığı

[ \alpha_k = \binom{sn}{k}(1/n)^k (1 - 1/n)^{sn-k} \approx e^{-s} s^k / k! ]

şeklindedir.

Bu yaklaşım, büyük (n) ve (k \ll n) için doğrudur ve toplamlar içinde güvenle kullanılabilir. Ayrıca en fazla (o(n)) düğüm ve kenar içeren belirli bir alt grafiğe koşullandırsak bile bu olasılık asimptotik olarak doğru kalır; çünkü bu durum kalan düğüm ve kenarların oranında ihmal edilebilir bir fark meydana getirir.

Her düğümün (\alpha_k) olasılığıyla (k) çocuğa sahip olduğu bir dallanma sürecini ele alalım. Bu dallanma süreci BFS’ten tamamen ayrıdır ve yalnızca her düğümün (\alpha_k) olasılığıyla (k) çocuğa sahip olduğu bir ağaç meydana getirir.

(\mathrm{BRT}_h), böyle bir dallanma sürecini (h) derinliğe kadar çalıştırarak elde edilen ağaç olsun. Daha sonra göstereceğiz ki, BFS sırasında (h) derinliğine kadar hiçbir çevrim bulunmadığını varsayarsak, elde edilen (\mathrm{BFS}_h(V)) ağacının dağılımı asimptotik olarak (\mathrm{BRT}_h)’nin dağılımıyla aynıdır.

Eğer (\mathrm{BFS}_h(V)) bir ağaç ise ve yalnızca yükü en az iki olan düğümler içeriyorsa, içine derinliği (h) olan tam ve dengeli bir ikili ağaç yerleştirilebilir. Bu olayın olasılığının, (\mathrm{BRT}_h) içine derinliği (h) olan tam ve dengeli bir ikili ağaç yerleştirilebilme olasılığına yakın olduğunu göstereceğiz.

Sonraki iki lemma, (s \le 3.35) ise (\mathrm{BRT}_h) içine derinliği (h) olan tam ve dengeli bir ikili ağaç yerleştirmenin olası olmadığını gösterir.

Lemma 3.3

(p_i), dallanma sürecini (i) derinliğe kadar çalıştırarak elde edilen (\mathrm{BRT}_i) ağacına derinliği (i) olan tam ve dengeli bir ikili ağacın yerleştirilebilme olasılığı olsun. O halde

[ p_{i+1} = 1 - e^{-p_i s}(1 + p_i s). ]

İspat

(p_i)’yi yinelemeli olarak hesaplarız. Yüksekliği (i+1) olan bir düğüme bakalım. Çocuklarından en az ikisinin yinelemeli özelliği sağlaması gerekir; bu olayın olasılığı (p_i)’dir.

Eğer (k) çocuk varsa, bunlardan ikiden azının bu özelliği sağlaması olasılığı

[ (1 - p_i)^k + k p_i (1 - p_i)^{k-1} ]

şeklindedir.

(k) çocuğa sahip olma olasılığı (\alpha_k)’dir. Tüm (k) değerleri üzerinde toplarsak

[ p_{i+1} = 1 - e^{-s} e^{s(1-p_i)} - e^{-s p_i} s p_i e^{s(1-p_i)} ]

elde edilir.

Bu ifade sadeleştirildiğinde

[ p_{i+1} = 1 - e^{-p_i s}(1 + p_i s) ]

sonucuna ulaşılır.

Lemma 3.4

Herhangi bir (s \le 3.35) için, (\mathrm{BRT}_h) içine derinliği (h) olan tam ve dengeli bir ikili ağacın yerleştirilebilme olasılığı, aşağıdaki seçim yapılarak

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

herhangi bir sabit (c) için (1/n^c)’den daha küçük hale getirilebilir.

İspat

(s) şu koşulu sağladığı sürece

[ 1 - e^{-ps}(1 + ps) < p ]

herhangi bir (p \in (0,1]) için, (p_i) dizisi monoton biçimde azalır.

Eğer (ps) çok küçükse, bu ifade yaklaşık olarak (p^2 s^2)’ye eşittir; çünkü (e^{-ps}) değeri (1 - ps) ile yaklaşık ifade edilebilir. Sabit sayıda adımda (p), (1/(10s))’ten daha küçük yapılabilir; bundan sonra ise şu yineleme ile her adımda karesel biçimde azalır:

[ p_{i+1} = p_i^2 s^2, ]

bu da

[ p_{i+1} s^2 = (p_i s^2)^2 ]

ifadesine denktir.

Dolayısıyla bu noktadan sonra (\log \log n + O(1)) adım içinde olasılık (1/n^c)’nin altına düşer.

Herhangi bir (p \in (0,1]) için

[ 1 - e^{-ps}(1 + ps) < p ]

olmasını isteriz.

Bu, şu ifadeye denktir:

[ e^{ps} < \frac{1 + ps}{1 - p}. ]

Her iki tarafı da (p)’nin Taylor serisi olarak yazıp karşılaştırdığımızda, bunun

[ \frac{s^2}{2} < s + 1 ]

koşulu sağlandığında gerçekleştiğini görürüz.

Bu da

[ s < \sqrt{3} + 1 < 3.74 ]

sonucunu verir.

Daha iyi bir 3.35 değeri, aşağıdaki fonksiyonun

[ f(x) = 1 + xs - e^{xs}(1 - x) ]

([0,1]) aralığında çizilmesi ve (s \le 3.35) için bu aralıkta (f(x) > 0) olduğunun gösterilmesiyle elde edilir.

Bu (s) değeri sıkıdır; yani (s > 3.36) için (p)’nin 0.5’e yakınsadığı gösterilebilir ve bu da bir ikili ağacın yerleştirilebileceğini ifade eder.

Şimdi dallanma sürecinden elde edilen ağaç için elde edilen bu sonucu, BFS ile elde edilebilecek herhangi bir ağaca genişletiyoruz.

Lemma 3.5

Yüksek olasılıkla, (1 - O(1/n^{c-1})), (G) içinde öyle bir (V) düğümü yoktur ki (V)’den aşağıdaki derinliğe kadar yapılan BFS

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

hiçbir çevrimle karşılaşmasın ve içine derinliği (h) olan tam ve dengeli bir ikili ağaç yerleştirilmiş bir ağaç meydana getirsin.

(Not: BFS, (UV) kenarından başlatılabilir; bu durumda kök (V)’den BFS’in ilk seviyesi (U)’yu ziyaret etmez. Bu, daha sonra kullanılacak teknik bir ayrıntıdır.)

İspat

BFS bir ağaç meydana getirirse, dağılımının asimptotik olarak dallanma sürecinin meydana getirdiği dağılımla aynı olduğunu savunuruz.

Öncelikle ziyaret edilen toplam düğüm sayısının (n)’e göre küçük olduğunu gözlemleyelim. Çünkü maksimum derece (d), yüksek olasılıkla (O(\log n))’dir ve ele aldığımız (h) değeri (O(\log \log n))’dir. Dolayısıyla toplam düğüm sayısı

[ d^h ]

olup

[ (\log n)^{O(\log \log n)} ]

şeklindedir.

En fazla (o(n)) düğüm ve kenar içeren belirli bir alt grafiğin varlığına koşullansak bile, bu durum kalan düğüm ve kenarların oranında ihmal edilebilir bir fark meydana getirir.

Dolayısıyla BFS sırasında en fazla (x) düğüm ve kenar keşfedildikten sonra (burada (x \le (\log n)^{O(\log \log n)})), genişletilen bir sonraki düğümün kendisinden çıkan (k) kenara sahip olma koşullu olasılığı ((k \le O(\log n))) ve bu kenarların hepsinin yeni düğümlere gitmesi olasılığı, (\alpha_k)’ya çok yakındır.

Bu koşullu olasılık, ele aldığımız küçük (k) ve (x) değerleri için (\alpha_k)’dan en fazla

[ 1 + O(kx/n) ]

çarpanı kadar farklıdır.

Dolayısıyla BFS ile dallanma sürecinin en fazla (x) düğüm içeren belirli bir yapıya sahip aynı ağaçları üretme olasılıkları en fazla

[ 1 + O(kx^2/n) = 1 + o(1) ]

çarpanı kadar farklıdır.

Derinliği (h) olan tam dengeli bir ikili ağaç içerebilecek tüm olası ağaçlara bu argümanı uyguladığımızda, yüksek olasılıkla (1 - O(1/n^c)) ile (\mathrm{BRT}_h) içinde böyle bir ikili ağaç bulunamayacağına göre, aynı durumun (\mathrm{BFS}_h(V)) için de geçerli olması gerekir; hatta bu yapı bir ağaç olsa bile. Bu sonuç tüm (V) düğümlerine (1 - O(1/n^{c-1})) olasılıkla genişletilebilir.

Şimdiye kadar yalnızca (\mathrm{BFS}_h(V))’nin bir ağaç olduğu durumu ele aldık. Şimdi BFS’in çevrim oluşturan çok fazla kenar bulmasının da çok düşük olasılıklı olduğunu gösterelim. Çevrim oluşturan kenarlar ile kastettiğimiz, arama sırasında daha önce ziyaret edilmiş düğümlere giden kenarlardır.

Lemma 3.6

Yüksek olasılıkla (1 - O(1/n^c)), (G) içinde (x \le c \log n) düğümden oluşan ve en az

[ x + O(c) ]

(daha kesin olarak (x + c(4 + \log(s/2)))) kenara sahip bir alt grafik yoktur.

İspat

Eğer (x) düğümlü böyle bir alt grafik varsa, bu olayın olasılığının ihmal edilebilir olduğunu göstereceğiz.

(sn/2) kenar arasından (x) düğüm ve (x + u) kenar seçmenin yolu sayısı

[ \binom{n}{x} \binom{sn/2}{x+u} ]

şeklindedir.

Belirli bir kenarın bu alt grafiğin içinde yer alma olasılığı

[ \frac{\binom{x}{2}}{\binom{n}{2}} \le \frac{x^2}{n^2} ]

olur.

Dolayısıyla toplam olasılık, (n) ile polinomik olarak azalan ifadelerle sınırlanabilir; bu da olayın gerçekleşmesinin son derece düşük olasılıklı olduğunu gösterir.

Lemma 3.7

(s \le 3.35) için, yüksek olasılıkla (1 - O(1/n^c)), yüksekliği (o(\log n)) olan bir (T) alt ağacında, (T)’deki düğümler arasında olup (T)’nin kenarları olmayan (5c) kenarın (G) içinde bulunması mümkün değildir.

İspat. Eğer böyle olsaydı, (T)’de bulunmayan fakat (G)’de bulunan bu (5c) kenarın uç noktalarını ele alalım ve bu uç noktalardan köke giden tüm yolların birleşimini alarak bir ağaç oluşturalım. Bu (5c) kenarın uç noktalarının sayısı en fazla (10c)’dir ve her biri köke bağlanmak için en fazla (O(\log n)) kenar gerektirir. Dolayısıyla bu kapsayan ağacın boyutu (x) açıkça (c \log n)’den küçüktür.

Bu kapsayan ağaca (5c) kenarı eklediğimizde en az (x + 5c) kenar elde ederiz. Lemma 3.6’ya göre, (s < 4) için bu durum düşük olasılıklıdır ve en fazla (O(1/n^c)) olasılıkla gerçekleşir.

Lemma 3.8

Yüksek olasılıkla, (1 − O(1/n^c)), rastgele grafik (G) içine yüksekliği (h = \log \log n + O(1)) olan tam ve dengeli bir ikili ağaç (B) yerleştirmek mümkün değildir.

İspat. Böyle bir ikili ağaç (B)’yi (G) içine, kökü (V) olacak şekilde yerleştirebildiğimizi varsayalım. (V)’den (h) derinliğine kadar bir BFS yapalım. Lemma 3.7’ye göre yüksek olasılıkla (\mathrm{BFS}_h(V)) içinde en fazla (5c) çevrim oluşturan kenar bulunabilir. Bu (5c) kenarı (\mathrm{BFS}_h(V))’den silerek elde edilen ağacı (\mathrm{BFS}'_h(V)) ile gösterelim.

(B)’de derinliği en fazla (\log(5c) + 1) olan bir (V') düğümü bulunmalıdır ki bu düğümden başlayan ikili alt ağaç (\mathrm{BFS}'_h(V)) içinde hâlâ bozulmamış olsun; yani silinen (5c) kenarın hiçbirini içermesin.

(B)’nin (V') köklü ikili alt ağacına (B') diyelim. Şimdi silinen kenarların uç noktalarından (V)’ye giden en fazla (10c) yolu ele alalım. Tek bir yol (B')’de belirli bir seviyede en fazla iki düğümle kesişebileceğinden, (B')’de derinliği (\log(20c) + 1) olan ve bu (10c) yolun hiçbirinin üzerinde bulunmayan bir (V'') düğümü bulunmalıdır.

Ayrıca (B')’de (V'')’nin iki çocuğundan en az biri (örneğin (W)) (\mathrm{BFS}'_h(V))’de de (V'')’nin çocuğu olmalıdır; çünkü (\mathrm{BFS}'_h(V))’de (V'')’nin en fazla bir ebeveyni vardır. (B')’de (W) köklü ikili alt ağaca (B'') diyelim. (B'')’nin yüksekliği, (B)’nin yüksekliğinden en fazla (\log(5c) + \log(20c) + 3) kadar farklıdır.

Ayrıca (V''W) kenarından başlatılan BFS (yani (W)’den BFS’in ilk seviyesi (V'')’yi ziyaret etmez) çevrim içermez; aksi halde (V'') bu (10c) yoldan birinin üzerinde olurdu. Dahası, bu BFS içinde tam ve dengeli bir ikili ağaç (B'') yer alır. (h)’yi yeterince büyük seçerek (B'')’nin yüksekliğinin Lemma 3.5’in gerektirdiği değerden en az o kadar olmasını sağlayabiliriz; bu da bir çelişki doğurur.

Artık bir ekleme sırasında, (\log \log n + O(1)) derinliğe kadar yapılan geriye doğru aramanın yüksek olasılıkla yükü 2’den küçük olan bir düğüm bulması gerektiğini göstermeye hazırız. Toplam arama süresi en fazla (O(\log n))’dir.

Teorem 1

(s \le 3.35) için, yüksek olasılıkla (1 − O(1/n^2)), bir ekleme sırasında (\log \log n + O(1)) derinliğe kadar geriye doğru ilerlersek yüksek olasılıkla yükü 2’den küçük olan bir düğüm buluruz ve en fazla (O(\log n)) düğüm incelenir. Bu aramanın beklenen süresi (O(1))’dir.

İspat. Bir ekleme sırasında yükü 2’den küçük bir düğüm bulamadığımızı varsayalım. O halde, yüksek olasılıkla Lemma 3.2’ye göre birkaç seviyeden sonra takılıp kalamayacağımız ve Lemma 3.7’ye göre en fazla (5c) çevrim oluşturan kenarla karşılaşabileceğimiz için, derinliği (\log(5c) + 1) olan bir düğüm bulunmalıdır ki bu düğümün altında yapılan geriye doğru arama hiçbir çevrim bulmasın. Bu da yüksekliği (\log \log n + O(1)) olan tam bir ikili ağaç verir ve Lemma 3.8 ile çelişir.

Aramanın beklenen derinliği sabittir; çünkü (p_i)’nin (i)’ye göre karesel biçimde azaldığı görülmektedir. Bu da eklemelerin yüksek olasılıkla maksimum yük 2 korunarak yapılabileceğini gösterir.

Algoritma, öğe sayısı (m) (n)’den büyük olsa bile (2m/n \le 3.35) olduğu sürece çalışır. Her kovada iki giriş statik olarak ayrılmış olsa bile, (m/(2n)) bellek kullanım oranı

(3.35/4 > 83.75%)

olabilir. Böylece bellek israfı yalnızca %16.25 olur.

Buradaki (s = 3.35) değerinin maksimum yükü iki olarak tutmak için sıkı bir sınır olmayabileceğini belirtmek gerekir; çünkü hesaplama tam bir ikili ağacın varlığına dayanarak yapılmıştır ve bu durum ne 2‑yoğun bir alt grafiğin varlığı için ne de (\log \log n + O(1)) hamlede ekleme yapabilmek için zorunlu olabilir.

Bununla birlikte, (s > 3.72) için maksimum yükü iki olarak tutmanın imkânsız olduğunu göstermek kolaydır. Bunun nedeni, böyle bir rastgele grafikte izole düğümleri ve derece bir olan düğümleri sildiğimizde yoğunluğu 2’den büyük olan boş olmayan bir bileşen elde etmemizdir.

2’den Büyük Sabit Kova Boyutuna Genelleme

Maksimum kova boyutu 2 için yaptığımız analiz, herhangi bir sabit maksimum yük (i) için genellenebilir. İlginç biçimde, (i > 2) için başlangıç değerlerinde kanıtlanabilir en iyi bellek kullanım oranı yaklaşık %80 civarında kalır ve (i) büyüdükçe düşmeye başlar.

Önceki algoritma bir BFS gerçekleştirir. Alternatif bir algoritma ise az yüklü bir düğüm bulmak için basitçe rastgele bir yürüyüş yapmaktır. (m < 0.65n) için uzunluğu (O(\log n)) olan bir rastgele yürüyüşün yükü en fazla 1 olan bir düğümü ortaya çıkaracağını gösteriyoruz. Yer darlığı nedeniyle ispatı burada verilmemiştir.

Teorem 2

Yüksek olasılıkla, (1 − O(1/n^2)), herhangi bir (s < 1.3) için uzunluğu (O(\log n)) olan bir rastgele yürüyüş yükü en fazla iki olan bir düğüm bulur.

Teorem 3

Yüksek olasılıkla, (1 − O(1/n^2)), (m = n) için uzunluğu (O(\log n)) olan bir rastgele yürüyüş yükü en fazla 4 olan bir düğüm bulur.

Şimdiye kadar sabit bir yükü korumak için gereken hamle sayısını inceledik. Burada daha az sayıda kutu incelendiğinde maksimum yükün ne olduğunu ele alıyoruz. Özellikle yalnızca iki kutuyu ve onların çocuklarını inceleyebiliriz. Örneğin bir öğe (U_1) ve (U_2)’ye hashlenirse yalnızca (U_1), (U_2) ve bunların çocuklarını inceleyip bunlar arasından en az yüklü olanı yeni yükü taşımak için seçebiliriz. Bu en fazla bir hamle gerektirir.

Çocukları yalnızca bir seviye derinliğe kadar incelemek yerine, ters yöndeki yönlendirilmiş kenarlar boyunca BFS yaparak tüm torunları (h) derinliğine kadar keşfedebiliriz. Aramayı (h) derinliğiyle sınırlayarak en fazla (h) hamle gerektiğini garanti ederiz. Bu bölümde eklemeler sırasında (h) derinliğe kadar tüm torunlar incelendiğinde maksimum yük için bir üst sınır veriyoruz.

Temel sezgi şudur: Yeni öğenin yükü (i) yüklü bir düğüm tarafından taşınıyorsa, incelenen her düğümün en az (i) çocuğu olmalıdır. Dolayısıyla yaklaşık olarak toplam (i^h) düğüm incelemiş olmalıyız ve bunların her birinin yükü en az (i)’dir. Eğer (p_i) bir düğümün yükünün en az (i) olma olasılığı ise ve bu olayların bağımsız olduğunu varsayarsak, bunların gerçekleşme olasılığı (p_i^{i^h}) olur. Bu yaklaşık olarak (p_{i+1} = p_i^{i^h}) verir ve dolayısıyla

(p_i = 2^{-\Omega((i−1)!^h)})

elde edilir. (p_i), şu durumda

i > O((\log \log n) / (h \log(\log \log n / h)))

olduğunda (o(1/n^c)) olur.

Bu sonucu, bağımsızlık varsayımı yapmadan daha biçimsel bir ispatla veriyoruz.

İspatımız tanık ağacı yaklaşımına dayanır — bu yaklaşımın en erken kullanımlarından bazıları [5], [16] ve [2]’de bulunabilir. Belirli bir düğümde (6l) yüküne yol açan bir olayı ele alalım. Bu olayın gerçekleşebilmesi için, daha önce meydana gelmiş olması gereken tüm olayları izleyerek elde edilen büyük boyutlu bir ağacın var olması gerektiğini göstereceğiz.

Ancak bu yaklaşım, kenar yönlerinin zaman içinde değişmesi nedeniyle problemimize uyarlanırken önemli düzenlemeler gerektirir. Açıklamayı sadeleştirmek için ispatı (m = n) ((s = 1)) varsayımı altında sunacağız; esasen aynı ispat herhangi bir sabit (s) için de çalışır.

Tanık Grafiğinin Kurulumu

Bir düğüm (X)’in yükü (i) olduğunda, bunun gerçekleşmesine neden olan benzersiz bir kenar eklemesi vardır. Diyelim ki bu kenar (U_1U_2)’dir; yani öğe (U_1) ve (U_2) kovalarına hashlenmiştir. Bu kenar eklenirken yönlendirilmiş grafiğe bakalım.

Ekleme sırasında hem (U_1) hem de (U_2)’den (h) derinliğe kadar geriye doğru bir arama yapılmıştır. Diyelim ki (X) düğümü (U_1)’den geriye doğru en fazla (h) derinliğe gidilerek elde edilmiştir. Şunu söyleyeceğiz ki:

• U1U2 kenarı, X'in i-inci katkı kenarıdır (contributing-edge),
• U2, X'in i-inci katkı eşidir (contributing-peer),
• X'ten U1'e kadar yapılan hareketlerin izlediği yönlü yol, X için i-inci katkı yoludur (contributing-path).

X, ziyaret edilen düğümler arasında en küçük yüke sahip bir düğüm olduğundan, U2'den en fazla h derinlikte bulunan tüm düğümlerin yükünün en az i − 1 olması gerekir.

Katkı kenarı U1U2'nin, U2'den yapılan geri arama sırasında geçilen tüm kenarlardan daha yeni ve dolayısıyla onlardan farklı olması gerektiğini unutmayın. Ayrıca her düğüm ve her i değeri için i-inci katkı kenarının benzersiz olması gerekir.

Tanık grafı, katkı eşi U2'den başlatılan geri aramada ziyaret edilen düğümler için katkı kenarlarının özyinelemeli olarak takip edilmesiyle elde edilir.

Öncelikle, tanık grafı oluşturulurken hiçbir zaman döngülerle karşılaşmadığımız ve grafın her zaman bir ağaç olarak kaldığı şeklinde basitleştirici bir varsayım yapıyoruz. Daha sonra, Bölüm 3'te olduğu gibi, döngü oluşturan kenarların sayısının yeterince az olduğunu ve bu nedenle göz ardı edilebileceğini göstereceğiz.

Amacımız, yüksek dereceli düğümlere sahip büyük bir tanık ağacı elde etmek ve böyle bir altgrafın G içinde bulunmasının olası olmadığını ileri sürmektir. Sorun şu ki, döngülerle karşılaşmadığımız varsayımı altında bile katkı yolları aracılığıyla daha önce ziyaret edilmiş düğümlere ulaşmak hâlâ mümkündür; çünkü katkı yolları tamamen ziyaret edilen alt ağaçtaki kenarlardan oluşabilir ve yeni düğümlere gitmeyebilir.

Bu sorunu, tanık ağacını aşağıdaki özyinelemeli prosedürle hesaplayarak aşarız.

• U2'nin bu kenara karşılık gelen i-inci katkı eşi olduğunu varsayalım; yani bu ekleme için yük, U1'in altındaki bir düğüm tarafından alınmıştır.

• Eklemenin gerçekleştiği anda U2 düğümünden h derinliğe kadar geri arama yapılarak elde edilen T alt ağacına bakın (döngüyle karşılaşılmadığı varsayımı nedeniyle bunun bir ağaç olması gerekir). Bu alt ağacın yaprak kümesi L'ye bakın. O anda T içindeki her düğümün yükü en az i − 1'dir. L içindeki her iç düğümün en az i − 1 çocuğu olduğundan, L içindeki kenar sayısı en fazla 2|L| olur.

• L içindeki herhangi bir düğüm için j = i − 1, i − 2 veya i − 3 olacak şekilde j-katkı kenarı olan tüm kenarların kümesi S'ye bakın. Başka bir deyişle, e ∈ S ise ve ancak L içinde bir V düğümü ve j ∈ {i − 1, i − 2, i − 3} olacak şekilde e, V için j-katkı kenarı ise.

T alt ağacının en fazla 2|L| kenara sahip olduğu ve S kümesinin 3|L| kenar içerdiği göz önüne alındığında, S içinde T alt ağacının dışında kalan en az |L| kenardan oluşan bir Q kümesi bulunmalıdır. Bu kenarlara götüren tüm katkı yolları, alt ağacı tanık ağacının geri kalanına bağlayan U1U2 kenarından daha eski olduğundan ve varsayım gereği hiçbir döngü oluşmadığından, Q içindeki bu kenarların şu ana kadar oluşturulan tanık ağacının tamamının dışında olması gerekir.

Döngülerden kaçınmak için, karşılık gelen katkı yollarının Q içindeki katkı kenarına ulaşmadan önce T'den dallanması gerekir.

Verilen bir i-katkı kenarı U1U2 için:

• j ≥ i − 3 olacak şekilde Q içindeki her j-katkı kenarı için özyinelemeli olarak işlemi tekrarla.

Özyinelemenin derinliğini l'ye düşürüyoruz. Ayrıca geri BFS sırasında her düğüm için, daha fazlası mevcut olsa bile yalnızca l çocuk seçiyoruz. Temelde tanık ağacı, katkı yollarıyla bağlanmış alt ağaçlardan oluşan bir ağaç gibi görünür. Her alt ağacın l^h adet “çocuk” alt ağacı vardır ve hiçbir düğüm veya kenar tekrar edilmez. Bu ağacın alt ağaç sayısı cinsinden yüksekliği l'dir. Bu ağaçtaki tüm kenarları yönsüz olarak düşünün.

Yeterince büyük l için böyle bir tanık ağacının yüksek olasılıkla var olamayacağını göstereceğiz.

Lemma 4.1

Tanık ağacı oluşturulurken hiçbir döngüyle karşılaşılmadığı varsayımı altında, aşağıdaki koşul için böyle bir tanık ağacının var olma olasılığı

l > (log log n) / (h log(log log n / h)) + O(1)

en fazla O(1/n^c)'dir; burada c herhangi bir sabittir.

İspat. Olasılığı, mümkün olan tüm bu tür ağaçların toplam sayısını ve bunların tekil olasılıklarını çarparak hesaplayacağız. Katkı yolları üzerindekiler hariç tüm düğümlerin en az l çocuğu olduğuna dikkat edin.

l çocuk seçme yolları:

Belirli bir düğüm için bu çocukları seçmenin yol sayısı (n choose l)'dir; kenarları atamanın yol sayısı en fazla n^l'dir; ve böyle bir kenar atamasının gerçekleşme olasılığı en fazla (2/l)^l'dir.

Bir katkı yolu seçme yolları:

Bu düğümler yalnızca bir düğümden kendi katkı eşine giden uzunluğu en fazla h olan katkı yolları üzerinde bulunabilir. Uzunluğu en fazla h olan tüm bu katkı yolları, kaynak aldıkları alt ağaçtan dallanmalıdır.

Belirli bir katkı yolu için bu dallanma noktası en fazla lh farklı şekilde seçilebilir.

Uzunluğu en fazla h olan yolun geri kalanını seçmenin, olasılıkla ağırlıklandırılmış yol sayısı:

≤ (h adet tepe noktası seçme yollarının sayısı) × (h adet kenar seçme yollarının sayısı) × (bu kenarların doğru yerlere düşme olasılığı)

≤ n^h n^h (2/n^2)^h ≤ 2^h.

Dolayısıyla olasılıkla ağırlıklandırılmış toplam katkı yolu seçme sayısı en fazla 2^h l^h = (2l)^h olur.

Toplam olasılık:

Her alt ağaçta en az l^{h−1} adet düğüm vardır ve bunların her birinin l çocuğu bulunur; ayrıca her alt ağacın kökü bir katkı yolundadır. Dolayısıyla her alt ağacı seçmenin, olasılıkla ağırlıklandırılmış yol sayısı (2e/l)^{l^h}'dir.

Bu tür alt ağaçların toplam sayısı en az l(l−1)^h'dir. Bu nedenle tanık ağaçlarını seçmenin olasılıkla ağırlıklandırılmış toplam sayısı (4e/l)^{l^{l^h}} olur.

Bu olasılığın o(1/n^c) olması için l değerini seçmemiz gerekir. Bu, şu şekilde ayarlanarak sağlanır:

l = (log log n) / (h log(log log n / h)) + O(1).

Şimdiye kadar tanık grafının oluşturulması sırasında döngü üreten hiçbir kenarla karşılaşılmadığını varsaydık. Döngülere yol açan kenarların sayısının çok fazla olmasının oldukça düşük olasılıklı olduğunu göstereceğiz.

Yine, Bölüm 3'te olduğu gibi, Lemma 3.7 kullanılarak şu argüman yapılır: yükü 6l olan bir düğümle başlamak yerine, yükü 6l + 5c olan bir düğümle başlanır ve tanık ağacı l + 1 özyineleme derinliğine kadar kurulmaya çalışılırsa, 5c'den fazla döngü üreten kenarla karşılaşma olasılığı çok düşüktür.

Kök katkı eşinin altındaki düğümün 5c'den fazla çocuğu olduğundan, bunlardan en az birinin altında yapılan tanık grafı oluşturma süreci döngü üreten kenarlardan arınmış olmalıdır ve bu da istenen sonucu verir. Bu, aşağıdaki teoremi kanıtlar.

Teorem 4

h derinliğine kadar arama yapıldığında, yüksek olasılıkla 1 − O(1/n^c), bir ekleme işlemi aşağıdakinden daha büyük bir yüke yol açmaz:

6 (log log n) / (h log(log log n / h)) + O(1),

burada c herhangi bir sabittir.

Teşekkür

Faydalı tartışmalar için Tomas Feder, Michael Mitzenmacher, Christian Scheideler ve Rajeev Motwani'ye teşekkür ederim. Ayrıca makalesinin taslağını sağladığı için Artur Czumaj'a da teşekkür etmek isterim [7].

Kaynaklar

1. Y. Azar, A. Z. Broder, A. R. Karlin ve E. Upfal. Dengeli tahsisler. SIAM Journal on Computing, 29:180–200, 1999. Bu makalenin ön sürümü Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, 1994'te yayımlanmıştır.

2. M. Adler, S. Chakrabarti, M. Mitzenmacher ve L. Rasmussen. Paralel rastgele yük dengeleme. Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing içinde, sayfa 238–247, Mayıs 1995.

3. A. Broder ve M. Mitzenmacher. IP Aramalarını İyileştirmek İçin Birden Fazla Hash Fonksiyonunun Kullanılması. Proceedings of IEEE INFOCOM 2001, s. 1454–1463, 2001.

4. R. Cole, A. Frieze, B. M. Maggs, M. Mitzenmacher, A. W. Richa, R. K. Sitaraman ve E. Upfal. Silme işlemleriyle toplar ve kutular üzerine. Second International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM) içinde, Lecture Notes in Computer Science serisi 1518 numara, sayfa 145–158. Springer-Verlag, Ekim 1998.

Kaynaklar

[5] A. Czumaj, F. Meyer auf der Heide ve V. Stemann. Üçlü logaritmik gecikmeli paylaşımlı bellek simülasyonları. Lecture Notes in Computer Science, 979:46–59, 1995.

[6] A. Czumaj ve V. Stemann. Rastgeleleştirilmiş tahsis süreçleri. Proceedings of the Thirty-Eighth Annual Symposium on Foundations of Computer Science içinde, sayfa 194–203, Ekim 1997.

[7] A. Czumaj, C. Riley ve C. Scheideler. Mükemmel Dengeli Tahsis. Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM’03) içinde, sayfa 240–251.

[8] Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert ve Robert E. Tarjan. Dinamik mükemmel hashing: Üst ve alt sınırlar. SIAM Journal on Computing, 23(4):738–761, 1994.

[9] L. Devroye ve P. Morin. Cuckoo hashing: Ek analiz. Information Processing Letters, 86:215–219, 2003.

[10] Martin Dietzfelbinger ve Friedhelm Meyer auf der Heide. Yeni bir evrensel hash fonksiyonları sınıfı ve gerçek zamanlı dinamik hashing. Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP ’90) içinde, Lecture Notes in Computer Science serisi 443, sayfa 6–19. Springer-Verlag, Berlin, 1990.

[11] M. Dietzfelbinger ve F. Meyer auf der Heide. Basit ve verimli paylaşımlı bellek simülasyonları. Proceedings of the 5th SPAA (1993) içinde, s. 110–119.

[12] Ehud Friedgut ve Gil Kalai. Her monoton graf özelliğinin keskin bir eşiği vardır. Proceedings of the American Mathematical Society, 124 (1996), 2993–3002.

[13] Michael L. Fredman, Janos Komlos ve Endre Szemeredi. O(1) en kötü durum erişim süresiyle seyrek bir tablonun saklanması. Journal of the Association for Computing Machinery, 31(3):538–544, 1984.

[14] Dimitris Fotakis, Rasmus Pagh, Peter Sanders ve Paul Spirakis. En kötü durumda sabit erişim süresine sahip alan açısından verimli hash tabloları. 20th Annual Symposium on Theoretical Aspects of Computer Science, 2003.

[15] M. Mitzenmacher, A. Richa ve R. Sitaraman. İki Rastgele Seçimin Gücü: Teknikler ve Sonuçlar Üzerine Bir İnceleme. Handbook of Randomized Computing: Volume 1 kitabında bölüm, editörler P. Pardalos, S. Rajasekaran ve J. Rolim, s. 255–312.

[16] F. Meyer auf der Heide, C. Scheideler ve V. Stemann. Rastgeleleştirilmiş paylaşımlı bellek simülasyonlarını hızlandırmak için depolama fazlalığından yararlanma. Theoretical Computer Science, 162(2):245–281, 1996. Ön sürümü Proceedings of the 12th STACS (1995) içinde, s. 267–278.

[17] R. Pagh ve F. Rodler. Cuckoo Hashing. Proceedings of the 9th Annual European Symposium on Algorithms içinde, s. 121–133, 2001.

[18] B. Pittel, S. Spencer ve N. Wormald. Rastgele bir graf içinde dev bir k-core'un ani ortaya çıkışı. Journal of Combinatorial Theory, Series B, 67 (1996), no. 1, 111–151.

[19] Peter Sanders, Sebastian Egner ve Jan H. M. Korst. Paralel disklere hızlı eşzamanlı erişim. Algorithmica, 35(1):21–55, 2003. Ön sürümü SODA 2000 içinde, s. 849–858 olarak yayımlanmıştır.