Rastgele Hiperçizgelerin Cache-Oblivious Soyulması

Djamal Belazzougui1, Paolo Boldi2, Giuseppe Ottaviano3, Rossano Venturini4 ve Sebastiano Vigna2
1 Bilgisayar Bilimleri Bölümü, Helsinki Üniversitesi, djamal.belazzougui@cs.helsinki.fi
2 Dipartimento di Informatica, Università degli Studi di Milano, {boldi,vigna}@di.unimi.it
3 ISTI-CNR, Pisa, giuseppe.ottaviano@isti.cnr.it
4 Dipartimento di Informatica, Università di Pisa, rossano@di.unipi.it

Rastgele üretilmiş bir hiperçizgede bir soyma sırasının hesaplanması, perfect hashing şemaları, rastgele r-SAT çözücüleri, hata düzeltme kodları ve yaklaşık küme kodlamaları gibi birçok yapının en çok zaman alan adımıdır. Doğrudan uygulanabilen doğrusal zamanlı bir algoritma bulunmasına rağmen, zayıf I/O performansı nedeniyle boyutu mevcut iç belleği aşan hiperçizgeler için pratik değildir.

Bir soyma sırasının hesaplanmasını az sayıda ardışık tarama ve sıralamaya indirgemeyi gösteriyor ve I/O karmaşıklığını cache-oblivious modelinde analiz ediyoruz. Ortaya çıkan algoritma, n kenarlı rastgele bir hiperçizgeyi soymak için O(sort(n)) I/O ve O(n log n) zaman gerektirir.

Bu algoritmanın uygulamasının performansını gerçek bir senaryoda deneysel olarak değerlendiriyoruz; test durumu olarak minimal perfect hash functions (MPHF) oluşturmayı kullanıyoruz: algoritmamız tek bir makinede 7.6 milyar anahtar için bir MPHF'yi 21 saatten kısa sürede oluşturur. Ortaya çıkan veri yapısı, büyük ölçekli anahtar kümeleri için mevcut en ileri MPHF oluşturma yöntemleriyle elde edilenden hem daha az alan kullanır hem de daha hızlıdır.

Paolo Boldi ve Sebastiano Vigna, EU-FET NADINE (GA 288956) hibesi tarafından desteklenmiştir. Giuseppe Ottaviano, Midas EU Project (318786), MaRea project (POR-FSE-2012) ve Tiscali tarafından desteklenmiştir. Rossano Venturini, İtalya MIUR projesi PRIN ARS Technomedia 2012 ve eCloud EU Project (325091) tarafından desteklenmiştir.

arXiv:1312.0526v1 [cs.DS] 2 Dec 2013

Özet

1 Giriş

Hiperçizgeler, bir sistemdeki değişkenler arasındaki bağımlılık kümelerini modellemek için kullanılabilir: düğümler değişkenlere, kenarlar ise değişkenler arasındaki bağıntılara, örneğin değişkenleri birlikte bağlayan denklemlere karşılık gelir. Bu karşılık, çizge kuramı özelliklerinin özgün bağımlılık sistemindeki çözülebilirlik koşullarına aktarılmasını sağlar.

Bunlar arasında en kullanışlı kavramlardan biri soyma sırasıdır. Bir r-hiperçizgesi verildiğinde, soyma sırası; kenarların, sıradaki önceki kenarlar kaldırıldıktan sonra elde edilen altçizgede her kenarın derece 1 olan bir düğüme sahip olacağı şekilde sıralanmasıdır. Böyle bir sıra, hiperçizgenin boş olmayan bir 2-core'a sahip olmaması durumunda vardır; yani tüm düğümlerinin derecesi en az 2 olan bir altçizge oluşturan bir düğüm kümesi bulunmadığında.

Yukarıdaki yorumda, bir sistemin denklemleri soyma sırasına göre düzenlenirse, her denklem sıralamada kendisinden sonra gelen hiçbir denklemde görünmeyen en az bir değişken içerir; yani sistem üçgensel hale gelir ve geriye doğru yerine koyma yöntemiyle kolayca çözülebilir. Bu nedenle soyma sıraları, hash yapıları [3, 6, 9, 10, 11, 12, 21], rastgele r-SAT örneklerinin çözümü [12, 24, 25] ve hata düzeltme kodlarının oluşturulması [15, 20, 23] gibi birçok temel problemde uygulama bulmuştur. Bu uygulamalar, rastgele bir r-hiperçizgenin kenar seyrekliği γ belirli bir seyreklik eşiği cr değerinden büyük olduğunda (örneğin c3 ≈ 1.221), yüksek olasılıkla hiperçizgenin boş bir 2-core'a sahip olacağı garantisini kullanır [25].

Perfect hash function (PHF) oluşturulması, yukarıda bahsedilen uygulamalar arasında muhtemelen en önemlisidir. n anahtardan oluşan bir S kümesi verildiğinde, S için bir PHF, n anahtarı ilk m doğal sayının kümesine bire bir olacak şekilde eşler. Eğer m = n = |S| ise perfect hash function minimaldir (MPHF). Mehlhorn [22] tarafından verilen bir alt sınır, bir MPHF'yi temsil etmek için n log e ≈ 1.44n bit gerektiğini belirtir; buna karşılık gelen (daha düşük mertebeden terimler hariç) bir üst sınır [16]'da verilmiştir, ancak bu yapı pratik değildir. Bunun yerine çoğu pratik yaklaşım rastgele 3-hiperçizgelere dayanır ve yaklaşık 2c3 n ≈ 2.5n bit kullanan MPHFs üretir [6, 10, 21]. Bölüm 3'te gözden geçirdiğimiz bu çözümler, aslında en zor görevi bir soyma sırasının hesaplanması olan MWHC tekniğine [21] dayanır.

Var olduğu durumda bir soyma sırası veya olmadığı durumda bir 2-core bulmak için şaşırtıcı derecede basit bir açgözlü algoritma vardır: derece 1 olan bir düğüm bulunur, tek kenarı hiperçizgeden kaldırılır (soyulur) ve bu işlem ya kenar kalmayana kadar (bu durumda kaldırma sırası bir soyma sırasıdır) ya da kalan tüm izole olmayan düğümlerin derecesi en az 2 olana kadar (bu durumda bir 2-core oluşur) tekrarlanır. Bu algoritma doğrusal zaman ve alanla çalışacak şekilde kolayca uygulanabilir.

MPHF'ler, (sıkıştırılmış) tam metin indeksleri [4], monoton MPHFs [1], Bloom filter benzeri veri yapıları [5] ve önek arama veri yapıları [2] gibi birçok alan verimli veri yapısının ana bileşenidir. Bu tür veri yapılarından en çok fayda sağlayan uygulamaların genellikle ana belleğin büyüklüğünden kat kat daha büyük anahtar kümeleri içerdiği açıktır. Ne yazık ki standart doğrusal zamanlı soyma algoritması, nihai veri yapısı anahtar başına yalnızca birkaç bit ile saklanabilse bile, çalışma belleğinde anahtar başına birkaç on bayt gerektirir. Bu nedenle veri yapısı belleğe sığsa bile, onu gerçekten oluşturmak için bellek yeterli olmayabilir. Bu durumda dış belleğe başvurmak gerekir, ancak algoritmanın zayıf I/O performansı böyle bir yaklaşımı uygulanamaz hale getirir.

Uygulamaya özel geçici çözümler geliştirilmiştir; örneğin Botelho ve arkadaşları [6], anahtar kümesini küçük kovalar hâlinde bölerek ve her kova için bağımsız MPHFs hesaplayarak dış bellekte MPHF oluşturmak için bir algoritma (HEM olarak adlandırılır) önermiştir. Verilen bir anahtarın hangi kovada olduğunu bulmak için birinci seviye bir indeks kullanılır. Bu çözümün başlıca dezavantajı, birinci seviye indeksin hem alan hem de sorgulama süresinde kayda değer bir ek yük getirmesidir; ayrıca bu yapı hashing dışındaki uygulamalara genişletilemez.

Bu makalede, n kenarlı ve γn düğümlü (r = O(1) ve γ > cr) rastgele bir r-hiperçizgesi verildiğinde, cache-oblivious modelinde yüksek olasılıkla O(n log n) zamanda ve O(sort(n)) I/O ile bir soyma sırası hesaplayan ilk verimli algoritmayı sunuyoruz. Bu sonucu kullanarak (monoton) MPHFs, statik fonksiyonlar ve Bloom filter benzeri veri yapılarını O(sort(n)) I/O ile oluşturabiliriz. Deneysel değerlendirmemizde algoritmanın gerçekten çok büyük hiperçizgeleri soyabilmesini sağladığını gösteriyoruz: 7.6 milyar anahtardan oluşan bir küme için bir MPHF 21 saatten kısa sürede hesaplanmıştır; aynı donanımda standart algoritma 2.1 milyardan fazla anahtarı işleyemezdi. Deneylerde minimal perfect hash function oluşturmayı test durumu olarak kullansak da, temel hiperçizgelerin rastgele doğası nedeniyle bu sonuçlar diğer tüm uygulamalar için de geçerlidir.

2 Gösterim ve Araçlar

Model ve Varsayımlar

Algoritmalarımızı cache-oblivious modelinde [14] analiz ediyoruz. Bu modelde makine iki seviyeli bir bellek hiyerarşisine sahiptir: hızlı seviye M kelimelik bilinmeyen büyüklükte bir kapasiteye sahiptir ve verilerimizin bulunduğu yavaş seviye sınırsız büyüklüktedir. Hızlı seviyenin, bilinmeyen B ≤ M kelimelik bloklar hâlinde yapılan aktarımlarla (diğer adıyla I/O) yavaş seviyeye karşı optimal bir değiştirme stratejisi kullanan bir önbellek görevi gördüğünü varsayıyoruz; bir algoritmanın I/O maliyeti bu blok aktarımlarının toplam sayısıdır.

Tarama ve sıralama, cache-oblivious algoritmaların tasarımında iki temel yapı taşıdır [14]. Tall-cache varsayımı altında [8], N bitişik öğeden oluşan bir dizi için tarama ve sıralama için gereken I/O sayıları şunlardır:

• scan(N) = O(1 + N / B)
• sort(N) = O((N / B) log_{M/B} (N / B))

Hiperçizgeler

Bir V düğüm kümesi üzerindeki bir r-hiperçizge, V'nin r kardinaliteli alt kümelerinin kümesi olan (\binom{V}{r})'nin bir E alt kümesidir. E'nin bir elemanına kenar denir. V'den sıralı bir r-li demete yönlendirilmiş kenar diyoruz; e bir kenar ise, düğümleri e'de bulunan bir yönlendirilmiş kenar e'nin bir yönlendirmesi olarak adlandırılır.

Bundan sonra 3-hiperçizgelere odaklanacağız; genel r için genelleştirme doğrudandır. Geçerli yönlendirmeleri, v1 < v2 olacak şekilde (v0, v1, v2) yönlendirilmiş kenarları olarak tanımlarız (genel r için v1 < ... < v_{r−1}). Böylece her kenar için 6 yönlendirme vardır, ancak yalnızca 3'ü geçerlidir (r! yönlendirmeden r tanesi geçerlidir).

Bir geçerli yönlendirilmiş kenarın (v0, v1, v2) i'inci yönlendirme olduğunu, v0'ın üç düğüm arasındaki i'inci en küçük olması durumunda söyleriz; özellikle 0'ıncı yönlendirme kanonik yönlendirmedir. Kenarlar kanonik yönlendirmeleri ile bire bir eşleşir. Ayrıca geçerli yönlendirmeler, e bir kenar ve v e içinde bulunan bir düğüm olacak şekilde (e, v) çiftlerine aşağıdaki karşılıkla bire bir eşlenebilir:

(v0, v1, v2) → ({v0, v1, v2}, v0)

Bundan sonra tüm yönlendirmelerin geçerli olduğunu varsayacağız; bu nedenle yönlendirme terimini geçerli yönlendirme anlamında kullanacağız.

Majewski ve arkadaşları [21], sıralamayı koruyan bir minimal perfect hash function hesaplamak için bir teknik (MWHC) önermiştir; yani bir anahtar kümesi S'yi belirli bir biçimde [|S|] aralığına eşleyen bir fonksiyon. Bu teknik aslında f : S → [σ] biçimindeki herhangi bir fonksiyonun özlü bir biçimde saklanmasını mümkün kılar. Bu bölümde yapılarını kısaca açıklıyoruz.

Öncelikle üç rastgele hash fonksiyonu seçeriz h0, h1, h2 : S → [γn] ve γ değeri kritik eşik c3'ün üzerinde sabit bir değer olacak şekilde γn düğümlü bir 3-hiperçizge oluştururuz [25]; her anahtar x, {h0(x), h1(x), h2(x)} kenarına eşlenir.

Amaç, γn adet [σ] aralığında tamsayı içeren bir u dizisi bulmaktır; öyle ki her anahtar x için şu eşitlik sağlansın:

f(x) = u_{h0(x)} + u_{h1(x)} + u_{h2(x)} mod σ

Bu, n denklem ve γn değişken u_i içeren doğrusal bir sistem verir; eğer ilgili hiperçizge soyulabilirse sistemi çözmek kolaydır. γ değeri kritik eşikten büyük olduğundan, n → ∞ iken algoritma 1 − o(1) olasılıkla başarılı olur [25].

Her biri ⌈log σ⌉ bit gerektiren bu u_i değerlerini ve üç hash fonksiyonunu saklayarak f(x) değerini geri elde edebiliriz. Toplamda gereken alan ⌈log σ⌉ γn bittir; bu miktar bir ranking yapısı kullanılarak ⌈log σ⌉ n + γn + o(n) seviyesine indirilebilir [17].

Bu teknik MPHFs oluşturmak için kolayca genişletilebilir: f : S → [3] fonksiyonunu x → i olarak tanımlarız; burada h_i(x), x'e karşılık gelen kenar soyulduğunda derece 1 olan düğümdür. Bu durumda h_{f(x)}(x) : S → [γn] bir PHF olur. Fonksiyon daha sonra u vektörü üzerinde bir ranking yapısı eklenerek tekrar minimal hâle getirilebilir [6].

Giriş bölümünde belirtildiği gibi, doğrusal sistemi çözmek için gerekli soyma işlemi açgözlü bir algoritma kullanılarak doğrusal zamanda gerçekleştirilebilir (standart doğrusal zamanlı soyma olarak adlandırılır). Ancak bu işlem, muhasebe amacıyla anahtar başına birkaç tamsayıya rastgele erişim gerektirir; ayrıca çizge rastgele olduğundan ziyaret sırası da rastgeleye yakındır. Sonuç olarak, anahtar kümesi çalışma veri yapılarının bir kısmının diske taşınmasını gerektirecek kadar büyükse, I/O hacmi algoritmayı kabul edilemez derecede yavaşlatır.

Pratik Geçici Çözümler (HEM)

Botelho ve arkadaşları [6] pratik bir dış bellek çözümü önermiştir. Her anahtar, çakışma olmayacak şekilde rastgele bir hash fonksiyonu ile hesaplanan Θ(log n) bitlik bir imza ile değiştirilir. Daha sonra bu imzalar sıralanır ve en anlamlı bitlerine göre küçük kovalar hâlinde bölünür; her kova için yukarıda açıklanan yaklaşımla ayrı bir MPHF hesaplanır.

Daha sonra kova fonksiyonlarının gösterimleri tek bir dizi içinde birleştirilir ve ofsetleri ayrı bir vektörde saklanır.

Oluşturma algoritması yalnızca imzaların sıralanmasını (dış bellekte verimli şekilde yapılabilir) ve ortaya çıkan dizinin taranarak kova fonksiyonlarının hesaplanmasını gerektirir; bu nedenle son derece ölçeklenebilirdir. Ancak bloklara erişmek için gereken ek dolaylı adresleme, elde edilen veri yapısının tek bir fonksiyonun tüm anahtar kümesi üzerinde hesaplanmasıyla elde edilene göre hem daha yavaş hem de daha büyük olmasına yol açar.

Yazarlar, HEM adı verilen pratik bir yapı sürümü ile yaptıkları deneylerde elde edilen veri yapısının düz MWHC ile oluşturulana göre %21 daha büyük olduğunu ve sorgulamaların %30–50 daha yavaş olduğunu rapor etmiştir. Benzer bir ek yük bizim deneylerimizde de doğrulanmıştır; bu deneyler Bölüm 5'te tartışılmaktadır.

Bu bölümde bir r-hiperçizgeyi soymak için cache-oblivious bir algoritma açıklıyoruz. Algoritmayı 3-hiperçizgeler için anlatıyoruz, ancak genel r için genelleştirmek kolaydır.

Algoritmanın yürütülmesi boyunca hiperçizgeyi temsil etmek için her v0 düğümünün insidans listesini saklayan bir veri yapısına ihtiyacımız vardır; yani şu listeyi:

L_{v0} = {(v0, v1^0, v2^0), ..., (v0, v1^{d−1}, v2^{d−1})}

Burada liste, ilk düğümü v0 olan geçerli yönlendirilmiş kenarlardan oluşur.

Soyma algoritmasını gerçekleştirmek için listeler üzerinde aşağıdaki işlemleri uygulamak yeterlidir.

Yukarıdaki tüm işlemler için kenarın geçerli bir yönlendirme ile verildiği varsayılır. Bu işlemler kümesi altında veri yapısının kenarların gerçek listesini saklaması gerekmez: bunun yerine şu biçimde bir demet saklamak yeterlidir:

(v0, d, ṽ1, ṽ2)

Burada d kenar sayısıdır ve ṽ1 = XOR_{j<d} v1^j ile ṽ2 = XOR_{j<d} v2^j olup, yani listedeki aynı konumdaki tüm düğümler birlikte XOR işlemi uygulanarak birleştirilir.

Bir (v0, v1', v2') kenarı üzerindeki AddEdge ve DeleteEdge işlemleri, sırasıyla v1' değerini ṽ1 içine ve v2' değerini ṽ2 içine XOR'lar ve d değerini artırır ya da azaltır. Tüm kenarların geçerli olduğu varsayıldığından (yani v1' < v2'), bu işlemler değişmezliği korur.

D = 1 olduğunda açıkça ṽ1 = v1 ve ṽ2 = v2 olur; burada (v0, v1, v2) L_{v0} içindeki tek kenardır, dolayısıyla RetrieveEdge tarafından döndürülebilir.

Gerekirse veri yapısı (v0, v1, v2, ℓ) biçimindeki etiketli kenarlara da kolayca genişletilebilir; bunun için ℓ etiketleri yeni bir ṽℓ alanında XOR'lanır.

Bu veri yapısına packed incidence list adını veriyoruz ve bu tekniğe XOR trick diyoruz. Açık bir liste tutmaya göre avantajı, belirgin alan tasarrufunun yanı sıra, bağlı kenar sayısından bağımsız olarak her düğüm için yalnızca tek bir sabit boyutlu kayıt tutmanın yeterli olmasıdır.

Bu durum bir sonraki bölümdeki soyma algoritmasını önemli ölçüde daha basit ve daha hızlı hâle getirecektir. Aynı teknik, geleneksel olarak kullanılan bağlı listelerin yerine kullanılarak standart doğrusal zamanlı algoritmaya da uygulanabilir. Bölüm 5'te göreceğimiz gibi, hem çalışma alanında hem de çalışma süresinde iyileşmeler belirgindir.

Sunulan soyma (peeling) yordamı, Molloy [25] tarafından sunulan CORE yordamının bir uyarlamasıdır. Temel fikir, işlemi turlar hâlinde yürütmektir: her turda derece 1 olan tüm düğümler kaldırılır ve ardından ya bir 2-core kalana kadar ya da grafik boşalana kadar, elde edilen indüklenmiş altgraf üzerinde bir sonraki tur gerçekleştirilir. İkinci durumda algoritma, kenarları her tur için bir katman olacak şekilde aşağıdaki tanımları kullanarak bir katmanlar dizisine ayırır:

• Degree(Lv0), v0 düğümünün bağlanım (incidence) listesinde bulunan kenar sayısı d'yi döndürür;
• DeleteEdge(Lv0, e), e kenarını v0'ın bağlanım listesinden siler;
• RetrieveEdge(Lv0), Degree(Lv0) = 1 ise listedeki tek kenarı döndürür.

Her katman, kendi turunda kaldırılan kenarların kümesi olarak tanımlanır. Katmanların birleştirilmesiyle elde edilen kenar sırasının, her katman içindeki sıra ne olursa olsun bir soyma sırası (peeling order) olduğu kolayca görülebilir.

Katmanlı soyma süreci az sayıda turda sonlanır: Jiang ve diğerleri [18], hipergraph rastgele ve soyma eşiğinin üzerinde bir seyrekliğe sahip olacak şekilde üretildiğinde, tur sayısının yüksek olasılıkla O(log log n) ile sınırlı olduğunu göstermiştir. Ayrıca, her turda kalan düğümlerin oranı çift üstel olarak azalır. Aşağıda algoritmanın, hipergraph temsilinde ve güncelleme adımında özel dikkat gösterilerek G/Ç açısından verimli bir biçimde nasıl uygulanacağını gösteriyoruz.

Hipergraph temsili

Her i turunda hipergraph, Bölüm 4.1'de açıklandığı gibi (v0, d, ˜v1, ˜v2) biçimindeki demetlerden oluşan Ei listesi ile temsil edilir; her demet v0'ın bağlanım listesini temsil eder. Her Ei listesi v0'a göre sıralıdır. e = {v0, v1, v2} biçimindeki her kenarın tüm düğümlerinin bağlanım listelerinde bulunması gerektiğini unutmayın; dolayısıyla e kenarının üç yönelimi de Ei listesinde yer alır.

E0'ın oluşturulması

İlk tur için kenar listesi olan E0'ı oluşturmak amacıyla, hipergraph içindeki tüm kenarların tüm geçerli yönelimlerini tek bir listede bir araya getiririz. Liste daha sonra v0'a göre sıralanır ve sıralanmış listeden sıralı bağlanım listeleri E0 elde edilebilir: yönlendirilmiş kenarlar v0'a göre gruplanır, ardından boş paketlenmiş bağlanım listesi (v0, 0, 0, 0) ile başlanır ve gruptaki tüm kenarlar için AddEdge uygulandıktan sonra liste E0'a eklenir. G/Ç karmaşıklığı O(sort(n) + scan(n)) = O(sort(n)) olur.

Tur güncellemesi

Her turun başlangıcında bize i turunda hâlâ mevcut olan kenarların listesi Ei verilir ve Ei+1 üretilir. Önce Ei taranarak Degree(L) = 1 olan tüm L demetleri bulunur; her demet için RetrieveEdge uygulanır ve kenar Di listesine konur. Bu liste, mevcut i turunda kaldırılacak tüm kenarları temsil eder.

Aynı kenar, farklı yönelimler altında Di içinde birden fazla kez bulunabilir (mevcut turda birden fazla düğümünün derecesi 1 ise). Yinelenenleri kaldırmak için yönlendirilmiş kenarları kanonik yönelimlerine göre sıralar, her kenar için tek bir yönelim tutar ve bunları Pi listesinde saklarız.

Şimdi kenarları hipergraph'tan kaldırmamız gerekir. Bunun için Pi içindeki her kenar için üç yönelimi de içeren bir derece güncelleme listesi Ui üretir ve Ui listesini v0'a göre sıralarız. Hem Ei hem de Ui v0'a göre sıralı olduğundan, bunları v0 üzerinden eşleştirerek eşzamanlı biçimde tarayabiliriz. Ei içindeki her Lv0 demeti için, Ui içinde v0 ile başlayan yönlendirilmiş bir kenar yoksa demet Ei+1'e kopyalanır; aksi durumda her böyle yönlendirilmiş kenar e için DeleteEdge(Lv0, e) çağrılır ve elde edilen yeni L′v0, boş değilse Ei+1'e yazılır. Ei+1'in v0'a göre sıralı kaldığını unutmayın.

Her turda Ei iki kez ve Ui bir kez taranır, ayrıca Di ve Ui sıralanır. Bu durumda G/Ç sayısı şu olur:

2 scan(|Ei|) + scan(|Ui|) + sort(|Di|) + sort(|Ui|).

Tüm turlar üzerinden topladığımızda:

Σi (2 scan(|Ei|) + sort(|Di|) + sort(|Ui|) + scan(|Ui|)) = O(sort(n))

çünkü her kenar en fazla üç Di listesine ve üç Ui listesine ait olur. Her turda kalan düğümlerin oranı çift üstel olarak azaldığından ve XOR tekniği sayesinde Ei, i. turda canlı olan her düğüm için tam olarak bir demet içerdiğinden, Ei listelerinin tarama maliyeti toplamda O(scan(n)) G/Ç olur. Dolayısıyla genel olarak algoritma O(n log n) zaman ve O(sort(n)) G/Ç gerektirir.

Sonucu aşağıdaki teoremde özetliyoruz.

Teorem 4.1

r sabit ve γ > cr olacak şekilde n kenara ve γn düğüme sahip rastgele bir r-hipergraph'ın bir soyma sırası, cache-oblivious modelinde O(n log n) zamanda ve yüksek olasılıkla O(sort(n)) G/Ç ile hesaplanabilir.

Aşağıda uygulamamızda kullandığımız en önemli iyileştirmeleri sunuyoruz. Deneylerde kullanılan kaynak kodu şu adreste bulunmaktadır:

https://github.com/ot/emphf

uygulama ayrıntıları hakkında daha fazla bilgi edinmek ve ölçümleri yeniden üretmek isteyen okuyucular için.

Uygulama ayrıntıları

Dosya G/Ç

Dosya G/Ç işlemlerini doğrudan yönetmek yerine, dosya destekli bir bellek alanı oluşturan bir C++ bellek ayırıcı kullanarak memory-mapped dosya kullanıyoruz. Bu sayede std::vector gibi standart STL kapsayıcılarını sanki iç bellekte bulunuyorlarmış gibi kullanabiliyoruz. Eşlenen bölgenin ardışık erişim için optimize edilmesi amacıyla çekirdeğe talimat vermek üzere madvise kullanıyoruz. Özellikle, memory-mapped bölge üzerinde MADV_SEQUENTIAL parametresiyle madvise sistem çağrısını kullanıyoruz.

Sıralama

Sıralama uygulamamız iki adım gerçekleştirir. İlk adımda değerlerin alanını eşit aralıklı k kovaya böleriz; her kovaya düşen değer sayısını bulmak için diziyi tarar, ardından her değeri kendi kovasına taşırız. İkinci adımda her kova, C++ standart kütüphanesindeki sort kullanılarak sıralanır.

Kova sayısı, çok yüksek olasılıkla her kovaya ait verinin iç belleğe sığmasını sağlayacak şekilde seçilir; grafik rastgele olduğundan kenarları eşit biçimde dağılmıştır ve bu da eşit kovalamayı yüksek olasılıkla dengeli kılar.

Değerleri k kovaya dağıtmak için her kova için boyutu T olan bir tampon kullanırız; tampon dolduğunda diske yazılır. Bu algoritmanın teknik olarak cache-oblivious olmadığını belirtmek gerekir; çünkü mevcut bellek M en az kT olduğu sürece çalışır. k değerini Θ(S/M) olarak seçmek (S sıralanacak verinin boyutu olmak üzere) M'nin Ω(√(TS)) olmasını gerektirir.

Uygulamamızda T ≈ 1 MiB kullanıyoruz; dolayısıyla örneğin M = 1 GiB olduğunda yaklaşık ≈ 1 TiB veri sıralamak mümkündür. Bu koşul sağlandığında algoritma diziyi yalnızca üç kez tarar ve pratikte son derece verimlidir. Ayrıca mevcut cache-oblivious sıralama uygulamalarının aksine yerinde (in-place) çalışır ve ek disk alanı kullanmaz.

Belleğin yeniden kullanılması

Bölüm 4.2'de tanımlanan algoritma her tur için farklı bir Ei listesi kullanır. Demetler Ei'den okunmalarına göre Ei+1'e daha yavaş eklendiğinden aynı diziyi yeniden kullanabiliriz. Benzer bir yaklaşım Di ve Ui için de uygulanabilir. Sonuç olarak yalnızca γn adet paketlenmiş bağlanım listesi için bir dizi ve 3n yönlendirilmiş kenar için bir dizi ayırmamız yeterlidir.

Liste sıkıştırma

Disk üzerindeki veri yapılarının boyutunu azaltmak G/Ç verimliliğini ve dolayısıyla algoritmanın çalışma süresini önemli ölçüde iyileştirebilir. Alanın neredeyse tamamını kaplayan iki veri yapısı, paketlenmiş bağlanım listeleri Ei ve kenar listeleri Pi'dir. Listeler ardışık olarak okunup yazıldığından, bunları işlem sırasında sıkıştırıp açabiliriz.

Ei elemanlarının v0'a göre sıralı (v0, d, ˜v1, ˜v2) biçimindeki demetler olduğunu hatırlayın. Bu demetlerin ilk bileşenleri v0, Elias γ kodları kullanılarak boşluk (gap) kodlamasıyla temsil edilir. Kodlamanın toplam boyutu şöyledir:

Σ_{k=1}^{|Ei|} (2⌊log gk⌋ + 1) bit

burada gk, k'ıncı boşluktur. Boşlukların toplamı γn olduğundan Jensen eşitsizliğine göre toplam, tüm gk değerleri γn / |Ei| olduğunda en büyük olur ve şu alan sınırı elde edilir:

2|Ei|(log(γn / |Ei|) + 1) bit.

Ayrıca bu alan sınırı her zaman en fazla 2γn bittir çünkü maksimum değer Ei boyutu γn / 2 olduğunda ortaya çıkar.

Dereceler d ise unary kodlarla temsil edilir; derecelerin toplamı 3ni (burada ni, i turunda canlı olan kenar sayısıdır) olduğundan kodlamalarının toplam boyutu her zaman 3n bit ile üstten sınırlıdır.

Diğer iki bileşen ile Pi içindeki düğümler sabit uzunluklu kodlama ile, her biri ⌈log γn⌉ bit kullanılarak temsil edilir. γ = 1.23 için ve yukarıda açıklanan bellek yeniden kullanma tekniği sayesinde toplam disk kullanımı yaklaşık olarak şöyledir:

(5.46 + 11.46⌈log γn⌉) n bit.

En büyük girdilerimizde sıkıştırma kullanmak, düz 64 bitlik sözcükler kullanmaya kıyasla tüm algoritmanın yaklaşık 2.5 kat daha hızlı çalışmasını sağlamıştır.

Üçlü bölümlemeyi kullanma

Birçok MWHC tabanlı uygulama {h0(x), …, hr−1(x)} biçiminde r-hipergraph kenarlarını üretirken, [0, |V|) yerine eş alanı [i|V|/r, (i + 1)|V|/r) olan rastgele hash fonksiyonları hi kullanır; böylece r-parçalı bir r-hipergraph elde edilir. Başlıca avantaj, yapı gereği i ≠ j için hi(x) ≠ hj(x) olmasıdır; böylece süreç bozulmuş kenarlara sahip hipergraph'lar üretemez. Bu durum soyulabilir bir hipergraph bulmak için gereken deneme sayısını büyük ölçüde azaltır (pratikte tek bir deneme yeterlidir).

Botelho ve diğerleri [7], bu yöntemle elde edilen hipergraph'ların soyma eşiğinin tekdüze rastgele hipergraph'larla aynı olduğunu göstermiştir. Jiang ve diğerleri [18] ise katmanlı soyma sürecindeki tur sayısına ilişkin sınırın rastgele r-parçalı r-hipergraph'lar için de geçerli olduğunu göstermiştir; dolayısıyla bu yaklaşımı biz de kullanabiliriz.

r-bölümlemenin ek bir avantajı, herhangi bir 0-yöneliminin ilk düğümünün herhangi bir 1-yöneliminin ilk düğümünden daha küçük olmasıdır ve bu böyle devam eder. Genel olarak (u0, …, ur−1) bir i-yönelimi ve (v0, …, vr−1) bir j-yönelimi ise ve i < j ise u0 < v0 olur.

Algoritmamızda bunu E0'ın oluşturulması sırasında kullanıyoruz: grafiğimiz 3-parçalı olduğundan, her kenarın tüm geçerli yönelimlerini içeren bir liste oluşturup bunu v0'a göre sıralamak yerine yalnızca 0-yönelimlerini içeren bir liste oluşturur, bunu v0'a göre sıralar ve elde edilen paketlenmiş bağlanım listelerini E0'a ekleriz. Ardından sıralı listeyi tekrar dolaşır, tüm yönlendirilmiş kenarları 1-yönelimine çevirir ve aynı işlemi tekrar ederiz. Aynısı 2-yönelimleri için de yapılır.

Bu iyileştirme sayesinde algoritmanın ilk adımında —ki bu adım G/Ç açısından en yoğun olanıdır— gereken bellek miktarı üçte bire düşer.

Geriye doğru taramalardan kaçınma

MWHC tabanlı fonksiyon geliştirme sürecinde, ui değerlerini atayan son aşama kenarların ters soyma sırasına göre taranmasını gerektirir. Ne yazık ki işletim sistemleri ve diskler ileri yönde okumaya güçlü biçimde optimize edilmiştir ve agresif ileri okuma (lookahead) kullanırlar.

Ancak Bölüm 4.2'de belirtildiği gibi, katmanlar içindeki kenarların sırası önemli değildir; dolayısıyla katmanları ters sırada taramak yeterlidir, fakat her katman güvenle ileri yönde taranabilir. İleri yönde tarama sayısı tur sayısı ile sınırlıdır ve bu ihmal edilebilir düzeydedir. Diziyi geriye doğru okumaya kıyasla atama aşamasındaki performans iyileşmesi neredeyse on kat olmuştur.

Deneysel analiz

Kodumuz herhangi bir statik fonksiyon geliştirmek için kolayca genişletilebilir olsa da, soyma algoritmasının performansını deneysel olarak değerlendirmek amacıyla Bölüm 3'te tartışıldığı gibi minimal perfect hash function oluşturma görevinde test ettik. Bu görevde soyma süreci çalışma süresinin büyük bölümünü oluşturur.

Test ayrıntıları

MPHF oluşturma testleri, 32 GiB RAM'e sahip ve Linux 3.5.0 x86-64 çalıştıran 2.27 GHz hızında bir Intel Xeon i7 E5520 (Nehalem) üzerinde gerçekleştirildi. Depolama aygıtı 3 TB kapasiteli Western Digital WD30EFRX sabit disktir. Her test çalıştırılmadan önce, tüm verilerin diskten okunmasını sağlamak amacıyla çekirdek sayfa önbelleği temizlendi.

Deneyler C++11 ile yazıldı ve g++ 4.8.1 kullanılarak -O3 seçeneğiyle derlendi.

Aşağıdaki algoritmaları test ettik:

• Standard+XOR: XOR tekniğinin tek başına etkisini değerlendirmek amacıyla paketlenmiş bağlanım listesi kullanılarak uygulanmış standart doğrusal zamanlı soyma algoritması.
• cmph: Minimal perfect hashing için yaygın kullanılan, herkese açık ve optimize edilmiş bir kütüphane; standart bellek içi soyma algoritmasıyla aynı MWHC tabanlı MPHF geliştirme yöntemini uygular.
• Cache-Oblivious: Bölüm 4'te açıklanan cache-oblivious algoritması.

Veri kümeleri

Yukarıdaki algoritmaları aşağıdaki veri kümeleri üzerinde test ettik:

• URLs: ClueWeb09 veri kümesinden yaklaşık 4.8 milyar URL (ortalama dize uzunluğu ≈67 bayt, toplam ≈304 GiB).
• ngrams: Google Books Ngrams English veri kümesinden elde edilen yaklaşık 7.6 milyar {1, 2, 3}-gram (ortalama dize uzunluğu ≈23 bayt, toplam ≈168 GiB).

Dizeler öncelikle hash'lendiğinden verinin niteliği büyük ölçüde önemsizdir: önemli olabilecek tek unsur ortalama dize uzunluğudur (diskten girdiyi yükleme süresini etkiler). Gerçekten de rastgele üretilmiş verilerle yapılan testler aynı sonuçları vermiştir.

Deneysel sonuçlar

Anahtar sayısı arttıkça algoritmaların çalışma süreleri Şekil 1'de gösterilmiştir. Çalışma alanının ana belleğe sığdığı rejimdeki performansı değerlendirmek için grafiğin ilk kısmının büyütülmüş bir sürümü de gösterilmiştir.

İlk dikkat çekici gözlem, cache-oblivious algoritmasının cmph ile neredeyse aynı performansı göstermesidir; Cache-Oblivious biraz daha yavaştır çünkü çalışma alanı belleğe sığsa bile dosya G/Ç işlemleri yapmak zorundadır.

Ayrıca XOR tekniğinin fayda sağladığını da görebiliriz; Standard+XOR'un performansı bunu gösterir ve cmph'ten üç kata kadar daha hızlıdır. Daha düşük alan kullanımı aynı bellek bütçesiyle neredeyse iki kat daha fazla anahtarın işlenmesine de olanak tanır.

Bellek dışı olmayan her iki algoritma da mevcut bellek tükendiği anda kullanışlılığını kaybeder: makine daha sonra takas alanına rastgele erişim desenleri nedeniyle yoğun sayfa değişimi yapmaya başlar. Nitekim süreçler 48 saat sonra sonlandırılmak zorunda kalmıştır.

Bunun ne zaman gerçekleşeceğini oldukça kesin biçimde tahmin etmek mümkündür: cmph anahtar başına yaklaşık 34.62 bayt, Standard+XOR ise anahtar başına yaklaşık 26.76 bayt kullanır. Bu değerler, oluşturma sürelerinin yavaşlamaya başlayıp ardından hızla artmaya başladığı iki noktayı neredeyse tam olarak açıklar.

Öte yandan Cache-Oblivious giriş boyutuyla iyi ölçeklenir; daha büyük ngrams veri kümesinde neredeyse doğrusal performans sergilerken küçük anahtar kümelerinde de rekabetçi kalır.

HEM ile karşılaştırma

Son olarak algoritmamızı HEM [6] ile karşılaştırıyoruz. Bu yöntemde anahtar kümesi birkaç kovaya bölünür ve her kova için ayrı bir MPHF geliştirilir. Sorgu sırasında ilk seviyede bir indeks kullanılarak sorgu doğru kovaya yönlendirilir. Yeterince küçük kova boyutları seçmek, kova MPHF'sini geliştirmek için standart bir iç bellek algoritması kullanılmasına olanak tanır. Teknik olarak bir soyma algoritması olmasa da bu dış bellek çözümü basit ve zariftir.

Adil bir karşılaştırma yapmak için, başlangıç kovalamayı gerçekleştirmek üzere kendi sıralama uygulamamızı ve kova MPHF’lerini oluşturmak için Standard+XOR algoritmasını kullanarak HEM algoritmasını yeniden uyguladık.

Oluşturma Süresi (sn): n-gramlar – Küçük Örnekler

Cache-Oblivious
cmph
Standard+XOR

Anahtar sayısı (milyon): 0, 200, 400, 600, 800, 1000, 1200, 1400, 1600

Şekil 1: Yukarıda: iki veri kümesi üzerindeki oluşturma süreleri. Aşağıda: n değeri 1.6 × 10⁹ anahtara kadar olan yakın görünüm.

Hash fonksiyonu, [6]’da kullanılan aynı 96 bitlik hash fonksiyonudur (2⁴⁸ anahtara kadar olan kümeler için yeterlidir), ancak anahtar kümelerimiz 2³²/γ’den daha büyük olduğu için 32 bit yerine 64 bitlik kova ofsetleri kullandık.

Sonuç olarak, Şekil 2’de gösterildiği gibi, oluşturma süresi Cache-Oblivious’a kıyasla 2 ile 6 kat arasında daha küçüktür. Ancak bu verimlilik, arama süresi (çift dolaylı erişim nedeniyle) ve boyut (birinci seviye indeks için gereken ek alan nedeniyle) açısından bir maliyete sahiptir. Çoğu uygulamada MPHF’ler nadiren oluşturulup sık sık sorgulandığından, daha kısa oluşturma süresi alan ve sorgu süresindeki artışı karşılamaya değmeyebilir.

Nitekim Tablo 1’de gösterildiği gibi, alan kaybı %17 ile %27 arasındadır. Alan ek yükündeki değişkenlik, HEM’de kova sayısının 2’nin kuvveti olması gerekliliğinden kaynaklanır; dolayısıyla gerçek ortalama kova boyutu anahtar sayısına bağlı olarak 2 katlık bir faktör kadar değişebilir. Ayrıca bellekte oluşturabildiğimiz en büyük girdiler üzerinde cmph tarafından kullanılan alanı da dahil ediyoruz. MWHC uygulamamızla aynı veri yapısını kullanmasına rağmen, daha yoğun sıralama tabloları kullandığı için kapladığı alan biraz daha büyüktür.

Tablo 1 — Alan Kullanımı

Arama verimliliğinin değerlendirilmesi çok daha inceliklidir; çünkü bazıları donanım mimarisine bağlı olan çeşitli faktörlere dayanır. Bu nedenle deneyleri üç farklı makine üzerinde gerçekleştirmeye karar verdik: 3.40 GHz hızında bir Intel i7‑4770 (Haswell), oluşturma deneylerinde kullanılan aynı Intel i7 (Nehalem) makinesi ve 2.3 GHz hızında bir AMD Opteron 6276.

Oluşturma Süresi (sn): URL’ler

Anahtar sayısı (milyon): 0, 1000, 2000, 3000, 4000, 5000

Oluşturma Süresi (sn): n-gramlar

Anahtar sayısı (milyon): 0, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000

Her iki makine ve her iki veri kümesi için 10 milyon farklı anahtarın araması gerçekleştirildi ve bu işlem 10 kez tekrarlandı. Arama süreleri bir mikrosaniyeden daha küçük mertebelerde olduğundan, tek tek aramaları doğru şekilde ölçmek imkânsızdır. Bu nedenle aramaları her biri 2¹⁶ anahtar içeren 1.525 partiye böldük ve her parti için ortalama arama süresini ölçtük. Bu ortalama sürelerden genel ortalamayı ve standart sapmayı hesapladık.

Tablo 2’deki sonuçlar, HEM’in tüm durumlarda MWHC’den daha yavaş olduğunu göstermektedir. AMD Opteron üzerinde yavaşlama en küçüktür ve %17 ile %20 arasında değişir. Intel i7 (Nehalem) üzerinde bu aralık %19–%26’ya kadar çıkar. En yeni ve en hızlı CPU olan Intel i7 (Haswell) üzerinde ise yavaşlama %30–%35’e kadar ulaşır; bu durum CPU hızı arttıkça HEM’in çift dolaylı erişiminden kaynaklanan önbellek kaçırma maliyetinin daha belirgin hâle geldiğini göstermektedir. Tüm durumlarda standart sapma ihmal edilebilir derecede küçüktür, bu da karşılaştırmayı istatistiksel olarak anlamlı kılar.

Ayrıca MWHC arama uygulamamızın (HEM’de de kullanılır) daha seyrek bir sıralama tablosu kullanmasına rağmen cmph’den yaklaşık iki kat daha hızlı olduğunu da belirtmek gerekir. Bunun nedeni, sıralama işlemini gerçekleştirmek için bir döngü ile doğrusal bit taraması yerine, yalnızca birkaç dallanmayan talimatla 64 bitlik bir sözcük içindeki sıfır olmayan çiftlerin sayısını hesaplayan bir broadword [19] algoritması kullanmamızdır. Daha küçük sıralama tablosu ayrıca daha düşük önbellek baskısı oluşturur. Son olarak, Jenkins hash fonksiyonunun 64 bitlik bir uygulamasını kullanıyoruz; bu da cmph’de kullanılan 32 bitlik sürüme kıyasla uzun dizgelerde daha hızlıdır.

Tablo 2 — Arama Süresi

Intel i7 (Haswell)

Intel i7 (Nehalem)

AMD Opteron

Kaynaklar

[1] Djamal Belazzougui, Paolo Boldi, Rasmus Pagh ve Sebastiano Vigna. Monotone minimal perfect hashing: Sıralı bir tabloda O(1) erişimle arama. SODA içinde, sayfa 785–794, 2009.

[2] Djamal Belazzougui, Paolo Boldi, Rasmus Pagh ve Sebastiano Vigna. Az alan kullanarak hızlı önek araması, uygulamalarla birlikte. ESA (1) içinde, sayfa 427–438, 2010.

[3] Djamal Belazzougui, Paolo Boldi, Rasmus Pagh ve Sebastiano Vigna. Monotone minimal perfect hashing’in kuramı ve uygulaması. ACM Journal of Experimental Algorithmics, 16, 2011.

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

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

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

[7] Fabiano C. Botelho, Nicholas Wormald ve Nivio Ziviani. Rastgele r-bölmeli hipergrafların çekirdekleri. Information Processing Letters, 112(8–9):314–319, 2012.

[8] Gerth Stølting Brodal ve Rolf Fagerberg. Cache-oblivious yaklaşımının sınırları üzerine. STOC içinde, sayfa 307–315, 2003.

[9] Denis Charles ve Kumar Chellapilla. Bloomier filtreleri: İkinci bir bakış. ESA içinde, sayfa 259–270, 2008.

[10] Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld ve Ayellet Tal. Bloomier filtresi: statik destek arama tabloları için verimli bir veri yapısı. SODA içinde, sayfa 30–39, 2004.

[11] Zbigniew J. Czech, George Havas ve Bohdan S. Majewski. Perfect hashing. Theoretical Computer Science, 182(1–2):1–143, 1997.

[12] Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh ve Michael Rink. xorsat aracılığıyla cuckoo hashing için sıkı eşikler. ICALP (1) içinde, sayfa 213–225, 2010.

[13] Peter Elias. Evrensel kod sözcüğü kümeleri ve tam sayıların gösterimleri. IEEE Transactions on Information Theory, 21(2):194–203, 1975.

[14] Matteo Frigo, Charles E. Leiserson, Harald Prokop ve Sridhar Ramachandran. Cache-oblivious algoritmalar. ACM Transactions on Algorithms, 8(1):4, 2012.

[15] Michael T. Goodrich ve Michael Mitzenmacher. Tersine çevrilebilir Bloom arama tabloları. CCC içinde, sayfa 792–799, 2011.

[16] Torben Hagerup ve Torsten Tholey. Neredeyse minimal alanda verimli minimal perfect hashing. STACS içinde, sayfa 317–326, 2001.

[17] G. Jacobson. Alan açısından verimli statik ağaçlar ve graflar. FOCS içinde, sayfa 549–554, 1989.

[18] Jiayang Jiang, Michael Mitzenmacher ve Justin Thaler. Paralel peeling algoritmaları. CoRR, abs/1302.7014, 2013.

[19] 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.

[20] Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi ve Daniel A. Spielman. Verimli silinme düzeltmeli kodlar. IEEE Transactions on Information Theory, 47(2):569–584, 2001.

[21] Bohdan S. Majewski, Nicholas C. Wormald, George Havas ve Zbigniew J. Czech. Perfect hashing yöntemlerinden oluşan bir aile. Computer Journal, 39(6):547–554, 1996.

[22] Kurt Mehlhorn. Perfect ve evrensel hash fonksiyonlarının program boyutu üzerine. FOCS içinde, sayfa 170–175, 1982.

[23] Michael Mitzenmacher ve George Varghese. Biff (Bloom filter) kodları: büyük veri kümeleri için hızlı hata düzeltme. ISIT içinde, sayfa 483–487, 2012.

[24] Michael Molloy. Rastgele hipergraflarda saf literal kuralı eşiği ve çekirdekler. SODA içinde, sayfa 672–681, 2004.

[25] Michael Molloy. Rastgele hipergraflarda ve Boolean formüllerinde çekirdekler. Random Structures and Algorithms, 27(1):124–135, 2005.