(Minimal Perfect Hash) Fonksiyonlarının Hızlı ve Ölçeklenebilir Oluşturulması

Marco Genuzio¹, Giuseppe Ottaviano² ve Sebastiano Vigna*¹

¹Dipartimento di Informatica, Università degli Studi di Milano, Milan, İtalya
²Facebook, Menlo Park, ABD

Özet

Sonlu alanlar üzerindeki rastgele doğrusal sistemlerdeki son gelişmeler, mevcut tekniklere kıyasla daha az alan kullanarak statik fonksiyonları ve minimal perfect hash fonksiyonlarını sabit zamanlı veri yapıları olarak oluşturmanın yolunu açmıştır. Bu sonuçların herhangi bir pratik uygulamasının önündeki temel engel, bu doğrusal sistemleri çözmek için gereken kübik zamanlı Gaussian elemesidir: bu sistemler çok küçük yapılabilse de, hesaplama hâlâ uygulanabilir olacak kadar hızlı değildir.

Bu makalede, bu sistemlerin çözümünü birkaç mertebe hızlandırmak için bir dizi sezgisel yaklaşımı ve programlama tekniğini ayrıntılı biçimde açıklıyoruz; böylece genel oluşturma süreci, hipergraph peeling’e dayanan standart ve yaygın olarak kullanılan MWHC tekniğiyle rekabet edebilir hâle gelmektedir. Özellikle, hızlı denklem işlemleri için broadword programlama teknikleri ve tembel (lazy) bir Gaussian eleme algoritması tanıtıyoruz.

Ayrıca veri yapısında alan kullanımını daha da azaltan ve arama hızını artıran bir dizi teknik iyileştirmeyi de açıklıyoruz.

Bu tekniklerin gerçekleştirimimiz, eleman başına 2.24 bit yer kaplayan bir minimal perfect hash fonksiyonu veri yapısı üretmektedir; bu değer MWHC tabanlı olanlarda 2.68 bittir. Ayrıca çarpan niteliğindeki ek yükü 1.23’ten 1.03’e düşüren bir statik fonksiyon veri yapısı da elde edilmektedir.

Statik fonksiyonlar, sonlu kümelerden tamsayılara yapılan keyfi eşlemeleri depolamak için tasarlanmış veri yapılarıdır; yani n adet (kᵢ, vᵢ) çifti verilen bir durumda, burada kᵢ ∈ S ⊆ U, |S| = n ve vᵢ ∈ 2ᵇ olmak üzere, bir statik fonksiyon kᵢ verildiğinde sabit zamanda vᵢ değerini döndürür. Bununla yakından ilişkili olan minimal perfect hash fonksiyonlarında (MPHF), yalnızca kᵢ’lerin oluşturduğu S kümesi verilir ve veri yapısı S → n biçiminde birebir bir numaralandırma üretir. Bu görevler hash tabloları kullanılarak kolayca gerçekleştirilebilir olsa da, statik fonksiyonlar ve MPHF’ler sorgulanan anahtar özgün küme S içinde değilse herhangi bir değeri döndürmekte serbesttir; bu gevşeme, S kümesini depolamanın bilgi kuramsal alt sınırını aşmayı mümkün kılar.

Gerçekten de statik fonksiyon yapıları yalnızca O(nb) bit alan kullanırken MPHF’ler O(n) bit alan kullanır; bu değer anahtarların boyutundan bağımsızdır. Bu durum, özellikle büyük metin dizileri gibi veri kümeleriyle çalışırken statik fonksiyonları ve MPHF’leri güçlü teknikler hâline getirir. Ayrıca bunlar, (sıkıştırılmış) tam metin indeksleri [7], monotone MPHF’ler [3, 5], Bloom filter benzeri veri yapıları [8] ve önek arama veri yapıları [4] gibi alan açısından verimli veri yapılarının önemli yapı taşlarıdır.

Hem kuramsal hem de pratik açıdan önemli bir araştırma yönü, büyük-O alan sınırlarındaki çarpan sabitlerini azaltırken aynı zamanda uygulanabilir oluşturma sürelerini korumaktır.

1. Giriş

Sebastiano Vigna ve Marco Genuzio bir Google Focused Grant tarafından desteklenmektedir.

Bu makalede, rastgele doğrusal sistemler kuramındaki ve perfect hash veri yapılarındaki [14, 22] son gelişmeleri temel alarak, şimdiye kadarki en düşük alan sınırlarına sahip ve yaygın olarak kullanılan tekniklerle karşılaştırılabilir oluşturma süresine sahip pratik statik fonksiyonlar elde ediyoruz. Ancak yeni sonuçlar, güncel en iyi çözümlerde olduğu gibi bir hipergraph üzerinde basit bir derinlik öncelikli dolaşım yerine doğrusal sistemlerin çözülmesini gerektirir.

Yapılarımızın milyarlarca anahtarı yönetebilmesini hedeflediğimiz için, bu yapıların kullanılabilir hâle getirilmesindeki temel zorluk oluşturma sırasında Gaussian elemesinin kübik çalışma süresini denetim altına almaktır. Bu amaçla, broadword programlama [18] temelli yeni teknikler ve yapılandırılmış Gaussian elemesinin tembel bir sürümünü tanıtıyoruz.

Yaygın olarak kullanılan hipergraph tabanlı yapılardan belirgin biçimde daha küçük veri yapıları elde ederken, arama sürelerini koruyor veya iyileştiriyor ve yine de uygulanabilir bir oluşturma süresi sağlıyoruz.

Bu makalede tartışılan tüm gerçekleştirimler Sux4J projesinin bir parçası olarak özgür yazılım şeklinde dağıtılmaktadır (http://sux4j.di.unimi.it/).

Doğal sayılar için von Neumann’ın tanımını ve gösterimini kullanıyoruz; buna göre n, {0, 1, ..., n − 1} kümesiyle özdeşleştirilir. Dolayısıyla 2 = {0, 1} ve 2ᵇ, b bitlik sayıların kümesidir.

2. Gösterim ve Araçlar

Model ve varsayımlar

Hesaplama modelimiz kelime boyutu w olan bir birim maliyetli word RAM modelidir. n = |S| = O(2^{cw}) olduğunu, burada c sabit bir sayı olmak üzere varsayıyoruz; böylece |S|’ye bağlı sabit zamanlı statik veri yapıları kullanılabilir.

Hipergraph’lar

Bir V tepe kümesi üzerindeki r-hipergraph, (\binom{V}{r}) kümesinin bir alt kümesidir; bu küme kardinalitesi r olan V alt kümelerinden oluşur. E kümesinin bir elemanına kenar (edge) denir. Bir hipergraph’ın k-çekirdeği (k-core), derecesi en az k olan maksimum indüklenmiş alt grafıdır.

Bir hipergraph soyulabilir (peelable) ise, kenarlarını öyle bir liste hâlinde sıralamak mümkündür ki her kenar için listede kendisinden sonra gelen kenarlarda görünmeyen bir tepe bulunur. Bir hipergraph ancak ve ancak 2-core’u boşsa soyulabilir. Bir hipergraph yönlendirilebilir (orientable) ise, her hiperkenarla farklı bir tepe ilişkilendirmek mümkündür. Açıkça görülür ki soyulabilir bir hipergraph yönlendirilebilirdir, ancak tersi her zaman doğru değildir.

3. Arka Plan ve İlgili Çalışmalar

Doğrusal fonksiyonlar ve MWHC

Çoğu statik fonksiyon yapısı, gereksinimleri sağlayan bir doğrusal fonksiyon bulunmasıyla çalışır. Basitlik için önce ikili değerlere sahip fonksiyonların özel durumunu ele alalım; yani vᵢ ∈ F₂ (iki elemanlı alan). Görev, w ∈ F₂^m vektörünü bulmaktır; öyle ki her i için

hθ(kᵢ)ᵀ w = vᵢ
(1)

olur; burada hθ, H ile gösterilen uygun bir aileden seçilen ve θ tarafından indekslenen U → F₂^m türünde bir fonksiyondur.

Aramayı sabit zamanlı yapmak için, hθ(k)’nin sabit sayıda r tane bir içermesi ve bu birlerin konumlarının sabit zamanda hesaplanabilmesi ek koşulunu getiririz. Böylece küçük bir gösterim kötüye kullanımıyla hθ,j’nin j-inci sıfır olmayan elemanın konumu olduğunu yazabiliriz; dolayısıyla arama işlemi şu hâle gelir

w_{hθ,0(kᵢ)} + ... + w_{hθ,r−1(kᵢ)} = vᵢ.
(2)

Böyle bir fonksiyon varsa veri yapısının yalnızca w ve θ değerlerini saklaması gerektiği açıktır. hθ sabitlenmişse, yukarıdaki n denklemi yazmak doğrusal bir sistem verir: satır vektörleri hθ(kᵢ)ᵀ’yi bir H matrisi içinde ve değerleri vᵢ’yi bir v vektörü içinde toplarsak çözmek istediğimiz denklem

Hw = v.
(3)

olur.

Çözüm w’nin var olması için yeterli koşul, H matrisinin tam rütbeli (full rank) olmasıdır.

vᵢ ∈ F₂^b olan ve b bitlik bir tamsayıyı temsil eden genel duruma genellemek için, v yerine vᵢ değerlerinin satırlar hâlinde istiflendiği n × b boyutlu V matrisi kullanılır ve w yerine m × b boyutlu bir matris alınır. H’nin tam rütbeli olması, HW = V denkleminin çözülebilirliği için yine yeterli koşuldur. Geriye m değişken sayısının ve hθ fonksiyonlarının H’nin tam rütbeli olmasını sağlayacak şekilde nasıl seçileceğini göstermek kalır.

Öncü makalelerinde [20], Majewski, Wormald, Havas ve Czech (bundan sonra MWHC olarak anılacaktır) yukarıdaki çerçeve kullanılarak açıklanabilen ilk statik fonksiyon oluşturma yöntemini tanıttılar. H olarak, değerleri tam olarak r adet bir içeren U → F₂^m fonksiyonları kümesini seçerler; yani hθ(k) vektörü, j ∈ r için hθ,j(k) konumlarında r adet bir içerir.

Fonksiyonlar düzgün rastgele seçildiğinde, (hθ,0(k), ..., hθ,r−1(k)) r-lüleri m düğümlü rastgele bir hipergraph’ın kenarları olarak görülebilir. Uygun bir c_r sabiti için m > c_r n olduğunda, yüksek olasılıkla hipergraph soyulabilir olur ve soyma süreci ilgili doğrusal sistemi üçgensel biçime getirir. Başka bir deyişle, sistemin çözülebilir olduğuna dair olasılıksal bir güvenceye ve çözümün doğrusal zamanda bulunabileceğine sahip oluruz.

c_r sabiti derece r’ye bağlıdır ve minimum değerini r = 3 için alır; c₃ ≈ 1.23. H ailesi, θ parametresinin alt doğrusal sayıda bit ile temsil edilebildiği daha küçük bir küme ile değiştirilebilir; böylece toplam alan 1.23bn + o(n) bit olur. Pratikte hθ,j(k) basitçe rastgele tohum θ içeren bir hash fonksiyonu olacaktır ve bu O(1) bit ile temsil edilebilir.

MPHF’ler

Chazelle, Kilian, Rubinfeld ve Tal [12], MWHC yapısından habersiz olarak bunu bağımsız biçimde önerdiler; ayrıca soyma sürecinin bir yan etkisi olarak her hiperkenara benzersiz bir düğüm atanabileceğini de fark ettiler. Yani her anahtara m içinde birebir bir tamsayı atanabilir. Perfect hash fonksiyonu S → m elde etmek için hiperkenarın r düğümünden hangisinin atanmış olduğunu saklamak yeterlidir; bu da c_r ⌈log r⌉ n + o(n) bit ile yapılabilir.

Bunu minimal yapmak, yani S → n elde etmek için bir sıralama (ranking) yapısı eklenebilir. Yine en iyi değer r = 3 olup kuramsal olarak 2.46n + o(n) boyutunda bir veri yapısı elde edilir [10].

HEM

Botelho, Pagh ve Ziviani [10], hipergraph’ı bellekte tutamayacak kadar büyük kümeler için MPHF oluşturmak amacıyla Heuristic External Memory (HEM) adlı pratik bir dış bellek algoritması tanıttılar. Her anahtarı, rastgele bir hash fonksiyonuyla hesaplanan Θ(log n) bitlik bir imza ile değiştirirler ve çakışma oluşmadığını kontrol ederler.

İmzalar daha sonra sıralanır ve en anlamlı bitlerine göre küçük parçalara ayrılır; her parça için yukarıda açıklanan yaklaşımla (yerel bir tohum kullanarak) ayrı bir fonksiyon hesaplanır. Parça fonksiyonlarının temsilleri daha sonra tek bir dizi hâlinde birleştirilir ve bunların ofsetleri ayrı olarak saklanır.

Cache-oblivious oluşturma yöntemleri

HEM’e alternatif olarak [2] numaralı çalışmada, hipergraph’ları soyup karşılık gelen yapıları hesaplamak için yalnızca tarama ve sıralama kullanan cache-oblivious algoritmalar önerilmektedir. Temel avantaj, ölçeklenebilirlikten ödün vermeden HEM’deki ofset dizisine erişim maliyetini ortadan kaldırmaktır.

CHD

Belazzougui, Botelho ve Dietzfelbinger [6], CHD (compressed hash-and-displace) adı verilen tamamen farklı bir yöntem tanıttılar. Beklenen oluşturma süresinin artması pahasına, kuramsal olarak yaklaşık anahtar başına 1.44 bit olan bilgi kuramsal alt sınıra ulaşmayı mümkün kılar.

Hipergraph’ların ötesi

Statik fonksiyonlar için MWHC yöntemi geliştirilebilir. Dietzfelbinger ve Pagh [14], nb alan sınırının önündeki sabit çarpanı istenildiği kadar küçültmeyi mümkün kılan yeni bir yapı tanıttılar.

Calkin teoremine göre, bir βᵣ sabiti vardır ve eğer m > βᵣ n ise ve H matrisinin satırları ağırlığı r olan vektörlerden rastgele seçilmişse, H yüksek olasılıkla tam rütbeli olur. Sonlu bir minimumu olan cᵣ’nin aksine, βᵣ değeri r arttıkça hızla sıfıra yaklaşır. Dolayısıyla satırlar ne kadar yoğun olursa m değeri n’e o kadar yaklaşabilir.

Örneğin r = 3 için β₃ ≈ 1.12 < c₃ ≈ 1.23 olur. MWHC’nin doğrusal zamanlı soyma algoritmasının aksine, genel matris tersleme işlemi süperkuadratik zaman gerektirir (Gaussian elemesiyle O(n³)). Doğrusal zamanlı bir algoritma elde etmek için, S kümesini bir hash fonksiyonu kullanarak küçük parçalara böler ve her alt küme üzerinde statik fonksiyonları bağımsız biçimde hesaplarlar.

Yazarlar ayrıca sistemin çözülebilir olmasının karşılık gelen hipergraph’ın yönlendirilebilir olduğunu ima ettiğini fark etmişlerdir; bu da minimal perfect hash fonksiyonları oluşturmayı mümkün kılar. Daha sonraki çalışmalar [15, 16, 13] çözülebilirlik ve yönlendirilebilirlik eşiklerini daha da iyileştirmiştir: r = 3 için 1.09’dan küçük, r = 4 için 1.03’ten küçük.

Bu makalede, geliştirilmiş oluşturma yöntemleri sağlamak için bir dizi yeni sonucu ve tekniği birleştiriyoruz. Veri yapımız HEM yöntemi üzerine kuruludur: anahtar kümesi rastgele olarak beklenen boyutu sabit olan parçalara bölünür ve fonksiyon her parça için bağımsız biçimde hesaplanır.

Soyulabilirliği garanti eden bir tepe/kenar oranı kullanmak yerine, yönlendirilebilirliği ve ilgili doğrusal sistemin yüksek olasılıkla çözülebilir olmasını garanti eden daha düşük bir oran seçiyoruz. Soyulabilirliğin kaybedilmesi doğrusal sistemi çözmek için Gaussian elemesi kullanmamızı gerektirir; ancak parçalar sabit boyutlu olduğundan toplam oluşturma süresi doğrusal kalır (imzaların sıralanması için gereken O(n log n) adımına ek olarak).

Ayrıca Bölüm 7’de HEM veri yapısına yapılan iyileştirmeleri de açıklıyoruz.

Öncelikle [13] çalışmasındaki yönlendirilebilirlik eşiklerini kullanıyoruz; bunların XORSAT çözülebilirlik eşikleriyle aynı olduğu gösterilmiştir. Örneğin rastgele bir 3-hipergraph’ta tepe/kenar oranı c > 1.09 olduğunda boş olmayan bir 2-core içerir; ancak hipergraph yönlendirilebilir olur ve insidans matrisi tam rütbeye sahiptir.

Böylece MWHC tekniğini boş olmayan 2-core içeren 3-hipergraph’lara genişletebiliriz: soyma işleminin ardından yalnızca 2-core tarafından belirlenen denklemleri çözeriz. Daha önce bu yaklaşımın oluşturma süresi MWHC’den iki büyüklük mertebesi daha yavaştı ve pratik değildi.

Ayrıca Goerdt ve Falke’nin yakın zamanda modulo‑3 sistemleri için XORSAT’a benzer bir sonuç kanıtlaması sayesinde [17], genelleştirilmiş selfless algoritmasını [13] kullanarak rastgele bir 3-hipergraph’ın yönelimini elde edebilir ve ardından yönelimin indüklediği modulo‑3 doğrusal sistemi çözerek bir perfect hash fonksiyonu elde edebiliriz. Her iki prosedürün de kontrollü bir başarısızlık olasılığı vardır; böyle bir durum gerçekleşirse yeni bir hipergraph üretiriz.

Daha sonra sıralama (ranking) kısmının neredeyse hiç alan maliyeti olmadan nasıl yönetileceğini gösteriyoruz.

5. Satır İşlemleri için Broadword Programlama

Gaussian elemesiyle pratik bir çözüme doğru attığımız ilk adım broadword programlamadır [18] (SWAR — SIMD Within A Register olarak da bilinir). Bu teknikler, değerleri w bitlik makine sözcükleri içine paketleyerek ve işlemleri tüm sözcük üzerinde gerçekleştirerek aynı anda birden fazla değeri işler.

Kuramsal özlü (succinct) veri yapılarında genellikle w = Θ(log n) varsayılır ve boyutu O(w) olan alt problemlere indirgenir; bu alt problemlerin sonuçları alt doğrusal boyutlu tablolarda önceden hesaplanabilir ve sabit zamanda tablo bakışıyla elde edilebilir. Ancak pratik n değerleri için bu tablolar hiç de ihmal edilebilir değildir.

Bu durumda broadword algoritmaları genellikle aynı fonksiyonları sabit veya sabite yakın zamanda hesaplamak için yeterlidir ve bir arama tablosu saklama gereksinimini ortadan kaldırır.

1 Teknik olarak makaledeki ispat k > 15 için verilmiştir; ancak yazarlar aynı tekniklerle sonucun k ≥ 3 için de kanıtlanabileceğini belirtmektedir ve pratikte çözülebilir bir sistem elde etmek için hiçbir zaman iki denemeden fazlasına ihtiyaç duymadık.

Alanı Sıkıştırmak

Bizim problemimizde Gaussian elemesinin iç döngüsü tamamen satır işlemlerinden oluşur: verilen x ve y vektörleri ve bir α skalerine göre x + αy hesaplanır. Alan F2 olduğunda bu işlemi her seferinde w eleman üzerinde gerçekleştirmek çok kolaydır; bu statik fonksiyon hesaplamasında kullanılan durumdur. Her elemanı bir bit içine paketleyebiliriz ve skaler yalnızca 1 olabileceğinden toplam basitçe bit düzeyinde XOR işlemi olur: C gösterimiyle x ^ y.

MPHF’ler için ise alan F3’tür ve bu daha karmaşık algoritmalar gerektirir.

Öncelikle her elemanı {0, 1, 2} kümesinden 2 bit ile kodlayabiliriz; böylece bir sözcüğe w/2 eleman sığdırılabilir. Skaler α yalnızca 1 veya −1 olabilir; dolayısıyla x + y ve x − y durumlarını ayrı ayrı ele alabiliriz.

Toplama işlemi için, x ve y'yi basitçe toplayarak başlayabiliriz. Her iki taraftaki elemanlar da 2'den küçük olduğunda yapılacak bir şey yoktur: sonuç 3'ten küçük olacaktır. Ancak iki taraftan en az biri 2 ve diğeri 0 değilse, sonucu [0..3) aralığındaki kanonik gösterime geri getirmek için sonuçtan 3 çıkarmamız gerekir. İki tarafın da 2 olduğu durumda sonucun 2 bitini aştığını unutmayın (10₂ + 10₂ = 100₂), fakat 2^w modülüne göre toplama ve çıkarma işlemleri birleşmeli olduğundan, işlemin her bir 2 bitlik eleman üzerinde bağımsız olarak gerçekleştirildiğini varsayabiliriz; yeter ki nihai sonuç 2 bit içine sığsın.

Dolayısıyla, sonuç en az 3 olduğunda 3 değerini alan bir maske hesaplamamız ve bunu x + y'den çıkarmamız gerekir.

Çıkarma işlemi çok benzerdir. İlk olarak y'yi eleman bazında 3'ten çıkarırız; tüm elemanlar kesin olarak 3'ten küçük olduğundan herhangi bir elde oluşmaz. Ortaya çıkan elemanlar böylece en az 1 olur. Artık x + y hesaplamasını daha öncekiyle aynı durum analizini kullanarak gerçekleştirebiliriz; yalnız bu kez sağ taraftaki elemanlar [1..3] aralığındadır, dolayısıyla maske için koşullar biraz farklıdır.

Hem toplama hem de çıkarma yalnızca 10 aritmetik işlem gerektirir ve modern 64 bit CPU'larda aynı anda 32 elemanlık vektörleri işleyebilir.

Son olarak, geri yerine koyma (back substitution) yapılırken satır–matris çarpımları hesaplamamız gerekir; burada bir satır bir denklemin katsayılarıyla verilir ve matris şimdiye kadar hesaplanmış çözümleri içerir.

F2 alanında bu işlem, satırdaki 1 değerleri üzerinde yineleme yaparak ve sağ taraftaki matristeki karşılık gelen b bitlik satırları toplayarak gerçekleştirilebilir. Bu 1 değerleri, mevcut satır kelimesinin LSB'sini bularak ve standart broadword tekniği x = x & -x ile onu silerek yinelenebilir.

MPHF'ler için ise alan F3'tür fakat çözüm matrisi bir vektördür; dolayısıyla çarpım yalnızca bir skaler çarpımdır. Bunu hesaplamak için, iki vektörün 64 bitlik kelimeler olarak temsil edildiği durumda skaler çarpımı hesaplayan aşağıdaki broadword algoritmasını kullanırız.

uint64_t add_mod3_step2(uint64_t x, uint64_t y) {
    uint64_t xy = x | y;

    // (x veya y == 2) ve (x veya y == 1) ise MSB'yi ayarla.
    uint64_t mask = (xy << 1) & xy;

    // (x == 2) ve (y == 2) ise MSB'yi ayarla.
    mask |= x & y;

    // Her 2 bitlik elemanın MSB'si artık sonuç >= 3 ise ayarlanmıştır. LSB'leri temizle.
    mask &= 0x5555555555555555 << 1;

    // Şimdi MSB'si ayarlı olan elemanları 3'e dönüştür.
    mask |= mask >> 1;

    return x + y - mask;
}

uint64_t sub_mod3_step2(uint64_t x, uint64_t y) {
    // y = 3 - y.
    y = 0xFFFFFFFFFFFFFFFF - y;

    // Şimdi y > 0

    // x == 2 ise MSB'yi ayarla.
    uint64_t mask = x;

    // (x == 2 ve y >= 2) veya (y == 3) ise MSB'yi ayarla.
    mask |= ((x | y) << 1) & y;

    mask &= 0x5555555555555555 << 1;
    mask |= mask >> 1;

    return x + y - mask;
}

t değerini hesaplayan ifade, verilen bir konuma x ve y'deki karşılık gelen konumların çarpımına eşdeğer bir değerin yerleştirilmesini sağlar (bu durum durum bazında bir analizle kolayca doğrulanabilir). Bazı durumlarda aslında 3 değerini sıfıra eşdeğer olarak kullandığımızı belirtelim. Bu noktada son satırlar her çarpımın katkısını hesaplar (popcount() bir kelimedeki ayarlı bitlerin sayısını döndürür). Sonucun hâlâ 3 moduna göre indirgenmesi gerektiğini unutmayın.

uint64_t prod_mod3_step2(uint64_t x, uint64_t y) {
    uint64_t high = x & 0xAAAAAAAAAAAAAAAA;
    uint64_t low  = x & 0x5555555555555555;

    // Her 10 değerini 11 yap ve diğer her şeyi sıfırla.
    uint64_t high_shift = high >> 1;

    // Birleri ikilerle değiştir ve 00 değerlerini 11 yap.
    uint64_t t = (y ^ (high | high_shift)) & (x | high_shift | low << 1);

    return popcount(t & 0xAAAAAAAAAAAAAAAA) * 2
         + popcount(t & 0x5555555555555555);
}

Broadword algoritmalarıyla donanmış olsak bile, bir HEM parçası boyutundaki (binlerce denklem ve değişken içeren) sistemleri Gauss eliminasyonu ile çözmek aşırı derecede yavaş olurdu; bu da veri yapılarımızın oluşturulmasını standart MWHC tekniğine göre bir büyüklük mertebesi daha yavaş hâle getirirdi.

Yapılandırılmış Gauss eliminasyonu, çok sayıda denklemde görünen bazı değişkenleri ayırmaya çalışarak ve ardından sistemin geri kalanını yalnızca bu değişkenleri kullanarak yeniden yazarak doğrusal bir sistemin çözümünde gerekli işlem sayısını azaltmayı amaçlar. Bu, büyük seyrek sistemlerin çözümünü gerektiren ayrık logaritma hesaplamaları bağlamında geliştirilmiş bir sezgisel yöntemdir [21, 19].

Standart formülasyon, çok sayıda denklemde görünen değişkenlerin belirli bir oranının (keyfi olarak seçilen) seçilmesini ve ardından gevşek biçimde tanımlanmış bir dizi iyileştirme adımını gerektirir.

Burada yapılandırılmış Gauss eliminasyonunun parametresiz yeni bir sürümünü tanımlıyoruz; buna lazy Gaussian elimination adını veriyoruz. Bu sezgisel yöntem sistemlerimiz üzerinde son derece etkili olmuş ve standart eliminasyonla çözülecek sistemin boyutunu orijinalinin yaklaşık %4'üne kadar düşürmüştür.

Bir alan üzerindeki bir denklem sistemi düşünün. Herhangi bir anda bir değişken aktif, boşta (idle) veya çözülmüş olabilir; bir denklem ise seyrek veya yoğun olabilir. Başlangıçta tüm denklemler seyrek ve tüm değişkenler boştadır. Sistemi aşağıdaki değişmezleri koruyarak değiştireceğiz:

• Yoğun denklemler boşta değişken içermez.
• Bir denklem en fazla bir çözülmüş değişken içerebilir.
• Bir çözülmüş değişken tam olarak bir yoğun denklemde görünür.

Amacımız, sistemdeki tüm denklemleri yoğun hâle getirmek ve bunu yaparken aktif değişken sayısını en aza indirmeye (ya da eşdeğer olarak çözülmüş değişken sayısını en üst düzeye çıkarmaya) çalışmaktır. Bu noktada aktif değişkenlerin değerleri, çözülmüş değişken içermeyen yoğun denklemler üzerinde standart Gauss eliminasyonu uygulanarak hesaplanabilir; çözülmüş değişkenler ise aktif değişkenlere atanan değerlerden kolayca hesaplanabilir.

Bir değişkenin ağırlığı, içinde bulunduğu seyrek denklem sayısıdır. Bir seyrek denklemin önceliği ise o denklemde bulunan boşta değişkenlerin sayısıdır. Lazy Gaussian elimination, denklemleri bir minimum öncelik kuyruğunda tutar ve şu işlemleri gerçekleştirir:

1. Önceliği sıfır olan ve bazı değişkenler içeren bir seyrek denklem varsa yoğun hâle getirilir. Değişken yoksa denklem ya bir özdeşliktir (bu durumda atılır) ya da imkânsızdır (bu durumda sistem çözülemezdir ve işlem durur).
2. Önceliği bir olan bir seyrek denklem varsa, denklemdeki tek boşta değişken çözülmüş hâle gelir ve denklem yoğun hâle getirilir. Ardından bu denklem kullanılarak çözülmüş değişken diğer tüm denklemlerden elimine edilir.
3. Aksi durumda, en fazla sayıda seyrek denklemde görünen boşta değişken aktif hâle getirilir.

Sistem çözülebilir olduğu sürece bu prosedürün her zaman tamamlandığını unutmayın — en kötü durumda tüm boşta değişkenler aktif hâle getirilir (ve böylece tüm denklemler yoğun olur).

İki gözlem yapılabilir:

• Bir boşta değişkenin ağırlığı asla değişmez; çünkü 2. adımda çözülmüş değişkeni elimine eder ve yalnızca aktif değişkenlerin katsayılarını değiştiririz. Bu da değişkenleri başlangıçta göründükleri denklem sayısına göre (örneğin countsort ile) sıralayıp 3. adımda boşta değişkenleri bu sırayla seçebileceğimiz anlamına gelir.
• Denklemler için gerçekten bir öncelik kuyruğuna ihtiyacımız yoktur. Bir denklem önceliği sıfır veya bir olduğunda, ilk adımda kontrol ettiğimiz bir deque'nin sırasıyla sol veya sağ tarafına taşınır.

Dolayısıyla doğrusal olmayan zaman gerektiren tek işlemler, 2. adımda gerçekleştirilen eliminasyonlar ve yoğun denklemler üzerinde yaptığımız son Gauss eliminasyonudur; bunu broadword programlama kullanarak hesaplarız.

HEM'i İyileştirme

HEM sürümümüz, oluşturma sürecini hızlandırmak için disk üzerinde bucket sıralaması kullanır. Anahtarlar önce hash değerlerinin en yüksek bitlerine göre 256 adet disk üzeri fiziksel parçaya bölünür (Jenkins’in SpookyHash fonksiyonunu kullanıyoruz). Bu disk parçaları daha sonra belleğe yüklenir ve sıralanır; istenen boyuttaki sanal parçalar fiziksel parçaların bölünmesi veya birleştirilmesiyle hesaplanır.

Her anahtar için 192 bitlik bir hash ve 64 bitlik bir değer sakladığımızdan, anahtar sayısına bağlı olarak kullanılan bellek miktarının anahtar başına bir biti aşmayacağını garanti edebiliriz (hesaplanacak yapının kendisi hariç).

Sıralama Yapısını Ortadan Kaldırma

Minimal perfect hashing durumunda, denklem sistemi tarafından hesaplanan perfect hashing'i minimal yapmak için gerekli olan sıralama yapısını kaldırarak yapıyı daha da hızlandırabilir ve alan kullanımını azaltabiliriz.

Standart HEM oluşturmasında, s boyutundaki bir parçayla ilişkilendirilen düğüm sayısı ⌈cs⌉ olarak verilir; burada c uygun bir sabittir ve ofset bilgisi bu sayıların kısmi toplamlarını içerir.

Biz farklı bir yaklaşım kullanacağız: parçayla ilişkilendirilen düğüm sayısı ⌈c(S + s)⌉ − ⌈cS⌉ olacaktır; burada S, önceki parçalarda depolanan eleman sayısıdır. ⌈cs⌉ değerine fark en fazla birdir, ancak yaklaşımımızı kullanarak S ve s verildiğinde parçayla ilişkilendirilen düğüm sayısını hesaplayabiliriz.

Dolayısıyla ofset bilgisini saklamak yerine, her parça için önceki parçalarda depolanan eleman sayısı olan S değerini saklayacağız. Bu değer, parça içindeki sıralama için bir taban olarak kullanılabilir. Böylece sıralama yapısına artık gerek kalmaz; bu da alan kullanımını ve bellek erişimi sayısını azaltır.

r = 3 olduğunda, yaygın olarak yapıldığı gibi, her değer için iki bit kullanabiliriz; bu sırada bir hiperkenarla ilişkilendirilen düğüm için 0 yerine 3 değerini kullanmaya dikkat ederiz. Sonuç olarak sıralama, bir parçayla ilişkilendirilen değerlerdeki sıfır olmayan çiftlerin sayısını saymayı gerektirir; bu da yine broadword programlama ile gerçekleştirilebilir:

int count_nonzero_pairs(uint64_t x) {
    return popcount((x | x >> 1) & 0x5555555555555555);
}

Ofsetleri ve Tohumları Sıkıştırma

Sıralama yapısı kaldırıldıktan sonra geriye yalnızca parça başına anahtar sayısının kısmi toplamlarını ve parça hash fonksiyonu için kullanılan tohumu saklamak kalır. Bu, tüm girdi kümesi üzerinde fonksiyonu tek seferde oluşturma durumuna kıyasla HEM veri yapısının getirdiği toplam ek yükü oluşturur.

Bu iki sayıyı ayrı ayrı saklamak yerine tek bir 64 bitlik tam sayıda birleştiriyoruz. Bunu mümkün kılan temel gözlem şudur: her parça için uygun bir tohum bulma olasılığı son derece yüksek olduğundan, bunu saklamak için çok az sayıda rastgele bit yeterlidir.

Her parça için aynı tohum dizisini kullanabilir ve başarılı olandan önceki başarısız deneme sayısını saklayabiliriz. Deneylerimizde bu sayı geometrik olarak dağılmıştır ve hiçbir zaman 24'ten büyük olmamıştır. Eğer n anahtar saklıyorsak, tohum için 64 − ⌈log n⌉ bit kullanılabilir; bu da gerçekçi herhangi bir n için fazlasıyla yeterlidir.

Deneylerimizi Java kullanarak, BUbiNG [9] tarafından toplanan eu-2015 taramalarından türetilmiş iki veri kümesi üzerinde gerçekleştirdik. Kullanılan donanım Intel® Core™ i7-4770 CPU @ 3.40GHz (Haswell) idi. Daha küçük veri kümesi ana makine (host) listesi (11,264,052 anahtar, ≈22 B/anahtar), daha büyük veri kümesi ise sayfa listesi (1,070,557,254 anahtar, ≈80 B/anahtar) idi. Tarama verileri LAW web sitesinde herkese açıktır.

Seçilen parça boyutuna bağlı olan nihai performans değerlerinin yanı sıra, ilgi duyulan ölçümlerin parça boyutuyla nasıl değiştiğini görmek de ilginçtir.

Şekil 1'de r = 3 için eleman başına bit sayısının, oluşturma süresinin ve arama süresinin parça boyutuyla nasıl değiştiğini gösteriyoruz. Minimal perfect hash fonksiyonları durumunda anahtar başına gerçek bit sayısını gösterdiğimizi unutmayın. Genel statik fonksiyonlar durumunda ise her anahtarı sıralı konumuna eşleyen bir fonksiyon kuruyor ve algoritma tarafından kullanılan anahtar başına ek bit sayısını raporluyoruz.

Parçalar büyüdükçe anahtar başına bit sayısı biraz azalır (çünkü ofset yapısının etkisi daha iyi amortize edilir). Aynı zamanda:

• Oluşturma süresi artar çünkü Gauss eliminasyonu süreci doğrusal değildir (özellikle parça boyutu 2¹¹'den sonra çok hızlı artar).
• Minimal perfect hash fonksiyonları durumunda daha büyük parçalar, rank fonksiyonunun parça boyutuyla doğrusal olarak daha fazla iş yapmasına neden olur ve gerçekten de arama süresi bu durumda keskin biçimde artar.
• Statik fonksiyonlar durumunda 2¹⁰'dan büyük parçalar, ofset dizisi L3 önbelleğine sığacak kadar küçüldüğünden arama süresinde küçük bir iyileşme sağlar.

Deneysel Sonuçlar

Tablo 1'de "en iyi seçim" parça boyutumuz olan 2¹⁰ için anahtar başına arama ve oluşturma süresini, aynı alan kullanımı için [1]'de raporlanan verilerle (yani ek 1.10 b/anahtar) ve λ = 3 olduğunda anahtar başına bit sayısı bizimkine neredeyse eşit olan CHD tekniği için yazarlar tarafından sağlanan C koduyla karşılaştırıyoruz.

Daha büyük veri kümesi için CHD durumunda farklı donanım kullanmak zorunda kaldığımızı belirtelim; çünkü mevcut bellek (16 GB) oluşturma işlemini tamamlamak için yeterli değildi, buna rağmen nihai sonuç yalnızca 3 GB idi.

Tablo 1: Anahtar başına oluşturma ve değerlendirme süresinin karşılaştırması, r = 3. CHD [6]'dan, ADR [1]'dendir.

Statik fonksiyonlar durumunda, veri yapıları daha önce mümkün olandan yaklaşık iki yüz kat daha hızlı oluşturulabilir [1] (gösterilen veriler 10⁷ anahtarlı bir veri kümesine aittir).

Tablo 2: Statik fonksiyonlar için anahtar başına oluşturma ve değerlendirme süresi, r = 4.

elemanlar; arama süresi rapor edilmemiştir). Kullandığımız her tekniğin katkısı hakkında okuyucuya bir fikir vermek için Tablo 3, peeling aşamasının (teknik olarak gerekli değildir — sistemi doğrudan da çözebilirdik), standart seyrek sistem temsili yerine broadword hesaplamanın ve standart Gauss eliminasyonu yerine lazy Gauss eliminasyonunun herhangi bir kombinasyonu kullanıldığında oluşturma süresindeki artışı gösterir. Tekniklerimizin birleşimi elli katlık bir hız artışı sağlar (temel hızımız zaten [1]'inkinin yaklaşık dört katıdır; muhtemelen donanımımızın daha yeni olmasından dolayı).

Tablo 3: r = 3 için yalnızca pre-peeling (P), broadword hesaplama (B), lazy Gauss eliminasyonu (G) veya bunların kombinasyonları kullanıldığında oluşturma süresindeki artış.

MPHF'ler durumunda son derece rekabetçi bir arama hızına (CHD'nin iki katı) ve çok daha iyi ölçeklenebilirliğe sahibiz. Küçük boyutlarda, oluşturmanın tamamen ana bellekte yapılması (CHD'nin yaptığı gibi) avantaj sağlar; ancak veri kümesi büyür büyümez yaklaşımımız çok daha iyi ölçeklenir. Ayrıca kodumuzun, nesneleri çalışma zamanında bit vektörlerine dönüştüren stratejilere dayanan oldukça soyut bir Java uygulaması olduğunu da belirtelim: böylece herhangi bir nesne türü anahtar olarak kullanılabilir. Yalnızca byte dizilerini hashleyebilen CHD'nin sıkı bir C uygulaması önemli ölçüde daha hızlı olacaktır. Nitekim [2]'de raporlanan verilerden bunun yaklaşık iki kat daha hızlı olacağını tahmin edebiliriz.

Hızdaki fark anahtar boyutuna göre oldukça kararlıdır: aynı yapıları çok kısa (8 bayttan az) rastgele anahtarlarla test etmek elbette daha hızlı arama sağlar, ancak arama süreleri arasındaki oran aynı kalır.

Son olarak, CHD'nin çok daha büyük bir oluşturma süresi pahasına bellek kullanımını daha da azaltabildiğini göz önünde bulundurmak gerekir; ancak alandaki yalnızca %9'luk bir azalma, oluşturma süresini bir büyüklük mertebesi kadar artırır; bu da büyük veri kümeleri için bu ödünleşimi cazip olmaktan çıkarır.

Önceki peeling tabanlı uygulamalarımıza kıyasla, oluşturma süresini ≈%50 (SF) ve ≈%100 (MPHF) oranında artırırken aynı zamanda arama süresini azaltıyoruz.

Tablo 2'de r = 4 durumu için zamanlamaları raporluyoruz ([1] için oluşturma süresi tahmin edilmiştir; çünkü yazarlar bu durum için zamanlama bilgisi sağlamamaktadır). Ek gereken alan artık yalnızca ≈%3'tür (r = 3 olduğunda ≈%10 idi). Başlıca dezavantajlar daha yavaş oluşturma süresi (sistem daha yoğun hâle geldiği için) ve daha yavaş arama süresidir (çünkü daha fazla belleğe erişilmesi gerekir). r'nin daha büyük değerleri ilgi çekici değildir; çünkü alandaki marjinal kazanç ihmal edilebilir hâle gelir.

Statik fonksiyonlar, monotone minimal perfect hash fonksiyonlarının [5], zayıf önek araması için veri yapılarının [4] ve benzerlerinin temel yapı taşlarından biridir. Bu yapı taşlarının yaygın MWHC uygulamasını geliştirilmiş oluşturma yöntemimizle değiştirmek, bu veri yapılarında kullanılan alanı ve arama süresini otomatik olarak azaltacaktır.

Statik fonksiyonların ilginç bir uygulamasının, statik yaklaşık sözlüklerin neredeyse en uygun biçimde depolanması olduğunu belirtmek isteriz. Bir anahtardan rastgele bir hash fonksiyonu tarafından üretilen b bitlik bir imzaya yapılan eşlemeyi statik bir fonksiyon olarak kodlayarak, “x ∈ X?” sorusuna sabit zamanda, yanlış pozitif oranı 2^-b olacak şekilde ve (r = 4 olduğunda) yalnızca 1.03nb bit kullanarak yanıt verilebilir; alt sınır nb'dir [11].

Daha Fazla Uygulama

Statik fonksiyonlar ve minimal perfect hash fonksiyonları için yeni pratik veri yapıları tartıştık. Her ikisi de milyarlarca anahtara ölçeklenebilir ve her ikisi de önceki yapılara kıyasla arama hızını önemli ölçüde iyileştirir. Özellikle, broadword programlama ile seyrek sistemlerin çözümüne yönelik yeni ve parametresiz tembel bir yaklaşımın birleşimi sayesinde, Gauss eliminasyonuna dayalı statik fonksiyonları önceki yaklaşımlardan iki büyüklük mertebesi daha hızlı oluşturabiliyoruz. Bu yapıların, yüksek performanslı arama sunan ölçeklenebilir bir yöntem olarak zamanla köklü MWHC yaklaşımının yerini almasını bekliyoruz.

Sonuçlar

Kaynaklar

[1] Martin Aumüller, Martin Dietzfelbinger ve Michael Rink. Kuramsal olarak iyi bir veri alma veri yapısının deneysel varyasyonları. Amos Fiat ve Peter Sanders (editörler), Algorithms – ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7–9, 2009. Proceedings, Lecture Notes in Computer Science serisi, cilt 5757, sayfa 742–751. Springer, 2009.

[2] Djamal Belazzougui, Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini ve Sebastiano Vigna. Rastgele hipergraphların önbellek-duyarsız peeling işlemi. 2014 Data Compression Conference (DCC 2014) içinde, sayfa 352–361. IEEE, 2014.

[3] Djamal Belazzougui, Paolo Boldi, Rasmus Pagh ve Sebastiano Vigna. Monotone minimal perfect hashing: Sıralı bir tabloda O(1) erişimle arama. Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA) içinde, sayfa 785–794, New York, 2009. ACM Press.

[4] Djamal Belazzougui, Paolo Boldi, Rasmus Pagh ve Sebastiano Vigna. Az alan kullanarak hızlı önek araması ve uygulamaları. Mark de Berg ve Ulrich Meyer (editörler), Algorithms – ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6–8, 2010. Proceedings, Part I, Lecture Notes in Computer Science serisi, cilt 6346, sayfa 427–438. Springer, 2010.

[5] Djamal Belazzougui, Paolo Boldi, Rasmus Pagh ve Sebastiano Vigna. Monotone minimal perfect hashing'in kuramı ve uygulaması. ACM Journal of Experimental Algorithmics, 16(3):3.2:1–3.2:26, 2011.

[6] Djamal Belazzougui, Fabiano C. Botelho ve Martin Dietzfelbinger. Hash, yer değiştirme ve sıkıştırma. Amos Fiat ve Peter Sanders (editörler), Algorithms – ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7–9, 2009. Proceedings, sayfa 682–693, 2009.

[7] Djamal Belazzougui ve Gonzalo Navarro. Alfabe bağımsız sıkıştırılmış metin indeksleme. ESA (1) içinde, sayfa 748–759, 2011.

[8] Djamal Belazzougui ve Rossano Venturini. Uygulamalarıyla birlikte sıkıştırılmış statik fonksiyonlar. SODA içinde, sayfa 229–240, 2013.

[9] Paolo Boldi, Andrea Marino, Massimo Santini ve Sebastiano Vigna. BUbiNG: Kitleler için büyük ölçekli tarama. Proceedings of the Companion Publication of the 23rd International Conference on World Wide Web Companion (WWW Companion ’14) içinde, sayfa 227–228. International World Wide Web Conferences Steering Committee, 2014.

[10] Fabiano C. Botelho, Rasmus Pagh ve Nivio Ziviani. Neredeyse en uygun alanda pratik perfect hashing. Information Systems, 38(1):108–131, 2013.

[11] Larry Carter, Robert Floyd, John Gill, George Markowsky ve Mark Wegman. Kesin ve yaklaşık üyelik test edicileri. Proceedings of Symposium on Theory of Computation (STOC ’78) içinde, sayfa 59–65. ACM Press, 1978.

[12] Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld ve Ayellet Tal. Bloomier filtresi: statik destek arama tabloları için verimli bir veri yapısı. J. Ian Munro (editör), Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004) içinde, sayfa 30–39. SIAM, 2004.

[13] Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh ve Michael Rink. XORSAT aracılığıyla cuckoo hashing için sıkı eşik değerleri. Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide ve Paul G. Spirakis (editörler), Automata, Languages and Programming, Lecture Notes in Computer Science serisi, cilt 6198, sayfa 213–225. Springer Berlin Heidelberg, 2010.

[14] Martin Dietzfelbinger ve Rasmus Pagh. Veri alma ve yaklaşık üyelik için özlü veri yapıları (genişletilmiş özet). Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir ve Igor Walukiewicz (editörler), Automata, Languages and Programming, 35th International Colloquium (ICALP 2008), Proceedings, Part I: Track A: Algorithms, Automata, Complexity, and Games, Lecture Notes in Computer Science serisi, cilt 5125, sayfa 385–396. Springer, 2008.

[15] Nikolaos Fountoulakis ve Konstantinos Panagiotou. Cuckoo hashing için keskin yük eşikleri. Random Structures & Algorithms, 41(3):306–333, 2012.

[16] Alan M. Frieze ve Páll Melsted. Rastgele iki parçalı graflarda maksimum eşleşmeler ve cuckoo hash tablolarının alan kullanımı. Random Structures & Algorithms, 41(3):334–364, 2012.

[17] Andreas Goerdt ve Lutz Falke. k-XORSAT ötesinde sağlanabilirlik eşikleri. Edward A. Hirsch, Juhani Karhumäki, Arto Lepistö ve Michail Prilutskii (editörler), Computer Science — Theory and Applications: 7th International Computer Science Symposium in Russia (CSR 2012) Proceedings içinde, sayfa 148–159. Springer Berlin Heidelberg, 2012.

[18] Donald E. Knuth. The Art of Computer Programming. Pre-Fascicle 1A. Bölüm 7.1.3 taslağı: Bit düzeyinde hileler ve teknikler, 2007.

[19] Brian A. LaMacchia ve Andrew M. Odlyzko. Sonlu alanlar üzerinde büyük seyrek doğrusal sistemlerin çözülmesi. Advances in Cryptology: CRYPTO ’90 içinde, sayfa 109–133. Springer, 1991.

[20] Bohdan S. Majewski, Nicholas C. Wormald, George Havas ve Zbigniew J. Czech. Bir perfect hashing yöntemleri ailesi. Computer Journal, 39(6):547–554, 1996.

[21] Andrew M. Odlyzko. Sonlu alanlarda ayrık logaritmalar ve bunların kriptografik önemi. Advances in Cryptology içinde, sayfa 224–314. Springer, 1985.

[22] Michael Rink. Hashing Tabanlı Veri Yapılarına Uygulamalarıyla Rastgele İki Parçalı Graflarda Eşleşmeler İçin Eşikler. Doktora tezi, Technische Universität Ilmenau, 2015.