(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

arXiv:1603.04330v2 [cs.DS] 22 Mar 2016

Abstract

Son yıllarda sonlu alanlar üzerindeki rastgele doğrusal sistemlerde elde edilen ilerlemeler, mevcut tekniklere kıyasla daha az alan kullanarak statik fonksiyonları ve minimal perfect hash fonksiyonlarını temsil eden sabit zamanlı veri yapılarının oluşturulmasının önünü açmıştır. Bu sonuçların pratik uygulamalarının önündeki temel engel, bu doğrusal sistemleri çözmek için gereken kübik zamanlı Gaussian eliminasyonudur: sistemler çok küçük hale getirilebilse bile, hesaplama hâlâ uygulanabilir olmayacak kadar yavaştır.

Bu makalede, bu sistemlerin çözümünü birkaç büyüklük mertebesi hızlandırmak için çeşitli sezgisel yöntemleri ve programlama tekniklerini ayrıntılı biçimde açıklıyoruz. Böylece genel oluşturma süreci, hipergraph peeling temeline dayanan ve yaygın olarak kullanılan standart MWHC tekniği ile rekabet edebilir hale gelmektedir. Özellikle hızlı denklem işleme için broadword programlama tekniklerini ve tembel (lazy) bir Gaussian eliminasyonu algoritmasını tanıtıyoruz.

Ayrıca veri yapısına ilişkin, alan kullanımını daha da azaltan ve arama hızını artıran çeşitli teknik iyileştirmeleri de açıklıyoruz.

Bu tekniklerin uygulamamız, eleman başına 2.24 bit yer kaplayan bir minimal perfect hash fonksiyonu veri yapısı sağlamaktadır; bu değer MWHC tabanlı yapılarda 2.68 bittir. Ayrıca çarpan tabanlı ek yükü 1.23’ten 1.03’e düşüren bir statik fonksiyon veri yapısı da sunmaktadır.

Statik fonksiyonlar, sonlu kümelerden tamsayılara keyfi eşlemeleri depolamak için tasarlanmış veri yapılarıdır; yani n adet ((k_i, v_i)) çiftinden oluşan bir küme verildiğinde, burada (k_i \in S \subseteq U), (|S| = n) ve (v_i \in 2^b) olmak üzere, bir statik fonksiyon (k_i) verildiğinde sabit zamanda (v_i) değerini geri döndürür.

Bununla yakından ilişkili olan yapı minimal perfect hash fonksiyonlarıdır (MPHF); burada yalnızca anahtarlar kümesi (S) (yani (k_i)’ler) verilir ve veri yapısı (S \to n) biçiminde enjeksiyonlu bir numaralandırma üretir. Bu görevler hash tabloları kullanılarak kolayca gerçekleştirilebilir olsa da, statik fonksiyonlar ve MPHF’lerin sorgulanan anahtar özgün küme (S) içinde değilse herhangi bir değer döndürmesine izin verilir; bu gevşeme, küme (S)’nin depolanması için geçerli olan bilgi kuramsal alt sınırın aşılmasını 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, anahtarların boyutundan bağımsızdır. Bu özellik, özellikle büyük metin dizeleri kümeleriyle çalışırken statik fonksiyonları ve MPHF’leri güçlü teknikler haline getirir. Ayrıca aşağıdaki gibi alan açısından verimli veri yapılarının önemli yapı taşlarıdır:

• (sıkıştırılmış) tam metin indeksleri [7]
• monotone MPHF’ler [3, 5]
• Bloom filter benzeri veri yapıları [8]
• önek arama veri yapıları [4]

Hem teorik hem de pratik açıdan önemli bir araştırma yönü, oluşturma sürelerini uygulanabilir tutarken büyük-O alan sınırlarındaki çarpan sabitlerini azaltmaktır.

1. Introduction

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 pratik statik fonksiyonlar ve yaygın kullanılan tekniklerle karşılaştırılabilir oluşturma süreleri 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.

Milyarlarca anahtarı yönetebilen yapıları hedeflediğimiz için, bu yapıların kullanılabilir hale getirilmesindeki temel zorluk, oluşturma aşamasındaki Gaussian eliminasyonunun kübik çalışma süresini kontrol altına almaktır. Bu amaçla broadword programlama [18] ve yapılandırılmış Gaussian eliminasyonunun tembel bir sürümü üzerine kurulu yeni teknikler tanıtıyoruz.

Sonuç olarak, yaygın kullanılan hipergraph tabanlı yapılardan belirgin biçimde daha küçük olan, buna karşın arama sürelerini koruyan veya iyileştiren ve yine de uygulanabilir oluşturma süresine sahip veri yapıları elde ediyoruz.

Bu makalede tartışılan tüm uygulamalar Sux4J projesi kapsamında özgür yazılım olarak 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; burada (n), ({0,1,\ldots,n-1}) kümesiyle özdeşleştirilir. Dolayısıyla (2 = {0,1}) ve (2^b), b bitlik sayıların kümesidir.

2. Notation and Tools

Model and Assumptions

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

Hypergraphs

Bir tepe kümesi (V) üzerinde tanımlı r-hypergraph, (E \subseteq \binom{V}{r}) olacak şekilde, (V)’nin kardinalitesi (r) olan alt kümelerinin kümesinin bir alt kümesidir. (E)’nin bir elemanına kenar (edge) denir. Bir hipergraph’ın k-core’u, derecesi en az (k) olan en büyük indüklenmiş alt grafıdır.

Bir hipergraph, kenarlarının öyle bir listeye sıralanması mümkünse peelable olarak adlandırılır ki listedeki her kenar için, o kenarda bulunan ve listenin sonraki elemanlarında görünmeyen bir tepe noktası bulunsun. Bir hipergraph ancak ve ancak 2-core’u boşsa peelable’dır.

Bir hipergraph, her bir hiperkenara farklı bir tepe noktası atanabiliyorsa orientable olarak adlandırılır. Açıkça, peelable bir hipergraph orientable’dır; ancak bunun tersi her zaman doğru değildir.

3. Background and Related Work

Linear Functions and MWHC

Çoğu statik fonksiyon yapısı, gereksinimleri sağlayan bir doğrusal fonksiyon bulunmasına dayanır. Basitlik için, ikili değerli fonksiyonların özel durumuyla başlayalım; yani (v_i \in \mathbb{F}_2) (iki elemanlı alan). Amaç şu vektörü bulmaktır:

[ w \in \mathbb{F}_2^m ]

öyle ki her (i) için

[ h_\theta(k_i)^T w = v_i ]

burada (h_\theta), (\theta) ile indekslenen uygun bir (H) ailesinden gelen bir (U \to \mathbb{F}_2^m) fonksiyonudur.

Aramanın sabit zamanlı olması için ek bir kısıt daha ekleriz: (h_\theta(k)) sabit sayıda (r) adet 1 içermelidir ve bu 1’lerin konumları sabit zamanda hesaplanabilmelidir. Bu durumda, gösterimde küçük bir esneklik yaparak (h_{\theta,j})’yi j-inci sıfır olmayan elemanın konumu olarak yazabiliriz. Böylece arama işlemi

[ w_{h_{\theta,0}(k_i)} + \cdots + w_{h_{\theta,r-1}(k_i)} = v_i. ]

şeklini alır.

Böyle bir fonksiyonun var olduğu açıktır; bu durumda veri yapısında yalnızca (w) ve (\theta)’nın saklanması gerekir. (h_\theta) sabitlenmişse, yukarıdaki (n) denklemi yazmak bir doğrusal sistem elde edilmesine yol açar. Satır vektörleri (h_\theta(k_i)^T) bir matriste (H) olarak, değerler (v_i) ise (v) vektöründe toplanırsa çözmemiz gereken sistem

[ Hw = v ]

olur.

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

(v_i \in \mathbb{F}_2^b) yani b bitlik bir tamsayı olduğu genel duruma geçmek için, (v) yerine (v_i)’lerin satırlar olarak yer aldığı (n \times b) boyutlu (V) matrisini kullanırız ve (w) yerine (m \times b) boyutlu bir matris koyarız. (H)’nin tam rütbeli olması, aşağıdaki sistemin çözülebilmesi için yine yeterlidir:

[ HW = V. ]

Geriye, (H)’nin tam rütbeli olmasını sağlayacak şekilde değişken sayısı (m)’in ve (h_\theta) fonksiyonlarının nasıl seçileceğini göstermek kalır.

Öncü makalelerinde [20], Majewski, Wormald, Havas ve Czech (MWHC) bu çerçeve ile açıklanabilen ilk statik fonksiyon yapısını tanıttılar. Onlar (H) olarak, değerleri tam olarak (r) adet 1 içeren (U \to \mathbb{F}2^m) fonksiyonlarının kümesini seçerler. Yani (h\theta(k)), (j \in r) için konumları (h_{\theta,j}(k)) olan bir vektördür.

Fonksiyonlar rastgele ve eşit olasılıkla seçilirse

[ (h_{\theta,0}(k), \ldots, h_{\theta,r-1}(k)) ]

üçlüleri, (m) düğümlü rastgele bir hipergraph’ın kenarları olarak görülebilir. Eğer

[ m > c_r n ]

olursa, uygun bir (c_r) sabiti için hipergraph yüksek olasılıkla peelable olur. Peeling süreci ilişkili doğrusal sistemi üçgensel hale getirir; böylece sistem çözülebilir ve çözüm doğrusal zamanda bulunabilir.

(c_r) sabiti derece (r)’ye bağlıdır ve en küçük değerini (r = 3) için alır:

[ c_3 \approx 1.23. ]

(H) ailesi, parametresi (\theta) alt doğrusal sayıda bit ile temsil edilebilen daha küçük bir kümeyle değiştirilebilir; böylece toplam alan

[ 1.23bn + o(n) \text{ bit} ]

olur.

Uygulamada (h_{\theta,j}(k)), rastgele tohum (\theta) kullanan bir hash fonksiyonu olarak gerçekleştirilir.

MPHFs

Chazelle, Kilian, Rubinfeld ve Tal [12], MWHC yapısından bağımsız olarak, peeling sürecinin bir yan etkisi olarak her hiperkenara benzersiz bir düğüm atanabildiğini gözlemlediler. Böylece her anahtara (m) içinde enjeksiyonlu bir tamsayı atanabilir.

Hiperkenarın (r) düğümünden hangisinin atanmış olduğunu saklayarak bir perfect hash fonksiyonu (S \to m) elde ederiz. Bunun için gereken alan

[ c_r \lceil \log r \rceil n + o(n) \text{ bit} ]

düzeyindedir.

Minimal perfect hash fonksiyonu (S \to n) elde etmek için bir sıralama (ranking) yapısı eklenir. En iyi değer yine (r=3) için elde edilir ve teorik olarak

[ 2.46n + o(n) ]

bitlik bir veri yapısı sağlar [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ı geliştirdiler.

Her anahtar, rastgele bir hash fonksiyonu ile hesaplanan (\Theta(\log n)) bitlik bir imza ile değiştirilir; böylece çakışma oluşmaz. İmzalar sıralanır ve en anlamlı bitleri kullanılarak küçük parçalara ayrılır. Yukarıda açıklanan yöntem kullanılarak her parça için ayrı bir fonksiyon hesaplanır.

Parça fonksiyonlarının temsilleri tek bir dizi içinde birleştirilir ve her parçanın başlangıcını belirten ofsetler ayrı olarak saklanır.

Cache-Oblivious Constructions

HEM’e alternatif olarak [2], hipergraph’ları soyup karşılık gelen yapıları hesaplamak için yalnızca tarama ve sıralama işlemlerini kullanan cache-oblivious algoritmalar önermektedir. Bu yaklaşımın başlıca avantajı, ölçeklenebilirliği kaybetmeden HEM ofset dizisine erişim maliyetini ortadan kaldırmasıdır.

CHD

Belazzougui, Botelho ve Dietzfelbinger [6], CHD (compressed hash-and-displace) adı verilen farklı bir yapı tanıttılar. Beklenen oluşturma süresi artırılarak CHD teorik olarak yaklaşık anahtar başına 1.44 bit olan bilgi kuramsal alt sınıra ulaşabilir.

Hypergraph’ların Ötesi

Dietzfelbinger ve Pagh [14], (nb) alan sınırının önündeki sabitin keyfi olarak küçültülmesine izin vererek MWHC yapısını geliştirdiler. Calkin teoremine göre, öyle bir (\beta_r) sabiti vardır ki

[ m > \beta_r n ]

olduğunda ve (H)’nin satırları ağırlığı (r) olan rastgele vektörler olduğunda, (H) yüksek olasılıkla tam rütbeli olur.

Sonlu minimum değeri olan (c_r)’nin aksine, (\beta_r) değeri (r) arttıkça hızla azalır. Böylece daha yoğun satırlar (m)’in (n)’e yaklaşmasına izin verir. Örneğin:

• (r = 3): (\beta_3 \approx 1.12 < c_3 \approx 1.23)

Ancak MWHC’nin doğrusal zamanlı peeling algoritmasının aksine, genel matris tersleme işlemi süperkuadratik zaman gerektirir (Gaussian eliminasyonu kullanıldığında (O(n^3))). Doğrusal zaman elde etmek için anahtar kümesi bir hash fonksiyonu kullanılarak küçük alt kümelere bölünür ve her alt küme için statik fonksiyonlar bağımsız olarak hesaplanır.

Daha sonraki çalışmalar [15, 16, 13], çözülebilirlik ve yönlendirilebilirlik eşiklerini daha da geliştirmiştir:

• (r=3) için 1.09’dan küçük
• (r=4) için 1.03’ten küçük

Bu makalede geliştirilmiş yapılar sağlamak için yeni teknikleri birleştiriyoruz. Veri yapımız HEM yaklaşımını izler: anahtar kümesi rastgele olarak beklenen boyutu sabit olan parçalara bölünür ve minimal perfect hash fonksiyonu her parça için bağımsız olarak hesaplanır.

Peelable olmayı garanti eden bir tepe/kenar oranı kullanmak yerine, ilişkili doğrusal sistemin yüksek olasılıkla yönlendirilebilir ve çözülebilir olmasını garanti eden daha düşük bir oran seçiyoruz.

Peelability özelliğinin kaybı sistemi Gaussian eliminasyonu ile çözmeyi gerektirir; ancak parçaların boyutu sabit olduğundan toplam oluşturma süresi doğrusal zaman olarak kalır, buna ek olarak imzaların sıralanması için (O(n \log n)) adımı vardır.

[13] çalışmasındaki yönlendirilebilirlik eşiklerini kullanıyoruz; bunlar XORSAT çözülebilirliği eşikleriyle aynıdır. Örneğin rastgele bir 3-hypergraph için tepe/kenar oranı

[ c > 1.09 ]

olduğunda boş olmayan bir 2-core içerir, ancak yine de yönlendirilebilir kalır ve insidans matrisi tam rütbelidir.

Dolayısıyla MWHC tekniğini boş olmayan 2-core içeren 3-hypergraph’lara genişletiyoruz: peeling işleminden sonra 2-core tarafından belirlenen denklemleri çözüyoruz.

Daha önce oluşturma süresi MWHC’den iki büyüklük mertebesi daha yavaştı [1]; bu da yöntemi pratik olmayan bir hale getiriyordu. Michael Rink’in doktora tezi [22] bu sınırlamaları ayrıntılı biçimde tartışmaktadır.

Goerdt ve Falke’nin [17] modulo‑3 sistemleri üzerine yakın tarihli sonuçları, rastgele bir 3-hypergraph’ı genelleştirilmiş selfless algoritması [13] kullanarak yönlendirmeye ve oluşan modulo‑3 doğrusal sistemi çözerek bir perfect hash fonksiyonu elde etmeye de olanak tanır.

Her iki prosedürün de kontrollü bir başarısızlık olasılığı vardır; başarısızlık durumunda yeni bir hipergraph üretilir. Ayrıca sıralama bileşeninin nasıl yönetileceğini, neredeyse hiç ek alan maliyeti olmadan gerçekleştirebileceğimizi de gösteriyoruz.

5. Broadword Programming for Row Operations

Pratik bir Gaussian eliminasyonu çözümüne doğru attığımız ilk adım broadword programlamadır [18] (aynı zamanda SWAR — “SIMD Within A Register” olarak da bilinir).

Bu teknikler, değerleri (w) bitlik makine sözcüklerine paketleyerek ve tüm sözcük üzerinde işlemler uygulayarak birden fazla değerin aynı anda işlenmesini sağlar.

Teorik özlü (succinct) veri yapılarında genellikle (w = \Theta(\log n)) olduğu varsayılır ve problemler (O(w)) boyutlu alt problemlere indirgenir. Bu alt problemlerin sonuçları daha sonra önceden hesaplanarak alt doğrusal boyutta arama tablolarında saklanabilir.

Ancak pratik (n) değerleri için bu tablolar ihmal edilebilir değildir. Broadword algoritmaları genellikle aynı fonksiyonları sabit veya sabite yakın zamanda arama tablolarına ihtiyaç duymadan hesaplar.

¹ Teknik olarak makaledeki kanıt (k > 15) için verilmiştir; ancak yazarlar aynı tekniklerle sonucun (k \ge 3) için de gösterilebileceğini belirtmektedir. Uygulamada çözülebilir bir sistem üretmek için hiçbir zaman iki denemeden fazlasına ihtiyaç duymadık.

4. Alanı Sıkıştırma

Problemimiz için Gaussian eliminasyonunun iç döngüsü tamamen satır işlemlerinden oluşur: verilen x ve y vektörleri ile bir α skalerine göre x + αy hesaplanır. Alanın F2 olduğu durumda (statik fonksiyon hesaplamasında olduğu gibi) bu işlemi bir seferde w eleman üzerinde gerçekleştirmek çok kolaydır: her bit bir elemanı temsil edecek şekilde paketlenir ve skaler yalnızca 1 olabileceğinden toplam işlem C gösteriminde bit düzeyinde XOR x ^ y olur. Ancak MPHF’ler için alan F3’tür ve bu daha gelişmiş algoritmalar gerektirir.

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

Toplama işlemi için, basitçe x ve y’yi 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 bitlik sınırı aştığını unutmayın (10₂ + 10₂ = 100₂), fakat 2^w modülüne göre toplama ve çıkarma birleşmeli olduğundan, sonucun nihai olarak 2 bit içine sığması koşuluyla işlemin her bir 2 bitlik eleman üzerinde bağımsız biçimde gerçekleştirildiğini düşünebiliriz. Bu nedenle, sonuç en az 3 olduğunda değeri 3 olan bir maske hesaplamamız ve bunu x + y’den çıkarmamız gerekir.

Çıkarma işlemi çok benzerdir. Başlangıçta y’yi eleman bazında 3’ten çıkarırız; tüm elemanlar kesin olarak 3’ten küçük olduğu için herhangi bir elde oluşmaz. Böylece elde edilen elemanlar en az 1 olur. Artık x + y hesaplamasını öncekiyle aynı durum analizini kullanarak gerçekleştirebiliriz; ancak 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örler işlenebilir.

Son olarak, geri yerine koyma (back substitution) sırasında 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, satırdaki birlerin üzerinden ilerleyip sağ taraftaki matriste karşılık gelen b bitlik satırları toplayarak gerçekleştirilebilir. Birler, mevcut satır sözcüğünün LSB’si bulunarak ve standart broadword tekniği x = x & -x ile silinerek yinelenebilir.

Buna karşılık MPHFs için alan F3’tür, ancak çözüm matrisi bir vektördür; dolayısıyla çarpım yalnızca bir skaler çarpımdır. Bunu hesaplamak için, 64 bit sözcükler olarak temsil edilen iki vektörün skaler çarpımını 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 yalnızca sonuç >= 3 ise ayarlanmıştır.
    // LSB’leri temizle.
    mask &= 0x5555555555555555 << 1;

    // Şimdi MSB’si ayarlanmış 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;

    // Artık 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;
}

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’e dönüştür ve diğer her şeyi sıfırla.
    uint64_t high_shift = high >> 1;

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

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

t’yi hesaplayan ifade, x ve y içindeki karşılık gelen konumların çarpımına eşdeğer bir değeri belirli bir konuma yerleştirmeyi sağlar (bu durum durum bazında bir analizle kolayca doğrulanabilir). Bazı durumlarda 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 sözcükte ayarlanmış bitlerin sayısını döndürür). Sonucun hâlâ mod 3’e göre indirgenmesi gerektiğini unutmayın.

Broadword algoritmaları kullanılsa bile, bir HEM parçası büyüklüğündeki (binlerce denklem ve değişken) sistemleri Gaussian 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 mertebe daha yavaş hâle getirirdi.

Yapılandırılmış Gaussian 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 kullanacak şekilde yeniden yazarak doğrusal bir sistemin çözümünde gereken 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 yaklaşımdır [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ış bazı iyileştirme adımlarının uygulanmasını gerektirir.

Burada, lazy Gaussian elimination adını verdiğimiz, parametresiz yeni bir yapılandırılmış Gauss eliminasyonu sürümünü açıklıyoruz. Bu sezgisel yöntem sistemlerimizde son derece etkili oldu ve standart eliminasyonla çözülecek sistemin boyutunu orijinalinin yaklaşık %4’üne düşürdü.

Bir alan üzerindeki bir denklem sistemini ele alalım. Herhangi bir anda bir değişken active, idle veya solved olabilir ve bir denklem sparse veya dense olabilir. Başlangıçta tüm denklemler sparse ve tüm değişkenler idle durumdadır. Aşağıdaki değişmezleri koruyarak sistemi değiştireceğiz.

6. Lazy Gaussian Elimination

• Dense denklemler idle değişken içermez.
• Bir denklem en fazla bir solved değişken içerebilir.
• Bir solved değişken tam olarak bir dense denklemde görünür.

Amacımız sistemi, tüm denklemler dense olacak şekilde değiştirmektir; bunu yaparken active değişken sayısını en aza indirmeye (ya da eşdeğer olarak solved değişken sayısını en üst düzeye çıkarmaya) çalışırız. Bu noktada active değişkenlerin değerleri, solved değişken içermeyen dense denklemler üzerinde standart Gaussian eliminasyonu ile hesaplanabilir ve solved değişkenler active değişkenlere atanan değerlerden kolayca elde edilebilir.

Bir değişkenin ağırlığı, içinde göründüğü sparse denklem sayısıdır. Bir sparse denklemin önceliği ise denklemdeki idle değişken sayısıdır. Lazy Gaussian elimination denklemleri bir min-öncelik kuyruğunda tutar ve aşağıdaki işlemleri gerçekleştirir:

1. Önceliği sıfır olan ve bazı değişkenler içeren bir sparse denklem varsa dense yapılır. Eğer hiç 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 sparse denklem varsa, denklemdeki tek idle değişken solved hâline gelir ve denklem dense olur. Daha sonra bu denklem solved değişkeni diğer tüm denklemlerden elemek için kullanılır.
3. Aksi durumda, en fazla sayıda sparse denklemde görünen idle değişken active olur.

Sistem çözülebilir ise işlemin her zaman tamamlandığını unutmayın—en kötü durumda tüm idle değişkenler active yapılır (ve dolayısıyla tüm denklemler dense olur).

İki gözlem yapılabilir:

• Bir idle değişkenin ağırlığı asla değişmez; çünkü 2. adımda solved değişkeni elimine eder ve yalnızca active değişkenlerin katsayılarını değiştiririz. Bu, başlangıçta değişkenleri göründükleri denklem sayısına göre (örneğin countsort ile) sıralayabileceğimiz ve 3. adımda idle değişkenleri bu sıraya göre seçebileceğimiz anlamına gelir.
• Denklemler için aslında bir öncelik kuyruğuna ihtiyacımız yoktur: bir denklem önceliği sıfır veya bir olduğunda sırasıyla bir deque’nin sol veya sağ tarafına taşınır ve ilk adımda kontrol edilir.

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

HEM’i İyileştirme

HEM sürümümüz, yapıyı daha hızlı oluşturmak için disk üzerinde bucket sıralaması kullanır: anahtarlar önce hash değerlerinin en yüksek bitlerine bağlı olarak disk üzerinde 256 fiziksel parçaya bölünür (Jenkins’in SpookyHash fonksiyonunu kullanırız). Disk üzerindeki 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ı hariç).

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

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

Standart HEM oluşturma sürecinde, s büyüklüğündeki bir parçayla ilişkilendirilen düğüm sayısı ⌈cs⌉ ile verilir; burada c uygun bir sabittir ve offset bilgisi bu sayıların kısmi toplamlarını içerir.

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 saklanan eleman sayısıdır. ⌈cs⌉ ile arasındaki 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 offset bilgisini saklamak yerine, her parça için önceki parçalarda saklanan 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ı artık gerekli olmaz, alan kullanımı ve bellek erişim sayısı azalır.

r = 3 olduğunda, yaygın olduğu gibi, her değer için iki bit kullanabiliriz; hiperkenarla ilişkilendirilen düğüm için 0 yerine 3 değerini kullanmaya dikkat ederiz. Sonuç olarak sıralama yalnızca bir parçayla ilişkili değerlerde 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);
}

Offset ve Seed Değerlerini 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 seed değerini saklamak kalır. Bu, HEM veri yapısının tüm giriş kümesi üzerinde tek seferde fonksiyon oluşturulmasına kıyasla getirdiği toplam ek yükün tamamıdır.

Bu iki sayıyı ayrı ayrı saklamak yerine tek bir 64 bit tamsayı içinde birleştiriyoruz. Bunu mümkün kılan temel gözlem şudur: her parça için uygun bir seed bulma olasılığı son derece yüksek olduğundan, onu saklamak için çok az rastgele bit gerekir. Her parça için aynı seed dizisini kullanabilir ve başarılı olan denemeden ö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. n adet anahtar saklıyorsak seed için 64 − ⌈log n⌉ bit kullanılabilir; bu miktar gerçekçi herhangi bir n için fazlasıyla yeterlidir.

Deneysel Sonuçlar

Java kullanarak iki veri kümesi üzerinde deneyler gerçekleştirdik; bu veri kümeleri BUbiNG tarafından toplanan eu-2015 crawls verilerinden türetilmiştir. Deneyler Intel® Core™ i7-4770 CPU @ 3.40GHz (Haswell) üzerinde yapılmıştır.

• Daha küçük veri kümesi host listesidir (11,264,052 anahtar, ≈22 B/anahtar).
• Daha büyük veri kümesi sayfa listesidir (1,070,557,254 anahtar, ≈80 B/anahtar).

Crawl verileri LAW web sitesinde herkese açıktır.

Son performans değerlerinin (seçilen parça boyutuna bağlı olan) yanı sıra, ilgi çekici ölçümlerin parça boyutuyla nasıl değiştiğini görmek de önemlidir. Ş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 boyutuna göre 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ıra numarasına 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 (offset yapısının etkisi daha iyi amortize edildiği için). Aynı zamanda:

• Gaussian eliminasyonu süreci doğrusal olmayan olduğu için oluşturma süresi artar (özellikle parça boyutu 2¹¹’den sonra keskin biçimde).
• Minimal perfect hash fonksiyonları durumunda daha büyük parçalar rank fonksiyonunun parça boyutuyla doğrusal olarak daha fazla çalışmasına neden olur ve gerçekten de arama süresi keskin biçimde artar.
• Statik fonksiyonlar durumunda 2¹⁰’dan büyük parçalar offset dizisi L3 önbelleğe sığacak kadar küçüldüğünden arama süresinde küçük bir iyileşme sağlar.

Şekil 1: r = 3 olduğunda eu-2015 ve eu-2015-host veri kümeleri için eleman başına bit cinsinden boyut ile oluşturma ve arama süreleri (mikrosaniye).

Tablo 1’de “en iyi seçimimiz” olan 2¹⁰ parça boyutu için arama ve oluşturma sürelerini, aynı alan kullanımına sahip [1]’de raporlanan verilerle (yani ek 1.10 b/anahtar) ve yazarlar tarafından sağlanan CHD tekniğine ait C koduyla (http://cmph.sourceforge.net/) karşılaştırıyoruz. λ = 3 olduğunda anahtar başına bit sayısı bizimkine neredeyse aynıdır.

Büyük veri kümesi için CHD durumunda farklı donanım kullanmak zorunda kaldığımızı belirtelim; çünkü mevcut bellek (16 GB) sonucun yalnızca 3 GB olmasına rağmen oluşturma işlemini tamamlamak için yeterli değildi.

Tablo 1: Anahtar başına oluşturma ve değerlendirme süresi (r = 3)

Statik fonksiyonlar durumunda veri yapıları, daha önce mümkün olandan [1] yaklaşık iki yüz kat daha hızlı oluşturulabilmektedir.

Tablo 2: Statik fonksiyonların anahtar başına oluşturma ve değerlendirme süresi (r = 4)

eleman; arama süresi raporlanmamıştır). Okuyucuya kullandığımız her tekniğin katkısı hakkında fikir vermek için Tablo 3, soyma aşaması (peeling phase) kullanıldığında (teknik olarak gerekli değildir—sistemi doğrudan çözebilirdik), standart seyrek sistem gösterimi yerine broadword hesaplama kullanıldığında ve standart yerine lazy Gaussian elimination uygulandığında oluşturma süresindeki artışı gösterir. Tekniklerimizin birleşimi hızda elli katlık bir artış sağlar (temel hızımız zaten [1]’in yaklaşık dört katıdır; muhtemelen daha yeni donanım kullandığımız için).

Tablo 3: r = 3 için yalnızca pre-peeling (P), broadword hesaplama (B), lazy Gaussian elimination (G) ya da bunların birleşimi kullanıldığında oluşturma süresindeki artış.

BG
+13%

GP
+57%

G
+98%

BP
+296%

B
+701%

P
+2218%

None
+5490%

MPHF’ler durumunda son derece rekabetçi bir arama hızına sahibiz (CHD’nin iki katı) ve çok daha iyi ölçeklenebilirlik sağlıyoruz. Küçük boyutlarda, CHD’nin yaptığı gibi oluşturma işlemini tamamen ana bellekte gerçekleştirmek bir avantajdır; ancak veri kümesi büyüdüğünde yaklaşımımız çok daha iyi ölçeklenir.

Ayrıca, kodumuzun çalışma zamanında nesneleri bit vektörlerine dönüştüren stratejilere dayanan oldukça soyut bir Java uygulaması olduğunu da belirtiriz: bu nedenle her türlü nesne anahtar olarak kullanılabilir. CHD’de olduğu gibi yalnızca bayt dizilerini hashleyebilen sıkı bir C uygulaması önemli ölçüde daha hızlı olurdu. Nitekim, [2]’de rapor edilen verilerden bunun yaklaşık iki kat daha hızlı olacağını tahmin edebiliriz.

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

Son olarak, çok daha uzun bir oluşturma süresi pahasına CHD’nin bellek kullanımını daha da azaltabileceği dikkate alınmalıdır; ancak alanda yalnızca %9’luk bir azalma, oluşturma süresini bir büyüklük mertebesi artırır ve bu da büyük veri kümeleri için bu değiş tokuşu cazip olmaktan çıkarır.

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

Tablo 2’de r = 4 durumu için zamanlamaları rapor ediyoruz ([1] için oluşturma süresi tahmin edilmiştir, çünkü yazarlar bu durum için zamanlama verileri sağlamamaktadır). Artık gerekli ek alan yalnızca ≈%3’tür (r = 3 olduğunda ≈%10 olmasına karşılık). Başlıca dezavantajlar daha yavaş oluşturma süresi (sistem daha yoğun hale geldiğinden) 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 hale gelir.

Statik fonksiyonlar, monoton 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ında yaygın olarak kullanılan MWHC uygulamasını geliştirilmiş yapımızla 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 optimal depolanması olduğunu belirtiriz. Rastgele bir hash fonksiyonu tarafından üretilen b-bitlik bir imzaya bir anahtardan yapılan eşlemeyi statik bir fonksiyon olarak kodlayarak, “x ∈ X?” sorusu sabit zamanda yanıtlanabilir; yanlış pozitif oranı 2−b olur ve (r = 4 olduğunda) yalnızca 1.03nb bit kullanılır; alt sınır nb’dir [11].

Diğer Uygulamalar

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, geniş sözcük (broadword) programlama ile seyrek sistemlerin çözümü için parametresiz yeni bir tembel yaklaşımın birleşimi sayesinde, Gaussian eliminasyonu tabanlı statik fonksiyonları önceki yaklaşımlardan iki büyüklük mertebesi daha hızlı oluşturabiliriz. Bu yapıların zamanla, yüksek performanslı arama sağlayan ölçeklenebilir bir yöntem olarak köklü MWHC yaklaşımının yerini almasını bekliyoruz.

Sonuçlar

Kaynaklar

[1] Aumüller, M., Dietzfelbinger, M., Rink, M.: Kuramsal olarak iyi bir erişim veri yapısının deneysel varyasyonları. İçinde: Fiat, A., Sanders, P. (eds.) Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7–9, 2009. Proceedings. Lecture Notes in Computer Science, cilt 5757, ss. 742–751. Springer (2009)

[2] Belazzougui, D., Boldi, P., Ottaviano, G., Venturini, R., Vigna, S.: Rastgele hipergrafların önbellek-duyarsız peeling işlemi. İçinde: 2014 Data Compression Conference (DCC 2014). ss. 352–361. IEEE (2014)

[3] Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Monoton minimal perfect hashing: O(1) erişimle sıralı bir tabloda arama. İçinde: Proceedings of the 20th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA). ss. 785–794. ACM Press, New York (2009)

[4] Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Az alan kullanarak hızlı önek araması ve uygulamaları. İçinde: de Berg, M., Meyer, U. (eds.) Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6–8, 2010. Proceedings, Part I. Lecture Notes in Computer Science, cilt 6346, ss. 427–438. Springer (2010)

[5] Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Monoton minimal perfect hashing’in kuramı ve uygulaması. ACM Journal of Experimental Algorithmics 16(3), 3.2:1–3.2:26 (2011)

[6] Belazzougui, D., Botelho, F.C., Dietzfelbinger, M.: Hash, yer değiştirme ve sıkıştırma. İçinde: Fiat, A., Sanders, P. (eds.) Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7–9, 2009. Proceedings. ss. 682–693 (2009)

[7] Belazzougui, D., Navarro, G.: Alfabe bağımsız sıkıştırılmış metin indeksleme. İçinde: ESA (1). ss. 748–759 (2011)

[8] Belazzougui, D., Venturini, R.: Uygulamalarıyla birlikte sıkıştırılmış statik fonksiyonlar. İçinde: SODA. ss. 229–240 (2013)

[9] Boldi, P., Marino, A., Santini, M., Vigna, S.: BUbiNG: Herkes için büyük ölçekli web tarama. İçinde: Proceedings of the Companion Publication of the 23rd International Conference on World Wide Web Companion. ss. 227–228. WWW Companion ’14, International World Wide Web Conferences Steering Committee (2014)

[10] Botelho, F.C., Pagh, R., Ziviani, N.: Neredeyse optimal alanda pratik perfect hashing. Inf. Syst. 38(1), 108–131 (2013)

[11] Carter, L., Floyd, R., Gill, J., Markowsky, G., Wegman, M.: Kesin ve yaklaşık üyelik testleri. İçinde: Proceedings of Symposium on Theory of Computation (STOC ’78). ss. 59–65. ACM Press (1978)

[12] Chazelle, B., Kilian, J., Rubinfeld, R., Tal, A.: Bloomier filter: statik destek arama tabloları için verimli bir veri yapısı. İçinde: Munro, J.I. (ed.) Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004. ss. 30–39. SIAM (2004)

[13] Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R., Rink, M.: XORSAT aracılığıyla cuckoo hashing için sıkı eşik değerleri. İçinde: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P. (eds.) Automata, Languages and Programming. Lecture Notes in Computer Science, cilt 6198, ss. 213–225. Springer Berlin Heidelberg (2010)

[14] Dietzfelbinger, M., Pagh, R.: Erişim ve yaklaşık üyelik için özlü veri yapıları (genişletilmiş özet). İçinde: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Proceedings, Part I: Track A: Algorithms, Automata, Complexity, and Games. Lecture Notes in Computer Science, cilt 5125, ss. 385–396. Springer (2008)

[15] Fountoulakis, N., Panagiotou, K.: Cuckoo hashing için keskin yük eşikleri. Random Struct. Algorithms 41(3), 306–333 (2012)

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

[17] Goerdt, A., Falke, L.: k-XORSAT ötesinde sağlanabilirlik eşikleri. İçinde: Hirsch, E.A., Karhumäki, J., Lepistö, A., Prilutskii, M. (eds.) Computer Science — Theory and Applications: 7th International Computer Science Symposium in Russia, CSR 2012. Proceedings. ss. 148–159. Springer Berlin Heidelberg (2012)

[18] Knuth, D.E.: The Art of Computer Programming. Pre-Fascicle 1A. Draft of Section 7.1.3: Bitwise Tricks and Techniques (2007)

[19] LaMacchia, B.A., Odlyzko, A.M.: Sonlu alanlar üzerinde büyük seyrek doğrusal sistemlerin çözümü. İçinde: Advances in Cryptology: CRYPTO ’90. ss. 109–133. Springer (1991)

[20] Majewski, B.S., Wormald, N.C., Havas, G., Czech, Z.J.: Bir perfect hashing yöntemleri ailesi. Comput. J. 39(6), 547–554 (1996)

[21] Odlyzko, A.M.: Sonlu alanlarda ayrık logaritmalar ve bunların kriptografik önemi. İçinde: Advances in Cryptology. ss. 224–314. Springer (1985)

[22] Rink, M.: Hashing tabanlı veri yapıları için uygulamalarla birlikte rastgele iki parçalı graflarda eşleşme eşikleri. Doktora tezi, Technische Universität Ilmenau (2015)