ShockHash: Kaba Kuvvetin Ötesinde Neredeyse Optimal Alanlı Minimal Perfect Hashing

Hans-Peter Lehmann
Karlsruhe Institute of Technology, Almanya

Peter Sanders
Karlsruhe Institute of Technology, Almanya

Stefan Walzer
Karlsruhe Institute of Technology, Almanya

Özet

Bir minimal perfect hash fonksiyonu (MPHF), n anahtardan oluşan S kümesini çakışma olmadan ilk n tam sayıya eşler. Bir MPHF’yi temsil etmek için gereken alt sınır n log2 e − O(log n) ≈ 1.44n bittir. Bu sınıra, beklenti değerinde e^n adet hash fonksiyonu tohumu deneyen ve MPHF ile sonuçlanan ilk tohumu saklayan bir kaba kuvvet algoritması ile ulaşılabilir. MPHF oluşturmak için daha önce geliştirilmiş en alan-verimli algoritmaların tamamı, temel yapı taşı olarak bu tür bir kaba kuvvet yaklaşımını kullanır.

Bu makalede, minimal perfect hashing için küçük ve yoğun şekilde aşırı yüklenmiş cuckoo hash tabloları olan ShockHash’i tanıtıyoruz. ShockHash iki hash fonksiyonu h0 ve h1 kullanır ve f : S → {0, 1} biçiminde bir fonksiyonun var olmasını umar; öyle ki x → h_{f(x)}(x) ifadesi S üzerinde bir MPHF olur. Ardından f fonksiyonunu n + o(n) bit kullanarak saklamak için 1 bitlik bir retrieval veri yapısı kullanır.

Graf terminolojisinde ShockHash, bir pseudoforest ile karşılaşana kadar n kenarlı rastgele grafikler üretir — burada her bileşen düğüm sayısı kadar kenar içerir. ShockHash daha sonra cuckoo hashing kullanarak pseudoforest’ten doğrusal zamanda bir MPHF türetir. ShockHash’in beklenti değerinde yalnızca yaklaşık (e/2)^n ≈ 1.359^n adet tohum denemesi gerektiğini gösteriyoruz. Bu durum, tohumu saklamak için gereken alanı yaklaşık n bit azaltır (asimptotik olarak optimal alan tüketimini korurken) ve kaba kuvvet yaklaşımına kıyasla yapım sürecini neredeyse 2^n kat hızlandırır. Bipartite ShockHash, aday hash fonksiyonlarından oluşan bir havuzu koruyup tüm olası çiftleri kontrol ederek beklenen yapım süresini tekrar yaklaşık 1.166^n seviyesine düşürür.

ShockHash’i RecSplit çerçevesi içinde bir yapı taşı olarak kullandığımızda ShockHash-RS elde ederiz; bu yaklaşım rakip yöntemlere göre üç büyüklük mertebesine kadar daha hızlı oluşturulabilir. ShockHash-RS, 10 milyon anahtar için anahtar başına 1.489 bit kullanarak yaklaşık yarım saatte bir MPHF oluşturabilir. Bunun yerine ShockHash verimli bir k-perfect hash fonksiyonundan sonra kullanıldığında, en iyi rakiplere benzer alan kullanımı elde ederken oluşturma ve sorgulama işlemlerinde önemli ölçüde daha hızlıdır.

2012 ACM Subject Classification
Theory of computation → Data compression; Information systems → Point lookups

Related Version
ShockHash dergi sürümü için hazırlanan bu ön baskı, ALENEX 2024’te yayımlanan bir konferans makalesine [40] dayanmaktadır. Bipartite ShockHash’in temel fikri, bu arXiv makalesinin daha önceki bir sürümünde [38] analiz olmadan açıklanmıştır.

Supplementary Material
Software (Source code): https://github.com/ByteHamster/ShockHash
Software (Comparison with competitors): https://github.com/ByteHamster/MPHF-Experiments

Funding
Bu proje, Avrupa Birliği’nin Horizon 2020 araştırma ve yenilik programı kapsamında Avrupa Araştırma Konseyi’nden (ERC) finansman almıştır (hibe sözleşmesi No. 882500).

Keywords and phrases
sıkıştırılmış veri yapısı, perfect hashing, bit paralelliği, vektör komutları

1 Giriş

Bir perfect hash fonksiyonu (PHF), N anahtardan oluşan bir kümeyi çakışma olmadan ilk M tam sayıya eşler. Eğer M = N ise hash fonksiyonu minimal perfect (MPHF) olarak adlandırılır ve anahtarlar ile ilk N tam sayı [N] arasında bire bir eşleme kurar. Minimal perfect hashing’in birçok uygulaması vardır.

Örneğin, garantili sabit erişim süresine sahip statik hash tablolarını gerçekleştirmek için kullanılabilir [28]. Hash tablosu hücrelerinde yalnızca payload verisi saklandığında güncellenebilir bir retrieval veri yapısı elde edilir [44]; yalnızca fingerprint’ler saklandığında ise [7,22] yaklaşık üyelik veri yapısı elde edilir. Hash değerleri ayrıca giriş anahtarlarının küçük tanımlayıcıları olarak da kullanılabilir [10]; bu tanımlayıcılarla çalışmak büyük ve karmaşık anahtarlara göre daha verimlidir. Son olarak, biyoinformatik [1,13,14,15] ve metin indeksleme [3,5,57] alanlarında çeşitli uygulamalar bulunmaktadır.

İlgili Çalışmalar

Bir MPHF’yi temsil etmek için gereken alt sınır yaklaşık N log2 e ≈ 1.44N bittir. Ayrıca bu sınırı karşılayan ve doğrusal zamanda çalışan, sabit sorgu süresine izin veren teorik bir yapı da vardır [32]. Ancak bu yapı gerçekçi olmayan N < 2^150 durumları dışında çalışmaz [11]; bu nedenle (minimal) perfect hashing, algoritma mühendisliği açısından hâlâ ilgi çekici bir konudur. Önceki çalışmaların uzun bir dizisi, farklı alan–zaman dengeleri sunan çeşitli pratik yaklaşımlar geliştirmiştir.

Birçok yaklaşım önce g : S → [b] biçiminde bir dış hash fonksiyonu oluşturur ve giriş kümesi S’i boyutları s1 ≈ s2 ≈ … ≈ sb olan küçük alt kümelere S1, S2, …, Sb şeklinde böler; ardından i ∈ [b] için hi : Si → {1, …, si} biçiminde bir perfect hash fonksiyonu oluşturur. (si)i∈[b] değerleri verildiğinde, ya da daha iyisi i ∈ [b] için pi = s1 + … + si önek toplamları verildiğinde, S üzerinde bir MPHF şu şekilde elde edilir: x → p_{g(x)} + h_{g(x)}(x).

Bir yandan, böyle bir bölme adımının zorunlu olmadığı bütüncül yöntemler vardır (her ne kadar yine de faydalı olabilse de). Bu yöntemler şu ana kadar alan alt sınırından sabit bir çarpan kadar uzaktadır (örneğin [6,13,39,44]). Bunlar arasında en alan-verimli yaklaşımlardan biri SicHash’tir [39]; bu yöntem N anahtarı, cuckoo hashing’in bir genellemesini kullanarak [24,48], N(1 + ε) adet benzersiz tablo girişine eşler. Her anahtar için seçilen hash fonksiyonu daha sonra bir retrieval veri yapısında saklanır ve küçük bir geri dönüş veri yapısı oluşturulan PHF’yi bir MPHF’ye dönüştürür. SicHash alan açısından optimal değildir; bunun bir nedeni cuckoo tablosunun anahtarlarını yerleştirmek için birçok geçerli yerleşime izin vermesidir, yani tek bir giriş kümesi PHF veri yapısının birçok farklı durumu tarafından gereksiz şekilde temsil edilir.

Diğer yandan, n boyutlu alt kümeler üzerinde hash fonksiyonlarını kaba kuvvet deneme-yanılma yöntemiyle kullanan yöntemler vardır [4,9,21,27,49]; bu yöntemler yaklaşık e^n ≈ 2.718^n deneme gerektirir. Bu nedenle kabul edilebilir bir toplam çalışma süresi elde etmek için agresif bir bölme adımı gerekir. Daha önceki en alan-verimli yaklaşım olan RecSplit [21] bu türdendir ve giriş kümesini yinelemeli olarak çok küçük (n ≈ 16) yaprak alt kümelere böler. İlginç biçimde, kapsamlı biçimde ayarlandığında bu yöntem, alan alt sınırından oldukça uzak olmasına rağmen en iyi bütüncül yöntemlerden bile daha yüksek oluşturma verimi sağlayabilir [9].

Katkı

Bu makalede ShockHash’i tanıtıyoruz — küçük ve yoğun şekilde aşırı yüklenmiş cuckoo hash tabloları. Bu yaklaşım, her anahtar için iki hash fonksiyonu kullandığımız ve cuckoo hash tablosunu tamamen doldurabilene kadar oluşturma işlemini tekrar ettiğimiz SicHash’in uç bir versiyonu olarak görülebilir. Böylece ara aşamada minimal olmayan bir PHF kullanmadan doğrudan bir MPHF elde ederiz.

Graf terminolojisinde ShockHash, her anahtarın o anahtarın aday konumlarını bağlayan bir kenara karşılık geldiği n kenarlı rastgele bir grafı tekrar tekrar üretir. Tablo yalnızca ve yalnızca graf bir pseudoforest ise doldurulabilir — yani hiçbir bileşen düğüm sayısından daha fazla kenar içermez. ShockHash fikri prensipte basit olsa da, iki seçenekli ikili cuckoo hashing kullanıldığında (dolayısıyla 1 bitlik retrieval yapısı ile) yalnızca önemsiz düzeyde bir fazlalık bulunduğunu kanıtlayabiliyoruz. Bu nedenle ShockHash büyük n için bilgi kuramsal alt sınıra yaklaşır ve çalışma süresi (e/2)^n · poly(n) ≈ 1.359^n olur (kaba kuvvete göre yaklaşık 2^n kat daha hızlıdır).

Bipartite ShockHash ile daha ileri üstel iyileştirmeler mümkündür. Her oluşturma denemesinde yeni bir hash fonksiyonu çifti kullanmak yerine, büyüyen bir hash fonksiyonu havuzu oluşturur ve bu havuzdan oluşabilecek tüm çiftleri değerlendiririz. Ayrıca iki hash fonksiyonunun ayrık aralıklara hash üretmesini sağlarız; bu da etkili biçimde her kenarın iki bölümde birer uç noktaya sahip olduğu bir bipartit graf örneklediğimiz anlamına gelir.

Bu bipartit durumda, her iki bölümün hash fonksiyonlarının da ayrı ayrı sürjektif olması gerekir. Bu nedenle tüm kombinasyonları test etmeden önce her bölümdeki aday hash fonksiyonlarını ayrı ayrı filtreleyebiliriz. Bu yaklaşım oluşturma süresini ek bir üstel çarpanla iyileştirerek yaklaşık 1.166^n · poly(n) seviyesine düşürür.

Değerlendirme

ShockHash hâlâ üstel zamanlı bir algoritma olduğundan, girdiyi böldükten sonra onu bir yapı taşı olarak kullanıyoruz. RecSplit çerçevesinde kaba kuvvet yerine ShockHash’i temel durum olarak kullanarak ShockHash-RS elde ediyoruz.

Bir retrieval veri yapısına ek erişim nedeniyle sorgu süresinde küçük bir ceza olsa da, ShockHash-RS oluşturma süreci aynı mimari üzerinde alan-verimli yapılandırmalar için ayarlanmış RecSplit’e [9] kıyasla yaklaşık iki büyüklük mertebesi daha hızlıdır. Bipartite ShockHash-RS bunu yeniden yaklaşık 20 kat iyileştirir.

Teori ile pratiğin bu uyumlaştırılmasındaki önemli bir adım, ShockHash tarafından denenen hash fonksiyonlarının yalnızca üstel olarak çok küçük bir bölümünün gerçekten bir cuckoo hash tablosu oluşturmayı gerektirdiğinin gözlemlenmesidir. Diğer durumlar, cuckoo tablosundaki tüm girişlerin en az bir anahtar tarafından ziyaret edilip edilmediğini kontrol eden basit bir bit-paralel filtre ile ele alınabilir. Bu durum, kaba kuvvetin görünürde daha üstün olmasına yol açan zaman ek yükünün büyük bölümünü ortadan kaldırır [9].

Büyük örneklerde ve anahtar başına 1.56 bit alan tüketimi için, en alan-verimli rakip olan ayarlanmış RecSplit [9] anahtar başına 137 µs gerektirir. Benzer bir sürede, yaklaşımın GPU kullanılarak yoğun paralelleştirilmesiyle anahtar başına 1.499 bit elde edilebilir [9]. Bipartite ShockHash-RS ise yalnızca anahtar başına 1.489 bit ile benzer oluşturma süresinde yeni bir rekor elde eder ve bunu yalnızca tek bir CPU iş parçacığı kullanarak gerçekleştirir (gelecekte verimli GPU paralelleştirmesi mümkün görünmektedir).

Ayrıca ShockHash’in RecSplit çerçevesi dışında da yararlı olduğunu gösteriyoruz. Girdiyi bölmek için k-perfect hashing kullandığımızda ShockHash-Flat elde ederiz; bu yaklaşım en alan-verimli rakiplere benzer alan kullanımı sağlar. Aynı zamanda oluşturma işlemi önemli ölçüde daha hızlıdır ve sorgu süresini yaklaşık %30 azaltarak çok daha fazla alan kullanan yaklaşımların sorgu performansına yaklaşır.

Genel Bakış

Bölüm 2’de ShockHash’i anlamak için gerekli ön bilgileri açıklıyoruz ve Bölüm 3’te ilgili çalışmaları tartışıyoruz. Ardından Bölüm 4’te ShockHash algoritmasını ve Bölüm 5’te bipartit bir varyantını açıklıyoruz. Bölüm 6’da her iki yaklaşımı analiz ediyoruz. ShockHash’i büyük giriş boyutları için uygulanabilir kılmak amacıyla Bölüm 7’de onu farklı bölme şemalarında bir yapı taşı olarak nasıl kullanabileceğimizi gösteriyoruz. Bölüm 8’de pratikte oluşturma sürecini iyileştiren ek varyantlar ve iyileştirmeler sunuyoruz. Bölüm 9’da ayrıntılı deneyler gerçekleştiriyor ve makaleyi Bölüm 10’da sonlandırıyoruz.

2 Ön Bilgiler

Bu bölümde ShockHash’in temel bileşenlerini açıklıyoruz. Buna ShockHash-RS’in dayandığı iki perfect hash fonksiyonu yapısı olan SicHash [39] ve RecSplit [21] de dahildir.

Cuckoo Hashing

Cuckoo hashing [48], hash tablolarında çakışmaları ele almak için iyi bilinen bir yaklaşımdır. Her nesne iki hash fonksiyonu aracılığıyla iki aday hücre elde eder. Bir sorgu işlemi bu iki hücreye bakar ve nesneyi arar.

Bir ekleme işlemi, dolu bir hücreye nesne eklemeye çalıştığında, hücrede zaten bulunan nesne çıkarılır ve kendi diğer aday konumu kullanılarak yinelemeli biçimde tekrar eklenir. Cuckoo hashing daha fazla hash fonksiyonu kullanacak şekilde genişletilebilir [24] veya bir hücrede birden fazla nesne tutulabilir [18]. Bu makalede yalnızca iki hash fonksiyonlu ve hücre başına tek nesneli temel sürümle ilgileniyoruz.

Bir cuckoo hash tablosunun yük eşiği [25,26,41], ekleme işleminin başarısız olma olasılığının artmasından önce doldurulabilecek hücre yüzdesidir. İki aday hücreli cuckoo hashing için yük eşiği c = 0.5’tir. Buna rağmen ShockHash’te birçok tekrar denemesi kullanarak tamamen doldurulmuş cuckoo hash tablolarını ele alıyoruz.

Cuckoo Grafı ve Pseudoforest

Cuckoo hashing, her düğümün bir tablo hücresini ve her kenarın iki aday hücreyi bağlayan bir nesneyi temsil ettiği rastgele bir graf G olarak modellenebilir.

Bir cuckoo hash tablosu, G grafının kenarları her düğümün giriş derecesi ≤ 1 olacak şekilde yönlendirilebiliyorsa başarılı biçimde oluşturulabilir. Aşağıda buna 1-orientation diyoruz. Bir 1-orientation ancak ve ancak G bir pseudoforest ise vardır; yani G’nin her bağlı bileşeni bir pseudotree’dir.

Bir pseudotree ya bir ağaçtır ya da üzerine ağaçların dallandığı bir döngüdür. Bir grafın pseudoforest olup olmadığını kontrol etmenin bir yolu, her bileşenin düğüm sayısından en fazla o kadar kenar içerdiğini doğrulamaktır.

Retrieval Veri Yapıları

S anahtar kümesi N elemanlı olsun ve r bir tam sayı olsun. Bir retrieval veri yapısı (veya statik fonksiyon veri yapısı), her anahtarı belirli bir r bitlik değere eşleyen f : S → {0,1}^r fonksiyonunu saklar. S kümesinde bulunmayan anahtarlar için keyfi değerler döndürebileceği için, fonksiyonu S kümesini temsil etmeden saklamak mümkündür.

Bir retrieval veri yapısını temsil etmek için en az rN bit gerekir ve doğrusal oluşturma süresi ile sabit sorgu süresi sağlayan, rN + o(rN) bit kullanan pratik veri yapıları vardır.

Özellikle r = 1 için Bumped Ribbon Retrieval (BuRR) [19], fonksiyon değerlendirmesini bir hash fonksiyonu değerini önceden hesaplanmış bir tablonun bir segmentiyle XOR işlemine tabi tutup sonucun parity değerini raporlamaya indirger. Bu tablo, neredeyse diyagonal bir doğrusal denklem sisteminin (“ribbon”) çözülmesiyle belirlenebilir. Pratikte BuRR’nin alan ek yükü %1’in altındadır.

SicHash

Perfect hashing için küçük düzensiz cuckoo tabloları (SicHash) [39], cuckoo hashing aracılığıyla perfect hash fonksiyonları oluşturur. Önce bir cuckoo hash tablosu kurar ve ardından her anahtar için nihai olarak hangi hash fonksiyonu seçiminin kullanıldığını saklamak üzere bir retrieval veri yapısı kullanır.

SicHash’in temel yeniliği, anahtarlar için 2, 4 veya 8 seçim anlamına gelen 1–3 bitlik retrieval veri yapılarının dikkatli bir karışımını kullanmasıdır. Anahtar başına 2–3 bit alan kullanılmasına izin verildiğinde uygun bir alan–performans dengesi sağlar.

Bunun altına inemez; çünkü yalnızca 1 bit retrieval kullanmak minimal yapıdan oldukça uzak sonuçlar doğurur gibi görünürken, retrieval için 2 veya daha fazla bit kullanmak alan optimalitesine ulaşamayan gereksiz seçimlere izin verir.

SicHash, yük eşiklerinin ötesinde tabloyu aşırı yükleyip birden fazla hash fonksiyonu deneyerek alan verimliliğinde sınırlı bir iyileşme elde eder. Bu yaklaşım esas olarak sığabilecek anahtar sayısındaki varyansı kullanır. SicHash, aşırı yüklenmiş tabloların başarılı biçimde kurulma olasılığını açık bir soru olarak bırakır. ShockHash ise aşırı yükleme fikrini en uç noktaya taşır ve bu durum için resmi bir analiz sunar.

Son olarak, bipartite ShockHash’te tohumları kodlamak için kullandığımız eşleme fonksiyonlarını açıklıyoruz.

Şekil 1. Farklı eşleme fonksiyonlarının gösterimleri:

• (a) Cantor eşleme fonksiyonu
• (b) Szudzik eşleme fonksiyonu
• (c) Üçgensel eşleme fonksiyonu

RecSplit

RecSplit [21], esas olarak alan verimliliğine odaklanmış bir minimal perfect hash fonksiyonudur. İlk olarak, tüm anahtarlar beklenen sabit b boyutundaki kovalara (buckets) hash'lenir. Bir kovanın anahtar kümesi, tüm yaprak düğümlerin (leaf nodes) —sonuncusu hariç— tam olarak n boyutunda olmasını (Ref. [21]'de yaprak boyutu ℓ olarak adlandırılır) sağlamak için kaba kuvvetle (brute-force) seçilen bölme hash fonksiyonları (splitting hash functions) tarafından ağaç benzeri bir yapıda alt kümelere ayrılır. Yapraklar içinde RecSplit, bir minimal perfect hash fonksiyonu (bijeksiyon olarak da adlandırılır) bulmak için kaba kuvvet araması gerçekleştirir. Ağaç yapısı yalnızca mevcut kovanın boyutuna dayanır. Bu, yapısal bilgileri saklamadan yalnızca hash fonksiyonları için tohum (seed) değerlerini saklamayı mümkün kılar. Tohumlar için kodlama ek yükleri hariç tutulduğunda, bu durum RecSplit'i bir kova içinde bilgi-teorik olarak optimal kılar. İki en alt seviyedeki çocuk düğüm sayısı (fanout), kaba kuvvet iş yükü bölmeler ve bijeksiyonlar arasında dengelenecek şekilde seçilir.

Ayrıca çoklu iş parçacığı (multi-threading) ve SIMD talimatları veya GPU [9] kullanan paralel bir uygulama da mevcuttur. Makale ayrıca bijeksiyonları aramak için rotasyon uydurma (rotation fitting) adı verilen yeni bir teknik önermektedir. Rotasyon uydurma, bir yapraktaki anahtarlara doğrudan hash fonksiyonları uygulamak yerine, anahtarları bir 1-bitlik hash fonksiyonu kullanarak iki kümeye böler. Ardından iki kümenin her birini tek tek hash'leyerek, bitlerin hangi hash değerlerinin dolu olduğunu belirttiği iki kelime oluşturur. Daha sonra, ikinci kelimeyi döngüsel olarak döndürerek ilk küme tarafından bırakılan boş pozisyonların ikinci kümenin pozisyonları tarafından doldurulup doldurulamayacağını bulmaya çalışır. Makale, her rotasyonun yeni bir hash fonksiyonu tohumu ile benzer bir başarı olasılığına sahip olduğunu göstermektedir; dolayısıyla bu, ek hash fonksiyonu tohumlarını hızlı bir şekilde değerlendirmenin bir yoludur.

Eşleştirme Fonksiyonları (Pairing Functions)

Bir eşleştirme fonksiyonu, iki doğal sayıyı tek bir doğal sayı içinde kodlar. Daha doğrusu, bir eşleştirme fonksiyonu N₀² düzlemi ile N₀ arasında bir bijeksiyondur.

Verimli bir şekilde tersine çevrilebilen eşleştirme fonksiyonlarıyla ilgileniyoruz. En popüler eşleştirme fonksiyonu, 2B ızgarayı çaprazlama numaralandıran Cantor eşleştirme fonksiyonudur (bkz. Şekil 1a). Şöyle hesaplanabilir:

pair_c(x, y) = (x + y)(x + y + 1)/2 + y

Diğer bir eşleştirme fonksiyonu, 2B ızgarayı bir karenin kenarlarını takip ederek numaralandıran Szudzik [54] tarafından geliştirilendir (bkz. Şekil 1b). Eşleştirme fonksiyonu şöyle hesaplanabilir:

pairs(x, y) = y² + x eğer x ≤ y
pairs(x, y) = x² + x + y aksi takdirde.

Bu makalede, 2B ızgaranın yalnızca x > y olan koordinatlarını numaralandıran bir fonksiyona ihtiyaç duyuyoruz. Geleneksel terminolojiyi hafifçe esneterek buna hala eşleştirme fonksiyonu diyeceğiz. Üçgensel eşleştirme fonksiyonumuz (bkz. Şekil 1c) şöyle hesaplanabilir:

pair_t(x, y) = x(x − 1)/2 + y

Sezgi, Küçük Gauss formülünden kaynaklanır. Fonksiyonumuzun tersini

(x′, y′) = pair_t⁻¹(z)

hesaplamanın temel fikri, tanımı içinde y = 0 olarak ayarlamak ve x için çözmektir. Bu şunu verir:

x′ = ⌊1/2 + √(1/4 + 2z)⌋

y′ = z − pair_t(x′, 0)

Bipartit uygulamamızda, kodlamak istediğimiz sayıların dağılımına bağlı olarak hem üçgensel eşleştirme fonksiyonumuzu hem de Szudzik eşleştirme fonksiyonunu kullanıyoruz.

Eşleştirme işlemi yalnızca tam sayı operasyonlarını kullanırken, her üç eşleştirme fonksiyonu da tersini almak için karekök operasyonuna ve yuvarlamaya dayanır. Bu, fonksiyonların pratikte tersine çevrilmesinin kayan nokta (floating point) hataları nedeniyle sorunlara yol açabileceği anlamına gelir. z'nin tersinin alınmasının başarılı olup olmadığı, şu kontrolle kolayca doğrulanabilir:

pair(x′, y′) = z

Uygulamamızda, tersine çevrilebilirliği yapım (construction) aşamasında kontrol ediyoruz, böylece sorgular sırasında bir çalışma zamanı yükü oluşmaz.

Ön bilgilerde açıkladığımız RecSplit ve ShockHash'e ek olarak, bir dizi başka minimal perfect hash fonksiyonu da mevcuttur. Aşağıdaki paragraflarda yaklaşımlara genel bir bakış sunuyoruz.

Hash-and-Displace

Hash-and-Displace [4,27,49] ile perfect hashing, hızlı sorgulara ve asimptotik olarak optimal alan tüketimine izin verir.

Her bir x anahtarı önce küçük bir b(x) anahtar kovasına hash'lenir. Her bir b kovası için, şu fonksiyonun:

x ↦ f_{i(b(x))}(x)

enjeksiyonel bir fonksiyon olmasını sağlayacak bir f_{i(b)} hash fonksiyonu indeksi i(b) saklanır. Belirli bir kova için, bu indeks kaba kuvvet yöntemiyle aranır. Aramayı hızlandırmak için kovalar önce boyutlarına göre sıralanır.

FCH [27], asimetrik bir kova ataması kullanır: anahtarların %60'ını kovaların %30'una hash'ler. Bu verimlidir çünkü en büyük (ve dolayısıyla yerleştirmesi en zor olan) kovalar yerleştirilirken pozisyonların çoğu hala boştur.

CHD [4], beklenen boyutları eşit olan kovalar kullanır ancak saklanan hash fonksiyonu tohumlarını sıkıştırır.

PTHash [49], asimetrik bir kova ataması kullanarak ve tohumları sıkıştırılmış formda saklayarak bu fikirleri birleştirir.

Parmak İzi Alma (Fingerprinting)

Fingerprinting [13,44] yoluyla perfect hashing, N anahtarı sıradan bir hash fonksiyonu kullanarak γN pozisyonuna hash'ler (burada γ bir ayar parametresidir).

Alan açısından en verimli seçim olan γ = 1, anahtar başına e (log₂ e değil) bitlik bir alan tüketimine yol açar. γN uzunluğundaki bir bit vektörü, tam olarak bir anahtarın eşleştiği pozisyonları gösterir. Çakışmalara neden olan anahtarlar, aynî veri yapısının başka bir katmanında yinelemeli olarak işlenir.

Sorgu aşamasında, bir anahtar kendi konumuna eşleşen tek anahtar olduğunda, bit vektörü üzerindeki bir rank operasyonu MPHF değerini verir.

Halka açık uygulamalar arasında BBHash [42] ve önemli ölçüde daha hızlı olan FMPH [6] yer alır. FMPHGO [6], bu fikri daha az çakışmaya neden olan bir hash fonksiyonu seçmek için yapılan birkaç kaba kuvvet denemesiyle birleştirir.

Tablo Bakımı (Table Lookup)

Pahalı kaba kuvvet aramasının yerini alabilecek cazip bir yol, çözümlerin önceden hesaplanması ve ardından tablo bakımı (table lookup) yapılmasıdır — bu, birçok sıkıştırılmış veri yapısında kullanılan standart bir tekniktir.

Kaba bir fikir olarak, n anahtarlı bir alt problem için, bunları önce bir ara hash fonksiyonu kullanarak U′ ∈ Ω(n²) boyutundaki bir aralığa enjeksiyonel olarak eşlediğimizi varsayalım (daha azı çakışmalara yol açar — doğum günü paradoksu). Ardından, 2^{U′} boyutundaki bir bakma tablosunu kullanarak, önceden hesaplanmış perfect hash fonksiyonlarını sabit zamanda bulabiliriz.

Ancak, polinom çalışma süresi alt problem boyutunu şununla sınırlar:

n ∈ O(√log N)

burada N, genel girdi kümesinin boyutudur. Gerçekçi N değerleri için somut değerler hesaplandığında, düz RecSplit ile bile kolayca işlenebilecek olandan çok daha küçük alt problem boyutları elde edilir.

Yine de, Hagerup ve Tholey [32], bu yaklaşımı perfect hashing probleminin kapsamlı bir teorik çözümüne dönüştürerek doğrusal yapım süresi, sabit sorgu süresi ve alt sınırın 1 + o(1) katı alan elde etmişlerdir. Ancak bu yöntem, N < 2^{150} [11] için iyi tanımlanmış bile değildir.

Rotasyon uydurma kullanan bir RecSplit varyantı [9], sabit zamanda uygun rotasyonları bulmak için 2^n boyutunda bakma tabloları kullanır. Ne yazık ki bunun, tüm rotasyonları doğrudan denemekten daha yavaş olduğu ortaya çıkmıştır.

Daha Fazla İlgili Çalışma

ShockHash Veri Yapısı

Şimdi bu makalenin ana fikri olan ShockHash'i tanıtıyoruz.

İkili bir cuckoo hash tablosunun asimptotik yük eşiği c = 0.5'tir (bkz. Bölüm 2), dolayısıyla n hücreli ve n/2'den fazla anahtarlı bir tablo oluşturma başarı olasılığı sıfıra eğilim gösterir. ShockHash, bir cuckoo hash tablosunu asimptotik yük eşiğinin çok ötesinde aşırı yükler — n anahtarı n boyutunda bir ikili cuckoo hash tablosuna yerleştirir.

Teorem 8'de göreceğimiz üzere, yapım süreci beklenti değerinde (e/2)^n · poly(n) denemeden sonra başarılı olur. Ardından başarılı tohumu

s = min{s ∈ ℕ | ∃ f ∈ {0,1}^S : x ↦ h_{s,f(x)}(x) is MPHF}

(h_{i,0}){i∈ℕ}, (h{i,1})_{i∈ℕ} : S → [n]

ve her anahtarın iki aday pozisyonu arasındaki başarılı f seçimini kaydederiz.

Tohumun, Golomb–Rice kodları [30,50] kullanılarak beklenti değerinde yaklaşık

n log(e/2) + o(n) ≈ 0.44n + o(n)

bite ihtiyacı vardır. Seçimler, n + o(n) bit gerektiren 1-bitlik bir retrieval veri yapısında saklanır. Bu, MPHF tanımının çoğunun (kaba kuvvet yapımında olduğu gibi) tohumda değil, retrieval veri yapısında saklandığı anlamına gelir.

x anahtarı için bir sorgu, retrieval veri yapısından f(x) değerini getirir ve h_{s,f(x)}(x) sonucunu döndürür.

ShockHash'in güzelliği, (retrieval veri yapısı tarafından temsil edilebilen 2^n farklı fonksiyon tarafından belirlenen) 2^n farklı olası hash fonksiyonunu O(n) sürede kontrol edebilmesidir. Bu, alt düzey terimler hariç aynı miktarda alan tüketirken, kaba kuvvetten önemli ölçüde daha hızlı yapım sağlar.

Bölüm 2'de tartışıldığı gibi, bir tohum ancak ve ancak:

{{h_{s,0}(x), h_{s,1}(x)} | x ∈ S}

kenarlarına sahip karşılık gelen rastgele (çoklu)graf bir pseudoforest oluşturuyorsa başarılı bir cuckoo hash tablosu yapımına yol açar. c boyutundaki her bileşen, ancak ve ancak c'den fazla kenar içermiyorsa bir pseudotree'dir. Bu, bağlı bileşen algoritmaları kullanılarak doğrusal zamanda veya sıradan bir cuckoo hash tablosunun artımlı yapımı kullanılarak doğrusal zamana yakın bir sürede kontrol edilebilir.

Bununla birlikte, kaba kuvvetin basit bit-paralel mükemmellik testiyle [21] karşılaştırıldığında, her bir kontrol büyük bir sabit katsayıyla daha yavaştır. Bir sonraki paragrafta, bu darboğazı ele almanın bir yolunu tartışıyoruz.

Bit Maskesi ile Filtreleme

Bir grafın pseudoforest olup olmadığını kontrol etmek için harcanan zamanı azaltmak amacıyla, çoğu tohumu hızlıca reddetmek için bir filter kullanıyoruz.

Daha spesifik olarak, bazı tablo hücrelerinin anahtarların hiçbirinin aday pozisyonu olmadığı tohumları reddediyoruz. Eğer böyle bir hücre varsa, cuckoo hashing'in başarılı olamayacağını zaten biliyoruz ve tam testi atlayabiliriz. Aksi takdirde, cuckoo hashing başarılı olabilir.

Filtre, basit kaydırma ve karşılaştırma operasyonları kullanılarak uygulanabilir. Ayrıca filtre, daha karmaşık olan tam yapımın aksine yazmaçları (registers) kullanabilir. Bu, ShockHash'i pratik hale getiren ana bileşenlerden biridir ve çok etkili olduğu kolayca kanıtlanabilir.

Lemma 1. Bir tohumun filtreyi geçme olasılığı, yani her tablo hücresine en az bir anahtar tarafından vurulma olasılığı en fazla şudur:

(1 − e^{-2} + o(1))^n ≈ 0.864^n.

Kanıt. X_i, i ∈ [n] hücresine kaç kez vurulduğunu göstersin. Bu durumda (X₁, …, X_n) bir multinom dağılımı izler. X₁, …, X_n değişkenleri, [35]'te tanıtılan anlamda negatif ilişkilidir. Toplam

X₁ + ··· + X_n = 2n

sabit olduğu için, i ∈ [n] için {X_i ≥ 1} olaylarının birlikte gerçekleşme olasılığı, karşılık gelen bağımsız olaylara göre daha düşüktür.

X_i ∼ Bin(2n, 1/n)

olduğu için şunları elde ederiz:

P(X_i ≥ 1) = 1 − (1 − 1/n)^{2n} = 1 − e^{-2} + o(1) ≈ 0.864.

Dolayısıyla,

P(∀ i ∈ [n] : X_i ≥ 1) ≤ ∏_{i=1}^{n} P(X_i ≥ 1),

bu da iddiayı kanıtlar.

Daha dikkatli bir analiz [56], filtreyi geçme olasılığının b^n civarında olduğunu ortaya koymaktadır; burada

b = 2e^λ / (λ e^2) ≈ 0.836

ve λ ≈ 1.597, şu denklemin çözümüdür:

2 = λ / (1 − e^{-λ}).

Geliştirmeler

Bölüm 8'de, uygulamada yapım performansını artıran ek geliştirmeleri açıklıyoruz. Bu, ShockHash'e rotasyon uydurma [9] fikrinin uygulanmasını ve daha hızlı yönlendirilebilirlik kontrollerini içerir.

Bipartite ShockHash

Bipartite ShockHash, ShockHash fikrinin bir uzantısıdır. Sade ShockHash'e kıyasla önemli ölçüde daha hızlı yapım sağlar. Bu da daha agresif parametre seçimlerine imkan vererek alan verimliliğinin artmasını sağlar.

ShockHash rastgele graflar örneklerken, bipartite ShockHash bipartit rastgele graflar örnekler.

Sade ShockHash'te her kenar, iki bağımsız hash fonksiyonu kullanılarak iki düğüme bağlanır. Bipartit ShockHash'te hash fonksiyonları [n/2] aralığına sahiptir, ancak hash fonksiyonlarından birinin hash değerlerini n/2 kadar kaydırırız; bu, her kenarın bir uç noktasının [n/2] aralığında, diğerinin ise n/2 + [n/2] aralığında olduğu anlamına gelir.

Bu, cuckoo hashing'in iki bağımsız hash tablosu kullanan orijinal uygulamasına benzer [48]. Fikir ilk başta pek yardımcı görünmeyebilir ancak arama alanını budamak (pruning) için birkaç yol sunar.

Aşağıda, n sayısının çift olduğunu varsayıyoruz. Bölüm 8.4'te tek sayılar n için bir uzantı sunuyoruz.

Tohum Adaylarını Filtreleme

Bölüm 6'da, sade ShockHash için yaklaşık

(e/2)^n ≈ 1.359^n

hash fonksiyonu çiftini test etmenin yeterli olduğunu gösteriyoruz.

Bipartite ShockHash fikri, yaklaşık

√((e/2)^n) = (e/2)^{n/2}

hash fonksiyonunu ve onlardan oluşturulabilecek tüm çiftleri değerlendirmenin neredeyse aynı iyileşmeyi sağlamasıdır. Bu, daha az hash fonksiyonunun değerlendirilmesi gerektiği için pratik çalışma süresini şimdiden iyileştirir.

Bununla birlikte, asimptotik yapım süresi çok fazla iyileşmez çünkü hala tüm kombinasyonları test etmemiz gerekir. Temel bir farkındalık, bipartit durumda bir (h₀, h₁) hash fonksiyonu çiftinin ancak ve ancak hem h₀ hem de h₁'in ([n/2] aralığında) ayrı ayrı sürjektif (surjective) olması durumunda çalışabileceğidir.

Buna karşılık, bipartit olmayan durumda kontrol, h₀ ve h₁'in ([n] aralığında) birlikte [n]'deki her pozisyona en az bir kez vurmasıydı. Bu, hash fonksiyonlarını çiftler haline getirmeden önce aday listesini filtreleyebileceğimiz anlamına gelir.

Bölümlerin her birinde, n/2 pozisyona eşleşen n anahtara bakarız. Lemma 1'e benzer şekilde, filtreyi geçme olasılığı 0.836^{n/2}'dir [56]. Bu, yalnızca filtreyi geçen hash fonksiyonlarını eşleştirirsek, en fazla

((e/2)^{n/2} · 0.836^{n/2})² ≈ 1.136^n

çifti değerlendireceğimizi gösterir. Detaylar için Bölüm 6'ya bakınız.

Bipartite ShockHash Algoritması

Aşağıdaki paragraf yeni bipartite ShockHash algoritmamızı açıklamaktadır. ([n/2]) üzerinde sürjektif olan tohum adaylarından oluşan bir havuz tutuyoruz. Yeni bir aday bulmak için, sürjektif bir hash fonksiyonu veren bir (s_0) tohumu bulana kadar hash fonksiyonu tohumlarını doğrusal olarak kontrol ediyoruz.

Yeni adayı bulduğumuzda, onu havuzdaki önceki tüm (s_1) adaylarıyla birleştirmeyi deneriz. Daha kesin olarak, ([n]) düğümleri ve şu kenarlarla tanımlanan grafın:

\[{\{h_{s_0}(x),\; h_{s_1}(x) + n/2\} \mid x \in S}\]

bir pseudoforest olup olmadığını kontrol ederiz. Eğer bir pseudoforest ise, bir perfect hash fonksiyonu bulmuşuzdur. Sadece anahtarların aday hash fonksiyonlarına ((h_{s_0}) veya (h_{s_1})) olan atamasını bir retrieval veri yapısında saklamamız ve iki tohumu ((s_0) ve (s_1)) kaydetmemiz yeterlidir.

Eğer önceki tohum adaylarından hiçbiriyle yapılan kombinasyon bir pseudoforest ile sonuçlanmazsa, yeni aday (s_0)'ı sürjektif adaylar kümesine ekler ve bir sonrakini ararız.

Şekil 4 bu algoritma için psödokodu verir ve Şekil 5 hash fonksiyonlarını havuza koymadan önce filtreleme fikrini gösterir.

Grafın hangi parçası için hangi hash fonksiyonunu kullandığımız önemli değildir. Parçaları değiştirmek sadece izomorfik bir graf verir ve yönlendirilebilirliği etkilemez. Bu nedenle her zaman yeni belirlenen adayı doğrudan kullanır ve eski adayı ikinci parçada olması için (n/2) kadar kaydırırız.

Ayrıca, bir karma fonksiyonunun her iki bölümde de kendi kendisiyle birleştirilmesinin başarılı bir yapılandırmaya yol açma olasılığını göz ardı ediyoruz.¹ Bu, iki tohum değeri olan (s_0) ve (s_1)’i, (s_1 < s_0) olduğunu bilerek saklamamıza olanak tanır. Bunu, Bölüm 2’de açıkladığımız üçgensel eşleme fonksiyonumuzu kullanarak tek bir tam sayı içinde yapıyoruz. Eşleme fonksiyonunun, tohum çiftlerini tam olarak test ettiğimiz sırayla numaralandırdığını unutmayın. İki değişken uzunluklu tam sayıyı saklamakla karşılaştırıldığında, eşleme yöntemi kodlamadaki sabit ek yükleri azaltır.

Geliştirmeler

Bölüm 8’de, uygulamada yapılandırma performansını önemli ölçüde iyileştiren ek geliştirmeler sunuyoruz. Bunlar arasında karma fonksiyon adaylarından oluşan bir akış üretmenin diğer yolları, bit-paralel filtreleme ve eşit olmayan girdi boyutları için destek yer alır.

Bu bölümde ShockHash’in alan kullanımını ve yapılandırma süresini analiz ediyoruz. Temel zorluk, bir karma fonksiyonu tohumunun aşırı yüklenmiş cuckoo karma tablosunun başarılı şekilde yapılandırılmasına olanak tanıma olasılığı için bir alt sınır elde etmektir.

Öncelikle Bölüm 6.1’de, sade ShockHash için başarı olasılığının çok basit bir analizini sunuyoruz. Bu analiz daha karmaşık kanıtımıza göre daha gevşektir, ancak önemli ölçüde daha kısadır. Bölüm 6.2’de analizde kullanılan araçları açıklıyor ve tam kanıtın küçük yapı taşlarını kanıtlıyoruz. Daha sonra Bölüm 6.3 ve 6.4’te sırasıyla sade ve iki parçalı ShockHash’in başarı olasılığını analiz ediyoruz. Ardından Bölüm 6.5’te yaklaşık ((e/2)^n) karma fonksiyon adayı içeren bir havuzun genellikle yeterli olduğunu gösteriyoruz. Son olarak Bölüm 6.6’da ShockHash ve iki parçalı ShockHash’in yapılandırma süresini ve alan tüketimini veriyoruz.

Aşağıda bir tohum verildiğini varsayıyor ve gösterimde bunu bastırıyoruz.

Grafı ele almak yararlı olacaktır.

¹ Fonksiyonun (n/2) konumunun her birine tam olarak iki anahtar eşlemesi gerekirdi.

Erdős–Rényi rastgele grafına benzer olsa da, (G) kendi üzerine döngüler² ve çoklu kenarlar içerebilir. Modelimiz [29]’daki Model A ile uyumludur.

² Kendi üzerine döngüler içeren grafların burada analizi daha kolaydır ancak uygulamada daha iyi performans için bunlardan kaçınırız.

6.1 Basit Bir Kanıt

Öncelikle, Teorem 2’de (G)’nin bir pseudotree olma olasılığının en az

[(e/2)^{-n} \sqrt{\pi/(2n)}.]

olduğunu gösteren basit bir kombinatoryal argüman veriyoruz.

Bu, (G)’nin birden fazla ağaç içerebilen bir pseudoforest olma olasılığı için bir alt sınır sağlar. Bölüm 6.3 daha sonra bu olasılığın en az

[(e/2)^{-n} \pi/e.]

olduğunu gösterir.

Dolayısıyla basit argüman, çok daha karmaşık kanıta göre yalnızca (O(\sqrt{n})) katsayısı kadar daha gevşektir.

Teorem 2

(G), (n) düğüm ve (n) kenardan oluşan bir çoklu graf olsun. (G)’nin temel aldığı olasılık uzayı, (2n) tepe noktasının (yerine koymalı olarak) örneklenmesi ve her (i \in [n]) için (2i-1) ve (2i) örneklerinden bir kenar oluşturulmasıdır.

Buna göre (G)’nin bir pseudotree olma olasılığı en az

[(e/2)^{-n} \sqrt{\pi/(2n)}.]

Kanıt

(G)’nin bir pseudotree olması için, oluşturulan ilk (n-1) kenarın bir ağaç oluşturması yeterlidir (ancak gerekli değildir). (n^{n-2}) adet etiketli (n)-düğümlü ağaç vardır (Cayley Formülü [12]).

Kenarların sıralaması ve bir kenarı oluşturan iki örneğin sırası önemli olmadığından, bu ağaçların her biri

[2^{n-1}(n-1)!]

yolla elde edilebilir.

Son iki örnek herhangi bir şey olabilir; bu da bize (n^2) seçenek verir.

Stirling yaklaşımını uygulayarak bir pseudotree elde etme toplam olasılığının en az

[(e/2)^{-n} \sqrt{\pi/(2n)}.]

olduğunu gösterebiliriz.

6.2 Araçlar

Bu bölümde analizde daha sonra gerekli olacak araçları açıklıyoruz; bunlar arasında yapılandırma modeli ve graf soyma işlemi bulunur. Öncelikle kalan analizde kullanılan ancak doğası gereği oldukça genel olan iki küçük lemmayı kanıtlayarak başlıyoruz.

Lemma 3

(X \in \mathbb{N}_0) bir rastgele değişken olsun. O hâlde (X)’in en az 1 olma olasılığı

[P(X > 0) = \frac{E(X)}{E(X \mid X > 0)}.]

Kanıt

Herhangi bir negatif olmayan rastgele değişken (X) için toplam beklenti yasasını uygulayabiliriz:

[E(X) = P(X = 0)E(X \mid X = 0) + P(X > 0)E(X \mid X > 0).]

(E(X \mid X = 0) = 0) olduğundan bu ifade

[E(X) = P(X > 0)E(X \mid X > 0).]

şeklinde sadeleşir.

Düzenleme yapıldığında istenen sonuç elde edilir.

Yapılandırma Modeli

Yapılandırma modeli [45], rastgele grafların dağılımlarını tanımlamanın bir yoludur. Bu modelde, her düğüme belirli sayıda kenar ucu vererek grafın her düğümünün derecesini tam olarak sabitleyebiliriz. Graf, birbirine bağlı olmayan iki kenar ucunun eşit olasılıkla rastgele seçilmesi ve bağlanması işleminin tekrar edilmesiyle elde edilir.

Başka bir deyişle, bir kenar ucunu alıp eşine baktığımızda diğer tüm kenar uçları eşit olasılıklıdır.

Graf Soyma

Bu makalenin çeşitli bölümlerinde grafların soyulmasıyla (peeling) [33,43,55] ilgileniyoruz. Bunun için derece 1 olan herhangi bir düğümü alıp ona karşılık gelen kenarla birlikte kaldırırız. Bu işlem tüm düğümlerin derecesi 1’den büyük olana kadar devam eder.

Bir graf, kalan graf içindeki tüm düğümlerin derecesi 2 ise 1‑yönlendirilebilir veya bir pseudoforest olarak adlandırılır; bu da grafın yalnızca çevrimlerden oluştuğu anlamına gelir.

Yapılandırma Modelinde Graf Soyma

Soyma sürecini analiz etmek için (G)’yi iki adımda ortaya çıkarmak yararlıdır.

Önce her düğümün derecesi, (2n) kenar ucunun (veya yarım kenarın) (n) düğüm arasında rastgele dağıtılmasıyla belirlenir. Bu, daha sonra kenarların kenar uçlarının rastgele eşleştirilmesiyle elde edildiği bir yapılandırma modeli oluşturur.

Lemma 5

(x_1, \dots, x_{2n} \in [n]) bağımsız ve eşit olasılıklı rastgele değişkenler olsun. Aşağıda tanımlanan (G_1, G_2, G_3) grafları (G) ile aynı dağılıma sahiptir.

1. (G_1 = ([n], {{x_{2i-1}, x_{2i}} \mid i \in [n]})).
2. (G_2 = ([n], {{x_i, x_j} \mid {i,j} \in M})), burada (M), ([2n])’in eşit olasılıklı rastgele bir tam eşleşmesidir.
3. (G_3), (G_2) ile aynı şekilde tanımlanır; ancak (M), (n) turdan oluşan bir dizide elde edilir. Her turda eşleşmemiş bir (i \in [2n]) sayısı keyfi olarak seçilir ve rastgele seçilen farklı bir eşleşmemiş (j) sayısıyla eşleştirilir.

(G) için bu alternatif olasılık uzaylarını ele almamızın nedeni, (G) hakkında kısmi bilgilere (örneğin (x_1, \dots, x_{2n}) içinde örtük olarak bulunan derece dizisine) koşullandırma yapmamıza izin verirken kalan rastgelelik için temiz bir olasılık uzayı sağlamalarıdır.

Kanıt

(G) ile karşılaştırıldığında (G_1)’in tanımı yalnızca ilgili (2n) karma değerini tek bir listede toplar.

(G_2) için, önce (M)’nin ortaya çıkarıldığını düşünün. (M)’ye koşullu olarak (G_2), (G_1)’deki gibi (n) adet eşit olasılıklı rastgele kenardan oluşur.

(G_3) için temel gözlem şudur: her turda rastgele eşleştirilecek sayının bir karşıt tarafından seçilmesi durumunda bile (M) yine de eşit olasılıklı rastgele bir eşleşmedir.

6.3 Sade ShockHash’te Başarı Olasılığı

(PF(G)) ifadesini (G)’nin bir pseudoforest olduğu olay için kullanıyoruz. Bölüm 2’de belirtildiği gibi:

[PF(G) \Leftrightarrow \exists f : ori(f).]

İki karma fonksiyonu (h_0, h_1 : S \to [n]) ve bir (f : S \to {0,1}) fonksiyonu verildiğinde, (ori(f)) olayı şu durumu ifade eder:

[x \mapsto h_{f(x)}(x)]

bijektiftir.

(ori(f)) özelliğine sahip fonksiyonlar (f) ile (G)’nin 1‑yönlendirmeleri arasında bire bir eşleşme vardır; yani (G)’yi her düğümün iç derece­si en fazla 1 olacak şekilde yönlendirmenin yolları.

Bizim durumumuzda (n) düğüm ve (n) kenar olduğundan, (PF(G)) ifadesi (G)’nin her bileşeni bir pseudotree olan ve ağaç olmayan maksimal bir pseudoforest olduğunu ima eder.

Ağaç olmayan bir pseudotree tam olarak iki adet 1‑yönlendirmeye izin verir; çünkü tekil çevrim iki farklı yönde yönlendirilebilir ve diğer tüm kenarlar çevrimden dışarı doğru yönlendirilmek zorundadır.

Dolayısıyla:

[PF(G) \Rightarrow #{f : ori(f)} = 2^{c(G)}]

burada (c(G)), (G)’nin bağlı bileşen sayısıdır.

Kanıtın temel fikri şöyledir. Rastgele bir fonksiyonun minimal perfect olma olasılığı yaklaşık olarak

[e^{-n} \text{poly}(n)]

düzeyindedir (bkz. Lemma 7). (f : S \to {0,1}) biçimindeki (2^n) fonksiyonun her biri (ori(f)) koşulunu sağlama ve minimal perfect hash fonksiyonu üretme açısından bu olasılığa sahiptir.

Ancak bu olasılığı (2^n) ile basitçe çarpmak, böyle bir (f)’nin var olma olasılığı için mutlaka doğru bir yaklaşım vermez; çünkü ortaya çıkan fonksiyonlar birbiriyle ilişkilidir.

Eğer bazı graflar çok sayıda farklı 1‑yönlendirmeye izin veriyorsa, aynı anda birçok MPHF bulabiliriz ve en az bir yönlendirme bulunma olasılığı azalır. Bu sezgi Lemma 3 kullanılarak

[X = #{f : ori(f)}]

değişkeni ile biçimsel olarak ifade edilir.

Dolayısıyla temel adımlardan biri, rastgele maksimal pseudoforestlerde bileşen sayısının dağılımını analiz etmektir; bunu Lemma 6’da yapıyoruz.

Lemma 6

(G_n), derecesi 2 olan (n) düğümlü yapılandırma modelinden örneklenen rastgele graf olsun (yani (2n) kenar ucunun rastgele birleştirilmesiyle elde edilen 2‑düzenli graf).

(c(G_n)), (G)’nin bileşen sayısı olsun. O hâlde

[E(2^{c(G_n)}) \le e^{\sqrt{2n}}.]

Kanıt (Taslak)

Şu ifade için bir yineleme bağıntısı elde ederiz:

[d_n := E(2^{c(G_n)}).]

Keyfi bir (v) düğümünü ve onun kenar uçlarından birini ele alalım. Bu kenar ucu başka bir kenar ucuyla bir kenar oluşturur. (2n-1) olası eş arasından biri kendi üzerine döngüye karşılık gelir.

• (1/(2n-1)) olasılıkla bir kendi üzerine döngü oluşur. Bu izole bir bileşen meydana getirir ve (G_{n-1}) gibi dağılan bir graf bırakır; beklenti (2 d_{n-1}) olur.
• Aksi takdirde kenar başka bir (w \ne v) düğümüne bağlanır. (v) ve (w)’yi birleştirmek (G_{n-1}) gibi dağılan ve beklentisi (d_{n-1}) olan bir graf bırakır.

Bu durum şu yinelemeyi verir:

[d_n = \left(1 + \frac{1}{2n-1}\right)d_{n-1}.]

Bunu çözüp harmonik toplamlar için sınırlar uyguladığımızda

[d_n \le e^{\sqrt{2n}}.]

elde edilir.

Lemma 7

(S) kümesinde (n) anahtar bulunan rastgele bir (h : S \to [n]) fonksiyonu, minimal perfect (yani bijektif) olma olasılığı

[e^{-n} \sqrt{2\pi n} (1 + o(1)).]

olan bir fonksiyondur.

Kanıt

(S)’den ([n])’e toplam (n^n) olası fonksiyon vardır ve bunların (n!) tanesi bijektiftir. Dolayısıyla olasılık

[\frac{n!}{n^n}.]

şeklindedir.

Stirling yaklaşımı uygulanarak sınır elde edilir.

Teorem 8

(h_0, h_1 : S \to [n]) eşit olasılıklı rastgele fonksiyonlar olsun. Şu özelliği sağlayan bir (f : S \to {0,1}) fonksiyonunun var olma olasılığı

[x \mapsto h_{f(x)}(x)]

bijektif olacak şekilde en az

[(e/2)^{-n} e^{-1} \sqrt{\pi}.]

kadardır.

Lemma 3 kullanılarak şöyle yazabiliriz:

[P(\exists f : ori(f)) = \frac{E(#{f : ori(f)})}{E(#{f : ori(f)} \mid \exists f : ori(f))}.]

Kanıt. (ori(f)) ifadesinin (x \mapsto h_{f(x)}(x)) fonksiyonunun bijektif olduğu olayı için kullandığımız kısaltma olduğunu hatırlayın. Lemma 3’te verildiği gibi başarı olasılığını şu şekilde hesaplayabiliriz.

Önce payı ve paydayı ayrı ayrı ele alacağız.

Pay: Beklenti

Beklentinin doğrusallığı (bağımlı değişkenler için bile geçerlidir) şu sonucu verir:

[ E(#{f : \text{ori}(f)}) = \sum_f P(\text{ori}(f)) = \sum_f P(x \mapsto h_{f(x)}(x) \text{ fonksiyonu } S \text{ üzerinde bijektiftir}). ]

Her sabit (f) için (x \mapsto h_{f(x)}(x)) fonksiyonu her (x \in S) için bağımsız rastgele sayılar atar; yani Lemma 7’de ele alınan türde rastgele bir fonksiyondur ve dolayısıyla şu olasılıkla bijektiftir:

[ e^{-n} \sqrt{2\pi n} (1 + o(1)). ]

Dolayısıyla

[ E(#{f : \text{ori}(f)}) \ge 2^n e^{-n} \sqrt{2\pi n}. ]

Payda: Koşullu Beklenti

(1) ve (2) gözlemlerini kullanarak dikkatimizi (G) grafına kaydırabiliriz:

[ E(#{f : \text{ori}(f)} \mid \exists f : \text{ori}(f)) = E(2^{c(G)} \mid PF(G)). ]

Ayrıca Lemma 5 sayesinde (G_3) türünde bir yapılandırma modeline geçebiliriz. Önce (2n) kenar ucunun konumlarını (x_1, \ldots, x_{2n}) ortaya çıkarırız (dolayısıyla (G_3)’ün derece dizisini) ve ardından (G_3)’ün kenarlarını ortaya çıkaran ve adım adım sadeleştiren aşağıdaki soyma sürecini ele alırız (bkz. Bölüm 6.2).

Derecesi yalnızca bir kenar ucu olan bir (v) düğümü bulunduğu sürece, önce onu rastgele bir kenar ucuyla eşleştirerek ({v,w}) kenarını oluştururuz (iki kenar ucu tüketilir), ardından (v) düğümünü ve yeni oluşan ({v,w}) kenarını kaldırırız. Bu kaldırma işlemleri oluşan grafın bileşen sayısını etkilemez (çünkü (v), (w)’ye bağlıydı) ve oluşan grafın pseudoforest olup olmamasını da değiştirmez (çünkü (w)’nun bileşeni bir düğüm ve bir kenar kaybetmiştir).

Soyma işleminden sonra kalan düğüm sayısı (n') olsun ve kalan kenar uçlarının eşleştirilmesiyle elde edilen graf (G') olsun. Tartışıldığı gibi:

[ PF(G_3) \Leftrightarrow PF(G') \quad \text{ve} \quad c(G') = c(G_3). ]

(G_3)’ün ortalama derecesi 2 olduğundan ve her turda bir düğüm ile bir kenarı kaldırdığımızdan, (G')’ün ortalama derecesi de 2’dir. İki durum vardır.

1. (G')’de bazı düğümlerin derecesi 0’dır. O zaman (\neg PF(G')) çünkü (G')’nin bazı bileşenlerinin ortalama derecesi 2’den büyük olmalıdır.

2. (G')’de hiçbir düğümün derecesi 0 değildir. Soyma işlemini çalıştırdığımız için derecesi 1 olan düğüm de yoktur. Dolayısıyla (G')’deki her düğümün derecesi 2’dir. Bu da (G')’yi çevrimlerden oluşan bir koleksiyon yapar. Özellikle (PF(G')) geçerlidir. Ayrıca (G')’nin üretimi tam olarak Lemma 6’da ele alınan durumdur.

Bu iki durum (G')’nin pseudoforest olup olmaması hakkında zıt sonuçlar verdiğinden, (PF(G'))’nin ancak ve ancak Durum 2’ye ulaşıldığında geçerli olduğunu biliyoruz. (n')’nin dağılımı hakkında bir bilgimiz olmasa da yine de

[ 2^i = e^{\sqrt{2n}}. ]

hesabını yapabiliriz.

Pay ve payda için elde ettiğimiz sınırları birleştirdiğimizde nihai sonuç elde edilir.

6.4 İki Parçalı ShockHash’te Başarı Olasılığı

İki parçalı durumda, temel olarak iki parçalı olmayan sürümdekiyle aynı adımları gerçekleştirebiliriz. Analizi basitleştirmek için (n)’in çift olduğunu varsayıyoruz. Uygulamamız eşit olmayan (n) değerlerini de desteklese de (bkz. Bölüm 8.4), bu durum analizi karmaşıklaştırır ve ShockHash RecSplit gibi bir bölümleme çerçevesine entegre edildiğinde büyük ölçüde kaçınılabilir (bkz. Bölüm 7).

Bu bölümde yine karma fonksiyonlarının tohumunu gösterimde bastırıyoruz. Şöyle tanımlayalım:

• (h_0, h_1 : S \rightarrow [n/2]) karma fonksiyonları
• (f : S \rightarrow {0,1}) iki karma fonksiyonu arasında seçim yapan bir fonksiyon

Şimdi (f) fonksiyonunun tüm ilişkili seçimlerini test etmenin etkisine bakıyoruz. Bölüm 6.3’te tartışıldığı gibi, önce karşılık gelen grafı derecesi 1 olan düğüm kalmayana kadar soyuyoruz. Grafın bir pseudoforest olduğu koşulu altında bu işlem, her düğümün derecesi 2 olan bir graf bırakır.

Bu grafın dağılımı yine bir yapılandırma modeliyle açıklanır (bkz. Bölüm 6.2); yani kenar uçları arasında rastgele bir iki parçalı eşleşme verilir. Ayrıca başlangıçta iki parçalı bir grafla başladığımızı ve her iki bölümün de aynı boyutta olduğunu hatırlayın.

Lemma 6’ya benzer şekilde, şimdi Lemma 9’da kalan graftaki bileşen sayısının (c) şu koşulu sağladığını gösterebiliriz:

[ E(2^c) \le e^{\sqrt{n}}. ]

Soyma işlemi bileşen sayısını değiştirmediğinden, aynı durum özgün iki parçalı grafik için de geçerlidir. Bu da bize grafiğin yönelimlerinin beklenen sayısı için bir üst sınır verir; örneğin hash fonksiyon çifti ((h_0, h_1))’i minimal perfect yapan farklı (f) fonksiyonlarının sayısı.

Lemma 9

(n) çift bir sayı olsun ve (G_n), her bölümde (n/2) düğüm bulunan, tüm düğümlerin derecesinin 2 olduğu rastgele bir iki parçalı grafik olsun; bu grafik ilgili iki parçalı yapılandırma modelinden örneklenmiştir. Dolayısıyla bir bölümdeki stub’lar diğer bölümdeki stub’larla rastgele ve eşit olasılıkla eşleştirilir.

Buna göre (G_n)’in bileşen sayısı (c(G_n)) şu özelliği sağlar

[ E(2^{c(G_n)}) \le e^{\sqrt{n}}. ]

İspat

Aşağıdaki ifade için bir yineleme bağıntısı bulacağız

[ d_n := E(2^{c(G_n)}). ]

(G_n)’in ilk bölümünden rastgele bir (v) düğümünü ve (v)’deki stub’lardan birini ele alalım. Grafik iki parçalı olduğundan bu stub, grafiğin diğer bölümünden bir (r) düğümüne bir kenar oluşturur. (r) düğümünün ilk bölüme geri bağlanan ikinci bir stub’ı vardır.

Şimdi ilk bölümde (n/2 - 1) adet başka düğüm bulunur ve her birinin 2 stub’ı vardır; ayrıca (v)’deki ikinci stub’a sahibiz. Bu (n-1) stub’un her biri eşit olasılıkla eşleştirilir. Dolayısıyla bu kenarın bir çevrimi kapatma olasılığı

[ \frac{1}{n-1}. ]

1. Çevrimin kapatılması koşuluyla:

   Kalan grafiğin dağılımı (G_{n-2}) ile aynıdır ve (2^{c(G_n)})’in koşullu beklentisi

   [ E(2^{1 + c(G_{n-2})}) = 2 d_{n-2}. ]

2. Kenarın bir çevrimi kapatmaması koşuluyla:

   Bileşen sayısını etkilemeden incelenen üç düğümü tek bir düğümde birleştirebiliriz. Birleşmiş düğüm iki kullanılmamış stub devralır ve grafik artık her bölümde (n/2 - 1) düğüm bulunan iki parçalı bir yapıdadır. Dolayısıyla kalan grafiğin dağılımı yine (G_{n-2})’dir.

   Bu nedenle (2^{c(G)})’in koşullu beklentisi basitçe

   [ d_{n-2}. ]

Bu iki durum aşağıdaki yineleme bağıntısını verir

[ d_n = \frac{1}{n-1} \cdot 2 d_{n-2} + \left(1 - \frac{1}{n-1}\right) d_{n-2} = \left(1 + \frac{1}{n-1}\right) d_{n-2}. ]

Temel durum (d_0 = 1) ile birlikte yineleme çözülebilir ve değeri aşağıdaki eşitsizlikler kullanılarak sınırlandırılabilir

[ \ln(1+x) \le x \quad (x \ge 0) ]

ve

[ H_n := \sum_{i=1}^n \frac{1}{i} \le 1 + \ln n. ]

Bundan

[ d_n \le e^{\sqrt{n}}. ]

değeri elde edilir.

Theorem 10

(h_0, h_1 : S \rightarrow [n/2]) düzgün rastgele fonksiyonlar olsun. Aşağıdaki özelliği sağlayan bir (f : S \rightarrow {0,1}) fonksiyonunun var olma olasılığı

[ x \mapsto h_{f(x)}(x) + f(x) \cdot \frac{n}{2} ]

bijektif olduğunda

[ P(\exists f : \text{ori}(f)). ]

Lemma 7 uygulanırsa

[ E(#{f : \text{ori}(f)}) \ge 2^n e^{-n} \sqrt{2\pi n}. ]

Genel başarı olasılığını belirlemek için Theorem 8’e benzer şekilde ilerleriz ve

[ P(\exists f : \text{ori}(f)) = \frac{E(#{f : \text{ori}(f)})}{E(#{f : \text{ori}(f)} \mid \exists f : \text{ori}(f))}. ]

sonucunu elde ederiz.

Lemma 9 kullanıldığında

[ P(\exists f : \text{ori}(f)) \ge \frac{2^n e^{-n} \sqrt{2\pi n}}{e^{\sqrt{2n}}}. ]

Elde ettiğimiz sınır, düz ShockHash’e kıyasla (\sqrt{2}) katsayısı kadar daha iyidir; bu da beklenen bellek kullanımına ilişkin sınırı

[ \log_2(\sqrt{2}) = 0.5 ]

bit azaltır.

Ayrıca geri getirme veri yapısında birkaç ek bit daha tasarruf etmek mümkün olabilir çünkü (f)’nin anahtarların tam olarak yarısını 1’e eşlediği bilinmektedir. Yani tüm fonksiyonların yalnızca (1/\Theta(\sqrt{n})) oranındaki bir kısmı (f) olarak ortaya çıkabilir. Ancak burada bunu daha ayrıntılı incelemiyoruz.

6.5 Hash Function Pools

6.5.1 Notasyon ve Genel Bakış

İki parçalı ShockHash’i düz sürüme göre çok daha verimli hale getiren önemli bir unsur, adaylardan oluşan bir havuzdan hash fonksiyonlarını birleştirebilmemizdir. Bu sayede fonksiyonları birleştirmeden önce adayları filtrelemek mümkün olur.

Şimdi aday havuzundan iki hash fonksiyonunun tüm kombinasyonlarını test etmenin neden iki yeni fonksiyonu rastgele örneklemekle benzer başarı olasılığına sahip olduğunu analiz ediyoruz.

[ H := [n/2]^S ]

kümesi, (S)’den ([n/2])’ye giden tüm hash fonksiyonlarının kümesi olsun.

İki hash fonksiyonunu (l,r \sim U(H)) düzgün rastgele seçmek

[ P(PF(l,r)) = (e/2)^{-n} ]

sonucunu verir

(polinom çarpanları göz ardı edilerek).

Ayrıca promiscuous fonksiyonlar kümesini de ele alıyoruz:

[ H_{promisc} := { f \in H \mid |{ i \in [n/2] : |f^{-1}(i)| = 2 }| \ge 0.9 \cdot n/2 }. ]

Belirli bir (l) fonksiyonu için

[ C(l) := { r \in H \mid PF(l,r) } ]

ve

[ C^*(l) := C(l) \setminus H_{promisc}. ]

olarak tanımlayalım.

(X \subseteq H) kümesi için

[ |X| := \frac{|X|}{|H|}. ]

şeklinde tanımlarız.

Buna göre (|C(l)|), rastgele örneklenen bir hash fonksiyonunun (l) ile uyumlu olma olasılığıdır.

İlgilendiğimiz ana rastgele değişken

[ Z := \left| \bigcup_{i \in [k]} C(l_i) \right|. ]

olup, havuz için örneklenen hash fonksiyonlarına bağlıdır. (Z), rastgele seçilen bir hash fonksiyonunun havuzdaki ((l_i)_{i \in [k]}) fonksiyonlarından en az biriyle uyumlu olma olasılığıdır.

(Z)’nin

[(e/2)^{-n/2}.]

değerinin etrafında yoğunlaştığını göstereceğiz.

Çünkü her havuzda

[ k = (e/2)^{n/2} ]

adet hash fonksiyonu bulunduğundan, ((r_i)_{i \in [k]}) içinde uyumlu bir fonksiyon bulunma olasılığı sabit bir değere ulaşır.

Lemma 11

(2n) topu (n) kutuya bağımsız ve düzgün rastgele attığımızda, her kutunun tam olarak iki top alması olasılığı

[ p_n \le 5\sqrt{n} (2e^{-2})^n. ]

İspat

Topları her kutuya tam olarak iki tane gelecek şekilde yerleştirmek için (2n) topluk kümeden büyüklüğü 2 olan (n) altküme seçeriz. Bunun kaç farklı şekilde yapılabileceği çok terimli katsayıyla verilir

[ \binom{2n}{2,2,\ldots,2}. ]

Bu kombinasyonların her birinin olasılığı (n^{-2n})’dir. Dolayısıyla

[ p_n = \binom{2n}{2,2,\ldots,2} n^{-2n}. ]

Stirling yaklaşımı kullanıldığında

[ p_n \le \sqrt{4\pi n} (2e^{-2})^n e^{1/(24n)} \le 5\sqrt{n}(2e^{-2})^n. ]

Lemma 12

Lemma 12. n topu n/2 kutuya bağımsız ve düzgün rastgele attığımızda, kutuların %90’ından fazlasının tam olarak 2 top alması olasılığı (p_{90%})

[ p_{90%} \le 0.66^n. ]

İspat. Her birinin tam olarak 2 top alacağı (0.9 \cdot n/2) kutudan oluşan bir (A) kümesini ele alalım. Hangi kutuların tam olarak 2 top alacağı önemli değildir; dolayısıyla

[ \binom{n/2}{0.9,n/2} = \binom{n/2}{0.1,n/2} ]

farklı (A) kümesi seçimi vardır.

Tam olarak (2|A|) topun (A) içindeki kutulara düşmesi olasılığı

[ \binom{n}{0.1n} 0.1^{0.1n} 0.9^{0.9n}. ]

Bu koşul altında, bu (2|A|) topun (|A|) kutuya eşit şekilde dağılması olasılığı

[ p_{|A|} \le 5\sqrt{0.9,n/2},(2e^{-2})^{0.9,n/2} ]

olur (Lemma 11’e göre). Bunları bir araya getirirsek ve Lemma 4’ü uygularsak, (p_{90%}) için şu sınırı elde ederiz

[ p_{90%} \le \binom{n}{0.1n} (2e^{-2})^{0.9,n/2} 5\sqrt{0.45n}. ]

Basitleştirme sonrası

[ p_{90%} \le 0.66^n. ]

Lemma 13

Lemma 13. ((l_i)_{i \in [k]}) havuzundaki hash fonksiyonlarının hiçbirinin promiscuous olmaması olasılığı (1 - 0.77^n)’dir.

İspat. Her hash fonksiyonu (n) anahtarı grafikteki (n/2) düğüme eşler. Hash fonksiyonları rastgele örneklendiğinden bu süreç bir balls‑into‑bins modeli olarak ele alınabilir.

Lemma 12’yi uygulayabiliriz; bu lemma bir fonksiyonun promiscuous olma olasılığının

[ p_{90%} \le 0.66^n ]

olduğunu söyler.

Biz

[ k = (e/2)^{n/2} ]

adet hash fonksiyonundan oluşan bir havuz örnekliyoruz. Dolayısıyla hash fonksiyonlarımızdan en az birinin promiscuous olması olasılığı birlik sınırı kullanılarak üstten sınırlandırılabilir.

Düz ShockHash için, elde edilen grafiğin (G) bir pseudoforest olması olayını (PF(G)) ile incelemiş ve (\Pr(PF(G))) için sınırlar vermiştik. Bölüm 6.2’de grafiğin iki adımda ortaya çıkarılabileceğini gösterdik: önce her düğümün derecesini açığa çıkarırız, ardından bu stub’ları rastgele eşleştiririz.

Şimdilik düz ShockHash ile devam ederek düğümlerin derecelerine koşullayalım. (G)’deki düğümlerin dereceleri

[(d_1, \dots, d_n)]

olsun ve

[ p(d_1, \dots, d_n) := \Pr(PF(G) \mid \text{G grafiğinin düğümleri } d_1, \dots, d_n \text{ derecelerine sahiptir}) ]

koşullu başarı olasılığı olsun. Stub’lar rastgele eşleştirildiği için fonksiyon argümanlarının sırasının başarı olasılığı açısından önemli olmadığını unutmayın.

(B_n), (n) top ve (n/2) kutu içeren balls‑into‑bins sürecindeki dağılım olsun. Aşağıdaki lemmalarda (p(d_1, \dots, d_n))’nin ek özelliklerini vermeden önce fonksiyon hakkında basit bir gözleme bakalım:

[ \mathbb{E}{(d_1,\dots,d_n) \sim B{2n}}\big(p(d_1, \dots, d_n)\big) = \Pr(PF(G)) = (e/2)^{-n}. \tag{5} ]

Grafik (G), derece 1 olan düğümleri tekrar tekrar soyup sonunda yalnızca derece 2 olan düğümlerden oluşan (çevrimler oluşturan) bir grafik elde edebiliyorsak bir pseudoforest’tir. Soyma sırasında derece 1 olan bir düğümü alır ve kenarını rastgele bir stub’a kadar takip ederiz. Bu noktada üç olası sonuç vardır:

1. Kenar derece 1 olan bir düğüme gider. Bu durumda kenar sayısından fazla düğüm içeren bir bileşen bulmuş oluruz; yani kalan grafik bir pseudoforest olamaz.
2. Kenar derecesi (\ge 3) olan bir düğüme gider. Bu durumda hâlâ bir pseudotree olma ihtimali bulunan bir bileşenin alt ağacını soymuş oluruz. Artık grafikte bir adet daha az derece‑1 düğüm vardır. Bu durumda soyma işlemine başka bir derece‑1 düğüm ile devam ederiz.
3. Kenar derece 2 olan bir düğüme gider. Bu durumda yeni bir derece‑1 düğüm oluşur ve soyma işlemine aynı düğüm üzerinden devam edebiliriz.

Lemma 14

Lemma 14. Derecesi 2 olan düğümler başarı olasılığını etkilemez. Daha resmi olarak,

[ p(d_1, \dots, d_i, 2) = p(d_1, \dots, d_i). ]

İspat. Soyma süreci (3) durumuna ulaştığında, yani derece 2 olan bir düğüme bağlandığında, hemen bu düğüm üzerinden soyma işlemine devam edebiliriz. Bu işlem her zaman başarılıdır ve soyma sürecinin durmasına yol açmaz. Ardından bir düğüm eksilmiş olur ancak diğer tüm düğümlerin derecelerini etkilememiş oluruz. Bu nedenle daha ilginç olan (1) ve (2) durumlarına ulaşma olasılıkları birbirlerine göre aynı kalır.

Lemma 15

Lemma 15. Hash fonksiyonumuza karşılık gelen grafikte (b) adet derece‑1 düğüm varsa, (p) değeri (b) açısından üstel olarak küçüktür. Daha resmi olarak,

[ p(\underbrace{1, \dots, 1}{b}, d{b+1}, \dots, d_n) \le (7/8)^{b-1}. ]

İspat. Soyma sürecinde derece 2 olan tüm düğümleri göz ardı edebiliriz çünkü bunlar başarı olasılığını etkilemez (bkz. Lemma 14). Bu nedenle kalan düğümlere bakalım.

Eğer derece 1 olan düğümlerden birine bağlanırsak bir ağaç bulmuş oluruz. Bu da yapının başarısız olduğu anlamına gelir çünkü her bileşenin bir pseudotree olması gerekir, ağaç olması değil.

Ortalama derece 2 olduğundan, derecesi (\ge 3) olan düğümlerde en fazla (3b) stub bulunur.

Dolayısıyla derece 1 olan bir düğüme bağlanma olasılığı (derece 2 düğümleri üzerinden dolaylı bağlanma dahil)

[ \frac{b-1}{4b}. ]

olur.

Bunu tüm derece‑1 düğümler soyulana kadar yinelemeli olarak uygulayabiliriz. Bu da

[ p(\underbrace{1, \dots, 1}{b}, d{b+1}, \dots, d_n) \le \prod_{j=2}^{b} \left(\frac{7}{8}\right) = (7/8)^{b-1}. ]

sonucunu verir.

Bir hash fonksiyonunu promiscuous olarak adlandırırız eğer karşılık gelen (stub) grafiğinde düğümlerin %90’ından fazlasının derecesi 2 ise. Bu durumda çok fazla derece‑1 düğümü bulunamaz. Promiscuous hash fonksiyonları nadirdir; bu durum Bölüm 6.5.2’de gösterilmiştir.

Aşağıda, fonksiyonumuz promiscuous olmadığında uyumlu hash fonksiyonlarının sayısını sınırlandırıyoruz.

Lemma 16

Lemma 16. (l), (H \setminus H_{\text{promisc}}) kümesinden bir hash fonksiyonu ve ((d_1, \dots, d_{n/2})) buna karşılık gelen derece dizisi olsun. O zaman

[ p(d_1, \dots, d_{n/2}) \le (c_1)^{n/2} ]

olur; burada (c_1 \in (0,1)) sabit bir değerdir ve (n) yeterince büyüktür.

İspat. Derecesi (\ne 2) olan düğümlerin kümesi (X_{\ne 2}) olsun. Burada incelenen fonksiyonlar promiscuous olmadığından

[ |X_{\ne 2}| \ge 0.1 \cdot n/2. ]

Stub sayısı düğüm sayısının iki katı olduğundan (X_{\ne 2}) içindeki düğümler ortalama olarak 2 stub alır. Eğer düğümlerden biri 0 stub alırsa başarı olasılığı 0’dır. Aksi halde ortalamayı sağlamak için (X_{\ne 2}) içindeki düğümlerin en az yarısı tam olarak 1 stub almalıdır.

Dolayısıyla (l) en az

[ b = 0.05n/2 ]

adet derece‑1 düğüme sahiptir.

Lemma 15 uygulanır ve

[ c_1 > (7/8)^{0.05} ]

seçilirse ispat tamamlanır.

Şimdi tekrar iki parçalı ShockHash’e dönelim. Burada bize iki parçalı bir grafik (G) veren iki rastgele hash fonksiyonu (l) ve (r) vardır. İki bölümdeki düğümlerin dereceleri

[(d_1, \dots, d_{n/2}) \quad \text{ve} \quad (d'1, \dots, d'{n/2})]

olsun. (B_n)’nin (n) top ve (n/2) kutudan oluşan balls‑into‑bins sürecindeki dağılım olduğunu hatırlayın.

Şu şekilde tanımlarız:

[ q((d_1, \dots, d_{n/2}), (d'1, \dots, d'{n/2})) := \Pr(PF(G) \mid G \text{ grafiğinin derece dizileri } (d_1, \dots, d_{n/2}), (d'1, \dots, d'{n/2}) ). ]

Lemma 17

Lemma 17. Herhangi bir derece dizisi için

[ q((d_1, \dots, d_{n/2}), (d'1, \dots, d'{n/2})) \le p(d_1, \dots, d_{n/2}), p(d'1, \dots, d'{n/2}). ]

İspat. Yapılandırma modelindeki soyma sürecinin, düğümünün tek kalan stub’ı olan stub’ları yinelemeli olarak eşleştirdiğini hatırlayın. Bu nedenle süreç, sırayla yalnız bir stub’ın ve rastgele bir stub’ın kaldırılması (ve buna karşılık gelen kenarın çıkarılması) olarak anlaşılabilir. Başarısızlık, rastgele kaldırılan stub’ın yalnız olması durumunda gerçekleşir.

İki parçalı durumda soldaki ve sağdaki yalnız stub’ları sırayla seçersek, her bölüm içinde yalnız bir stub kaldırma ile rastgele bir stub kaldırma arasında dönüşümlü bir süreç yürütmüş oluruz. Dolayısıyla özünde iki bölüm içinde soyma sürecini ayrı ayrı çalıştırmış oluruz.

Bu, iki parçalı grafiğin bir pseudoforest olma olasılığının, iki indüklenmiş grafiğin pseudoforest olma olasılıklarının çarpımına eşit olduğunu düşündürür. Ancak küçük bir asimetri vardır: ilk bölümde yalnız bir stub kaldırarak başlarız, ikinci bölümde ise rastgele bir stub kaldırarak başlarız. Bu durum ikinci bölüm için başarısızlık olasılığını biraz artırır. Lemmadaki eşitsizlik bu farkı hesaba katar.

Hem (p(d_1, \dots, d_{n/2})) hem de (|C(l)|), bir hash fonksiyonu adayının kalitesini değerlendirmek için yöntemler sunar. Ancak aralarında önemli bir fark vardır. (|C(l)|) iki parçalı durumda uyumlu ortakları ölçerken, (p(d_1, \dots, d_{n/2})) grafiğin kendi kendine bağlandığı durumu ele alır.

Örneğin yalnızca derece 2 düğümlere yol açan bir hash fonksiyonu adayı

[ p(2, \dots, 2) = 1 ]

özelliğine sahiptir; ancak

[|C(l)| < 1]

çünkü böyle bir fonksiyon tüm çıktı değerlerine ulaşmayan ortaklarla uyumlu değildir.

Lemma 18

Lemma 18. Her (l \in H \setminus H_{\text{promisc}}) için

[ |C(l)| < (e/2)^{-n/2} (c_1)^{n/2} ]

olur; burada (c_1 \in (0,1)) sabit bir değerdir ve (n) yeterince büyüktür.

İspat. ((d_1, \dots, d_{n/2})) değerleri (l)’nin derece dizisi olsun. O hâlde

[ |C(l)| = \Pr(PF(l,r)) = \mathbb{E}{(d'1,\dots,d'{n/2})\sim B_n} \big[q((d_1,\dots,d{n/2}), (d'1,\dots,d'{n/2}))\big]. ]

Lemma 17’ye göre,

[ \le \mathbb{E}{(d'1,\dots,d'{n/2})\sim B_n} \big[p(d_1,\dots,d{n/2}) p(d'1,\dots,d'{n/2})\big]. ]

Dolayısıyla

[ = p(d_1,\dots,d_{n/2}) \mathbb{E}_{(d'1,\dots,d'{n/2})\sim B_n} \big[p(d'1,\dots,d'{n/2})\big] \le (c_1)^{n/2} (e/2)^{-n/2}. ]

[ Z = \left|\bigcup_{i \in [k]} C(l_i)\right| ]

rastgele seçilen bir fonksiyonun havuzumuzdaki bir fonksiyonla uyumlu olma olasılığı olsun. Ayrıca

[ C^*(l) = C(l) \setminus H_{\text{promisc}}. ]

ifadesini hatırlayalım.

(Z)’yi doğrudan sınırlayamadığımız için üç yardımcı rastgele değişken tanımlıyoruz:

• (Z^*)
• (\hat{Z})
• (D)

Bu değişkenler (Z) üzerinde sınırlar elde etmemizi sağlar.

Lemma 21

Lemma 21. (D) ve (\hat{Z}) yukarıda tanımlandığı gibi olsun. O hâlde

[ \mathbb{E}(D) \le (c_2)^{n/2} \mathbb{E}(\hat{Z}) ]

bazı (c_2 \in (0,1)) sabiti ve yeterince büyük (n) için geçerlidir.

İspat. Rastgele seçilmiş hash fonksiyonları üzerindeki beklentiler kullanılarak ve Lemma 18 uygulanarak

[ \mathbb{E}(D) \le (c_1)^{n/2} (e/2)^{-n/2} ]

sınırı elde edilir; bu da belirtilen sonucu verir.

Lemma 22

Lemma 22. (Z^*, \hat{Z}) ve (D) yukarıda tanımlandığı gibi olsun. O hâlde

[ \Pr(\hat{Z} \ge \mathbb{E}(\hat{Z})/2) > 1 - (c_3)^n ]

bazı (c_3 \in (0,1)) sabiti ve yeterince büyük (n) için geçerlidir.

İspat. İspat, bağımsız ve ortalaması sıfır olan rastgele değişkenler için Bernstein eşitsizliğini kullanır. Şöyle tanımlayalım:

[ V_i = \mathbb{E}(|C^(l_i)|) - |C^(l_i)|. ]

(|V_i|) ve (\mathbb{E}(V_i^2)) değerleri Lemma 18 kullanılarak sınırlandıktan ve Bernstein eşitsizliği uygulandıktan sonra iddia edilen yoğunlaşma sınırı elde edilir.

Lemma 23

Lemma 23. (Z^*, \hat{Z}) ve (D) yukarıda tanımlandığı gibi olsun. O hâlde

[ \Pr(Z^* < \mathbb{E}(\hat{Z})/4) \le (c_4)^n ]

bazı (c_4 \in (0,1)) sabiti için geçerlidir.

İspat. Gözlem 20 ve birleşim sınırı kullanılarak

[ \Pr(Z^* < \mathbb{E}(\hat{Z})/4) \le \Pr(\hat{Z} < \mathbb{E}(\hat{Z})/2) + \Pr(D \ge \mathbb{E}(\hat{Z})/4). ]

Birinci terim Lemma 22 aracılığıyla, ikinci terim ise Markov eşitsizliği ve Lemma 21 birlikte kullanılarak sınırlandırılır. Böylece belirtilen sınır elde edilir.

[ (c_3)^n + (c_2)^{n/2}/4 \le (c_4)^n \text{ bazı } c_4 \in (0,1) \text{ ve yeterince büyük } n \text{ için.} ]

6.5.5 ((r_i)_{i\in[k]}) Havuzu ile Birleştirme

Artık önceki sonuçları birleştirebiliriz; bu da bize (k) büyüklüğünde bir havuz kullanıldığında iki parçalı ShockHash’in başarı olasılığını verir. (\Pr(\text{success})) ile, havuzlarımızda (l_i) ve (r_j) olmak üzere uyumlu bir hash fonksiyon çifti bulunma olasılığını ifade ediyoruz; burada (i, j \in [n/2]).

Lemma 24

(Z) yukarıda tanımlandığı gibi olsun. O hâlde

[ \Pr(\text{success} \mid Z = z) = 1 - (1 - z)^k. ]

İspat.

[ \Pr(\text{success} \mid Z = z) = \Pr(\exists i \in [k] : r_i \in C(l_j)) ]

[ = \Pr_{p_1,\ldots,p_k \sim \text{Ber}(z)}(\exists i \in [k] : p_i = 1) = 1 - (1 - z)^k. ]

İspatın büyük kısmı zaten tamamlandı. Sadece önceki lemanın önkoşulunun sağlanma olasılığını hesaba katmamız gerekiyor.

Theorem 25

((l_i){i\in[k]}) ve ((r_i){i\in[k]}) olmak üzere büyüklüğü

[ k = (e/2)^{n/2} ]

olan iki havuz alalım; bu havuzlar rastgele örneklenmiş hash fonksiyonları içerir. O hâlde havuzlarda (l_i) ve (r_j) ((i, j \in [k])) olmak üzere iki hash fonksiyonunun bulunma olasılığı, öyle ki (PF(l_i, r_j)) değeri yeterince büyük (n) için (> 0.17) olur.

[ \Pr(\text{success}) \ge \Pr(\text{success} \land Z \ge E(\hat Z)/4) ]

[ = \Pr(\text{success} \mid Z \ge E(\hat Z)/4) \Pr(Z \ge E(\hat Z)/4) ]

[ \ge \Pr(\text{success} \mid Z \ge E(\hat Z)/4) \Pr(Z^* \ge E(\hat Z)/4) ]

[ = \sum_z \Pr(\text{success} \mid Z = z) \Pr(Z = z \mid Z \ge E(\hat Z)/4) \Pr(Z^* \ge E(\hat Z)/4) ]

[ = \sum_z (1 - (1 - z)^k) \Pr(Z = z \mid Z \ge E(\hat Z)/4) \Pr(Z^* \ge E(\hat Z)/4) ]

[ \ge (1 - (1 - E(\hat Z)/4)^k) \Pr(Z^* \ge E(\hat Z)/4) ]

Lemma 23 ve 19 kullanılarak

[ 1 - (1 - (e/2)^{-n/2})^k > 1 - e^{-1/5}. ]

Dolayısıyla

[ \Pr(\text{success}) \ge (1 - e^{-1/5})(1 - (c_4)^n) > 0.18 ]

yeterince büyük (n) için geçerlidir.

Bu, aday fonksiyon havuzundan hash fonksiyonlarının birleştirilmesine ilişkin ispatı tamamlar. Havuz büyüklüğünü

[ k = (e/2)^{n/2} ]

olarak seçmenin, havuzlarda iki uyumlu fonksiyon bulunması için sabit bir olasılık sağladığını gördük. Ayrıca gerçek uygulamamızın iki sabit büyüklükte havuz yerine tek bir büyüyen havuz kullandığını tekrar hatırlatalım. Bu nedenle başlangıçtaki havuz büyüklüğü yeterli olmazsa yapıyı yeniden denememiz gerekmez; havuza daha fazla fonksiyon eklemeye devam edebiliriz.

ShockHash farklı hash fonksiyonu tohumlarını dener; bu da rastgele grafikler üretmeye eşdeğerdir. Rastgele bir grafiğin bir pseudoforest olma olasılığı verildiğinde, ShockHash’in bir MPHF bulmak için denemesi gereken beklenen grafik sayısını belirlemek kolaydır. Bu da doğrudan ShockHash’in bellek kullanımı ve oluşturma süresine götürür; bunu aşağıdaki teoremde ifade ediyoruz.

Theorem 26

(n) anahtarı ([n]) aralığına eşleyen bir ShockHash minimal perfect hash fonksiyonu, beklenti olarak

[ \log_2(e)n + O(\log n) ]

bit bellek gerektirir ve beklenen oluşturma süresi

[ O((e/2)^n n) ]

şeklindedir.

İspat. Theorem 8’den, grafiğin pseudoforest olma olasılığının

[ \ge (e/2)^{-n} e^{-1}/\sqrt{\pi} ]

olduğunu biliyoruz.

Bu grafikleri eşit olasılıkla rastgele üretiyoruz; dolayısıyla denenmesi gereken beklenen tohum sayısı

[ \le (e/2)^n e/\sqrt{\pi}. ]

Bellek kullanımı, retrieval veri yapısı için gereken (n + o(n)) bit ile hash fonksiyon indeksini saklamak için gereken bitlerin toplamıdır:

[ E(\log_2(\text{seed value})) ]

[ \le \log_2(E(\text{seed value})) \le \log_2\left((e/2)^n e/\sqrt{\pi}\right) ]

[ = \log_2(e)n - n + O(1). ]

(*) ile işaretlenen adımda Jensen eşitsizliği [34] ve (\log_2)’nin konkav olduğu gerçeği kullanılır.

Böyle bir tohuma karşılık gelen (2^n) fonksiyondan en az birinin geçerli olup olmadığını belirlemek için Bölüm 4’te anlatıldığı gibi bağlı bileşenleri bulan bir algoritma kullanılabilir. Bu işlem her tohum için doğrusal zaman alır; dolayısıyla toplam oluşturma süresi

[ O((e/2)^n n) ]

olur.

Retrieval veri yapısının kurulması daha sonra doğrusal zamanda mümkündür [19] ve yalnızca bir kez gerçekleşir; bu nedenle burada asimptotik zaman açısından önemsizdir.

Basit brute-force yaklaşımına geri dönersek, onun

[ \frac{e^n}{\sqrt{2\pi n}} ]

beklenen denemelerinin her biri (n) hash fonksiyonu değerlendirmesi gerektirir; bu da

[ O(e^n \sqrt{n}) ]

şeklinde bir oluşturma süresine yol açar.

Şimdi Theorem 26’da gösterildiği gibi ShockHash

[ O((e/2)^n n) ]

zaman gerektirir.

Bu da ShockHash’i önceki en iyi yöntemden yaklaşık (2^n) kat daha hızlı yapar. Ref. [9]’daki gözlemler doğrultusunda, rotation fitting kullanan ShockHash’in hash fonksiyonu değerlendirmelerinin sayısını ek olarak (n) katsayısı kadar daha azaltacağını ve bellek ek yükünün sıfıra yaklaşacağını öne sürüyoruz. Aşağıdaki teoremde iki parçalı sürümün ortaya çıkan oluşturma süresi ve bellek tüketimini veriyoruz.

Theorem 27

İki parçalı bir ShockHash minimal perfect hash fonksiyonu beklenti olarak

[ \log_2(e)n + O(\log n) ]

bit bellek gerektirir ve beklenen oluşturma süresi

[ O(1.166^n). ]

İspat. Bir perfect hash fonksiyonu bulmadan önce beklenti olarak

[ (e/2)^n e/\sqrt{n} ]

adet aday ((h_0, h_1)) çiftini test etmemiz gerektiğini biliyoruz. Bölüm 5’te açıklandığı gibi, iki hash fonksiyonunu bağımsız örneklemek yerine bir hash fonksiyonu havuzu kullanıyor ve bunların tüm kombinasyonlarını test ediyoruz.

Theorem 25, havuz büyüklüğünü

[ k = (e/2)^{n/2} \approx 1.166^n ]

olarak seçersek sabit bir başarı olasılığı elde ettiğimizi gösterir. Bu noktaya kadar bu durum oluşturma süresini asimptotik olarak iyileştirmez; çünkü (k^2) kombinasyonun tamamının test edilmesi gerekir. Ancak tüm adayları birleştirmek yerine, aday havuzu oluşturulurken bunları doğrudan filtreleyebiliriz.

Filtre, düz ShockHash’te olduğu gibi oldukça etkilidir: büyüklüğü (n/2) olan bir bölmede (n) hash değerinin tüm çıktı konumlarını vurma olasılığı

[ \Theta(0.836^{n/2}) ]

şeklindedir [56]. Bu da beklenti olarak yalnızca

[ ((e/2)^{n/2} \cdot 0.836^{n/2})^2 = (e/2 \cdot 0.836)^n \approx 1.136^n ]

adet hash fonksiyonu çiftini dikkate aldığımız anlamına gelir. Dolayısıyla oluşturma süresi

[ \max{1.166^n, 1.136^n} ]

ile sınırlıdır.

Bu değerlerin zaten yukarı doğru yuvarlandığını unutmayın; bu nedenle polinom faktörler baskın değildir.

İki parçalı ShockHash’in bellek tüketimine bakıldığında, her biri beklenen değeri (\le k) olan iki tohum kodlamamız gerekir. Jensen eşitsizliği ve Theorem 26’daki retrieval veri yapısı aynı şekilde kullanılarak sonuçtaki bellek kullanımı elde edilir. Analizde polinom faktörleri bastırmış olmamız (O(\log n)) terimi içinde görünmez hâle gelir.

ShockHash önemli hız artışları gösterse de tek başına hâlâ üstel çalışma süresi gerektirir. Giriş bölümünde belirtildiği gibi, gerçek dünyadaki MPHF oluşturma yöntemleri genellikle tüm giriş kümesi için doğrudan bir fonksiyon aramaz. Bunun yerine büyüklüğü (N) olan girişi bölümlere ayırır ve daha küçük alt problemler (büyüklüğü (n)) üzerinde arama yapar.

Bu bölümde giriş kümesinin daha sonra ShockHash’i bir yapı taşı olarak kullanmadan önce nasıl verimli biçimde bölümlere ayrılabileceğine ilişkin ayrıntılar veriyoruz.

İlk seçenek, ShockHash’i yüksek derecede bellek verimli RecSplit çerçevesinde (bkz. Bölüm 2) bir temel durum olarak kullanmak ve ShockHash-RS elde etmektir. RecSplit’in genel yapısını koruruz. Yalnızca yapraklarda brute-force yerine ShockHash kullanırız. Anahtarların hash fonksiyonu indekslerine eşlemesini tek bir büyük retrieval veri yapısında saklarız. Son olarak tüm yapraklar işlendikten sonra tüm (N) giriş için 1 bitlik retrieval veri yapısını oluştururuz.

Fanouts

RecSplit, bölmeler ve bijeksiyonlar arasındaki zorluk dengesini kurmaya çalışır. ShockHash bijeksiyonların performansını önemli ölçüde iyileştirir ancak bölmelerin nasıl hesaplandığını değiştirmez. Bu makalede yalnızca bijeksiyonlara odaklanıyoruz.

Bölmeler ve bijeksiyonlar arasında yapılan iş miktarını dengelemek için RecSplit makalesindeki aynı teknikleri kullanarak bölme parametrelerini uyarlamamız gerekir. RecSplit makalesi son iki bölme seviyesi için optimal fanout değerlerini kanıtlar ve kullanır:

• (\lceil 0.35n + 0.5 \rceil)
• (\lceil 0.21n + 0.9 \rceil)

(bkz. [21, Section 5.4]).

ShockHash-RS için bu formülleri uyarlayabilir ve şu fanout değerlerini elde edebiliriz:

• (\lfloor 0.10n + 0.5 \rfloor)
• (\lfloor 0.073n + 0.9 \rfloor)

Ancak ön deneyler bunun pratikte optimal olmadığını gösterir. ShockHash o kadar hızlıdır ki bölmelere harcanan ek zaman fayda sağlamaz. Deneysel olarak en alt bölme seviyesini 4, ikinci en alt seviyeyi ise 3 olarak ayarlamanın pratikte çok daha iyi sonuçlar verdiğini görüyoruz. Ayrıca daha hızlı fakat bellek açısından verimsiz yapılandırmalar sağlamak için yaprak boyutu (n \le 24) seçildiğinde tüm fanout değerlerini 2 olarak belirliyoruz.

7 Bölümlendirme

7.1 ShockHash-RS = ShockHash + RecSplit

Giriş anahtarlarını bölmenin ek bir yolu k-perfect hashing kullanmaktır. Minimal k-perfect hash fonksiyonu (N) anahtarı (N/k) çıktı değerine eşler ve her çıktı değeri tam olarak (k) kez vurulur ((N)’in (k)’ya bölünebildiği varsayımıyla). Bunun dış bellek veri yapılarında uygulamaları vardır [36,37] ve mevcut yapılar bulunmaktadır [4].

ShockHash’i k-perfect hashing ile birleştirme fikri basittir ve ShockHash-RS’te yaptığımıza benzer. İki adımlı bir süreç uygularız:

1. Bir k-perfect hash fonksiyonu belirlemek.
2. Her çıktı değerine çarpan (k) anahtar için küçük ShockHash veri yapıları oluşturmak.

ShockHash-RS’ten farklı olarak burada tüm temel durumlar aynı boyuttadır; bazıları (n)’den küçük olmaz.

Bumped k-Perfect Hashing

Hızlı sorgulara odaklanan ve yine de nispeten küçük bellek tüketimini koruyan yeni bir k-perfect hash fonksiyonunu kısaca açıklıyoruz.

(N) anahtarı alıp bunları rastgele ve eşit olasılıkla

[ \gamma N/k ]

adet kovaya hash’leyelim; burada (\gamma \in (0,1]). (\gamma < 1) seçerek kovaları aşırı yükleriz; böylece çoğu kovanın en az (k) anahtar almasını sağlarız. Deneylerde (\gamma = 0.9) kullanıyoruz.

Taşan kovalar, her anahtar için bir fingerprint belirlenerek ele alınır. Her kova

[ \log_2(k) ]

bit kullanarak bir eşik değeri saklar; bu değer kovadan hangi anahtarların bumped edileceğini belirtir. Anahtarların bir eşik değerine göre kovadan çıkarılması fikri bumped ribbon retrieval (BuRR) [19] yönteminden esinlenmiştir. Separator hashing [31] benzer bir fikir kullanır ancak anahtarları tamamen çıkarmadan ve yalnızca minimal olmayan perfect hash fonksiyonlarını destekleyecek şekilde.

Bumped anahtarlar için aynı veri yapısının ikinci seviyesini kullanır ve bunları kalan

[ (1-\gamma)N/k ]

kovaya eşleriz.

Son olarak ikinci seviyede hâlâ bumped edilen az sayıda anahtar kalabilir. Bunları minimal perfect hash fonksiyonu kurarak numaralandırırız. Uygulamamızda ShockHash-RS kullanıyoruz. Bu MPHF, çıktı aralığındaki tüm boş konumları saklayan Elias–Fano kodlu bir diziyi [20,23] indeksler.

Bu tekniğin avantajı, çoğu sorgunun yalnızca şunları gerektirmesidir:

• eşik değerleri dizisine tek erişim
• anahtarın eşik değeri ile karşılaştırılması

Küçük bir kısmı ikinci seviyeyi değerlendirmek için iki erişim gerektirir ve çok küçük bir bölümü açık yeniden eşleme gerektirir.

ShockHash-Flat

Bumped k-perfect hash fonksiyonundan, ShockHash-RS’e göre çok daha düz bir yapıya sahip bir MPHF türetiyoruz. Ağaç yapısında ilerlemek yerine çoğu giriş anahtarı için eşik değeri ile basit bir karşılaştırma yapılır.

Genellikle hem eşik hem de kovanın ShockHash tohumu erişilmesi gerektiğinden, ShockHash-Flat eşikleri ve ShockHash tohumlarını iç içe geçmiş bir yerleşimde saklar.

Havuzdaki her tohum, izole anahtarların bir bit vektörünü saklar; bu (I_{s_i}) ile gösterilir. Bir tohum kombinasyonu yalnızca hiçbir anahtarın her iki bölümde de izole olmaması durumunda çalışabilir; yani

[ I_{s_i} \cap I_{s_j} = \varnothing. ]

Bu durum bit işlemleri kullanılarak verimli biçimde kontrol edilebilir. Filtre geçildiğinde ancak o zaman tam yönlendirilebilirlik kontrolü yapılır.

Bir sonraki bölümde ShockHash’in varyantlarını ve uygulama ayrıntılarını açıklıyoruz. Bölüm 8.1’de önce bit-paralel filtre kullanarak pratikte önemli iyileştirmeler elde etmenin nasıl mümkün olduğunu anlatıyoruz. Ardından Bölüm 8.2 ve 8.3’te hash fonksiyonu adaylarını daha verimli üretmek için iki teknik açıklıyoruz: rotation fitting [9] ve quad split.

Eşit olmayan giriş boyutları (n) ile iki parçalı ShockHash kullanmak için yalnızca küçük değişiklikler gerekir; bunları Bölüm 8.4’te açıklıyoruz. Daha sonra Bölüm 8.5’te pratik uygulama hilelerine devam ediyor ve son olarak Bölüm 8.6’da paralelleştirme için fikirleri tartışıyoruz.

5. Bölümde, grafiği iki parçalı hâle getirmenin hash fonksiyonu adaylarının verimli biçimde filtrelenmesini nasıl mümkün kıldığını zaten açıklamıştık. Bir sonraki bölümde, tohumları filtrelemenin ek bir yolunu açıklıyoruz. Bipartite ShockHash, örten (surjective) hash fonksiyonu adaylarından oluşan bir küme üretir ve ardından yönlendirilebilirlik açısından tüm kombinasyonları test eder. Ek bir filtre kullanarak bu yönlendirilebilirlik testini hızlandırabiliriz.

Fikir, bir anahtarın bir konuma eşlenen tek anahtar olduğu duruma bakmaktır. Bu anahtara, o hash fonksiyonu tohumu için izole diyoruz. Daha resmi olarak, bir x anahtarı, bir h hash fonksiyonu adayı kullanıldığında izole ise

{y ∈ S | h(x) = h(y)} = {x}.

Eğer bir anahtar her iki aday hash fonksiyonunda da izole ise, grafik terminolojisinde bu durum iki düğüm ve bir kenardan oluşan bağlı bir bileşene karşılık gelir. Nihai grafikteki her bağlı bileşenin aynı sayıda düğüm ve kenara sahip olması gerektiğinden, bu durumda yönlendirilebilirlik için tam testi gerçekleştirmeye gerek kalmaz.

Her tohum için, hangi anahtarların izole olduğunu gösteren bit desenleri belirleyebiliriz. Ardından tohum kombinasyonları, bit desenlerinin ortogonal olup olmadığını kontrol eden basit bit-paralel işlemler kullanılarak elenebilir. Burada kullanılan bit desenlerinin çıktı konumlarına değil, girdi anahtarlarına (ve dolayısıyla boyutunun n olduğuna) karşılık geldiğine dikkat edin. Şekil 9 süreci göstermektedir.

Bir anahtar, bir bölümde izoledir eğer başka hiçbir anahtar onun konumuna hashlenmiyorsa; bu durumun olasılığı

(1 − 1/(n/2))^(n−1) → e^(−2).

Bir tohum kombinasyonu, her iki bölümde de izole olan hiçbir anahtar içermiyorsa filtreden geçer. Bu yaklaşık olarak

(1 − e^(−4))^n ≈ 0.98^n,

olduğundan, filtre tohum kombinasyonlarının büyük çoğunluğu için tam kontrolü yapmaktan kaçınmayı mümkün kılar. Filtreyi her iki fonksiyonun da örten olduğu durum koşuluyla uyguladığımızı unutmayın; bu durum filtrenin yalnızca daha etkili olmasını sağlar.

Bu yöntemi kuramsal açıdan ilginç kılan şey, burada filtreleme konusunda daha da akıllı davranabilmemizdir. Daha önce belirtildiği gibi, eğer hash fonksiyonlarından biri bir konumda izole bir anahtara sahipse, aynı konumda izole anahtarı olan diğer tüm hash fonksiyonlarıyla test etmeyi atlayabiliriz. Tüm aday hash fonksiyonlarını, izole anahtarlara dayalı bir ikili trie veri yapısında düzenleyebiliriz. Yeni bir aday hash fonksiyonunu test etmek artık ağacı dolaşmaktan ibarettir. Kuramsal olarak bu, oluşturma süresinde ek üstel iyileşmeler sağlar. Ancak ön deneyler, pratikte kullandığımız n değerleri için bunun faydalı olmadığını göstermektedir.

8.2 Rotation Fitting

Mükemmel hash fonksiyonları için kaba kuvvet aramasını hızlandırmaya yönelik bir teknik rotation fitting'dir [9] (bkz. Bölüm 2). Aynı fikir ShockHash içinde de aramayı hızlandırmak için kullanılabilir.

Anahtarları, sıradan ve tohumsuz 1‑bitlik bir hash fonksiyonu kullanarak iki kümeye dağıtırız. Ardından her iki kümede de vurulan çıktı değerlerinin bit maskesini belirleriz. Yönlendirilebilirliği kontrol etmeden önce kullandığımız bit maskesi filtresinde olduğu gibi (bkz. Bölüm 4), yalnızca her iki maskenin mantıksal OR işlemi tüm bitleri 1 yapıyorsa tohumu daha yakından test etmek anlamlıdır.

Şimdi bit maskelerinden birini döngüsel olarak döndürüp tekrar denersek, her anahtarı yeniden hashlemek zorunda kalmadan tüm çıktı değerlerinin vurulması için temelde yeni bir şans elde ederiz. Daha sonra anahtarları döndürme mesafesini hash fonksiyonu tohumunun bir parçası olarak ele alırız. Bu, ikinci kümenin tüm hash değerlerine n modunda bir toplama işlemine karşılık gelir. Ref. [9]'da olduğu gibi bunun hash fonksiyonu değerlendirmelerinin sayısını n kat azaltacağını, buna karşılık alan ek yükünün sıfıra yaklaşacağını varsayıyoruz.

Bipartite ShockHash için rotation fitting de uygulanabilir, ancak biraz farklı bir şekilde. İki parçalı grafiğin bölümlerinden birini kendi içinde döndürmek yararlı değildir çünkü izomorfik grafikler üretir. İki bölümü birbirine döndürmek ise iki parçalı koşulu ihlal eder ve böylece hash fonksiyonu havuzlarının kullanımını engeller.

Bunun yerine rotation fitting'i, her bölüm içinde tohum adayları bulmak için kullanabiliriz. Daha spesifik olarak, bir bölüm için tohum adayları ararken anahtarları tohumsuz bir 1‑bit hash fonksiyonu kullanarak iki alt kümeye dağıtırız. Ardından ek hash fonksiyonu adayları elde etmek için kümelerden birini (n/2 modunda) döndürebiliriz. Her döndürme, yazmaçlarda gerçekleşebilen basit bit kaydırmaları kullanılarak örtenlik açısından test edilebilir. Pratikte bu, daha az hash fonksiyonu değerlendirilmesi gerektiği için oluşturma süresini önemli ölçüde iyileştirir. Ancak bir sonraki bölümde açıklanan quad split tekniği üstel hızlanmalar bile sağlayabilir.

8.3 Quad Split

Oluşturma sürecinde baskın zaman maliyeti hash fonksiyonu adaylarının değerlendirilmesine harcanır (bkz. Teorem 27), bu nedenle iyileştirmeler için bu adıma bakmak doğaldır. Bipartite ShockHash için quad split tekniği, örten tohum adaylarını bulmak için harcanan süreyi azaltır. Temelde bipartite ShockHash fikrini aynı veri yapısının başka bir seviyesinde uygular.

Rotation fitting'de olduğu gibi, girdi kümesini sabit bir 1‑bit hash fonksiyonu kullanarak S_A ve S_B olmak üzere iki kümeye ayırırız. Artık bu iki kümeyi bağımsız hash fonksiyonları kullanarak hashleyebiliriz. Özellikle, her iki kümeye bazı hash fonksiyonlarının atanmasına ilişkin tüm kombinasyonları test edebiliriz. Bu, hash fonksiyonu değerlendirmelerinin sayısını önemli ölçüde azaltır.

Bir i tohumu için, h_i(S_A) ve h_i(S_B) sırasıyla S_A ve S_B alt kümelerinin hash fonksiyonu çıktı değerleri kümelerini göstersin. S_A için bir i tohumu, S_B için bir j tohumu ile birlikte kullanılabilir eğer

h_i(S_A) ∪ h_j(S_B) = [n/2].

h_i(S_A) ve h_i(S_B) değerlerini çıktı değerlerini gösteren bit vektörleri olarak saklayarak, bu uyumluluk kontrolü basit ve verimli bir OR işlemine dönüşür. Bu nedenle quad split tekniğinde, örten bir tohum kombinasyonunu hızlı biçimde aramayı mümkün kılmak için her hash fonksiyonu tohumu bu bit vektörü ile işaretlenir. Bu süreç Şekil 10'da gösterilmiştir.

Şekil 10. Quad split içinde ek filtreleme fırsatları. Filtreleme yapmadan tüm tohumların bir havuzunu oluştururuz ancak her tohumu, hash fonksiyonu çıktı değerlerini içeren bir bit vektörü ile işaretleriz. Daha sonra iki tohumu birleştirerek bir bölüm için bir tohum oluştururuz. Örtenlik bit işlemleri kullanılarak verimli biçimde kontrol edilebilir. Bu nedenle ortaya çıkan tohum, dört tohumdan oluşan bir demettir—anahtarların her yarısı ve her bölüm için bir tane. Uygulamamızda ayrıca izole anahtar filtresini de üzerine ekliyoruz (bkz. Bölüm 8.1 ve Şekil 9).

Bölüm 8.1'de açıklanan izole anahtar filtresinde olduğu gibi, tüm kombinasyonları test etmekten kaçınmak için yine bir trie yapısı kullanabiliriz. Bunun oluşturma süresinde üstel iyileşmeler sağlayabileceğini düşünüyoruz ve bu, gelecekteki çalışmalarda uygulanabilir. Quad split, izole anahtar filtresinden bağımsızdır; dolayısıyla her iki optimizasyonu birlikte kullanabiliriz.

Birleştirilmiş tohumu kodlamak için yine bir eşleme fonksiyonu kullanırız. ShockHash'teki bipartite trie'lerin aksine, hash fonksiyonları yer değiştiremez, dolayısıyla bir tohumun diğerinden büyük olduğunu varsayamayız. Bu nedenle daha genel bir eşleme fonksiyonuna ihtiyaç duyarız. Burada en uygun eşleme fonksiyonu Szudzik’in eşleme fonksiyonudur (bkz. Bölüm 2); bu fonksiyon, tüm k ∈ ℕ için, [k] × [k] içindeki tüm çiftleri saydıktan sonra k'den büyük sayıları içeren çiftlere geçer. Bu, bir sonraki hash fonksiyonunu değerlendirmek zorunda kalmadan önce önceki hash fonksiyonlarının tüm kombinasyonlarını test edebileceğimiz anlamına gelir. Uygulamamızda, hash fonksiyonu kombinasyonlarını eşleme fonksiyonunun değerine göre doğrusal sırada denemeye dikkat ediyoruz.

Girdi anahtarlarının sayısı n tek olduğunda da desteklemek için iki parçalı özelliği gevşetebiliriz. Fikir şudur: çıktı değeri ⌈n/2⌉ her iki hash fonksiyonu tarafından da vurulabilir, ancak her biri tarafından yarı olasılıkla. İki yarı birleştirildiğinde bu değer diğer tüm çıktı değerleriyle aynı olasılığı elde eder. Örtenlik için aday hash fonksiyonlarını filtrelerken ilgili bitin göz ardı edilmesi gerekir—bir tohum adayı bu bit ayarlanmış olsun ya da olmasın geçerli olabilir.

Şimdi, hem sol hem de sağ kısım için tek bir havuzdan hash fonksiyonları kullanabilmek amacıyla sağ kısımda kullanılan fonksiyonları yansıtmak zorundayız. Bir görselleştirme için Şekil 11'e bakın.

Bir sonraki bölümde, oluşturma sürecimizi pratikte daha da hızlandırmak için eklediğimiz uygulama tekniklerini açıklıyoruz.

Orientability Check

Verilen bir grafiğin bir pseudoforest olup olmadığını belirlemek, bağlı bileşenler algoritması kullanılarak doğrusal zamanda gerçekleştirilebilir. Ancak bu, bir grafik veri yapısı oluşturmak için önemli ek yükler getirir. Bundan kaçınmak için uygulamamız, neredeyse doğrusal zamanlı artımlı cuckoo hash tablosu oluşturma yöntemini kullanır.

Bunun için graf düğümlerini temsil eden bir dizi tutarız. Bir anahtar eklemek için her iki hash fonksiyonu değerinin XOR'unu hesaplarız ve bunu iki aday dizi hücresinden birine yerleştirmeye çalışırız. Eğer hücre zaten başka bir anahtar içeriyorsa, eski anahtarı çıkarır ve diğer aday konumunu kullanarak yeniden yerleştiririz; bu konumu XOR işlemi sayesinde verimli biçimde elde edebiliriz. Bu fikir cuckoo hashing içinde XOR trick olarak da bilinir. Bir döngü tespit ettiğimiz anda ekleme işlemini durdururuz.

Partial Hash Calculation

Bölüm 8.2'de açıklandığı gibi, düz ShockHash içinde rotation fitting kullanabiliriz. Orada şu gözlemi yaparız: ilk anahtar kümesini hashlemek neredeyse her zaman kendi başına bir pseudoforest olan bir grafik üretir. Bu şaşırtıcı değildir çünkü yük faktörü genellikle yük eşiği c = 0.5'e yakındır ve n küçüktür (bu da daha yüksek yükü mümkün kılar [39]).

Bu gerçekten yararlanır ve hash fonksiyonu değerlendirmelerinin sayısını azaltırız: ilk küme için hash değerlerini aynı tutar ve yalnızca ikinci küme için hash fonksiyonlarını yeniden deneriz. Daha kesin olarak, x hash fonksiyonu tohumu ise, ilk kümedeki her anahtarı x − (x mod k) tohumu ile, ikinci kümedeki anahtarları ise x tohumu ile hashleriz; burada k ayarlanabilir bir parametredir. Böylece ilk kümenin hash değerleri birden fazla yineleme boyunca önbelleğe alınabilir.

Ön deneylerde k = 8 değerinin iyi bir seçim olduğunu görüyoruz—bundan çok daha büyük değerler performans iyileştirmesinde azalan getiriler sağlar ve alan tüketimini etkilemeye başlar. Ancak k = 8 için, n büyük olduğunda alan tüketimi üzerindeki etki ihmal edilebilir düzeydedir. Anahtarların hashlenmesi oluşturma sırasında bir darboğaz olduğundan, bu yaklaşım hashlenmesi gereken anahtar sayısını yaklaşık 2 kat azaltır. Bu optimizasyonu yalnızca n > 32 olduğunda uygularız.

Hash Cache

Bipartite ShockHash içinde, ortaya çıkan grafiğin bir pseudoforest olup olmadığını görmek için havuzumuzdan iki hash fonksiyonu adayını düzenli olarak birleştiririz. Bölüm 8.1'de açıklanan basit bit-paralel filtreyi kullanarak birçok adayı testten atlatsak da karşılaştırılması gereken çok sayıda aday kalır. Bu adaylar için hash fonksiyonlarını yeniden değerlendirmek, girdi boyutu n'e bağlı olarak bir darboğaz olabilir.

Bariz bir fikir, tohum adaylarının hash fonksiyonu çıktı değerlerini önbelleğe almaktır. Girdi kümeleri ve dolayısıyla hash değerleri çok küçük olduğundan, her hash değerini tek bir bayt içinde saklayabiliriz. Bu da her tohum adayı için gereken alan miktarını nispeten küçük tutar.

Sentinels

Büyük n değerleri için quad split tekniği oluşturma süresinin büyük kısmını tüm bitleri 1 olan bir sonuç ararken bit desenlerinin mantıksal OR işlemini hesaplayarak geçirir. Bu iç döngü yalnızca çok az sayıda assembler talimatından oluşur.

Dizinin sonuna tüm bitleri zaten 1 olan bir sentinel eleman ekleyerek burada önemli hızlanmalar elde edebiliriz. Böylece dizi için tekrar eden sınır kontrolüne artık ihtiyaç kalmaz. SIMD paralelleştirme kullanıldığında (bkz. Bölüm 8.6), SIMD hatlarının sayısına bağlı olarak birden fazla sentinel kullanırız.

ShockHash'in arkasındaki temel hesaplama yükü pseudoforest üreten tohumları arar ve birden fazla seviyede paralelleştirilebilir: RecSplit kullanılarak bölümleme yapıldığında kovalar arasında, ShockHash yapı taşları arasında, tohumlar arasında, hash fonksiyonu değerlendirmeleri arasında ve bit-paralel filtreler üzerinde.

Kalan işlemler de iyi şekilde paralelleştirilebilir. Anahtarların kovalar için hashlenmesi işlemciler arasında bölünebilir. Erişim veri yapısının paralel oluşturulması da benzer şekilde yapılabilir [19]. Aşağıda SIMD talimatları ve çok iş parçacığı kullanımı açısından olası bir paralelleştirmeyi açıklıyoruz. Ayrıca hibrit bir CPU/GPU uygulamasını da özetliyoruz.

SIMD

Düz ShockHash içinde SIMD paralelliğini iki yerde kullanırız. İlk olarak, tüm anahtarların iki aday konumunu belirlemek ve filtreleme için bit maskesini hesaplamak amacıyla SIMD kullanırız. Buradaki önemli nokta, bireysel hatların bit düzeyinde OR sonucunu toplamak ve tüm anahtarlar işlendiğinde hatları birleştirmektir. İkinci olarak, farklı döndürmeleri paralel olarak değerlendirmek için bit maskesi filtresini (bkz. Bölüm 4) SIMD ile uygularız. Uygulamamız mevcutsa AVX‑512 (8 adet 64‑bit değer) ve aksi hâlde AVX2 (4 adet 64‑bit değer) kullanır.

Bipartite ShockHash de SIMD talimatları kullanılarak paralelleştirilebilir. Quad split tekniği kullanıldığında aday fonksiyonlar için test paralelleştirilir; bu işlem uzun bit deseni listeleri üzerinde dolaşmayı, her biriyle mantıksal OR hesaplamayı ve tüm bitleri 1 olan bir sonuç aramayı içerir. Ancak diğer daha karmaşık veri yapıları daha karmaşık kontrol akışları nedeniyle SIMD kullanılarak paralelleştirilmesi daha zordur. Bu nedenle SIMD'i yalnızca bit deseni listelerini kontrol etmek için kullanırız; büyük n değerleri için ana darboğaz burasıdır.

Multi-Threading

ShockHash'in bir bölümleme çerçevesine entegre edilmesi amaçlandığından, farklı ShockHash temel durumları üzerinde kolayca paralelleştirme yapabiliriz. Kaba taneli basit bir paralellik kaynağı RecSplit kovalarıdır. Bunları iş parçacıkları arasında bölmek için herhangi bir yük dengeleme yöntemi kullanılabilir. Hatta statik yük dengeleme bile işe yarayabilir çünkü oluşturma süresindeki varyanslar ortalamada dengelenir.

Bununla birlikte, bir tür dinamik yük dengelemenin daha verimli olması muhtemeldir ve günümüzde birçok çok çekirdekli işlemcide standart hâle gelmeye başlayan farklı hızlardaki çekirdeklerle de uyumlu çalışır. Kullandığımız erişim veri yapısı BuRR [19] da paralelleştirilebilir.

8.6 Paralelleştirme

H.-P. Lehmann, P. Sanders, S. Walzer

GPUs

Tam bir GPU paralelleştirmesi cuckoo hashing için zor ve verimsiz olabilir çünkü düzensiz kontrol akışı ve bellek erişimi içerir. Yüksek alan verimliliğine sahip varyantlarda hesaplamalara asimptotik olarak filtreleme işlemleri hâkim olduğundan, GPU'nun tüm düğümleri kapsayan rastgele grafikleri tanımlayan bir tohum akışı ürettiği ve çok çekirdekli bir CPU'nun hesaplamanın sonraki aşamalarını gerçekleştirdiği hibrit bir uygulama düşünülebilir.

Örneğin quad split kullanan bipartite ShockHash için, oluşturma süresinin büyük bölümü iki hash fonksiyonu adayının uyumlu olup olmadığını kontrol etmek amacıyla bit desenlerini karşılaştırmakla geçer. Burada GPU'ların büyük paralellik kapasitesini kullanarak birçok deseni paralel biçimde karşılaştırabiliriz. Ardından CPU daha seyrek gerçekleşen ve daha karmaşık olan yönlendirilebilirlik kontrollerini gerçekleştirebilir.

Deneylerimizi 8 çekirdeğe ve 2.5 GHz temel saat hızına sahip bir Intel i7‑11700 işlemci üzerinde gerçekleştiriyoruz. Makine Ubuntu 22.04 üzerinde Linux 5.15.0 çalıştırmakta ve AVX‑512 talimatlarını desteklemektedir. GNU C++ derleyicisinin 11.2.0 sürümünü -O3 -march=native optimizasyon bayrakları ile kullanıyoruz. Rust ile yazılmış rakipler için derlemeyi target-cpu=native ayarıyla release modunda gerçekleştiriyoruz.

ShockHash uygulamamız, 128‑bit ribbon genişliği ve 2‑bit bumping bilgisi ile BuRR retrieval veri yapısını [19] kullanır. ShockHash‑RS için RecSplit [21] tabanlı bölümlendirme kullanıyoruz; özellikle SIMD‑paralel uygulamayı [9]. ShockHash‑Flat içinde anahtarları bölümlere ayırmak için IPS2Ra [2] kullanarak sıralama yapıyoruz.

Girdi verisi olarak, uzunluğu ∈ [10, 50] aralığında tekdüze rastgele seçilmiş kısa dizgeler kullanıyoruz; bu dizgeler sıfır baytı dışında rastgele karakterler içerir. Bunun nedeni, tüm rakiplerin yerel olarak dizgeleri desteklemesi, ancak bazılarının dahili yapıları kullanırken yalnızca tamsayı anahtarları desteklemesidir; bu durum onlara haksız bir avantaj sağlayabilir.

İlk adım olarak karşılaştırılan kodların neredeyse tamamının, yüksek kaliteli bir hash fonksiyonu kullanarak her anahtar için bir ana hash kodu ürettiğini belirtmek gerekir. Daha sonra olası ek hash fonksiyonları bu ana hash kodu üzerinde sabit zamanda değerlendirilebilir; bu işlem girdi dağılımından bağımsızdır. Tüm deneyler tek iş parçacığı kullanır. Karşılaştırılan kodların çoğunda çok iş parçacıklı uygulamalar bulunmasına ve mükemmel hashing işleminin bölümlendirme yoluyla kolayca paralelleştirilebilmesine rağmen, burada odak noktası bu değildir.

Deneylerimizi yeniden üretmek için gerekli kod ve betikler GNU General Public License altında GitHub üzerinde mevcuttur [51, 52].

9 Deneyler

9.1 Teoride ve Pratikte Deneme Sayısı

Şekil 12’de her bijeksiyon arama tekniği için ortalama hash fonksiyonu deneme sayısını karşılaştırıyoruz. Eğrilerin farklı eğimlerinden, rotation fitting [9] yönteminin basit brute‑force yaklaşımına kıyasla polinomik bir çarpan tasarrufu sağladığı, ShockHash’in ise üstel bir çarpan tasarrufu sağladığı açıkça görülmektedir.

Ek olarak, brute‑force ve ShockHash için deneme sayısına ait gösterilen üst sınırları da çiziyoruz. Rotation fitting varyantları için, temel varyantları n’e bölerek çiziyoruz; bunun teorik bir sınır olduğu resmi olarak gösterilmiş değildir, ancak açık bir varsayım niteliğindedir. Grafik, brute‑force ve rotation fitting yöntemlerinin verilen fonksiyonlara oldukça yakın olduğunu göstermektedir.

Saf ShockHash için ölçümler teoriden bile daha iyi sonuç vermektedir; bu da Teorem 8’deki ispatımızın sıkı olmadığını düşündürmektedir. Şaşırtıcı biçimde, ShockHash analizimizi √n’e bölerek elde ettiğimiz fonksiyonla uyuşuyor gibi görünmektedir. Rastgele bir pseudoforest için beklenen 1‑orientation sayısının aslında e√(2n) değil, sabite yakın olabileceğini varsayıyoruz. Bu durum ShockHash’i brute‑force tekniğinin daha da iyi bir alternatifi haline getirir.

Bipartite ShockHash de analizimizin eğimiyle uyuşmaktadır; ancak analizimizin yalnızca O(1.166ⁿ) biçiminde bir üst sınır verdiğini, 1.166ⁿ için tam bir değer sağlamadığını belirtmek gerekir.

Şekil 12

ShockHash’in daha basit brute‑force teknikleri ile karşılaştırıldığında hash fonksiyonu değerlendirmeleri ve alan ek yükü.

• (a) Ortalama başarılı seed. Bipartite ShockHash için quad split olmadan kullanılan uygulamayı kullanıyor ve seed’lerin eşleştirilmesinden önce değerlendirilen en büyük seed’in ortalamasını çiziyoruz. Noktalı fonksiyonlar üst sınırları göstermektedir. Bipartite ShockHash için yalnızca O(1.166ⁿ) biçiminde bir üst sınırın bilindiğini, 1.166ⁿ değerinin kesin olmadığını unutmayın.
• (b) log₂(nⁿ/n!) alt sınırına göre idealize edilmiş alan ek yükü (bit cinsinden). Ortalama seed değeri s ise log₂(s) bit maliyet eklenir, ayrıca retrieval için n bit (uygulanıyorsa).

Şekil 12 ayrıca idealize edilmiş alan tüketimi ile log₂(nⁿ/n!) alan alt sınırı arasındaki farkı da gösterir. Bu, ShockHash’in sabite yakın bir alan kaybı yaşadığını ve bunun büyük n değerlerinde ihmal edilebilir hale geldiğini göstermektedir. Bu durum, anahtar başına aynı alan tüketimini elde etmek için ShockHash‑RS’te RecSplit’in brute‑force kullanan sürümüne kıyasla daha büyük n seçmemiz gerektiğini açıklar. Bu daha büyük n değerlerine rağmen ShockHash inşası brute‑force yönteminden belirgin biçimde daha hızlıdır.

Bipartite ShockHash’in saf ShockHash’e göre küçük ve sabit bir alan ek yüküne sahip olduğu görülmektedir.

Şekil 13, seed adayları üretmek için farklı yöntemleri göstermektedir. Karşılaştırma için brute‑force araması da grafiğe dahil edilmiştir. ShockHash’in brute‑force yöntemine göre belirgin biçimde daha hızlı olduğu açıkça görülmektedir. Ayrıca bipartite sürüm, saf sürüme göre belirgin hız kazanımları göstermektedir. İzole anahtarlar temelinde yapılan filtreleme (Bkz. Bölüm 8.1) inşa sürecini yaklaşık iki kat hızlandırmaktadır.

Rotation fitting zaten etkileyici hızlanmalar sağlarken, quad split tekniğimiz (Bkz. Bölüm 8.3) büyük n değerleri için daha da hızlıdır. Yaklaşık n = 60 civarından başlayarak quad split tekniği, temel bipartite ShockHash uygulamasından bir büyüklük mertebesine kadar daha hızlı olabilmektedir.

Buradaki karşılaştırmanın dikkatle yorumlanması gerektiğini belirtmek gerekir; çünkü farklı yöntemlerin n değerine bağlı olarak farklı alan ek yükleri vardır. Ancak büyük n değerlerinde yöntemlerin alan kullanımları neredeyse aynıdır. Alan tüketimini dikkate alan bir grafik için Şekil 15’e bakınız.

Şekil 13

Seed adayları üretmek için farklı yöntemler kullanılarak elde edilen inşa verimi.

Karşılaştırma amacıyla brute‑force araması da grafiğe dahil edilmiştir. RF ile işaretlenen varyantlar rotation fitting kullanır. Bipartite ShockHash’in filtrelenmiş varyantları izole anahtarlar için filtre kullanır.

Şekil 14

Farklı bölümlendirme şemaları ve temel durum boyutları n için alan kullanımı, inşa performansı ve sorgu performansı.

Toplam girdi anahtar sayısı N = 100 milyon’dur. Temel durum olarak quad split içeren bipartite ShockHash kullanıyoruz.

Şekil 14’te iki farklı bölümlendirme şeması olan ShockHash‑RS ve ShockHash‑Flat için inşa süresi, sorgu süresi ve alan tüketimini veriyoruz.

Küçük n değerlerinde ShockHash‑RS inşa süresine bölme işlemleri hakimdir; bu durum ShockHash‑RS ile ShockHash‑Flat arasındaki farktan görülebilir. Büyük n değerlerinde temel durum baskın hale gelir ve her iki teknik benzer verim sağlar.

Sorgu performansına bakıldığında, iyi alan tüketimi açısından en ilginç aralık olan n > 48 için ShockHash‑Flat daha hızlıdır. Temel durum büyüdükçe sorgu verimi artar çünkü bölümlendirme adımında daha az zaman harcanır.

ShockHash‑Flat’te sorgu verimindeki sıçramalar, ShockHash seed’lerinin sabit genişlikli kodlanmasından kaynaklanır; bir seed sığmadığında geri dönüş veri yapısı gerekir. Aynı temel durum boyutu için düz bölümlendirme şemasının alan tüketimi RecSplit’e kıyasla daha yüksektir. ShockHash‑RS ile karşılaştırıldığında ShockHash‑Flat, daha hızlı sorgular karşılığında daha fazla alan tüketir.

Şimdi ShockHash‑RS ve ShockHash‑Flat’i literatürdeki rakiplerle karşılaştırıyoruz. Rakipler şunlardır:

• CHD [4]
• SicHash [39]
• PTHash [49]
• FMPHGO [6]
• RecSplit [21]
• SIMDRecSplit [9]

BBHash [42] grafiğe dahil edilmemiştir çünkü aynı tekniğin başka bir uygulaması olan FMPH [6] tarafından belirgin biçimde geride bırakılmaktadır. SIMDRecSplit hızlı bir GPU uygulaması da içerse de, farklı donanım mimarisi nedeniyle adil olmayacağı için çoğu grafikten çıkarılmıştır.

ShockHash’i N = 100 milyon anahtar ile ölçmemize rağmen (Bkz. Şekil 14), rakiplerle karşılaştırmayı yalnızca N = 10 milyon anahtar ile gerçekleştiriyoruz. Bunun nedeni, ShockHash’e yakın alan kullanımı sağlayan rakip yapılandırmaların aksi halde hesaplanmasının makul olmayan derecede uzun sürmesidir.

İnşa

Şekil 15 farklı rakiplerin inşa verimini karşılaştıran Pareto sınırlarını göstermektedir. Her Pareto sınırı, aynı yöntemin hem alan hem de inşa süresi açısından başka bir yapılandırması tarafından baskılanmayan veri noktalarını içerir.

Esas olarak alan alt sınırına yakın yapılandırmalarla ilgilendiğimiz için grafikte x‑ekseni log₂(e) alan alt sınırına göre logaritmiktir.

Yalnızca RecSplit tabanlı rakipler ve ShockHash‑Flat, anahtar başına 1.9 bit’in altında alan kullanımı elde edebilmektedir. Anahtar başına 1.65 bit’ten daha düşük yapılandırmalarda ShockHash‑RS, SIMDRecSplit’i belirgin biçimde geride bırakabilmektedir. ShockHash‑RS, SIMDRecSplit’e kıyasla alan verimli yapılandırmalara daha fazla odaklanmıştır.

Daha az alan verimli yapılandırmalarda ise SIMDRecSplit ile aynı verimi elde edemez. Bu durum şaşırtıcı değildir çünkü bu yapılandırmalarda bijeksiyon araması hızlıdır ve retrieval veri yapısının oluşturulması önemli bir performans maliyeti oluşturur.

Tablo 1 tipik yapılandırmalardan bir seçki sunmaktadır. SicHash [39], PTHash [49] ve FMPHGO [6] için orijinal makalelerde verilen yapılandırmaları kullanıyoruz; FMPHGO hash cache kullanacak şekilde ayarlanmıştır. RecSplit tabanlı teknikler için çoğunlukla b = 2000 ile alan verimli yapılandırmalar kullanıyor ve benzer alan tüketimi elde etmek için yaprak boyutu n’i seçiyoruz.

Anahtar başına 1.56 bit alan tüketimine sahip yapılandırmalar karşılaştırıldığında ShockHash‑RS, ShockHash tabanlı olmayan en yakın rakip olan SIMDRecSplit’ten yaklaşık 76 kat daha hızlıdır. Anahtar başına 1.53 bit’in altındaki alan tüketimlerinde bipartite ShockHash‑RS

Tablo 1. Sorgu ve İnşa Performansı

ShockHash ve rakiplerinin tipik yapılandırmaları için sorgu ve inşa performansı. N = 10 milyon anahtar. Mevcut olduğunda SIMD talimatları kullanılmıştır. Bipartite sürümlerde quad split tekniği kullanılmıştır. Tablo ayrıca Nvidia RTX 3090 üzerinde GPURecSplit’i de göstermektedir.

Daha fazla alan verimliliği sağlarken aynı zamanda SIMDRecSplit’ten üç büyüklük mertebesi daha hızlıdır.

Her yönteme yaklaşık yarım saatlik inşa süresi verildiğinde yapılan karşılaştırmada RecSplit anahtar başına 1.58 bit ile bir mükemmel hash fonksiyonu üretebilmektedir. Üç yıl boyunca SIMDRecSplit ile başlayan çalışmalar zinciri önce alan tüketimini 1.56 bit/anahtar seviyesine düşürmüştür. ShockHash‑RS ise 1.52 bit/anahtar elde edebilmekte ve ≈ 1.442 bit/anahtar olan alan alt sınırına olan farkı yaklaşık %30 azaltmaktadır. Son olarak bipartite ShockHash‑RS alan kullanımını 1.489 bit/anahtar seviyesine indirerek pratikte uygulanabilir inşa süresi ile alt sınırın yalnızca %3.3 üzerinde bir değere ulaşmaktadır.

Tek bir CPU iş parçacığı kullanarak bipartite ShockHash‑RS, daha önce yalnızca bir GPU üzerinde binlerce iş parçacığı kullanılarak elde edilen alan kullanımından daha iyi bir sonuç elde eder [9]. 1.53 bit/anahtar ile bir MPHF oluşturmak için SIMDRecSplit’in 15 saatten fazla zamana ihtiyacı varken, bipartite ShockHash‑RS daha iyi bir alan tüketimini yalnızca 57 saniyede elde edebilmektedir. Bipartite ShockHash‑Flat daha hızlı sorgular için alan kullanımını artırır. Ancak aynı alan kullanımını sağlayan bir yapılandırmada bile inşa süresi yaklaşık 32 kat daha hızlıdır.

Sorgular

Tablo 1 ayrıca tipik yapılandırmaların sorgu verimini de göstermektedir. RecSplit tabanlı teknikler diğer yöntemlere göre daha yavaş sorgulara sahiptir çünkü birkaç seviyeden oluşan bir ağacı dolaşmaları ve her adımda değişken bit uzunluğunda veriyi çözmeleri gerekir. ShockHash‑RS ayrıca bir retrieval veri yapısına erişmek zorundadır. Ancak benzer alan verimliliği sağlayan yapılandırmalar karşılaştırıldığında ShockHash‑RS’in sorgu performansı rakiplere benzerdir. Bu durum retrieval işleminin ek maliyetinin, yoğun biçimde sıkıştırılmış ağacı dolaşma işlemiyle karşılaştırıldığında küçük olduğunu göstermektedir.

Saf ShockHash‑RS ile karşılaştırıldığında bipartite uygulama aynı alan kullanımında yaklaşık %10 sorgu performansı kaybeder. Bunun nedeni seed’lerin eşleştirmesinin geri alınması ve quad split sırasında bölümlere ve alt kümeye bağlı durum ayrımlarının yapılmasıdır. Ancak bipartite ShockHash‑RS’teki daha büyük yapraklar, sorgular için önemli bir darboğaz olan RecSplit’in bölme ağacı veri yapısında geçirilen süreyi azaltabilir.

Bipartite ShockHash‑Flat, aynı alan gereksinimi altında önceki en alan verimli rakip olan SIMDRecSplit’e kıyasla yaklaşık 32 kat daha hızlı inşa edilebilir. Aynı zamanda %30 daha hızlı sorgular gerçekleştirir; bu da çok alan verimli MPHF’lerin sorgu performansını alan kullanımına odaklanmayan rakiplere oldukça yaklaştırır.

Sorgu performansının ana öncelik olduğu durumlarda PTHash [49], çok daha hızlı sorgular karşılığında çok daha yüksek alan kullanımı tercih eder. SicHash, hem sorgu süresi hem de alan tüketimi açısından PTHash ile bipartite ShockHash‑Flat arasında bir orta yol sunarken, her iki yaklaşımdan da daha hızlı inşa imkânı sağlar.

ShockHash, küçük kümeler üzerinde minimal perfect hash fonksiyonları hesaplamak için yeni bir yaklaşımdır. Deneme‑yanılma aramasını cuckoo hashing ve retrieval veri yapıları ile birleştirerek ShockHash, saf brute‑force yöntemine göre üstel bir hızlanma sağlar (yaklaşık olarak (2^n) çarpanı). Saf brute‑force yöntemi fonksiyonları örnekleyip bunlardan birinin MPHF olmasını umarken, ShockHash grafikleri örnekleyip bunlardan birinin pseudoforest olmasını bekler. Bipartite ShockHash ile yapılan genişletme ise bipartite grafikleri örnekler ve ek üstel hızlanmalar elde etmek için agresif filtreleme uygular.

Bu geliştirmeler, günümüzde alan açısından neredeyse optimal minimal perfect hash fonksiyonlarını elde etmenin en hızlı yolunu mümkün kılmakta ve temel durum alt problemleri için saf brute‑force yöntemine dayanan önceki en iyi yöntemlerin hakimiyetini sona erdirmektedir.

ShockHash, farklı bölümlendirme çerçevelerine temel durum olarak entegre edilmiştir. ShockHash RecSplit içinde kullanıldığında ortaya ShockHash‑RS çıkar; bu yapı, sıralı kodlar karşılaştırıldığında önceki en gelişmiş yaklaşıma göre üç mertebeye kadar daha hızlı kurulabilir. Tek bir iş parçacığıyla kurulum yapıldığında, ShockHash‑RS kaba kuvvet tekniğinin ayarlanmış bir GPU uygulamasından bile daha hızlıdır.

ShockHash’in yeni geliştirilen bir k‑mükemmel hash fonksiyonu içinde kullanılması ShockHash‑Flat ile sonuçlanır; bu yapı, önceki en gelişmiş yaklaşıma göre yaklaşık 32 kat daha hızlı kurulabilir ve aynı zamanda %30 daha hızlı sorgular sunar. Bu durum, alan verimliliği çok daha düşük olan yapılara olan farkı kapatmaya başlamaktadır ve alan açısından verimli mükemmel hash fonksiyonlarını pratik uygulamalara daha da yaklaştırmaktadır.

Gelecek Çalışmalar

Gelecekte, ek hızlanmalar sağlayabilecek ilave filtreleme teknikleri ilgi çekici olacaktır. Böyle bir filtre zaten tanımlanmıştır: hash fonksiyonu tohumlarını birleştirmeye çalışmadan önce uyumsuz olanları atlamak için bir trie kullanmak. Daha da büyük yapı bloklarını desteklemek için tekniğin GPU kullanılarak hibrit paralelleştirilmesi ilginç bir araştırma yönü olabilir.

Son olarak, sunulan k‑mükemmel hash fonksiyonu kendi başına da yararlı olabilir. Bir sonraki adım, fonksiyonu analiz etmek ve diğer k‑mükemmel hash fonksiyonlarıyla karşılaştırmak olacaktır.

Sonuç ve Gelecek Çalışmalar

H.-P. Lehmann, P. Sanders, S. Walzer

Kaynaklar

1. Fatemeh Almodaresi, Hirak Sarkar, Avi Srivastava ve Rob Patro. Sıkıştırılmış renkli de Bruijn grafı için alan ve zaman açısından verimli bir indeks. Bioinformatics, 34(13):i169–i177, 2018. doi:10.1093/BIOINFORMATICS/BTY292.

2. Michael Axtmann, Sascha Witt, Daniel Ferizovic ve Peter Sanders. Yerinde (paylaşımlı bellek) sıralama algoritmalarının mühendisliği. ACM Trans. Parallel Comput., 9(1):2:1–2:62, 2022. doi:10.1145/3505286.

3. Djamal Belazzougui, Paolo Boldi, Rasmus Pagh ve Sebastiano Vigna. Az alan kullanarak hızlı önek araması ve uygulamaları. ESA (1) içinde, Lecture Notes in Computer Science serisinin 6346. cildi, sayfa 427–438. Springer, 2010. doi:10.1007/978-3-642-15775-2_37.

4. Djamal Belazzougui, Fabiano C. Botelho ve Martin Dietzfelbinger. Hash, yer değiştirme ve sıkıştırma. ESA içinde, Lecture Notes in Computer Science serisinin 5757. cildi, sayfa 682–693. Springer, 2009. doi:10.1007/978-3-642-04128-0_61.

5. Djamal Belazzougui ve Gonzalo Navarro. Alfabe bağımsız sıkıştırılmış metin indeksleme. ACM Trans. Algorithms, 10(4):23:1–23:19, 2014. doi:10.1145/2635816.

6. Piotr Beling. Parmak izi tabanlı minimal mükemmel hashing’e yeniden bakış. ACM Journal of Experimental Algorithmics, 2023. doi:10.1145/3596453.

7. Michael A. Bender, Martin Farach‑Colton, Mayank Goswami, Rob Johnson, Samuel McCauley ve Shikha Singh. Bloom filtreleri, uyarlanabilirlik ve sözlük problemi. FOCS içinde, sayfa 182–193. IEEE Computer Society, 2018. doi:10.1109/FOCS.2018.00026.

8. Sergei Bernstein. Chebyshev eşitsizliğinin ve Laplace hata formülünün bir değişikliği üzerine. Ann. Sci. Inst. Sav. Ukraine, Sect. Math., 1(4):38–49, 1924.

9. Dominik Bez, Florian Kurpicz, Hans‑Peter Lehmann ve Peter Sanders. RecSplit tabanlı minimal mükemmel hash fonksiyonlarının yüksek performanslı kurulumu. ESA içinde, LIPIcs serisinin 274. cildi, sayfa 19:1–19:16. Schloss Dagstuhl – Leibniz‑Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ESA.2023.19.

10. Fabiano C. Botelho, Rasmus Pagh ve Nivio Ziviani. Veri yönetimi uygulamaları için mükemmel hashing. CoRR, abs/cs/0702159, 2007. doi:10.48550/ARXIV.CS/0702159.

11. Fabiano C. Botelho, Rasmus Pagh ve Nivio Ziviani. Neredeyse optimal alanda pratik mükemmel hashing. Inf. Syst., 38(1):108–131, 2013. doi:10.1016/J.IS.2012.06.002.

12. Arthur Cayley. Ağaçlar üzerine bir teorem. Quart. J. Math., 23:376–378, 1878.

13. Jarrod A. Chapman, Isaac Ho, Sirisha Sunkara, Shujun Luo, Gary P. Schroth ve Daniel S. Rokhsar. Meraculous: kısa eşleşmiş uçlu okumalarla de novo genom montajı. PLOS ONE, 6(8):1–13, 2011. doi:10.1371/journal.pone.0023501.

14. Yupeng Chen, Bertil Schmidt ve Douglas L. Maskell. Hibrit kısa okuma eşleme hızlandırıcısı. BMC Bioinformatics, 14:67, 2013. doi:10.1186/1471-2105-14-67.

15. Rayan Chikhi, Antoine Limasset ve Paul Medvedev. Dizileme verilerinden de Bruijn grafiklerini hızlı ve düşük bellekle sıkıştırma. Bioinformatics, 32(12):201–208, 2016. doi:10.1093/BIOINFORMATICS/BTW279.

16. Martin Dietzfelbinger ve Friedhelm Meyer auf der Heide. Yeni bir evrensel hash fonksiyonları sınıfı ve gerçek zamanlı dinamik hashing. ICALP içinde, Lecture Notes in Computer Science serisinin 443. cildi, sayfa 6–19. Springer, 1990. doi:10.1007/BFB0032018.

17. Martin Dietzfelbinger ve Michael Rink. Bir bölme hilesinin uygulamaları. Automata, Languages and Programming: 36th International Colloquium, ICALP 2009 içinde, Rhodes, Yunanistan, 5–12 Temmuz 2009, Bildiriler, Bölüm I, sayfa 354–365. Springer, 2009. doi:10.1007/978-3-642-02927-1_30.

18. Martin Dietzfelbinger ve Christoph Weidling. Dengeli tahsis ve sıkı paketlenmiş sabit boyutlu kutulara sahip sözlükler. ICALP içinde, Lecture Notes in Computer Science serisinin 3580. cildi, sayfa 166–178. Springer, 2005. doi:10.1007/11523468_14.

19. Peter C. Dillinger, Lorenz Hübschle‑Schneider, Peter Sanders ve Stefan Walzer. Ribbon kullanarak hızlı özlü erişim ve yaklaşık üyelik. SEA içinde, LIPIcs serisinin 233. cildi.

Kaynaklar

20. Peter Elias. Statik dosyaların içerik ve adres yoluyla verimli saklanması ve erişimi. J. ACM, 21(2):246–260, 1974. doi:10.1145/321812.321820.

21. Emmanuel Esposito, Thomas Mueller Graf ve Sebastiano Vigna. RecSplit: özyinelemeli bölme yoluyla minimal mükemmel hashing. ALENEX içinde, sayfa 175–185. SIAM, 2020. doi:10.1137/1.9781611976007.14.

22. Bin Fan, David G. Andersen, Michael Kaminsky ve Michael Mitzenmacher. Cuckoo filtresi: pratikte Bloom’dan daha iyi. CoNEXT içinde, sayfa 75–88. ACM, 2014. doi:10.1145/2674005.2674994.

23. Robert Mario Fano. Bir ilişkisel belleğin uygulanması için gereken bit sayısı üzerine. Teknik rapor, MIT Computer Structures Group, 1971. Project MAC, Memorandum 61.

24. Dimitris Fotakis, Rasmus Pagh, Peter Sanders ve Paul G. Spirakis. En kötü durumda sabit erişim süresine sahip alan açısından verimli hash tabloları. Theory Comput. Syst., 38(2):229–248, 2005. doi:10.1007/S00224-004-1195-X.

25. Nikolaos Fountoulakis, Megha Khosla ve Konstantinos Panagiotou. Rastgele hipergraphlar için çoklu yönlendirilebilirlik eşikleri. Combinatorics, Probability & Computing, 25(6):870–908, 2016. doi:10.1017/S0963548315000334.

26. Nikolaos Fountoulakis ve Konstantinos Panagiotou. Cuckoo hashing için keskin yük eşikleri. Random Struct. Algorithms, 41(3):306–333, 2012. doi:10.1002/RSA.20426.

27. Edward A. Fox, Qi Fan Chen ve Lenwood S. Heath. Minimal mükemmel hash fonksiyonları oluşturmak için daha hızlı bir algoritma. SIGIR içinde, sayfa 266–273. ACM, 1992. doi:10.1145/133160.133209.

28. Michael L. Fredman, János Komlós ve Endre Szemerédi. En kötü durumda O(1) erişim süresiyle seyrek bir tabloyu saklama. J. ACM, 31(3):538–544, 1984. doi:10.1145/828.1884.

29. Alan Frieze ve Michał Karoński. Rastgele Grafiklere Giriş. Cambridge University Press, 2016.

30. Solomon W. Golomb. Çalışma uzunluğu kodlamaları (yazışma). IEEE Trans. Inf. Theory, 12(3):399–401, 1966. doi:10.1109/TIT.1966.1053907.

31. Gaston H. Gonnet ve Per-Åke Larson. Sınırlı iç depolama ile harici hashing. J. ACM, 35(1):161–184, 1988. doi:10.1145/42267.42274.

32. Torben Hagerup ve Torsten Tholey. Neredeyse minimal alanda verimli minimal mükemmel hashing. STACS içinde, Lecture Notes in Computer Science serisinin 2010. cildi, sayfa 317–326. Springer, 2001. doi:10.1007/3-540-44693-1_28.

33. Svante Janson ve Malwina J. Luczak. k‑core problemi için basit bir çözüm. Random Struct. Algorithms, 30(1–2):50–62, 2007. doi:10.1002/rsa.20147.

34. Johan Ludwig William Valdemar Jensen. Konveks fonksiyonlar ve ortalama değerler arasındaki eşitsizlikler üzerine. Acta Mathematica, 30(1):175–193, 1906.

35. Kumar Joag-Dev ve Frank Proschan. Rastgele değişkenlerin negatif ilişkililiği ve uygulamaları. The Annals of Statistics, 11(1):286–295, 1983. doi:10.1214/aos/1176346079.

36. Florian Kurpicz, Hans-Peter Lehmann ve Peter Sanders. PaCHash: paketlenmiş ve sıkıştırılmış hash tabloları. Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) içinde, sayfa 162–175. SIAM, 2023. doi:10.1137/1.9781611977561.ch14.

37. Per-Åke Larson ve M. V. Ramakrishna. Harici mükemmel hashing. SIGMOD Conference içinde, sayfa 190–200. ACM Press, 1985. doi:10.1145/318898.318916.

38. Hans-Peter Lehmann, Peter Sanders ve Stefan Walzer. Bipartite ShockHash: verimli mükemmel hashing için ShockHash aramasını budama. CoRR, abs/2310.14959v1, 2023. doi:10.48550/ARXIV.2310.14959v1.

39. Hans-Peter Lehmann, Peter Sanders ve Stefan Walzer. SicHash – mükemmel hashing için küçük düzensiz cuckoo tabloları. ALENEX içinde, sayfa 176–189. SIAM, 2023. doi:10.1137/1.9781611977561.CH15.

40. Hans-Peter Lehmann, Peter Sanders ve Stefan Walzer. ShockHash: kaba kuvvetin ötesinde optimal alana yaklaşan minimal mükemmel hashing. ALENEX içinde. SIAM, 2024. doi:10.1137/1.9781611977929.15.

41. Marc Lelarge. Rastgele hipergraphların yönlendirilmesine yeni bir yaklaşım. Proc. 23rd SODA içinde, sayfa 251–264, 2012. doi:10.1137/1.9781611973099.23.

42. Antoine Limasset, Guillaume Rizk, Rayan Chikhi ve Pierre Peterlongo. Devasa anahtar kümeleri için hızlı ve ölçeklenebilir minimal mükemmel hashing. SEA içinde, LIPIcs serisinin 75. cildi, sayfa 25:1–25:16. Schloss Dagstuhl – Leibniz‑Zentrum für Informatik, 2017. doi:10.4230/LIPICS.SEA.2017.25.

43. Michael Molloy. Rastgele hipergraphlarda ve Boolean formüllerinde çekirdekler. Random Struct. Algorithms, 27(1):124–135, 2005. doi:10.1002/rsa.20061.

44. Ingo Müller, Peter Sanders, Robert Schulze ve Wei Zhou. Parmak izi kullanarak erişim ve mükemmel hashing. SEA içinde, Lecture Notes in Computer Science serisinin 8504. cildi, sayfa 138–149. Springer, 2014. doi:10.1007/978-3-319-07959-2_12.

45. Mark E. J. Newman. Ağlar: Bir Giriş. Oxford University Press, 2010.

46. Anna Pagh ve Rasmus Pagh. Sabit zamanda ve optimal alanda uniform hashing. SIAM J. Comput., 38(1):85–96, 2008. doi:10.1137/060658400.

47. Anna Pagh, Rasmus Pagh ve Milan Ruzic. Sabit bağımsızlık ile doğrusal yoklama. STOC içinde, sayfa 318–327. ACM, 2007. doi:10.1145/1250790.1250839.

48. Rasmus Pagh ve Flemming Friche Rodler. Cuckoo hashing. J. Algorithms, 51(2):122–144, 2004. doi:10.1016/j.jalgor.2003.12.002.

49. Giulio Ermanno Pibiri ve Roberto Trani. PTHash: FCH minimal mükemmel hashing’e yeniden bakış. SIGIR içinde, sayfa 1339–1348. ACM, 2021. doi:10.1145/3404835.3462849.

50. Robert F. Rice. Bazı pratik evrensel kayıpsız kodlama teknikleri. Jet Propulsion Laboratory, JPL Publication, 1979.

51. ShockHash – GitHub. https://github.com/ByteHamster/ShockHash, 2023.

52. MPHF Experiments – GitHub. https://github.com/ByteHamster/MPHF-Experiments, 2023.

53. Richard P. Stanley. Enumerative Combinatorics, Cilt 1 (İkinci Baskı). Cambridge Studies in Advanced Mathematics, 2011.

54. Matthew Szudzik. Zarif bir eşleme fonksiyonu. Wolfram Research (ed.) Special NKS 2006 Wolfram Science Conference içinde, sayfa 1–12, 2006.

55. Stefan Walzer. Yönlendirilebilirlik eşiğine yakın soyma – hashing tabanlı veri yapılarında uzamsal bağlaşım. SODA içinde, sayfa 2194–2211. SIAM, 2021. doi:10.1137/1.9781611976465.131.

56. Stefan Walzer. Doğrusal sayıda top ile her kutuya isabet etme olasılığı, 2024. doi:10.48550/ARXIV.2403.00736.

57. Ian H. Witten, Alistair Moffat ve Timothy C. Bell. Gigabaytları Yönetmek: Belgeleri ve Görüntüleri Sıkıştırma ve İndeksleme, İkinci Baskı. Morgan Kaufmann, 1999.