← perfect_hashing/
[25] 2019 #191

RecSplit: Minimal Perfect Hashing via Recursive Splitting

Esposito, Graf, Vigna

RecSplit: Özyinelemeli Bölme Yoluyla Minimal Perfect Hashing

Emmanuel Esposito*
Thomas Mueller Graf†
Sebastiano Vigna‡

*Università degli Studi di Milano, İtalya
†Bağımsız araştırmacı, İsviçre
‡Università degli Studi di Milano, İtalya

arXiv:1910.06416v2 [cs.DS] 30 Kas 2019

Özet

Bir minimal perfect hash fonksiyonu, evren $U$ içinden bir anahtar kümesi $S{{ content }}#39;yi ilk $|S|$ doğal sayıya birebir olarak eşler. Minimal perfect hash fonksiyonları, örneğin dizgiler gibi düzensiz biçimli anahtarları sıkıştırılmış bir alana eşlemek için kullanılır; böylece üstveri daha sonra basitçe bir dizi içinde saklanabilir. Bir minimal perfect hash fonksiyonunu saklamak için anahtar başına yalnızca 1.44 bitin yeterli olduğu bilinmesine rağmen, yayımlanmış hiçbir teknik pratikte anahtar başına 2 bitin altına inememektedir.

Beklenen doğrusal kurulum süresi ve beklenen sabit sorgulama süresiyle minimal perfect hash fonksiyonlarını saklamak için yeni bir teknik öneriyoruz. Bu teknik sayesinde, ilk kez anahtar başına 1.56 bit gerektiren—yani alt sınıra %8.3 mesafe içinde—yapıları anahtar başına 2 ms'den kısa sürede kurmak mümkün olmaktadır. Kurduğumuz yapı örneklerinin, anahtar başına 2 bit seviyesine ulaşan mevcut en iyi veri yapısının kurulum süresi, alan kullanımı ve sorgulama süresini aynı anda aşabildiğini gösteriyoruz.

Ayrıca, alan ve sorgulama süresi açısından alternatif fakat daha büyük boyutlu veri yapılarıyla rekabet edebilen yapılar sağlayan parametre seçimleri sunuyoruz. Veri yapılarımızın kurulumu kolaylıkla paralelleştirilebilir veya dağıtık hesaplama birimlerine (örneğin MapReduce çerçevesi içinde) eşlenebilir ve mevcut RAM'den daha büyük yapılar doğrudan kütle depolama üzerinde oluşturulabilir.

Bu makalede, özyinelemeli bölme ve kaba kuvvet aramaya dayalı, beklenen doğrusal kurulum süresi ve beklenen sabit sorgulama süresi sunan minimal perfect hash fonksiyonlarını saklama için yeni bir teknik sunuyoruz. Tekniğimiz 2 bit sınırını aşabilmekte ve aynı zamanda CHD'nin kurulum süresi, alan kullanımı ve sorgulama süresini iyileştirmektedir.

Bir MPHF oluşturma yaklaşımımız kavramsal olarak basittir ve üst düzeyde mevcut yaklaşımlara benzer: bir kümeyi kovalar (buckets) hâlinde bölümlere ayırır ve ardından her kovayı bağımsız olarak işleriz. Ancak diğer yaklaşımlardan farklı olarak, bizim yöntemimizde bir kovadaki girdiler mantıksal olarak bağımsız bir MPHF tanımlayan bir ağaç oluşturur. Kaba kuvvet aramanın verimli olması, sorgulamanın hızlı olması ve az alan kullanılması için bu ağaçların tam olarak nasıl görünmesi gerektiğini analiz ediyoruz. Ayrıca bu ağaçların nasıl örtük biçimde kodlanacağını ve çok küçük MPHF'ler için bile verimli sorgulama ve depolama sağlayan özlü veri yapılarının nasıl kullanılacağını da gösteriyoruz.

Minimal perfect hash fonksiyonları (MPHF'ler), verilen bir anahtar kümesi $S{{ content }}#39;nin ($|S| = n$) ilk $n$ doğal sayıya birebir eşlemesini saklayan statik veri yapılarıdır. Böyle bir birebir eşleme hash tabloları kullanılarak kolaylıkla saklanabilir; ancak MPHF'lerin, sorgulanan anahtar orijinal küme $S$ içinde değilse herhangi bir değer döndürmesine izin verilir. Bu gevşetme, küme $S{{ content }}#39;yi saklamanın bilgi kuramsal alt sınırını aşmayı mümkün kılar. Gerçekten de MPHF kurulumları, anahtarların boyutundan bağımsız olarak $O(n)$ bit alan elde eder. Bu özellik, MPHF'leri büyük dizgi kümeleri ve diğer düzensiz anahtarlarla çalışırken güçlü teknikler hâline getirir ve alan açısından verimli veri yapılarının önemli yapı taşlarıdır.

MPHF'ler için yaygın gereksinim, kurulumun doğrusal sürede tamamlanabilmesi ve sorgulamanın sabit zaman almasıdır; çoğu zaman bu gereksinimler beklenen doğrusal süre ve beklenen sabit zaman olarak gevşetilir.

Bir MPHF'nin alan alt sınırı yaklaşık olarak $\log_2(e) ≈ 1.44$ bit/anahtardır [FKS84] ve $S{{ content }}#39;den bağımsızdır. Bazı kuramsal kurulumlar bu alt sınıra ulaşır, ancak bunlar yalnızca son derece büyük $n$ değerleri için çalışır [HT01]. Pratikte ise aşağıda ayrıntılandırılan CHD kurulumu [BBD09] şu anda yaklaşık 2 bit/anahtar seviyesine ulaşabilmektedir; ancak bu alan kullanımında hem kurulum hem de sorgulama açısından yaklaşımımızın önemli ölçüde daha hızlı olduğunu gösteriyoruz.

Majewski, Wormald, Havas ve Czech tarafından sunulan yapının türevleri gibi rastgele doğrusal sistemlere dayalı teknikler [MWHC96], kurulumda makul derecede hızlı ve sorgulamalarda oldukça hızlıdır; ancak yalnızca yaklaşık 2.24 bit/anahtar seviyesine ulaşırlar [GOV16]. Son olarak, parmak izi (fingerprint) temelli teknikler [MSSZ14] kurulum ve sorgulamada son derece hızlıdır, ancak yalnızca alan kullanımının çok büyük olduğu durumlarda (örneğin anahtar başına 4 bitten fazla) iyi çalışırlar.

Yaklaşımımızın başlıca avantajlarından biri, bilgi kuramsal alt sınırdan yalnızca %9'dan az daha fazla alan kullanarak pratik MPHF'ler oluşturmayı mümkün kılmasıdır; mevcut en iyi yöntemler ise yaklaşık %40 daha fazla alan kullanır. Yaklaşımımız aynı zamanda esnektir ve geniş bir parametre aralığında yararlıdır: yalnızca en az alan kullanan pratik MPHF'leri sağlamaz, aynı zamanda geniş bir parametre aralığında kurulum süresi ve sorgulama süresi açısından da rekabetçidir. Buna karşılık mevcut algoritmalar yalnızca dar bir parametre aralığında rekabetçidir.

Bu makalede kullanılan tüm kodlar, Sux projesinin bir parçası olarak yazarlar tarafından GNU Lesser General Public License sürüm 3 veya daha sonrası altında sunulmaktadır: http://sux.di.unimi.it/.

1. Giriş

Doğal sayılar kümesi için von Neumann'ın tanımını ve gösterimini kullanıyoruz; dolayısıyla $n = {0, 1, …, n−1}$. Sağ ve sol bit kaydırma için >> ve << kullanıyoruz. Knuth'u [Knu11] izleyerek $\lambda x$ ile en yüksek (en soldaki) ayarlı bitin indeksini ifade ediyoruz ($x ≤ 0$ olduğunda $\lambda x$ tanımsızdır).

2. Gösterim

(Bölüm numaralandırması orijinal belgeden korunmuştur.)

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

3.1 Erken Çalışmalar

Sprugnoli [Spr77], küçük kümeler üzerinde perfect hash fonksiyonlarını, tamsayı bölmeleri ve kalanları içeren basit ifadelerde sabitleri kapsamlı biçimde test ederek tanımlar; bazı küçük boyutlu durumlarda minimal perfect hash fonksiyonu bulmayı başarır. Büyük anahtar kümeleri için anahtarların önce sabit sayıda kovaya (segment olarak adlandırılır) hash'lenebileceğini ve ardından her kovada bağımsız olarak işlem yapılabileceğini önerir.

Jaeschke [Jae81], kapsamlı arama kullanarak küçük kümelerde minimal perfect hash fonksiyonları elde etmek için bu yaklaşımı geliştirir. Hem kapsamlı arama hem de anahtarları kovalar hâlinde hash'leme, kurulumumuzun temel bileşenleridir.

3.2 Rastgele Doğrusal Sistemler

Temel çalışmalarında [MWHC96], Majewski, Wormald, Havas ve Czech doğrusal sistemler ile hipergraflar arasındaki bağlantıyı kullanarak statik fonksiyonlar için ilk kompakt kurulum yöntemini tanıttılar.

Bir $f: S → t$ fonksiyonunu saklamak için, $n = |S|$ denklem ve $m$ değişken içeren aşağıdaki biçimde rastgele bir sistem üretirler:

w_{h0(x)} + w_{h1(x)} + ... + w_{h_{k−1}(x)} = f(x) (mod t), $x ∈ S$ için.

Burada $h_i : U → m$ fonksiyonları $k$ adet tamamen rastgele hash fonksiyonudur ve $w_i$ değişkenleri $Z/tZ$ içinde değer alır. Rastgele grafların çevrimsizlik sınırları nedeniyle, değişken sayısı ile denklem sayısı arasındaki oran belirli bir eşik $γ_k{{ content }}#39;nin üzerindeyse, sistem çoğu durumda ilişkili hipergrafı soyarak doğrusal sürede üçgensel biçime getirilebilir ve böylece çözülebilir.

Veri yapısı daha sonra sistemin çözümü olur (yani $w_i$ değişkenlerinin değerleri). Çözümün saklanması, $f(x)$ değerinin sabit zamanda hesaplanmasını mümkün kılar. Alan kullanımı yaklaşık olarak anahtar başına $γ_k b$ bittir. $γ_k$ sabiti derece $k{{ content }}#39;ya bağlıdır ve en küçük değerine $k = 3$ için ulaşır ($γ_3 ≈ 1.23$).

Chazelle, Kilian, Rubinfeld ve Tal [CKRT04], MWHC kurulumundan habersiz olarak aynı fikri bağımsız biçimde önerdiler, ancak aynı zamanda soyulabilir bir hipergrafın yönlendirilebilir olduğu gerçeğinden yararlandılar. Soyma işlemi sırasında her hiperkenar benzersiz bir tepeye atanabildiğinden, her anahtar $⌈γ_k n⌉$ içinde bir tamsayıya enjekte edilebilir.

Perfect hash fonksiyonunu minimal hâle getirmek için ($⌈γ_k n⌉$ yerine $n{{ content }}#39;e eşlemek amacıyla) bir sıralama (ranking) veri yapısı eklenebilir. Boyutu $⌈γ_k n⌉$ olan bir bit vektörü hangi tepelerin bir hiperkenara atanmış olduğunu kaydeder ve ek $o(n)$ bit, sabit zamanda rank (belirli bir konumdan önce gelen birlerin sayısı) hesaplamaya izin verir [Vig08].

$k$ için en iyi değer 3'tür ve bu kuramsal olarak $2.46n + o(n)$ bitlik bir veri yapısı verir [BPZ13]. Daha sonra Genuzio, Ottaviano ve Vigna çevrimsizlik yerine çözülebilirlik sınırlarını kullanmanın $2.24n + o(n)$ bitlik bir veri yapısı sağladığını gösterdiler [GOV16].

3.3 CHD

Belazzougui, Botelho ve Dietzfelbinger [BBD09], CHD (Compressed Hash-and-Displace) adı verilen farklı bir kurulum tanıttılar; bu yöntem kuramsal olarak yaklaşık 1.44 bit/anahtar olan bilgi kuramsal alt sınıra ulaşabilir, ancak bunun karşılığında beklenen kurulum süresi artar.

Anahtarlar önce beklenen boyutu $λ$ olan küçük kovalar içine eşlenir (örneğin $λ = 4$). Daha sonra kovalar, en büyüklerden başlanarak, çakışma olmadan kodomain içine eşlenir. Her kova için $φᵢᵏ : U → k$ biçimindeki tamamen rastgele bağımsız hash fonksiyonlarının bir numaralandırması incelenir ($i = 0, 1, 2, …$). Mevcut kovayı çakışma olmadan eşleyen bir fonksiyon bulunduğunda, bu fonksiyonun indeksi veri yapısında saklanır.

Kuramsal analiz kova boyutunun artırılmasının alt sınıra keyfi biçimde yaklaşmayı mümkün kıldığını gösterse de pratikte anahtar başına yaklaşık 2 bitin altına inmek uygulanabilir değildir.

3.4 Parmak İzi Yöntemi

Müller ve diğerleri [MSSZ14], parmak izi kullanarak minimal perfect hashing için başka bir teknik sundular. Seviye (level) olarak adlandırılan ve boyutları giderek küçülen bir dizi bit dizisi, anahtarlar arasındaki çakışmalar hakkında bilgi kaydeder.

İlk seviyede rastgele bir hash fonksiyonu tarafından yalnızca tek bir anahtarın eşlendiği konumlar bir ile işaretlenir. Çakışan anahtarlar daha sonra bir sonraki seviyeye eşlenir ve süreç tekrar eder. Bir anahtarı geri almak için anahtar her seviyeye eşlenir ve işaretli bir konum bulunana kadar devam edilir. Bit dizilerinin birleştirilmiş hâli üzerinde sabit zamanlı bir sıralama yapısı, elde edilen perfect hash fonksiyonunu minimal perfect hash fonksiyonuna dönüştürür.

Parmak izi tabanlı MPHF'ler, her seviyenin boyutunu ayarlayarak hız açısından oldukça ayarlanabilir. Ancak bildirilen en iyi alan kullanımı yaklaşık 2.58 bit/anahtardır; bu da CHD veya bu makalede açıklanan tekniklerle rekabetçi değildir. Bu boyutta hem kurulum hem de sorgulama görece yavaştır.

4. RecSplit

RecSplit, çok küçük kümeler için uygun bir kodomain ile birebir eşleme aramak üzere kaba kuvvet kullanarak minimal perfect hash fonksiyonu bulmanın mümkün olduğu fikrine dayanır. Bu fikri, büyük kümeleri yönetilebilir boyutlara indirgemek için yapılan bölmeleri kaba kuvvetle arama yaklaşımına genişletiyoruz.

$n$ anahtarlı bir küme için bir RecSplit örneği kurmak amacıyla önce anahtarları rastgele bir $g : S → ⌈n/b⌉$ hash fonksiyonu kullanarak ortalama boyutu $b$ olan kovalar içine rastgele dağıtırız. Daha sonra her kova, doğrudan MPHF aramanın uygulanabilir olduğu hedef yaprak boyutu $ℓ{{ content }}#39;ye ulaşıncaya kadar daha küçük parçalara özyinelemeli olarak bölünür.

$ℓ$ ve $b$ parametreleri farklı alan–zaman dengeleri sağlar. Her kova için bağımsız olarak bir MPHF kurulur; bu da paralel veya dağıtık kurulum yapılmasına olanak tanır.

Hem bölmeleri hem de birebir eşlemeleri aramak için $φᵢᵏ : U → k$ biçimindeki tamamen rastgele bağımsız hash fonksiyonlarının bir numaralandırmasını kullanırız ($i = 0, 1, 2, …$). Bu fonksiyonların indeksleri veri yapısında saklanır.

Boyutu $m$ olan bir $X$ anahtar kümesi verildiğinde, bir bölme şu parçalar listesiyle tanımlanır: $k₀, k₁, …, k_{s−1}$ ve

k₀ + k₁ + ... + k_{s−1} = m.

Bölme indeksi, anahtarların parçalar arasında istenen dağılımını sağlayan ilk $φᵢᵐ$ fonksiyonunu arayarak hesaplanır.

5. Bölmeler ve Birebir Eşlemeler İçin Arama

Birçok farklı bölme stratejisi mümkündür. Tamamen analitik bir çözüm zor görünse de bazı gözlemler iyi stratejiler geliştirmeyi kolaylaştırır.

İlk gözlem, kova boyutlarının $p = b/n$ ve $n$ parametreli bir binom dağılımını izlemesidir. Bu dağılımın momentleri analitik olarak ifade edilebilir [Kno08].

Her parçanın boyutu prensipte keyfi olsa da $ℓ{{ content }}#39;nin katları olan boyutlarla çalışmak ve sonuncusu hariç tüm parçaların aynı boyutta olmasını sağlamak kullanışlıdır. Böylece her kovada tüm yaprakların boyutu $ℓ$ olur (sonuncu hariç) ve her ağaç düğümünde tüm alt ağaçlar aynı biçime sahip olur (yine sonuncu hariç).

Bir bölme stratejisi, her $m > ℓ$ için bir yaprak boyutu $ℓ$ ve bir bölme birimi $u$ (bu değer $ℓ{{ content }}#39;nin katı olmalıdır) ile tanımlanır. Bu parametreler, her $m > ℓ$ için bölme ağacının biçimini benzersiz biçimde belirler. $m$ anahtarla ilişkili bir düğümün dallanma derecesi $⌈m/u⌉$ olacaktır; tüm parçalar $u$ boyutunda olur, yalnızca son parça $m \bmod u$ boyutunda olabilir.

Bir $X$ kümesi için bölme ağacı verildiğinde, $X$ üzerinde bir minimal perfect hash fonksiyonu şu şekilde hesaplanabilir. $x ∈ X$ anahtarı için, bölme indekslerini kullanarak kökten bir yaprağa kadar ağaç boyunca ilerleriz. Her alt düğüme geçtiğimizde, bölme stratejisine göre o alt ağacın solunda tam olarak kaç anahtar bulunduğunu biliriz. Bir yaprağa ulaştığımızda, o yaprağın solunda $c$ anahtar olduğunu varsayalım. Daha sonra yaprakla ilişkili birebir eşlemeyi $x$ üzerine uygular ve sonuca $c$ ekleriz.

Birden fazla kova, her kovadaki anahtar sayısının ön ek toplamlarını (yani önceki kovalar için atanmış anahtar sayısını) takip ederek ve sonucu buna göre ayarlayarak ele alınır.

Başka bir deyişle, $X$ elemanlarını $m$ içine eşler ve değeri $k_0{{ content }}#39;dan küçük olanlara eşlenen elemanların tam olarak $k_0$ adet, değeri $k_0$ ile $k_0 + k_1$ arasında olanların tam olarak $k_1$ adet vb. olduğu ilk fonksiyonu buluruz.

Ardından, bir parçanın mevcut boyutu $ℓ{{ content }}#39;den küçük veya eşit olana kadar $s$ parça üzerinde özyinelemeli olarak devam ederiz. Bu noktada, bir $X$ parçası verildiğinde $X$ üzerinde birebir olan ilk $\varphi_i^{|X|}$ fonksiyonunu ararız. Böylece her iç düğümde bir bölme indeksi ve her yaprakta bir birebir eşleme indeksi bulunan köklü bir bölme ağacı elde ederiz (bkz. Şekil 1). Bu indekslerin her birini, geometrik dağılıma sahip olduklarından, optimal bir Golomb–Rice anlık kodu [Sal07] kullanarak temsil edeceğiz.

Özellikle, her kova için polinomla sınırlı (beklenen durumda bile olsa) çalışan her algoritma tüm anahtarlar üzerinde çalıştırıldığında beklenen doğrusal zaman alacaktır ve bir kovada polinom iş yapan herhangi bir sorgulama algoritması beklenen sabit zamanda çalışacaktır.

Fonksiyon ailemizin tamamen rastgele olduğunu varsayarsak, boyutu $m$ olan bir küme için sol parça boyutu $k$ ve sağ parça boyutu $m-k$ olacak şekilde bir bölme bulma olasılığı

$ \frac{1}{m^m} \binom{m}{k} k^k (m-k)^{m-k} \sim \frac{1}{m^m} \binom{m}{k} k^k (m-k)^{m-k} \cdot \frac{e^m}{\sqrt{2\pi k(m-k)}} $

şeklindedir.

Toplam fonksiyon sayısı olan $m^m{{ content }}#39;ye böldüğümüzde

$ \frac{1}{m^m} \binom{m}{k} k^k (m-k)^{m-k} $

elde edilir.

Stirling yaklaşımını kullanarak

$ \sim \sqrt{\frac{m}{2\pi k(m-k)}} $

sonucuna ulaşırız.

Buna göre bir bölme hash fonksiyonunu bulmak için gereken ortalama deneme sayısı asimptotik olarak

$ \sqrt{2\pi k(m-k)} $

olacaktır.

Bu değer $k = \lceil m/2 \rceil$ olduğunda, yani dengeli bölmeler için en yüksek değere ulaşır.

Seçtiğimiz kodomain $m$ ve eşik $k$ değerlerinin optimal olduğunu belirtelim. Gerçekten de, kodomainin $r$ ve eşik değerinin $t$ olduğu genel durumu ele alırsak, olasılık

$ \frac{1}{r^m} \binom{m}{k} t^k (r-t)^{m-k} $

yalnızca $r/t$ oranına bağlıdır, çünkü

$ (\alpha t)^k (\alpha r - \alpha t)^{m-k} = t^k (r-t)^{m-k}. $

Şimdi, $t = \alpha r$ ifadesini açıkça yazıp ifadeyi $\alpha$ açısından minimize edersek $\alpha = k/m$ elde ederiz. Dolayısıyla $t/r = k/m$ olacak şekilde seçilen herhangi bir $r$ ve $t$ çifti en yüksek başarı olasılığını sağlar.

İkiden fazla parçaya sahip bölmeler de kullanacağız. Genel olarak $m$ sayısını $s$ parçaya ayırmak istersek

$ m = k_0 + k_1 + \cdots + k_{s-1}, $

bölme fonksiyonlarının sayısı, $m{{ content }}#39;in $k_0, k_1, \ldots, k_{s-1}$ kardinalitelerine sahip kümelere olası sıralı bölünmelerinin sayısı (yani ilgili multinom katsayısı) ile her küme içindeki olası fonksiyonların sayısının çarpımıyla verilir.

Şekil 1

$\ell = 2$ için 15 elemanlı bir bölme ağacı örneği. Her düğüm ilişkili anahtarlar ve bölme veya birebir eşleme indeksi ile etiketlenmiştir. Boyutu bir olan yaprağın ilişkili bir indeksi olmadığını unutmayın.

5.2 Birebir eşlemelerin aranması

Benzer şekilde, boyutu $m$ olan bir yaprak üzerinde bir MPHF bulma olasılığını tahmin edebiliriz. Bir birebir eşlemeye denk gelme olasılığı

$ \frac{m!}{m^m}, $

şeklindedir; çünkü $m!$ adet birebir eşleme ve yapraktan kendisine olan toplam $m^m$ olası fonksiyon vardır. Dolayısıyla ortalama deneme sayısı

$ \frac{m^m}{m!} \approx \frac{e^m}{\sqrt{2\pi m}} $

olur; burada Stirling yaklaşımı kullanılmıştır.

Yaprak boyutları bir sabitle sınırlandığından, birebir eşlemeleri bulmak için gereken toplam iş anahtar sayısına göre doğrusaldır.

5.3 Değişmezlik

Tekniğimizin kullanışlı bir özelliği, bir değişmezlik özelliğini sağlamasıdır: $m$ elemanlı bir kümede birebir eşleme bulma olasılığı, bir bölme bulma ve her parça üzerinde bir birebir eşleme bulma olasılığına eşittir.

Teorem 1. $m$ elemanlı bir küme verildiğinde, küme üzerinde minimal mükemmel bir hash bulma olasılığı, kümenin $s$ parçaya $k_0, k_1, \ldots, k_{s-1}$ biçiminde bölünmesini bulma olasılığı ile her parça üzerinde birebir eşleme bulma olasılıklarının çarpımına eşittir.

İspat. Aşağıdaki eşitlikten dolayı doğrudan elde edilir:

$ \prod_{i=0}^{s-1} \frac{k_i!}{k_i^{k_i}} = \frac{m!}{m^m}. $

Tümevarımsal bir sonuç olarak, boyutu $m$ olan bir kümede bölmeleri ve birebir eşlemeleri tanımlayan her ağaç için tüm düğümlerdeki olasılıkların çarpımı sabittir ve $m! / m^m$ değerine eşittir.

Daha ilginç olarak, değişmezlik özelliği şunu söyler: $m$ anahtar için bir bölme ağacının düğümlerinde $p_0, p_1, \ldots, p_{t-1}$ olasılıkları varsa

$ \prod_{i=0}^{t-1} p_i = \frac{m!}{m^m}. $

Dolayısıyla ağacı saklama maliyeti beklenti olarak

$ \sum_{i=0}^{t-1} \left(c + \lg \frac{1}{p_i} + O(p_i)\right) = ct + \lg \prod_{i=0}^{t-1} \frac{1}{p_i} + O\left(\sum_{i=0}^{t-1} p_i\right) = ct + m \lg e + O(\lg m). $

Başka bir deyişle, her bölme ve birebir eşleme için yaklaşık $c$ bit kaybederiz; ancak bunun dışında bit sayısı $m$ büyüdükçe en iyi değere yaklaşır (ve $t$ sabit kalır; bu da özellikle yaprak boyutunun büyümesi gerektiği anlamına gelir).

Dolayısıyla bölme sayısını artırmak yapının oluşturulmasını hızlandırır ve aramaları yavaşlatır; fakat bölmeden geçen anahtar sayısı yeterince büyük olduğu sürece alan kullanımını yalnızca çok az artırır. Bununla birlikte $c$ ile ilişkili ana alan kaybı yapraklardan kaynaklanır; çünkü bu maliyet en az sayıda anahtar üzerine yayılır.

5.4 Bir bölme stratejisi

Şimdiye kadar elde edilen bilgilerle artık bölme stratejimizi açıklayacağız. Temel amacımız, yapıyı oluşturmak için gereken süreyi sınırlayan ana faktörün yaprak boyutunun seçimi olmasını sağlamaktır.

$\ell \le 24$ varsayımını yapacağız; çünkü daha büyük yapraklarda arama çok yavaş olur. Ayrıca bu aralıkta Golomb–Rice parametresi 32'den küçüktür ve yalnızca beş bit içinde paketlenebilir. Daha büyük yaprakların daha az değerlendirmeye yol açacağını ve dolayısıyla daha hızlı aramalara sahip yapılar sağlayacağını bekliyoruz.

Önceki analizden açıktır ki bölme ağacını daha düz hale getirmek istiyorsak alt seviyelerde daha büyük $s$ değerleri kullanmalıyız. Bu nedenle şu ölçütü tanımlıyoruz: alttan başlayarak, bölmeyi hesaplamak için gereken işin, yaprak birebir eşlemelerinin toplamını hesaplama işiyle aynı olduğu şekilde yaprakları birleştirmek istiyoruz.

Bir bölme denemesinin $m$ adet fonksiyon değerlendirmesi gerektireceğini ve bir birebir eşleme denemesinin yaklaşık olarak

$ \sqrt{\pi m / 2} $

adet fonksiyon değerlendirmesi gerektireceğini varsayıyoruz [Ram12, FGKP95]; her iki tahmin de yaklaşık değerlerdir.

Eğer aşağıdaki ifadeyi minimize eden tam sayıyı ararsak

$ \left(\frac{\ell!}{\ell^{\ell}}\right)^s $

$\ell \le 24$ için

$ s = \max{2, \lceil 0.35\ell + 0.5 \rceil} $

elde edilir.

Dolayısıyla açgözlü bir yaklaşımla bu sayıda yaprağı birleştirmeye çalışacağız.

Bir seviye daha yukarı çıktığımızda aynı soruyu tekrar sorabiliriz: yani fan-out değeri, yapılan işin alt iki seviyede yapılan işle aynı olduğu durum. Bu da başka bir ifadeyi minimize etmeye götürür ve şu sonucu verir:

$ t = \lceil 0.21\ell + 0.9 \rceil \quad \text{for } 7 \le \ell \le 24, $

ve $\ell < 7$ için $t = 2$.

Aynı ölçüt kullanılarak daha fazla birleştirme seviyesi eklenebilir; ancak bunun veri yapısının kullandığı alan üzerindeki etkisi ihmal edilebilir hale gelir ve her birleştirme seviyesi arama kodunda bir test gerektirir. İkinci birleştirme seviyesinden sonra fan-out değerini 2 olarak sabitleriz ve birim (ve sol parça) olarak

$ \left\lceil \frac{\lfloor m/2 \rfloor}{st\ell} \right\rceil \cdot st\ell $

kullanırız.

Bir RecSplit MPHF'yi verimli biçimde değerlendirebilmek için aşağıdaki verilerin saklanması gerekir:

6.1 Bucket-atama fonksiyonu $g$

Öncelikle her $x \in S$ anahtarını $\Theta(n)$ bitlik benzersiz bir imza $s(x)$ ile değiştiririz (uygulamamızda 128 bit). Bucket ataması sabit noktalı çarpma kullanılarak üretilir.

$s(x){{ content }}#39;in üst $t$ bitinin (örneğin $t = 64$) değeri olan $u(x){{ content }}#39;i

$ \alpha(x) = \frac{u(x)}{2^t} $

şeklinde $[0,1)$ aralığında sabit noktalı aritmetik ile temsil edilen bir gerçek sayı olarak yorumlarız ve $x{{ content }}#39;i şu bucket'a atarız:

$ \lfloor \alpha(x) \cdot \lceil n/b \rceil \rfloor. $

Eğer $\alpha(x)$ değerini birim aralıkta rastgele ve uniform dağılımlı bir gerçek sayı olarak yorumlarsak, bu işlem $\lceil n/b \rceil$ üzerinde rastgele uniform ayrık bir değer döndüren bir tersleme işlemiyle [Dev86] eşdeğerdir; bu da tam olarak ihtiyaç duyduğumuz şeydir.

Sabit noktalı aritmetik kullandığımız için bu işlem şu hesaplamaya indirgenir:

$ \left\lfloor \frac{u(x) \cdot \lceil n/b \rceil}{2^t} \right\rfloor, $

ve bu işlem bir çarpma ve bir kaydırma ile gerçekleştirilebilir. Bölmeler ve birebir eşlemeler aranırken de aynı tekniği kullanacağız.

Bölme ağaçları bir RecSplit örneğinin kapladığı alanın büyük bölümünü oluşturur. Bu nedenle hem tutumlu hem de hızlı erişilebilir bir temsil geliştirmek çok önemlidir.

Bu hedefe ulaşmak için ağacın şeklini (örneğin çocuklara işaretçiler) saklamayacağız. Bunun yerine yalnızca her düğümle ilişkili indeksleri preorder sırasıyla optimal bir Golomb–Rice kodu kullanarak bir bit dizisine yazarız. Bölme stratejisi sabitlendikten sonra her indeksin Golomb–Rice parametresi bilinir; çünkü bu parametre yalnızca düğümle ilişkili anahtar sayısına bağlıdır.

Her düğümün çocuk sayısı bölme stratejisi tarafından tanımlandığından bunları açıkça saklamaya gerek yoktur. Ancak ağacı yukarıdan aşağıya dolaşırken bir düğümün ilk çocuğuna gitmediğimiz her durumda önceki çocuklara ait alt ağaçları özyineli olarak atlamamız gerekir.

İlke olarak bir alt ağacı atlamak için yalnızca kökle ilişkili Golomb–Rice parametresini bilmemiz yeterlidir: önce ilk kodu atlarız ve ardından her çocuk için özyinelemeye gireriz. Ancak bu strateji çok yavaş olur.

Bu nedenle tüm sabit uzunluklu kod parçalarını bit dizisine yazar, ardından tüm unary parçalarını ekleriz. Bu seçim bir alt ağacın sabit uzunluklu kısmını atlamayı çok hızlı hale getirir; çünkü yalnızca bir işaretçiyi hareket ettirmemiz yeterlidir.

• Her bucket için, her düğümde saklanan indeksler dahil olmak üzere bölme ağacının bir temsili.

Hareket miktarı bir tabloda önceden hesaplanabilir (sabit bir bölme stratejisi için yalnızca düğümle ilişkili anahtar sayısına bağlıdır). Aynı fikirle sabit kısmın toplam uzunluğunu, yani unary kodlarının başlangıç noktasını da ek bilgi olmadan elde edebiliriz.

Belirli sayıda unary kodunu atlamak aslında bir seçim işlemidir (örneğin bir bit dizisinde k'ncı 1'i bulmak). Bu işlem için çok hızlı broadword programlama algoritmaları vardır [Vig08, GP14]. Atlanacak 1 sayısını bilmemiz gerekir; bu sayı atlanan düğüm sayısına karşılık gelir ve bu değer de önceden hesaplanıp bir tabloda saklanabilir.

Son olarak bucket boyutlarının önek toplamları $s_i$ ve her bucket'ın ofseti $o_i$, monoton diziler için kısa bir temsil olan özelleştirilmiş bir Elias–Fano temsili kullanılarak saklanır [Eli74, Fan71].

6.3 Önek toplamları ve ofsetler

Öncelikle bu iki değer arasındaki bağımlılıktan yararlanarak verimizi sıkıştırırız: $s_i$ ve $o_i − βs_i$ değerlerini saklarız; burada $β$, bölme ağaçlarını saklamak için gerekli anahtar başına bit sayısıdır. Daha sonra alışıldığı üzere her iki dizi için ardışık elemanlar arasındaki minimum fark $δ$ hesaplanır ve i'inci elemandan $iδ$ çıkarılarak diziler yeniden ölçeklendirilir. Bu işlem dizilerin aralığını ve buna bağlı olarak eleman başına bit sayısını azaltır. Değiştirilmiş $o_i − βs_i$ listesindeki öğeler arasındaki minimum fark negatifse yeniden ölçekleme listenin elemanlarını büyüterek diziyi tekrar monoton hale getirir.

Elias–Fano temsili iki eleman arasındaki ortalama boşluğun logaritmasıyla orantılı alan kullanır; bizim durumumuzda bu değer $b$ veya $αb{{ content }}#39;dir. Dolayısıyla hedef bucket boyutu $b$ büyütülerek önek toplamlarını saklamak için kullanılan alan keyfi biçimde azaltılabilir (bunun karşılığında oluşturma ve arama işlemleri yavaşlar).

7 Gerçekleme ayrıntıları

7.1 Logaritmalar

Bazı hesaplamalarda $\lg x$ değerine en yakın tam sayıyı, yani $\lfloor \lg x + 1/2 \rfloor$ değerini tahmin etmemiz gerekir. Bunun için şu yaklaşık formülü kullanırız:

λ(x + (x ≫ 1)) = ⌊lg(x + ⌊x/2⌋)⌋ ≈ ⌊lg(x + x/2)⌋

= ⌊lg x + lg 3 − 1⌋ ≈ ⌊lg x + 0.58⌋,

ve bu ifade yalnızca tam sayı işlemleri içerir.

7.2 Golomb–Rice kodları için parametre seçimi

Parametresi $p$ olan geometrik dağılımlı bir kaynak için Golomb–Rice kodunun en iyi parametresi $r(p)$ (4) ile verilir.

$p{{ content }}#39;nin olası değerleri yalnızca $m{{ content }}#39;ye bağlıdır; çünkü bölme stratejisi bölmenin yapılacağı parçaların sayısını ve boyutlarını tek anlamlı biçimde belirler. Bu nedenle $r(p)$ değerlerini önceden hesaplayıp en olası bucket boyutları için sonuçları bir tabloda saklayabiliriz.

Büyük bucket'lar durumunda (pratikte ihmal edilebilir bir durum) $m$ elemanını $s$ parçaya $k₀, k₁, …, k_{s−1}$ şeklinde bölerken en iyi parametre için aşağıdaki tam sayı yaklaşımını geliştirdik:

(s−1) ∑ i=0

λ(k_i + (k_i ≫ 1)) − λ(m)

((s−1) · 5 ≫ 1) +

≫ 1.

Benzer şekilde birebir eşlemeler için en iyi Golomb–Rice kodlarını da bir tabloda saklarız; çünkü bunlara yalnızca birkaç düzine farklı yaprak boyutu için ihtiyaç duyulur.

7.3 Korelasyondan kaçınma

Deneme sayısı tahminlerimizin geçerli olabilmesi için her bölme veya birebir eşleme araması bağımsız olmalıdır. Hem bölmeleri hem de birebir eşlemeleri bucket atamalarında kullanılan $\Theta(n)$ bitlik imzalar üzerinde hesaplayacağız, ancak üst $t$ biti atacağız; böylece her bucket içinde rastgele imzalardan oluşan bir küme ile çalışacağız.

Bölme işlemi sırasında özyineli olarak aşağı inerken daha önce denenmiş fonksiyonları yeniden kullanmamaya dikkat ederiz. Böylece bir yol boyunca bağımsızlık $φᵢᵏ$ fonksiyonlarının bağımsızlığıyla sağlanır; farklı parçalar arasında ise kullanılan anahtarların aslında kesişimi boş olan rastgele bir imza kümesi olması bağımsızlığı garanti eder.

7.4 Elias–Fano'nun özelleştirilmesi

Elias–Fano temsilinin ayrıntılarını kısaca hatırlayalım.

$n > 0$ adet doğal sayıdan oluşan monoton artmayan bir dizi olduğunu varsayalım:

0 ≤ x₀ ≤ x₁ ≤ ⋯ ≤ x_{n−2} ≤ x_{n−1} ≤ u,

burada $u > 0$ son değer için herhangi bir üst sınırdır. Bu diziyi iki bit dizisi kullanarak şu şekilde temsil ederiz:

• Her $x_i$ değerinin alt $ℓ = max{0, ⌊lg(u/n)⌋}$ biti alt-bitler dizisinde açıkça ve bitişik biçimde saklanır.

• Üst bitler üst-bitler dizisinde unary kodlanmış boşluklar dizisi olarak saklanır.

Daha sonra yüksek bitler üzerine bir seçim veri yapısı eklenir; böylece k'ncı 1'in konumu $p$ sabit zamanda bulunabilir. Bu noktada k'ncı elemanın üst bitleri yalnızca $p − k$ olur ve alt bitler doğrudan alınabilir.

Öncelikle şunu gözlemleriz: alt bitler sabit genişlikte olduğundan, bizim durumumuzda olduğu gibi aynı uzunlukta iki Elias–Fano temsili ile çalışıyorsanız ve her zaman iki listedeki aynı konumdaki elemanlara erişmeniz gerekiyorsa, alt bitler iç içe geçirilerek bir cache miss tasarrufu sağlanabilir.

Ayrıca listedeki elemanlar arasındaki boşlukların son derece düzenli olduğunu fark ederiz; çünkü bunlar bucket boyutları veya bir bucket'ı kodlamak için kullanılan bit sayılarıdır. Bu özellik nedeniyle seçim veri yapısı önemli ölçüde basitleştirilebilir ve iki seviyeli bir envanter haline getirilebilir: indeksi 2¹⁴'ün katı olan 1'lerin konumlarını 64 bitlik bir tam sayıda saklarız ve ardından indeksi 2^q'nun katı olan ara 1'lerin konumlarını kaydetmek için 16 bitlik tam sayılardan oluşan bir dizi kullanırız (kodumuzda $q = 8$).

Geri kalan 1'ler için broadword programlama kullanarak, envanterdeki en yakın 1'den başlayarak yerel bir doğrusal arama gerçekleştiririz.

Bu bilgileri iki listeden iç içe geçirerek çoğu zaman ek bir cache miss daha önleyebiliriz.

Ağaç kodlama örneği

Şekil 2: Şekil 1'deki ağaç için bir kodlama örneği. İndeksler önce preorder sırasıyla yerleştirilir. Ardından her indeks uygun bir Golomb–Rice kodu kullanılarak temsil edilir (unary kısmı bir dikey çizgi ile ayrılmıştır). Daha sonra unary ve sabit kısımlar ayrı ayrı saklanır.

Örnek diziler:

11101 1

0

1

1

Fixed

Unary

Kodlanmış temsil:

01|11101 001|1 1|001|01|0 001|01|001|1 01|01|01|1 01|

Ayrılmış parçalar:

01 001 1 001 01 001 01 001 01 01 01 01

8 Deneyler

Bu bölümde deneylerimizin sonuçlarını sunuyoruz. Deneyler Intel® Core™ i7‑7770 CPU @ 3.60 GHz (Kaby Lake), 64 GiB RAM, Linux 4.17.19 ve Java 12 kullanılan bir sistemde gerçekleştirilmiştir. C kodu için GNU C derleyicisi 8.1.1 kullanılmıştır.

Zaman ölçümü duvar saati ile yapılmıştır. Raporladığımız arama sürelerinde göreli standart sapma %5'in altındadır. Oluşturma süreleri (girdinin okunması, veri yapısının üretilmesi ve serileştirilmesi dahil) G/Ç nedeniyle biraz daha fazla değişkenlik gösterir. Turbo Boost denetleyicisinden kaynaklanan frekans değişimlerini önlemek için CPU saat frekansını sabitliyoruz.

RecSplit'i mevcut üç en iyi MPHF gerçekleme ile karşılaştırıyoruz:

• GOV [GOV16], rastgele hipergraphlara dayanan ve anahtar başına 2.24 bit ile hızlı erişim sağlayan bir yapıdır.

• CHD [BBD09] Bölüm 3.3’te tartışılmıştır. Test ettiğimiz haritalar arasında açık ara en yavaş olanıdır, ancak anahtar başına yaklaşık 2 bit seviyesine ulaşabilen tek yöntemdir. λ = 5 ve λ = 6 için verileri raporluyoruz. λ = 7 ile birkaç bin anahtarın ötesinde haritalar oluşturmayı başaramadık.

• BBHash [LRCP17], parmak izi tabanlı minimal perfect hashing yaklaşımının bir uygulamasıdır ve oluşturma ile sorgulama işlemlerinde çok hızlı olmayı hedefler, ancak büyük miktarda alan kullanır. En az alan kullanan sürümü (γ = 1) test ettik, ancak bu sürümün depolanabilmesi için anahtar başına 3 bitten fazla gereklidir.

Deneyimizde, 128 bitlik rastgele anahtarlar üzerinde haritalar oluşturup değerlendiriyoruz. Bu durum, uzun anahtarların hash değerlerini hesaplamak için gereken zamanı ortadan kaldırdığımız için sonuçlarımızın çözünürlüğünü önemli ölçüde artırır. Tüm uygulamalar ilk adımda anahtarlarını rastgele kısa anahtarlara hash’lediğinden, bu seçimin yapıların davranışı üzerinde hiçbir etkisi yoktur.

RecSplit, ℓ ve b parametrelerine bağlı olarak farklı davranış gösterir. ℓ değerinin artırılması daha küçük veri yapıları ve daha hızlı sorgulamalar sağlar, ancak bunun karşılığında oluşturma süresi artar. b değerinin artırılması alanı daha da azaltabilir (çünkü Elias–Fano listeleri daha iyi amortize edilir), ancak oluşturma ve sorgulama sürelerinde küçük bir artışa yol açar. Şekil 3, alanın bu iki parametreye bağımlılığını göstermektedir.

Olası birçok varyasyon arasından şu örnekleri ayırıyoruz:

• ℓ = 8, b = 100, CHD’nin anahtar başına 2 bit sınırını aşar; daha iyi alan kullanımı ve belirgin biçimde daha hızlı oluşturma ve sorgulama sağlar.

• ℓ = 12, b = 9, GOV ve BBHash’ten daha az alan kullanır. Sorgulama süresi daha hızlıdır veya karşılaştırılabilir düzeydedir, ancak tek iş parçacıklı ve dağıtık olmayan bir ortamda oluşturulması daha uzun sürer.

• ℓ = 5, b = 5, BBHash’ten daha az alan kullanır ve büyük boyutlarda daha hızlı oluşturulur.

• ℓ = 16, b = 2000, oluşturma açısından uygulanabilirliğin sınırındadır; çünkü anahtar başına neredeyse iki milisaniye gerektirir. Buna rağmen anahtar başına 1.56 bit seviyesine ulaşır; bu da alt sınırdan %8.3 uzaklıkta olduğu anlamına gelir. Sorgulama süresi GOV veya BBHash’ten belirgin biçimde daha büyüktür, ancak yine de CHD’den daha hızlıdır.

Tablo 1 ve Tablo 2’de, alan kullanımını anahtar başına bit cinsinden ve oluşturma ile sorgulama sürelerini anahtar başına nanosaniye cinsinden raporluyoruz.

Hemen göze çarpan bir gözlem şudur: Tablo 1 durumunda tüm yapılar önbelleğe sığarken, Tablo 2 durumunda sığmamaktadır. Bunun sonucunda, tüm yapılar sabit zamanda sorgulama gerçekleştirmesine rağmen, sorgulama süreleri yaklaşık bir büyüklük mertebesi kadar artmaktadır.

Anahtar sayısına bağlı daha genel bir görünüm Şekil 5 ve Şekil 6’da verilmiştir. Tüm kodlar C veya C++ dilindedir; yalnızca GOV’un oluşturma işlemi Java dilinde mevcuttur.

Karşılaştırdığımız her bir güncel harita için, alan ve/veya sorgulama hızı açısından karşılaştırılabilir bir RecSplit örneği bulunduğu ve bu iki ölçütten en az birinde iyileşme sağladığı açıkça görülmektedir.

Şekil 7, alan kullanımı ve sorgulama süresi çiftlerinden oluşan uzayın Pareto sınırını (koordinat bazında minimal noktalar kümesini) göstermektedir. Eleman başına 3 bitten daha düşük değerlerde bu noktaların tamamı RecSplit örnekleridir. BBHash biraz daha iyi bir sorgulama hızına sahiptir (yaklaşık %10 daha hızlı), ancak bunun karşılığında yaklaşık %40 daha fazla alan kullanır.

Üç boyutlu Pareto sınırı ele alındığında durum farklıdır; çünkü hızlı sorgulama sağlayan RecSplit örnekleri genellikle daha fazla oluşturma süresi gerektirir. Ancak RecSplit, şu anda küçük alan kullanımı için en ileri yöntem olan CHD’ye kıyasla üç parametrenin tamamında aynı anda iyileşme sağlar.

Ayrıca hem CHD hem de BBHash, veri yapısının nihai boyutu kadar RAM’in kullanılabilir olmasını gerektirir. Buna karşılık GOV ve RecSplit prensipte yapının disk üzerinde, muhtemelen dağıtık bir biçimde ve çok küçük miktarda RAM kullanılarak oluşturulmasına izin verir; çünkü her iki yapı da anahtarları bağımsız olarak işlenebilen küçük kovalar içine dağıtır.

RecSplit’in bir diğer avantajı, ℓ değerinin artırılmasının oluşturmayı yavaşlatmasına rağmen aynı zamanda alanı azaltması ve sorgulamayı hızlandırmasıdır. BBHash için daha küçük bir harita oluşturmak daha yavaş oluşturma ve daha yavaş sorgulama anlamına gelir. CHD için ise daha küçük bir harita daha yavaş oluşturma anlamına gelir ve sorgulamalar üzerinde etkisi yoktur.

ℓ ≥ 4 ve 64 ≤ b ≤ 2048 olan RecSplit örneklerini tek başına ele alırsak, bunların neredeyse tamamı üç boyutlu Pareto sınırı üzerindedir. Bu durum, bu parametre seçimlerinin alan kullanımı, oluşturma süresi ve sorgulama süresi arasında farklı denge noktaları sağladığını gösterir.

Şekillerden görüldüğü üzere, CHD ve BBHash’in bellek içi oluşturulması anahtar sayısı arttıkça önbellek ve Translation Lookahead Buffer kaçırmaları nedeniyle belirgin biçimde doğrusal olmayan bir davranışa yol açmaktadır. GOV ve RecSplit için bu durum gözlenmez.

Son olarak, Şekil 4 üstel aralıklı kova boyutları için yaprak boyutuna bağlı olarak oluşturma süresindeki artışı göstermektedir. Bölüm 5.4’teki tartışmadan beklendiği gibi, yaprak boyutunun bir artırılması oluşturma süresini yaklaşık olarak e ile çarpar; buna karşılık kova boyutunun etkisi daha azdır.

Sonuç

Beklenen doğrusal zamanlı oluşturma ve beklenen sabit zamanlı sorgulama ile minimal perfect hash fonksiyonunu depolayan yeni bir statik veri yapısı olan RecSplit sunulmuştur.

RecSplit, pratikte anahtar başına 2 bit sınırını aşabilen ilk veri yapısıdır ve alt sınıra çok yakın örnekler uygulanabilir biçimde, her ne kadar yavaş olsa da, oluşturulabilir. Oluşturma süresi, sabit nokta terslemesi monoton olduğu için MapReduce [DG08] gibi dağıtık bir hesaplama ortamı kullanılarak azaltılabilir. Kovalar, (çevrimdışı) sıralanmış imzaların doğrusal bir taramasıyla hesaplanabilir ve ardından her kovanın bölme ağacı bağımsız olarak oluşturulabilir.

Birebir eşlemelerin ve bölmelerin kodomain boyutu genişletilerek, bu makalede açıklanan teknikler son derece sıkıştırılmış perfect (ancak minimal olmayan) hash fonksiyonları oluşturmak için de kullanılabilir. Bu genişletme gelecekteki çalışmalar için bırakılmıştır.

Kaynaklar