PTHash: FCH Minimal Perfect Hashing Yaklaşımının Yeniden İncelenmesi

ÖZET

Farklı anahtarlardan oluşan (n) elemanlı bir (S) kümesi verildiğinde, (S) kümesinin anahtarlarını ({0, \ldots, n-1}) aralığına birebir eşleyen bir (f) fonksiyonuna (S) için bir minimal perfect hash fonksiyonu denir. (n) büyük olduğunda bu tür fonksiyonları bulan ve sabit değerlendirme süresini koruyan algoritmalar pratik açıdan ilgi çekicidir; örneğin arama motorları ve veritabanları genellikle dizeler gibi değişken uzunluklu anahtarlardan oluşan statik kümelere hızlı biçimde kimlik atamak için minimal perfect hash fonksiyonlarını kullanır.

Zorluk, üç farklı açıdan verimli olan bir algoritma tasarlamaktır: (f) fonksiyonunu bulma süresi (inşa süresi), (S) kümesindeki bir anahtar için (f) değerini hesaplama süresi (lookup süresi) ve (f) için kullanılan temsilin bellek alanı. Bu yönler arasında denge kurmak için çeşitli algoritmalar önerilmiştir.

1992 yılında Fox, Chen ve Heath (FCH), SIGIR konferansında çok hızlı lookup değerlendirmesi sağlayan bir algoritma sundu. Ancak bu yaklaşım, büyük inşa süresi ve daha sonraki tekniklere kıyasla daha yüksek alan tüketimi nedeniyle fazla ilgi görmedi. Yaklaşık otuz yıl sonra bu çerçeveyi yeniden ele alıyor ve büyük veri kümelerine iyi ölçeklenen, toplam alan tüketimini azaltan ve lookup süresinden ödün vermeyen geliştirilmiş bir algoritma sunuyoruz.

Geniş kapsamlı deneysel bir değerlendirme gerçekleştiriyor ve algoritmanın alan açısından en gelişmiş tekniklerle rekabet edebilen fonksiyonlar bulduğunu ve 2–4× daha iyi lookup süresi sağladığını gösteriyoruz.

CCS KAVRAMLARI

• Bilgi sistemleri → Erişim verimliliği
• Hesaplama kuramı → Veri yapıları tasarımı ve analizi

ANAHTAR KELİMELER

Minimal Perfect Hashing; FCH; XOR; Sıkıştırılmış Veri Yapıları

ACM Referans Formatı

Giulio Ermanno Pibiri ve Roberto Trani. 2021. PTHash: FCH Minimal Perfect Hashing Yaklaşımının Yeniden İncelenmesi. Bilgi Erişiminde Araştırma ve Geliştirme Üzerine 44. Uluslararası ACM SIGIR Konferansı Bildirileri (SIGIR ’21) içinde, 11–15 Temmuz 2021, Çevrimiçi Etkinlik, Kanada. ACM, New York, NY, ABD, 10 sayfa. https://doi.org/10.1145/3404835.3462849

Giulio Ermanno Pibiri
ISTI-CNR, Pisa, İtalya
giulio.ermanno.pibiri@isti.cnr.it

Roberto Trani
ISTI-CNR, Pisa, İtalya
roberto.trani@isti.cnr.it

arXiv:2104.10402v2 [cs.DS] 28 Mayıs 2021

1. GİRİŞ

Minimal perfect hashing problemi, statik bir (S) kümesinin (n) farklı elemanına ([n] = {0, \ldots, n-1}) aralığındaki sayıları atayan bir veri yapısı oluşturmaktır. Ortaya çıkan veri yapısına minimal perfect hash fonksiyonu (f), kısaca MPHF, denir ve bu yapı az yer kaplarken (S) kümesindeki herhangi bir anahtar için sabit zamanda değerlendirme sağlamalıdır.

İlke olarak, bir perfect hash tablosu kullanarak (S) için bir MPHF elde etmek oldukça basittir: her (x \in S) anahtarı tablo içinde saklanan (⟨x, p⟩) çifti ile (O(1)) zamanda ilişkilendirilir; burada (p), ([n]) aralığında (x) anahtarının kimliğidir. Ancak bu yaklaşım, (S) kümesinin kendisini temsil etme maliyetini de öder; buna ek olarak ([n]) aralığındaki sayıların depolanması gerekir ve bu da (Θ(n \log n)) bit yer kaplar.

Bununla birlikte, minimal perfect hashing problemi (S) kümesine ait olmayan anahtarlar üzerinde (f) fonksiyonunun davranışını dikkate almaz. Bu gevşetme, (S) kümesi için gereken alanın kaldırılmasını mümkün kılar ve böylece aşağıdaki alan alt sınırını kabul eder:

[ \log_2 e \approx 1.44 \text{ bit/anahtar} ]

Bu sınır, giriş verisinin boyutu ve türünden bağımsızdır.

Minimal perfect hashing uygulamaları bilişimde yaygın olarak kullanılır ve sıkıştırılmış tam metin indeksleri, bilgisayar ağları, veritabanları, önek arama veri yapıları, dil modelleri, Bloom filtreleri ve türevleri gibi pek çok alanı kapsar.

Bu problem için çeşitli algoritmalar bilinmektedir ve her biri inşa süresi, lookup süresi ve alan tüketimi arasında bir denge sunar. Bu yaklaşımları Bölüm 2’de inceliyoruz. Bu çalışmanın başlangıç noktası, Fox, Chen ve Heath tarafından ilk olarak tanımlanan ve onların adlarından türetilen FCH adlı eski bir tekniktir.

Bu araştırmacılar, MPHF’nin değerlendirilmesini birkaç hash ve aritmetik hesaplamaya ek olarak yalnızca bir diziye yapılan tek bir bellek erişimi ile mümkün kılan üç adımlı bir çerçeve önerdiler. Daha açık olarak, algoritma (c) parametresi için (c n) bit yer kaplayan bir MPHF oluşturur. Bu parametre inşanın verimliliğini belirler: (c) değeri büyüdükçe (f) fonksiyonunun inşa süresi azalır.

Ne yazık ki, büyük girişler üzerinde makul sürede FCH ile bir MPHF bulabilmek için (c) değerinin büyük seçilmesi gerekir ve bu da alan israfına yol açar. Öte yandan daha yeni algoritmalar oldukça iyi ölçeklenir ve anahtar başına daha az bit kullanır, ancak genellikle her lookup için 3–4 bellek erişimi gerçekleştirir. Bu nedenle bu çalışma, FCH’nin hızlı lookup süresini daha kompakt bir temsil ile birleştirmeyi amaçlar.

MPHF’nin kapladığı alan yeterince küçük olduğunda — teorik minimuma çok yakın olmasa bile — en önemli unsur, fonksiyonun uygulanabilir biçimde oluşturulabilmesi koşuluyla lookup süresidir. Nitekim pratik uygulamalarda MPHFs, statik sözlükler (anahtar–değer depoları) oluşturmak için temel yapı taşları olarak kullanılır; bu yapılar bir kez oluşturulur ve çok sayıda kez değerlendirilir.

Değerler MPHF’nin kendisinden çok daha fazla alan kapladığında — ki pratikte genellikle durum böyledir — MPHF’nin anahtar başına 3 veya 2 bit kullanması kritik bir mesele değildir. Bu nedenle hızlı lookup ve uygulanabilir inşa süresi bu problem için en kritik yönlerdir ve biz de çalışmamızda bunlara odaklanıyoruz.

Bu makalede PTHash adlı yeni bir algoritma öneriyoruz. Bu algoritma, FCH’nin lookup performansını kısa temsil ve büyük veri kümelerinde hızlı inşa ile birleştirir. PTHash’in temel özelliği, veri yapısında depolanan bilginin entropisini FCH’ye kıyasla önemli ölçüde azaltmasıdır. Bu durum, alan tüketimini ciddi biçimde düşüren hafif bir sıkıştırma düzenini mümkün kılar ve aynı zamanda dikkat çekici lookup performansını korur.

PTHash’i sabit ve değişken uzunluklu anahtarlardan oluşan büyük veri kümeleri üzerinde, en gelişmiş tekniklerle karşılaştırarak değerlendiriyoruz. Sonuçlar, inşa süresi bakımından diğer tekniklerle rekabet edebildiğini ve yaklaşık aynı alan tüketimi altında lookup süresinde 2–4× daha hızlı olduğunu göstermektedir.

PTHash’in C++ uygulaması aşağıdaki adreste mevcuttur:

https://github.com/jermp/pthash

2. İLGİLİ ÇALIŞMALAR

Bugüne kadar minimal perfect hashing problemini çözmek için dört farklı yaklaşım geliştirilmiştir. Bunları önerilme sırasına göre özetliyoruz. Hagerup ve Tholey tarafından sunulan bazı kuramsal yapılar, (n \log_2 e) bitlik alan alt sınırına ulaştıkları gösterilebilse de bu yalnızca asimptotik anlamda geçerlidir (yani (n) değeri pratik kullanım için aşırı büyüktür).

Hash ve Displace

hash and displace tekniği ilk olarak Fox, Chen ve Heath tarafından tanıtılmıştır (daha sonra Pagh, Tarjan ve Yao’nun çalışmalarından esinlenerek bu adı kullanmıştır).

Yaklaşımlarını (FCH) Bölüm 3’te ayrıntılı biçimde anlattığımız için burada yalnızca kısa bir genel bakış veriyoruz.

Anahtarlar önce hashlenir ve ({B_i}) biçimindeki düzensiz kovalar içine eşlenir. Daha sonra kovalar boyutlarına göre sıralanır ve büyükten küçüğe doğru işlenir. Her (B_i) kovası için (d_i \in [n]) yer değiştirme değeri belirlenir; böylece kovadaki tüm anahtarlar

[ (h(x) + d_i) \bmod n ]

konumlarında çakışma olmadan yerleştirilebilir; burada uygun bir hash fonksiyonu (h) ve (x \in B_i) kullanılır.

Son olarak yer değiştirme değerleri dizisi (d_i), her değer için (\lceil \log_2 n \rceil) bit kullanılarak kompakt biçimde saklanır. Kuramsal analiz, kova sayısını azaltmanın (daha uzun inşa süresi pahasına) alan kullanımını azaltabileceğini gösterse de pratikte büyük (n) değerleri için 2.5 bit/anahtar seviyesinin altına inmek zordur.

Belazzougui ve arkadaşlarının compressed hash and displace (CHD) varyantında anahtarlar önce beklenen boyutu (\lambda > 0) olan kovalar içine eşit dağıtılır. Her (B_i) kovası için (⟨d_0, d_1⟩) yer değiştirme çifti belirlenir; böylece tüm anahtarlar

[ (h_1(x) + d_0 h_2(x) + d_1) \bmod n ]

konumlarına çakışma olmadan yerleştirilebilir; burada (h_1) ve (h_2) hash fonksiyonları kullanılır.

Her çifti açıkça saklamak yerine, çiftin aşağıdaki dizideki indeksi saklanır:

[ ⟨0,0⟩, \ldots, ⟨0,n-1⟩, ⟨1,0⟩, \ldots, ⟨1,n-1⟩, \ldots, ⟨n-1,0⟩, \ldots, ⟨n-1,n-1⟩ ]

İndeks dizisi daha sonra Fredriksson ve Nikitin tarafından tanıtılan entropi kodlama mekanizması kullanılarak sıkıştırılır ve aynı zamanda (O(1)) erişim süresi korunur.

Doğrusal Sistemler

1990’ların sonlarında Majewski ve arkadaşları, doğrusal sistemler ile hipergraphlar arasındaki bağlantıyı kullanan bir MPHF oluşturma algoritması tanıttı. Yaklaşık on yıl sonra Chazelle ve arkadaşları benzer bir yapıyı bağımsız olarak önerdi.

MPHF (f), aşağıdaki biçimde (m) değişkenli (n) adet rastgele denklemden oluşan bir sistem kurularak bulunur:

[ w_{h_1(x)} + w_{h_2(x)} + \cdots + w_{h_r(x)} = f(x) ]

burada (h_i : S \rightarrow [m]) rastgele hash fonksiyonlarıdır ve ({w_i}) değişkenlerinin değerleri ([n]) aralığındadır.

Rastgele grafiklerin çevrimsizliği üzerine sınırlar sayesinde, (m) ile (n) arasındaki oran (\gamma_r) eşik değerinin üzerindeyse sistem neredeyse her zaman üçgenselleştirilebilir ve karşılık gelen hipergraph peeling yöntemiyle doğrusal zamanda çözülebilir. (\gamma_r) sabiti grafın derecesi (r)’ye bağlıdır ve en küçük değerini (r = 3) için alır; burada (\gamma_3 \approx 1.23)’tür.

Belazzougui ve arkadaşları, harici bellek yapıları için uygun olan cache‑oblivious bir uygulama önerdi. Daha sonra Genuzio ve arkadaşları, sistemi çözmek için kullanılan Gauss eliminasyonu tekniğinde pratik iyileştirmeler göstererek inşa süresi, lookup süresi ve alan kullanımını cache‑oblivious yaklaşımlarla rekabet edebilir hâle getirdi.

Fingerprinting

Müller ve arkadaşları fingerprinting tabanlı bir teknik tanıttı. Temel fikir şöyledir.

Tüm anahtarlar önce rastgele bir hash fonksiyonu kullanılarak ([n]) aralığına hashlenir ve çakışmalar (n_0 = n) boyutunda bir (B_0) bitmap’i ile kaydedilir. Çakışmayan anahtarlar konumlarını 1 ile işaretlerken, çakışmaya dahil olan konumlar 0 ile işaretlenir.

Eğer (n_1 > 0) çakışma meydana gelirse, işlem çakışan anahtarlar için (n_1) boyutunda bir (B_1) bitmap’i kullanılarak özyinelemeli olarak tekrarlanır. Tüm bitmap’ler (levels) tek bir (B) bitmap’inde birleştirilir.

Lookup algoritması, (B) içinde (p) konumunda bir 1 bulunana kadar anahtarı seviye seviye hashler. Sabit zamanlı bir ranking veri yapısı, döndürülen değerin ([n]) aralığında olmasını sağlamak için (B[0..p]) içindeki 1’lerin sayısını hesaplar.

En kısa temsil ayarında (yaklaşık 3 bit/anahtar) ortalama olarak yalnızca 1.56 seviye erişilir.

Limasset ve arkadaşları bu yaklaşımı BBHash içinde uyguladı. Bu yöntem hem inşa hem de lookup açısından çok hızlıdır ve çok iş parçacığı kullanarak çok büyük anahtar kümelerine ölçeklenebilir. (\gamma \ge 1) parametresi, her bitmap’i (\gamma n_i) bite genişleterek çakışmaları azaltır; böylece inşa ve sorgular hızlanır ancak alan kullanımı artar.

Recursive Splitting

Esposito ve arkadaşları yakın zamanda RecSplit adlı bir teknik önerdi. Bu teknik, beklenen doğrusal zamanda ve beklenen sabit lookup süresiyle çok kısa temsil sunan MPHFs oluşturmayı sağlar.

Araştırmacılar, çok küçük kümeler için uygun bir kodomain ile birebir eşleme brute‑force araması yaparak bir MPHF bulmanın mümkün olduğunu gözlemlediler. Aynı fikir daha büyük girişler için böl‑ve‑yönet yaklaşımıyla özyinelemeli olarak uygulanır.

(b) ve (\ell) parametreleri verildiğinde anahtarlar rastgele bir hash fonksiyonu kullanılarak ortalama boyutu (b) olan kovalar içine bölünür. Her kova, boyutu (\ell) olan bloklar elde edilene kadar özyinelemeli olarak bölünür; bu bloklar için brute‑force bir MPHF bulunabilir. Bu süreç köklü bir bölme ağacı oluşturur.

Bu yöntem çok kompakt bir temsil sağlasa da değerlendirme sırasında ağaç seviyesine başına bir bellek erişimi gerekir ve bu durum lookup süresini olumsuz etkiler.

3. FCH TEKNİĞİ

Fox, Chen ve Heath 1992 yılında minimal perfect hashing için üç adımlı bir çerçeve sundu. (n) anahtarlı bir (S) kümesi için teknik, boyutu (c n) bit olan bir MPHF (f) bulur; burada (c > \log_2 e) parametresi alan ile inşa süresi arasında bir denge kurar.

Construction

İnşa süreci üç adımda ilerler: mapping, ordering ve searching.

Önce mapping adımı anahtar kümesini düzensiz kovalar içine yerleştirerek bölümlere ayırır. Daha sonra kovalar belirli bir sırayla işlenir ve ardından tüm anahtarların çakışma olmadan farklı konumlara atanmasını sağlayacak yer değiştirme değerleri aranır.

(w h_1(x) + w h_2(x) + \cdots + w h_r(x) = f(x) \mod n, ; x \in S).

Ordering adımı kovaları azalmayan değil, azalan boyut sırasına göre düzenler ve anahtarların işlenme sırası bu şekilde belirlenir. Son olarak searching adımı, ([n]) içindeki boş konumları her kovanın anahtarlarına açgözlü biçimde atamaya çalışır. Bu süreçte iki hash fonksiyonu kullanılır. Pratikte MurmurHash [1] gibi bir pseudo‑random fonksiyon (h) kullanılır ve iki farklı seed değeri (s_1) ve (s_2) seçilir. (s_1) rastgele seçilebilirken, (s_2) birazdan açıklanacak bir özelliği sağlamalıdır.

(i) Mapping

Anahtarların kovalar içine düzensiz eşlenmesi şu şekilde yapılır. Tüm anahtarlar (h(x, s_1)) ile hashlenir ve (p_1) değeri seçilerek (S) kümesi iki alt kümeye ayrılır:

• (S_1 = {x \mid (h(x, s_1) \mod n) < p_1})
• (S_2 = S \setminus S_1)

Ardından

[ m = \left\lceil \frac{c n}{\log_2 n + 1} \right\rceil ]

adet kova anahtarları tutmak üzere ayrılır; burada (c) verilen parametredir. (c) değeri küçüldükçe kova sayısı azalır ve kova başına ortalama anahtar sayısı artar.

Son olarak (p_2) değeri seçilir ve her (x \in S) anahtarı aşağıdaki kovaya atanır:

[ \text{bucket}(x) = \begin{cases} h(x, s_1) \mod p_2 & x \in S_1 \ p_2 + (h(x, s_1) \mod (m - p_2)) & \text{aksi takdirde} \end{cases} ]

(1)

Keyfi eşik değerleri (p_1) ve (p_2) sırasıyla (0.6n) ve (0.3m) olarak ayarlanır; böylece anahtarların kovalar içine eşlenmesi eşit değildir: anahtarların yaklaşık %60’ı kovaların %30’una yerleştirilir.

(ii) Ordering

Tüm anahtarlar (m) kovasına yerleştirildikten sonra kovalar, searching adımını hızlandırmak için azalan boyut sırasına göre sıralanır.

(iii) Searching

Önceki adımın verdiği sıraya göre her (B_i) kovası için bir yer değiştirme değeri (d_i) ve ek bir (b_i) biti belirlenir; böylece kovadaki tüm anahtarlar, konumlara hashlenirken daha önce dolu olan konumlarla çakışma üretmez.

Özellikle küresel seed (s_2), aynı kovadaki anahtarlar arasında çakışma olmayacak şekilde seçilir. Arama sırasında ek bir serbestlik derecesi sağlamak için, hiçbir yer değiştirme değeri bulunamadığında başarısızlığı önlemek amacıyla (B_i) kovası için (h) fonksiyonunun seed’inde ek bir (b_i) biti kullanılır. (b_i = 0) için tüm yer değiştirmeler denendikten sonra aynı yer değiştirmeler (b_i = 1) ile tekrar denenir.

(d_i)’nin belirlenmesini hızlandırmak için, kullanılabilir konumları bulmak amacıyla (\Theta(n \log n)) bitlik iki tamsayı dizisinden oluşan yardımcı bir veri yapısı kullanılır. Rastgele seçilmiş bir kullanılabilir konum (p) verildiğinde, (B_i)’nin herhangi bir anahtarı (p)’ye hizalanarak (d_i) hesaplanır. Bu rastgele hizalama algoritma için kritik önemdedir çünkü tüm konumların işgal edilme olasılığının aynı olmasını garanti eder ve böylece arama verimliliğini korur.

Tartışma

Arama aşaması sona erdiğinde, her bir bucket için bir tane olmak üzere (m) adet (\langle d_i, b_i \rangle) çifti belirlenmiş olur ve (\text{bucket}) fonksiyonunun verdiği sıraya göre (P) adlı bir dizi içinde saklanır. MPHF’nin gerçekte sakladığı yapı bu dizidir.

Bir bucket için en fazla (n) yer değiştirme değeri denenebileceğinden, her (d_i) için (\lceil \log_2 n \rceil) bit gerekir. Dolayısıyla (\lceil \log_2 n \rceil + 1) bit, (\langle d_i, b_i \rangle) çiftini kodlamak için harcandığından, (P) dizisini saklamak için gereken toplam alan

[ m(\lceil \log_2 n \rceil + 1) \approx c n \text{ bit} ]

olur.

(P) dizisi ile (f(x))’i değerlendirmek basittir; aşağıdaki sözde kodda gösterilmiştir. Orijinal yazarlar uygulama ayrıntılarını tartışmamış olsa da, eğer (d_i) ve (b_i) büyüklüklerini (\lceil \log_2 n \rceil + 1) bitlik bitişik bir segment içinde iç içe yerleştirirsek, arama algoritması yalnızca tek bir bellek erişimi gerektirir.

Özellikle (b_i) en az anlamlı bit (sağdan) olarak yazılır ve (d_i) geri kalan (\lceil \log_2 n \rceil) en anlamlı bitleri alır. (P)’den okunan iç içe geçmiş (v) değerinden bu iki büyüklüğü geri elde etmek için basit ve hızlı bit düzeyi işlemler kullanılır:

• (b_i = v & 1)
• (d_i = v \gg 1)

Bu, sözde kodun 3. adımındaki (\langle d_i, b_i \rangle = P[i]) atamasının gerçek uygulamasıdır. Dolayısıyla FCH tekniği çok hızlı bir arama süresi sağlar.

Yapım sürecinden önce sabitlenen (c) sabiti, alan ile yapım süresi arasında açık bir dengeyi belirler: değer ne kadar büyükse, her bucket için aynı anda arama koşulunu sağlaması gereken daha az anahtar bulunduğundan yer değiştirmeleri hızlı bulma olasılığı o kadar yüksektir. Öte yandan (c) küçük seçilirse (örneğin (c = 2)), alan tüketimi azalır ancak uygun bir yer değiştirme değeri aramak çok uzun sürebilir — hatta tüm olası (n) yer değiştirme değerlerinin denenmesine kadar ((b_i)’nin her iki seçeneği için) ilerleyebilir ve yapım başarısız olabilir. Bu noktada hash fonksiyonlarının yeniden tohumlanması ve sürecin yeniden başlatılması gerekir.

Pratikte FCH, aynı alan bütçesi için daha yeni tekniklerle karşılaştırıldığında bir MPHF bulmak için oldukça fazla zaman harcar. Örneğin algoritma, 100 milyon rastgele 64‑bit anahtar kümesi üzerinde (c = 3) ile bir MPHF kurmak için 1 saat 10 dakika sürer. Bölüm 2’de incelenen diğer teknikler aynı işi birkaç dakika içinde, hatta daha kısa sürede gerçekleştirebilir; üstelik anahtar başına 3 bitlik aynı nihai alan bütçesiyle. Daha ayrıntılı bir karşılaştırma Bölüm 5.2’de sunulmaktadır.

Bölüm 3’te tartışılan çerçeveden esinlenerek şimdi PTHash adlı bir algoritma sunuyoruz. Bu algoritma, FCH’nin arama performansını korurken hem yapım süresini hem de alan tüketimini iyileştirmeyi amaçlar. Bunu yapmak için çerçevenin ilk iki adımını — eşleme ve sıralama — koruyoruz ancak en kritik adımı tamamen yeniden tasarlıyoruz: arama adımı.

Yeni arama algoritması iki önemli hedefe ulaşmamızı sağlar:

1. Sıkıştırılabilir çıktı garantisi veren bir algoritma tasarlamak.
2. Arama performansını bozmayan bir kodlama şeması tanıtmak.

Ayrıntıları göstermeden önce PTHash’in arkasındaki sezgiyi kısaca özetleyelim. Hatırlanacağı gibi FCH, verilen bir (c) değeri için boyutu (c n) bit olan bir MPHF bulur. Ancak FCH sıkıştırma için fırsat sunmaz. Her bucket için yer değiştirme değeri ([n]) aralığından eşit olasılıkla seçilir; böylece arama sırasında tüm konumların eşit olasılıkla dolması sağlanır. Bu durum aramanın çıktısı olan (P) dizisini neredeyse sıkıştırılamaz hale getirir; yani yer değiştirme başına (\lceil \log_2 n \rceil) bit kullanımı esasen en iyi seçenektir.

Eğer (P) sıkıştırılabilir olsaydı, arama sırasında (c' > c) olacak şekilde farklı bir sabit (c') kullanabilirdik; böylece sıkıştırılmış (P)’nin boyutu yine yaklaşık (c n) bit olurdu. Yani aynı alan bütçesiyle daha büyük bir (c) kullanarak bir MPHF arar ve böylece yapım süresini azaltırdık.

Arama Prosedürü

1. (f(x))
2. (i = \text{bucket}(x))
3. (\langle d_i, b_i \rangle = P[i])
4. return (\text{position}(x, d_i, b_i))

[ \text{position}(x, d_i, b_i) = (h(x, s_2 + b_i) + d_i) \mod n ]

PTHash

4.1 Arama

([n] = {0, \ldots, n-1}) aralığındaki dolu konumları takip etmek için (taken[0..n-1]) adlı bir bitmap kullanıyoruz. Bu, arama için ana destek yapısıdır ve yalnızca (n) bit maliyete sahiptir. Ayrıca bucket içi çakışmaları tespit etmek için küçük bir tamsayı vektörü de tutarız, ancak bunun alanı (n) bit ile karşılaştırıldığında ihmal edilebilir.

Anahtarlar

[ m = \left\lceil \frac{c n}{\log_2 n} \right\rceil ]

sayısında bucket’a (B_0, \ldots, B_{m-1}) Formül (1) kullanılarak eşlenir ve azalmayan büyüklük sırasına göre işlenir. Aynı bucket içindeki anahtarların farklı hash kodlarına eşlenmesi için sözde rastgele bir hash fonksiyonu (h) için bir (s) tohumu seçilir.

Her bucket (B_i) için, (x \in B_i) anahtarına atanan konumun

[ \text{position}(x, k_i) = (h(x, s) \oplus h(k_i, s)) \mod n ]

(2)

olmasını sağlayan bir (k_i) tamsayısı aranır ve

[ taken[\text{position}(x, k_i)] = 0 ]

(3)

koşulu sağlanır.

((x \oplus y)) büyüklüğü, (x) ve (y) arasındaki bit düzeyinde XOR işlemini temsil eder.

Eğer (k_i) araması başarılıysa — yani (k_i), (B_i) bucket’ındaki tüm anahtarları kullanılmamış konumlara yerleştiriyorsa — o zaman (k_i) değeri (P) dizisine kaydedilir ve konumlar

[ taken[\text{position}(x, k_i)] = 1 ]

şeklinde işaretlenerek dolu hale getirilir.

Aksi halde yeni bir (k_i) tamsayısı denenir.

(k_i) tamsayısına, (B_i) bucket’ı için bir pilot adını veriyoruz çünkü (B_i) içindeki anahtarların konumlarını benzersiz biçimde belirler. Buna bağlı olarak (P) dizisi bir pilots table (PT) olarak adlandırılır.

FCH’den farklı olarak anahtarların rastgele yer değiştirmesi artık yardımcı bir veri yapısı yerine bit düzeyinde XOR işlemi aracılığıyla gerçekleşir. İki rastgele tamsayının XOR’u da başka bir rastgele tamsayıdır. XOR işlemine giren iki tamsayı da rastgele bir hash fonksiyonu tarafından üretildiğinden, ikili gösterimlerinde yaklaşık aynı oranda 1 ve 0 bit içermeleri beklenir. XOR işlemi bu dengeyi korur.

(\text{position}(x, k_i)) hesaplamasının (n)’in ikinin kuvveti olmadığını varsaydığına dikkat edin; böylece XOR’dan çıkan tüm bitler modulo işlemi için anlamlı olur. Eğer (n) ikinin kuvvetiyse, anahtarlar bunun yerine ([n + 1]) aralığına eşlenir ve fazladan konum ayrı şekilde ele alınır.

Bu arama stratejisinin çeşitli sonuçları vardır:

• (h(x, s)) ile (h(k_i, s)) arasındaki XOR, yalnızca ikinci terimin farklı pilotlar (k_i) denenirken değiştiği rastgele bir yer değiştirme oluşturur. Bu durum tüm anahtarların hash değerlerinin önceden hesaplanmasına olanak tanır.
• (h(x, s))’nin tekrar tekrar hesaplanmasını önlemek özellikle dizgiler gibi uzun anahtarlarla çalışırken faydalıdır.
• FCH tarafından kullanılan yardımcı veri yapısına artık gerek kalmaz; bu da yapım sırasında bellek tüketimini iyileştirir.
• Algoritma hatalara karşı daha dayanıklı hale gelir çünkü teorik olarak denenebilecek farklı pilot (k_i) sayısında bir sınır yoktur.

Bir diğer önemli sonuç da pilot (k_i) değerlerinin rastgele seçilmesine gerek olmamasıdır. Bunun yerine (k_i),

[ K = 0, 1, 2, 3, \ldots ]

sırasındaki değerler arasından koşul (3)’ü sağlayan ilk değer olarak seçilir. Buradaki sezgi, pilotlar sıralı biçimde denense bile ortaya çıkan konumların yeterince rastgele kalmasıdır.

İki etkinin birleşimi (P) dizisini sıkıştırılabilir hale getirir:

1. Her (k_i) ile üretilen rastgele konumlar.
2. Önce daha küçük pilot değerlerinin denenmesi.

Beklenen Pilot Değeri

(E[k_i]) ifadesi beklenen pilot değerini göstersin. Her (k_i), (K) kümesinden (v) değerini alan rastgele bir değişkendir ve bu olasılık bitmap (taken)’ın mevcut doluluk oranına, yani zaten dolu olan konumların oranına bağlıdır.

Tanımlayalım:

[ \alpha(i) = \frac{\sum_{j=0}^{i-1} |B_j|}{n} ]

(i = 1, \ldots, m-1) için ve (\alpha(0) = 0).

O halde (B_i)’nin tüm anahtarlarını çakışma olmadan yerleştirmenin başarı olasılığı yaklaşık olarak

[ p_i = (1 - \alpha(i))^{|B_i|} ]

şeklindedir.

(k_i) geometrik dağılım izlediğinden beklenen değer

[ E[k_i] = \frac{1}{p_i} - 1 = \left(\frac{1}{1 - \alpha(i)}\right)^{|B_i|} - 1. ]

Bu formül pilot (k_i) değerlerinin ortalama olarak genellikle küçük olduğunu gösterir. İlk bucket’lar küçük bir (\alpha(i)) doluluk oranına sahiptir ve bu da küçük pilot değerleri verir. Ayrıca bucket’ların azalan büyüklük sırasına göre işlenmesi, doluluk oranı büyüse bile pilot değerlerinin küçük kalmasına yardımcı olur.

(n) anahtar

[ m = \left\lceil \frac{c n}{\log_2 n} \right\rceil ]

sayısında eşit olmayan bucket’a bölündüğünden bucket büyüklüğü

[ 0 \le |B_i| \le \Theta\left(\frac{\log n}{c}\right) ]

koşulunu sağlar.

Bu durum pilot tablosu (P) için hem verimli bir arama süreci hem de iyi sıkıştırılabilirlik özellikleri sağlar.

Deneysel çalışmalar, formülle tahmin edilen ortalama deneme sayısının yapım sırasında ölçülen değerlerle yakından örtüştüğünü göstermektedir. Bucket’lar işlendikçe ve doluluk oranı arttıkça deneme sayısı büyüyebilir; ancak üs değeri (|B_i|) küçük olduğundan genellikle düşük kalır.

Son olarak, pilot değerlerinin dağılımı çarpık olduğundan pilot tablosu (P) iki parçaya ayrılabilir: front ve back. Bu ayrım daha verimli sıkıştırmaya olanak tanır. Front kısmı anahtarların yaklaşık %60’ını içerirken dizinin yalnızca %30’unu kaplar; bu nedenle burada daha hızlı kodlama şemaları kullanmak ve back kısmında daha alan verimli kodlamalar uygulamak avantaj sağlar. Bu bölme stratejisi hem sıkıştırmayı hem de arama performansını iyileştirir.

Bölüm 4’ün başında belirtilen iki hedeften ilkine — yani sıkıştırılabilir bir çıktı garanti eden bir algoritma tasarlamaya — ulaştığımıza göre, şimdi ikinci hedefe odaklanıyoruz: yalnızca 𝑃’nin düşük entropisinden yararlanmakla kalmayıp aynı zamanda belirgin arama performansını da koruyan bir kodlama şeması geliştirmek.

Anlatımı basitleştirmek için, şimdi 𝑃’nin front ve back parçalarına ayrılmadığı duruma odaklanalım (genelleme oldukça basittir). 𝑃 düşük entropiye sahip olduğundan, sözlük tabanlı bir kodlamanın amacımıza uygun olduğunu savunuyoruz: 𝑃’nin farklı değerlerini bir 𝐷 dizisinde, yani sözlükte toplarız ve 𝑃’yi 𝐷’nin girişlerine referanslardan oluşan bir dizi olarak temsil ederiz. 𝑟, 𝐷’nin boyutu olsun. 𝑟 değeri bucket sayısı 𝑚’den küçük veya ona eşit olduğundan ve 𝑚 de anahtar sayısı 𝑛’den küçük olduğundan, 𝑃’nin her girişini FCH’nin kullandığı (⌈log2 𝑛⌉ + 1) bit yerine ⌈log2 𝑟⌉ bit kullanarak temsil edebiliriz. Toplam alan kullanımı, 𝑚⌈log2 𝑟⌉ bit alan kaplayan kodlanmış 𝑃 ile sözlük 𝐷’nin alanının toplamıdır. İkincisinin maliyeti 𝑃’ye kıyasla küçüktür. Özellikle 𝑐 büyüdükçe bu maliyet daha da küçülür.

Kodlama süresi 𝑃’nin boyutunda doğrusaldır, yani Θ(𝑚)’dir; dolayısıyla toplam yapım süresinin küçük bir kısmını oluşturur. Özellikle Bölüm 5’te ele aldığımız tüm kodlama yöntemleri doğrusal zamanda çalışır.

Sözlük kullanıldığında 𝑓(𝑥) için algoritma aşağıdaki gibidir.

Teorem 1. 𝑛 anahtar ve 𝑐 > log2 𝑒 parametresi için aramanın beklenen süresi O(n^{1+Θ(1/𝑐)})’dir.

Formül (4)’ün net etkisi, 𝑃’nin düşük entropiye sahip olmasıdır. Tablo 1’de, farklı 𝑐 değerleri için 𝑃’nin 0. dereceden ampirik entropisini rapor ediyoruz. Özellikle 𝑃 dizisinin bizim yaklaşımımızla belirlenen pilotları sakladığı durum ile orijinal FCH prosedürüne göre belirlenen yer değiştirmeleri sakladığı durumu karşılaştırıyoruz. Beklendiği gibi pilotların entropisi yer değiştirmelerinkinden daha küçüktür ve 𝑐 arttıkça bu fark daha da büyür. Bu durum arama çıktısının çok iyi biçimde sıkıştırılabileceğini açıkça gösterir.

Şimdi bir adım daha ileri gidiyoruz.

Daha önce ortalama deneme sayısının özellikle ilk işlenen bucket’lar için oldukça küçük olduğunu fark etmiştik; bunun nedeni düşük doluluk oranıdır. Bu durum Şekil 2’de, örneğin ilk %30’luk bucket bölümüne bakıldığında grafiksel olarak açıkça görülür. Başka bir deyişle ilk işlenen bucket’ların pilot değerleri küçüktür. Şimdi bu bucket’ların 𝑃 dizisinin ilk 𝑝2 = 0.3𝑚 girişine karşılık geldiğini ve 𝑝1 = 0.6𝑛 anahtar içerdiğini savunuyoruz. Bu, anahtarların bucket’lara çarpık dağılımının ve bucket’ların işlenme sırasının doğrudan bir sonucudur. Dolayısıyla 𝑃’nin ön kısmı olan 𝑃[0..𝑝2 − 1], arka kısmı olan 𝑃[𝑝2..𝑚 − 1] ile karşılaştırıldığında daha düşük entropiye sahiptir.

Tablo 2, 𝑐 değerini değiştirerek ve 𝑛 = 10⁶ için front ve back dizilerinin entropisini göstermektedir. Görüldüğü gibi front kısmının entropisi back kısmına kıyasla çok daha küçüktür (ortalama olarak 2 kattan fazla).

FCH ile karşılaştırıldığında burada 1 yerine 2 bellek erişimi yapıldığını (𝑃 ve 𝐷 için) not etmek gerekir. Ancak 𝐷 küçük olduğundan, erişimin hedef makinenin önbellek belleğine — örneğin L2 hatta L1 — yönlendirilmesi muhtemeldir. Bu nedenle dolaylı erişim arama performansını yalnızca çok az etkiler; bunu Bölüm 5’te göstereceğiz.

Yaklaşımı 𝑃’nin front ve back parçalarına genellemek oldukça basittir: her parçanın kendi sözlüğü vardır ve bu dizilere her erişim sözde kodun 3. adımında gösterildiği şekilde gerçekleştirilir.

𝑃’yi sıkıştırmak için başka daha gelişmiş seçenekler de mümkündür; örneğin Elias–Fano [11, 14] veya Fredriksson ve Nikitin tarafından önerilen Simple Dense Coding (SDC) [17]. Bölüm 5’te göreceğimiz gibi, bu mekanizmaların kullanılması daha yavaş bir arama süresi pahasına daha üstün sıkıştırma etkinliği sağlayabilir.

Şimdiye kadar arama stratejisinin sıkıştırma etkinliği üzerindeki etkilerini inceledik; çünkü Bölüm 4’ün başında belirtildiği gibi sıkıştırılabilir bir çıktı, yapımı hızlandıran daha büyük bir 𝑐 değerinin kullanılmasını mümkün kılar. Bölüm 3’ün sonunda verilen somut örneği hatırlayalım: 𝑛 = 10⁸ adet 64‑bit anahtar ve 𝑐 = 3 için FCH bir MPHF’yi 1 saat 10 dakikada bulur (deneysel düzenimizin açıklaması için Bölüm 5’e bakınız). PTHash ise 𝑐 = 5.6 ve tanıtılan front–back kodlaması ile aynı alanı kullanarak, yani anahtar başına 3.0 bit tüketerek bir MPHF bulur. Ancak bunu 70 saniyede gerçekleştirir; yani FCH’den 60 kat daha hızlıdır. Bölüm 5’te daha büyük ve daha ayrıntılı deneyler sunacağız.

Şekil 3

𝑛 = 10⁹ anahtar ve 𝑐 = 9 için bucket’lar işlenirken harcanan arama süresi. Son %11’lik bucket’lar boştur.

Aslında 𝑝ᵢ ≥ 𝑛 konumlarına eşlenen ve bu boşlukları doldurabilecek |𝐿| adet anahtar vardır. Bu nedenle

free[0..𝑛′ − 𝑛 − 1]

dizisini somutlaştırırız; burada

free[𝑝ᵢ − 𝑛] = 𝐿[𝑖], her 𝑖 = 0, …, |𝐿| − 1 için geçerlidir.

free dizisi için ayrılan alanın, boyutu 𝑛′ − 𝑛 olan ve maksimum değeri 𝑛’den küçük olan sıralı bir tamsayı dizisinin alanı olduğunu unutmayın. Dolayısıyla özellikle Elias–Fano ile sıkıştırıldığında küçük bir alan kaplar, yani:

(𝑛′ − 𝑛)(⌈log2 (𝑛 / (𝑛′ − 𝑛))⌉ + 2 + 𝑜(1)) bit.

Açıklayıcı bir örneği ele alalım. Diyelim ki 𝑛 = 9 ve 𝑛′ = 14. 𝑛′ − 𝑛 = 14 − 9 = 5 adet boşluk vardır; bunlar örneğin [0, 2, 8, 9, 12] konumlarında olsun. 𝐿 dizisi [0, 2, 8]’dir (𝑛 = 9 konumuna kadar olan boşluklar). Dolayısıyla [0..8] aralığının dışına eşlenen |𝐿| = 3 anahtar olacaktır ve bunlar [10, 11, 13] konumlarında olmalıdır. Daha sonra şu atamaları yaparız:

• free[10 − 9] = 𝐿[0]
• free[11 − 9] = 𝐿[1]
• free[13 − 9] = 𝐿[2]

Bunun sonucunda nihai free[0..4] = [*, 0, 2, *, 8] elde edilir; burada * atanmış olmayan bir değeri gösterir.

free dizisi ile 𝑓(𝑥) algoritması aşağıdaki gibidir.

4.4 Yük Faktörünü Sınırlandırma

Formül (4)’e göre, arama süresi aramanın sonuna doğru kayma gösterir; çünkü 𝛼 → 1 olurken beklenen deneme sayısı hızla artar. Bu olgu, büyük 𝑐 değerleri kullanıldığında daha da belirgin hale gelir; çünkü büyük bir 𝑐 değeri, Formül (4)’teki |𝐵ᵢ| üssünü düşürerek kovaların çoğu için beklenen deneme sayısını azaltır. Özellikle daha büyük 𝑐 değerlerinde zamanın küçük bir kısmı anahtarların çoğuna harcanırken, büyük bir kısmı yalnızca az sayıda anahtar içeren son kovalar için harcanır — dağılımın ağır “kuyruğu”.

Şekil 3, 𝑛 = 10⁹ anahtar ve 𝑐 = 9 için böyle bir dağılım örneğini gösterir. İşlenen kovaların %85’inden sonra sona doğru yüksek çarpıklığa dikkat edin: toplam arama süresinin %40’ından fazlası, boş olmayan son kovaların %5’ine düşen anahtarların yalnızca %1.4’ü için harcanmaktadır.

Ağır kuyruğun yükünden kaçınmak için 𝑓 fonksiyonunu daha büyük bir uzayda ararız; örneğin seçilmiş bir maksimum yük faktörü 0 < 𝛼 ≤ 1 için [𝑛′ = 𝑛 / 𝛼]. Örneğin 𝛼 = 0.99 ise 𝑓’i aramak için %1 ek alan kullanılır. Elde edilebilecek maksimum yük faktörünü sınırlamak, Formül (4)’e göre E[𝑘ᵢ] değerinin azalmasıyla birlikte hem arama süresini düşürür hem de sıkıştırma etkinliğini etkiler. Aslında genel bir 0 < 𝛼 ≤ 1 için, kanıtı yer kısıtları nedeniyle verilmemiş olan aşağıdaki daha genel sonucu elde ederiz.

Teorem 2. 𝑛 anahtar ve 𝑐 > log2 𝑒 ile 0 < 𝛼 ≤ 1 parametreleri için aramanın beklenen süresi O(n^{1+Θ(𝛼/𝑐)})’dir.

Şimdi, boyutu 𝑛′ = 𝑛 / 𝛼 > 𝑛 olan bir uzayda arama yapmanın sorunu, 𝑓 çıktısının minimal olmasının garanti edilmesi gerektiğidir; yani değer [𝑛] aralığında olmalıdır, [𝑛′] aralığında değil. Bu strateji, 𝑓’in kodomaini olan [𝑛] içinde bazı “boşluklar” bırakması ve bunların daha sonra uygun bir şekilde doldurulması gerektiği şeklinde düşünülebilir.

𝐿’nin 𝑛 − 1 konumuna kadar olan boşlukların listesi olduğunu varsayalım.

𝑓(𝑥) için algoritma

1. 𝑖 = bucket(𝑥)
2. 𝑘ᵢ = 𝑃[𝑖]
3. 𝑝 = (ℎ(𝑥, 𝑠) ⊕ ℎ(𝑘ᵢ, 𝑠)) mod 𝑛′

Koşulun ikinci dalı (else) rastgele sorgular için yaklaşık ≈ (1 − 𝛼) olasılıkla çalıştırılır. Eğer 𝛼 değeri 1.0’a yakın seçilirse, örneğin 0.99, bu dal oldukça öngörülebilir olur ve dolayısıyla arama performansını neredeyse hiç etkilemez.

Yaklaşımımız, kodomain [𝑛] dışındaki her anahtarın tek bir dizi erişimi ile, yani free dizisine erişilerek uygun konuma geri eşlenmesini garanti eder. Bölüm 5’te göstereceğimiz gibi, bu yöntem free dizisini [𝑛′] aralığındaki tüm kullanılabilir boş konumlarla doldurma şeklindeki yaygın stratejiden önemli ölçüde daha hızlıdır. Çünkü o durumda sözde kodun 3. adımında döndürülen her 𝑝 konumu için free üzerinde bir ardıl (successor) sorgusu yapılması gerekir.

Son olarak, algoritma rastgele erişimi destekleyen 𝑃’nin herhangi bir sıkıştırılmış gösterimine doğrudan uygulanabilir; örneğin önceki bölümlerde açıkladığımız sözlük tabanlı kodlama ile front–back düzeni.

Deneysel Değerlendirme

Bu bölümde PTHash’in kapsamlı bir deneysel değerlendirmesini sunuyoruz. Tüm deneyler Intel i9‑9900K çekirdekleri (@3.60 GHz), 64 GB RAM DDR3 (@2.66 GHz) ile donatılmış ve Linux 5 (64 bit) çalıştıran bir sunucu makinede gerçekleştirildi.

Her çekirdeğin iki özel önbellek seviyesi vardır:

• 32 KiB L1 önbellek (biri komutlar, biri veriler için)
• 256 KiB L2 önbellek

Paylaşılan bir L3 önbellek 16,384 KiB büyüklüğündedir.

Hem oluşturma hem de arama algoritmaları işlemcinin tek bir çekirdeğinde çalıştırıldı ve veriler tamamen dahili bellekte bulundu. PTHash’in uygulaması C++ ile yazılmıştır ve şu adreste mevcuttur:

https://github.com/jermp/pthash

Kod, gcc 9.2.1 ile -O3 ve -march=native iyileştirme bayrakları kullanılarak derlenmiştir.

Arama süresi, girdideki her bir anahtarın tek tek aranması ve 5 çalıştırma arasındaki ortalama sürenin alınmasıyla ölçüldü. Oluşturma süresi için ise 3 çalıştırmanın ortalamasını raporluyoruz.

MPHF’leri girdi olarak rastgele tamsayılar kullanarak oluşturuyoruz; çünkü veri yapılarının kapladığı alan açısından verinin doğası tamamen önemsiz olduğundan, karma tabanlı algoritmalar için kıyaslama yaparken bu yaygın bir uygulamadır [12, 13, 20, 23, 27]. Bizim durumumuzda [0, 2⁶⁴) aralığında eşit dağılımla rastgele 𝑛 adet 64 bit tamsayı ürettik.

Sonuçlarımızı daha da doğrulamak için PTHash’i gerçek dünya metin koleksiyonları üzerinde de değerlendireceğiz.

Sıkıştırma Etkinliği

Tablo 3a’da, 𝛼 = 1.0 için PTHash’in farklı kodlama şemaları altında oluşturma süresi, arama süresi ve bit/anahtar oranı açısından performansını raporluyoruz.

Bu kodlamaları belirtmek için kullanılan adlandırmayı açıklayalım:

• C, compact anlamına gelir ve 𝑃’deki her değerin ⌈log2(max(𝑃) + 1)⌉ bit ile kodlanmasını ifade eder (FCH’nin bu tekniği kullandığını ve max(𝑃) = 𝑛 varsayımını yaptığını unutmayın).
• D, Bölüm 4.3’te açıklanan sözlük tabanlı yöntemi gösterir.
• EF, Elias–Fano [11, 14] anlamına gelir.
• SDC, Simple Dense Coding [17] anlamına gelir.

X–Y ile gösterilen yöntemler, Bölüm 4.2’deki front–back sıkıştırma stratejisini ifade eder; burada X ön kısım için, Y ise arka kısım için kullanılan yöntemdir.

Tablo 3a elde edilebilen ödünleşimlerin (trade-off) yelpazesini vurgular:

• Yukarıdan aşağıya doğru 𝑐 artırılarak oluşturma süresi iyileştirilir.
• Soldan sağa doğru alan verimliliği artar ancak arama verimliliği azalır.

Oluşturma süresinin eşleme, sıralama, arama ve kodlama sürelerini içerdiğini hatırlatalım. En çok zaman alan adım aramadır; özellikle 𝑐 küçük olduğunda.

Tablo 3’te raporlanan deney için:

• eşleme + sıralama 105 saniye sürdü
• kodlama süresi 𝑐 değerinin 6’dan 11’e değişmesine bağlı olarak 10 ile 15 saniye arasında değişti

Geri kalan tüm süre arama adımında harcanmaktadır.

Ayrıca şu gözlemleri yapıyoruz:

• Front–back sıkıştırma fayda sağlar, çünkü her zaman alan verimliliğini artırır. Örneğin C‑C ve D‑D, sırasıyla C ve D’den daha kompakt olup göreli arama verimliliklerini korur.
• D ve D‑D her zaman C ve C‑C’den daha kompakt olup arama süresini yalnızca küçük ölçüde etkiler (𝑛 = 10⁹ için ortalama +12 ns/anahtar, ancak daha küçük 𝑛 değerleri için daha az). Bu durum, Bölüm 4.3’te açıklandığı gibi sözlük tabanlı kodlamanın iyi bir eşleşme olduğunu doğrular.

PTHash Ayarlama

Bu bölümde PTHash’i ayarlamaya odaklanıyoruz; aşağıdakilerin etkisini nicel olarak inceliyoruz:

• (i) MPHF veri yapısını temsil etmek için farklı kodlama şemaları,
• (ii) front‑back sıkıştırma ve
• (iii) yük faktörünün değiştirilmesi.

Tablo 4

n = 10^8 rastgele 64 bit anahtar için FCH performansı ve bazı bit/anahtar oranları. Karşılaştırma için ayrıca α = 0.99 ve C, D-D ve D-EF kodlamaları ile PTHash performansı da verilmiştir.

2.50 — 614 173 44

3.00 4286 62 (69×) 37 (116×) 22 (195×)

3.50 985 29 (34×) 27 (36×) 20 (49×)

4.00 463 25 (18×) 22 (21×) 20 (23×)

4.50 340 22 (15×) 20 (17×) 20 (17×)

5.00 145 21 (7×) 20 (7×) 20 (7×)

lookup (ns/key): 30 28 35 55

• EF ve SDC alan verimliliği açısından daha uygundur ancak D-D ile karşılaştırıldığında aramada 1.5–3× daha yavaştır.
• D-EF yapılandırması D-D ile EF arasında bir ödünleşim konumundadır; arka kısımda EF kullanılması alanı iyileştirir ancak aramayı yavaşlatır.

Yük Faktörünü Değiştirme

Bölüm 4.4’te α değerini değiştirmenin oluşturma süresi ile arama verimliliği arasında bir ödünleşim sağladığını açıklamıştık. Şekil 4, α değerinin 0.80’den 1.00’a kadar 0.01 adımıyla değiştirilmesi durumunda bu ödünleşimin görsel bir örneğini göstermektedir.

• Oluşturma süresi özellikle α ∈ [0.9, 1.0] aralığında önemli ölçüde azalır. Özellikle α = 1.0’dan α = 0.99’a geçerken görülen keskin düşüşe dikkat edin; bunun nedeni Şekil 3’te gözlenen ağır “kuyruk” etkisinden kaçınılmasıdır.
• Buna karşılık arama süresi α azaldıkça artar, ancak Bölüm 4.4’te açıklanan hızlı yeniden sıralama mekanizması sayesinde bu artış çok daha yavaş gerçekleşir ve fonksiyon çıktısının minimal olması garanti edilir.

Gerçekten de, örneğin α = 1.0’dan α = 0.94’e geçerken 2× daha hızlı oluşturma elde ederken arama süresi yalnızca 6 ns/anahtar artar. Şekil 4’te görülen spektrumun diğer ucunda ise α = 0.80 kullanırsak 3× daha hızlı oluşturma elde ederiz ancak aramada yaklaşık ≈22 ns/anahtar daha fazla maliyet oluşur.

• Bir diğer önemli avantaj ise daha düşük bir yük faktörü kullanmanın daha fazla alan tüketmemesi, hatta Bölüm 4.4’te açıklanan nedenlerle daha da az alan kullanmasıdır.

Şekil 4’te MPHF’in toplam alanını ve yalnızca pilot tablosu P tarafından kullanılan alanı gösteriyoruz. α < 1.0 olduğunda toplam alan, P’nin kapladığı alan ile Bölüm 4.4’te açıklandığı gibi Elias‑Fano ile sıkıştırdığımız free dizisinin alanının toplamıdır.

Tablo 3b’de Tablo 3a’daki aynı deneyin α = 0.99 yük faktörü ile elde edilen sonuçlarını raporluyoruz. Karşılaştırmayı daha net göstermek için tablolar yan yana sunulmuştur. Şekil 4’te de belirtildiği gibi, arama için yalnızca %1 ek alan kullanmak bile her kodlama yöntemi ve her c değeri için önemli avantajlar sağlar:

• (i) %25–35 daha düşük oluşturma süresi
• (ii) daha az alan kullanımı (özellikle C ve D kodlamaları için dikkat çekici iyileşmeler)
• (iii) arama verimliliğinin korunması

Aramayı Hızlandırma

Bu bölümdeki son deney olarak Tablo 4, aynı nihai bit/anahtar oranları için bazı PTHash yapılandırmalarının FCH oluşturma süresine göre elde ettiği hızlanma katsayılarını göstermektedir. PTHash için basit C kodlaması kullanılsa bile, eşit (veya daha iyi) arama verimliliği ile 7–69× daha hızlı oluşturma elde edilir. Tablonun sağ tarafına doğru gidildikçe oluşturma süresinde ek avantajlar elde edilir ancak bunun karşılığında aramada bir ceza ortaya çıkar.

Tablo 5

64 bit rastgele anahtarlar için çeşitli yöntemlerin oluşturma süresi, alan kullanımı ve arama süresi.

5.2 Genel Karşılaştırma

Bu bölümde PTHash’i Bölüm 2’de incelenen en gelişmiş tekniklerle karşılaştırıyoruz.

• FCH [15] — Orijinal makaleye sadık kalınarak (C++ ile) yeniden uygulanan tek algoritmadır. Algoritma, diğer yöntemlerin elde ettiği bit/anahtar oranı aralığını neredeyse kapsamak için c = 3, …, 7 değerleri ile test edilmiştir.
• CHD [4] — λ = 4, 5, 6 parametreleri ile test edilmiştir. Önceki çalışmalarda da belirtildiği gibi [12], λ = 7 değeri birkaç bin anahtardan fazlası için kullanılamamıştır.
• EMPHF [2] — Rastgele hiper-grafların soyulmasına (peeling) dayanan yöntemin verimli bir uygulamasıdır. Kütüphane harici belleği de hedefleyebilse de algoritma dahili bellekte çalıştırılmıştır.
• GOV [18,19] — Gauss elemesi kullanılarak rastgele doğrusal sistemlerin çözülmesine dayanan bir yöntemdir.
• BBHash [23] — Orijinal makalede önerildiği gibi γ = 1, 2, 5 parametreleri ile test edilmiştir. Oluşturma işlemi çok iş parçacıklı çalışabilir ancak adil bir karşılaştırma için tek iş parçacığı kullanılmıştır.
• RecSplit [12] — Oluşturma süresi ile alan verimliliği arasında farklı ödünleşimler sunmak amacıyla yazarların makalelerinde kullandıkları aynı yapılandırmalarla test edilmiştir.

Yukarıdaki tüm yöntemler için orijinal yazarların sağladığı kaynak kodları kullandık (ilgili GitHub depoları için Kaynaklar bölümüne bakınız) ve bir kıyaslama ortamı kurduk.

Popüler CMPH kütüphanesi FCH’nin bir uygulamasını içerir; ancak bu uygulama bizim uygulamamızdan büyüklük mertebeleri kadar daha yavaş olduğu için kullanılamamıştır.

Tüm uygulamalar C/C++ ile yazılmıştır; yalnızca GOV yönteminin oluşturma kısmı Java’da mevcuttur.

Tablo 5’teki sonuçlar, yakın zamanda yayımlanan çalışmaların raporladığı sonuçlarla güçlü biçimde tutarlıdır [12, 23]. PTHash için mümkün olan birçok yapılandırma arasından aşağıdaki dört tanesini özellikle öne çıkarıyoruz.

• (i) Arama süresini optimize etme — C-C kodlaması, α = 0.99, c = 7. Bu yapılandırmada PTHash, FCH ile aynı arama süresine ulaşırken çok daha iyi sıkıştırılmış bir alan kullanır. Alan açısından γ = 1, 2 olan BBHash’e benzer ancak aramada 3–4.5× daha hızlıdır. Daha fazla alan verimliliği sunan diğer yöntemlerle karşılaştırıldığında PTHash 0.5–1 bit/anahtar daha büyük yer kaplar fakat aramada 5.4–11× daha hızlıdır.

• (ii) Oluşturma süresini optimize etme — D-D kodlaması, α = 0.88, c = 11. Bu yapılandırma, PTHash’in daha yüksek alan kullanımı pahasına oluşturma süresi açısından diğer tekniklerin çoğuyla rekabet edebildiğini gösterir. Bununla birlikte arama performansı en az 2× daha iyidir.

• (iii) Alan verimliliğini optimize etme — EF kodlaması, α = 0.99, c = 6. Bu yapılandırmada PTHash, en özlü yöntemler (CHD ve RecSplit) ile karşılaştırılabilir alan verimliliğine ulaşırken aramada bu yöntemlerden hâlâ 2–4× daha hızlıdır.

• (iv) Genel ödünleşimi optimize etme — D-D kodlaması, α = 0.94, c = 7. Bu yapılandırma diğer üç yapılandırma arasında bir denge kurmayı amaçlar; iyi bir alan verimliliği ve oluşturma süresi ile birlikte çok hızlı arama değerlendirmesi sunar.

Tablo 5’ten çıkan açık sonuç şudur: PTHash’in, başka bir yönteme benzer alan kullanan fakat belirgin biçimde daha iyi arama performansı sağlayan ve uygulanabilir ya da daha iyi oluşturma hızına sahip bir yapılandırması bulunmaktadır.

5.3 Değişken Uzunluklu Anahtarlar Üzerinde Performans

Bu bölümde, değişken uzunluklu anahtarlardan oluşan gerçek dünya veri kümeleri üzerinde PTHash'i değerlendiriyoruz. Doğal dil q-gramlarını kullandık çünkü bunlar IR, NLP ve makine öğrenimi uygulamalarında yaygın biçimde kullanılmaktadır; URL'ler ise ortalama uzunluklarının çok fazla olması nedeniyle bir tür “en kötü durum” girdisini temsil etmeleri bakımından ilgi çekicidir.

Daha ayrıntılı olarak şunları kullandık:

• English GoogleBooks (version 2) derleminden 24,357,349 ve 665,752,080 giriş içeren sırasıyla 1-gram ve 2-gramlar
• ClueWeb09 (Category B) veri kümesinden yaklaşık 50 milyon Web sayfasına ait URL'ler
• .uk alan adına ilişkin olarak 2005 yılında UbiCrawler tarafından toplanan URL'ler

Bunlar sırasıyla toplam 49,937,704 ve 39,459,925 URL'ye karşılık gelmektedir.

MPHF veri yapısının alan kullanımı verinin doğasından bağımsız olsa da, sabit boyutlu 64 bit anahtarlara kıyasla kurulum ve arama süresindeki farkı vurgulamak için ortalama anahtar boyutu giderek artan veri kümelerini seçtik.

PTHash'in kurulum sırasında her bir giriş anahtarını yalnızca bir kez (anahtarları kovalar arasında dağıtmak için) ve her aramada da bir kez karma işleminden geçirdiğini hatırlayın. Bu nedenle zaman ölçümlerinin anahtar başına sabit bir miktar kadar artmasını bekleriz; bu artış, uzun bir anahtarın karma işlemi ile 64 bitlik bir anahtarın karma işlemi arasındaki farkı yansıtır.

Tablo 6

Dize koleksiyonları üzerinde PTHash'in kurulum süresi, alan kullanımı ve arama süresi. Karşılaştırma amacıyla 64 bit (sabit uzunluklu) rastgele anahtarlar üzerindeki performans da verilmiştir. Kullanılan yapılandırma: (iv) D-D, α = 0.94, c = 7.

Alan verimliliği, gerçek dünya veri kümeleri ile rastgele anahtarlar arasında değişmemektedir. Kurulum süresi de özünde değişmeden kalır çünkü karma işlemi ek yükü (anahtar başına nanosaniyeler) saniyeler süren bir sürece kıyasla ihmal edilebilir düzeydedir.

Buna karşılık arama süresi anahtar uzunluğuyla orantılı olarak artar; bu durum, PTHash'in arama süresinin büyük bölümüne karma işleminin katkıda bulunduğunu göstermektedir. Daha ayrıntılı olarak:

• q-gram veri kümelerinde 1.3–2× daha uzun anahtarlar için +6–9 ns/anahtar
• URL'lerde 7–9× daha uzun anahtarlar için +25–26 ns/anahtar

Bu artışlar, daha uzun anahtarların karma işleminden geçirilmesinin etkisini, kodlama şemasından ve veri kümesi boyutundan bağımsız olarak göstermektedir.

Bölüm 5.2'de test edilen diğer yöntemler de, her arama başına bir kez karma işlemi yapanlarda (PTHash gibi) benzer artışlar veya her arama başına birkaç kez karma işlemi yapanlarda (örneğin BBHash) daha büyük performans cezaları göstermektedir.

Sonuç

PTHash'i sunduk; bu algoritma, kompakt alan kullanımıyla minimal perfect hash fonksiyonları oluştururken aynı zamanda mükemmel arama performansını korur. Bu sonuç, Fox, Chen ve Heath (FCH) tarafından 1992 yılında tanıtılan çerçevenin dikkatli biçimde yeniden ele alınmasıyla elde edilmiştir.

Kapsamlı deneysel değerlendirme, PTHash'in önceki en ileri seviye algoritmalarla özünde aynı alanı kullandığını ancak 2–4× daha iyi arama süresi sağladığını göstermektedir. Alan verimliliği önemli olmaya devam etse de, minimal perfect hashing problemi ve uygulamaları için verimli arama süresi daha da kritik öneme sahiptir.

C++ uygulamamız, PTHash kullanımını teşvik etmek ve problem üzerine daha fazla araştırmayı hızlandırmak amacıyla herkese açık olarak sunulmuştur.

Gelecekteki çalışmalar şunları içermektedir:

• paralel ve harici bellek kullanarak kurulum (örneğin girdiyi parçalara ayırıp her parça üzerinde bağımsız bir MPHF oluşturmak)
• daha özlü kodlamalar
• perfect (minimal olmayan) ve k-perfect hash fonksiyonları gibi diğer fonksiyon türlerine genişletmeler

Bu çalışma kısmen MobiDataLab (EU H2020 RIA, hibe anlaşması No. 101006879) ve OK-INSAID (MIUR-PON 2018, hibe anlaşması No. ARS01_00917) projeleri tarafından desteklenmiştir.

Kaynaklar

[1] Austin Appleby. 2016. SMHasher. https://github.com/aappleby/smhasher.

[2] Djamal Belazzougui, Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini ve Sebastiano Vigna. 2014. Rastgele hiper grafiklerin cache-oblivious soyulması. 2014 Data Compression Conference içinde. IEEE, 352–361. https://github.com/ot/emphf

[3] Djamal Belazzougui, Paolo Boldi, Rasmus Pagh ve Sebastiano Vigna. 2010. Az alan kullanarak hızlı önek arama ve uygulamaları. European Symposium on Algorithms içinde. Springer, 427–438.

[4] Djamal Belazzougui, Fabiano C. Botelho ve Martin Dietzfelbinger. 2009. Hash, displace ve compress. European Symposium on Algorithms içinde. Springer, 682–693. https://github.com/bonitao/cmph

[5] Djamal Belazzougui ve Gonzalo Navarro. 2014. Alfabe bağımsız sıkıştırılmış metin indeksleme. ACM Transactions on Algorithms (TALG) 10, 4 (2014), 1–19.

[6] Paolo Boldi, Bruno Codenotti, Massimo Santini ve Sebastiano Vigna. 2004. Ubicrawler: Ölçeklenebilir tamamen dağıtık bir web tarayıcısı. Software: Practice and Experience 34, 8 (2004), 711–726.

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

[8] Andrei Broder ve Michael Mitzenmacher. 2004. Bloom filtrelerinin ağ uygulamaları: Bir inceleme. Internet Mathematics 1, 4 (2004), 485–509.

[9] Chin-Chen Chang ve Chih-Yang Lin. 2005. Birliktelik kurallarının madenciliği için perfect hashing şemaları. Computer Journal 48, 2 (2005), 168–179.

[10] Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld ve Ayellet Tal. 2004. Bloomier filter: statik destek arama tabloları için verimli bir veri yapısı. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms içinde. Citeseer, 30–39.

[11] Peter Elias. 1974. Statik dosyaların içerik ve adres üzerinden verimli depolanması ve geri alınması. Journal of the ACM (JACM) 21, 2 (1974), 246–260.

[12] Emmanuel Esposito, Thomas Mueller Graf ve Sebastiano Vigna. 2020. Recsplit: Özyinelemeli bölme yoluyla minimal perfect hashing. Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX) içinde. SIAM, 175–185. https://github.com/vigna/sux

[13] Bin Fan, Dave G. Andersen, Michael Kaminsky ve Michael D. Mitzenmacher. 2014. Cuckoo filter: pratikte bloom'dan daha iyi. Proceedings of the 10th ACM International Conference on Emerging Networking Experiments and Technologies içinde. 75–88.

[14] Robert Mario Fano. 1971. Bir ilişkisel belleğin uygulanması için gereken bit sayısı üzerine. Memorandum 61, Computer Structures Group, MIT (1971).

[15] Edward A. Fox, Qi Fan Chen ve Lenwood S. Heath. 1992. Minimal perfect hash fonksiyonları oluşturmak için daha hızlı bir algoritma. Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval içinde. 266–273.

[16] Michael L. Fredman, János Komlós ve Endre Szemerédi. 1984. En kötü durumda O(1) erişim süresine sahip seyrek bir tablonun depolanması. Journal of the ACM (JACM) 31, 3 (1984), 538–544.

[17] Kimmo Fredriksson ve Fedor Nikitin. 2007. Rastgele erişimi ve hızlı dize eşleştirmeyi destekleyen basit bir sıkıştırma kodu. International Workshop on Experimental and Efficient Algorithms içinde. Springer, 203–216.

[18] Marco Genuzio, Giuseppe Ottaviano ve Sebastiano Vigna. 2016. (Minimal perfect hash) fonksiyonlarının hızlı ve ölçeklenebilir oluşturulması. International Symposium on Experimental Algorithms içinde. Springer, 339–352. https://github.com/vigna/Sux4J

[19] Marco Genuzio, Giuseppe Ottaviano ve Sebastiano Vigna. 2020. ([compressed] static | minimal perfect hash) fonksiyonlarının hızlı ve ölçeklenebilir oluşturulması. Information and Computation (2020), 104517.

[20] Thomas Mueller Graf ve Daniel Lemire. 2020. Xor filtreleri: bloom ve cuckoo filtrelerinden daha hızlı ve daha küçük. Journal of Experimental Algorithmics (JEA) 25 (2020), 1–16.

[21] Torben Hagerup ve Torsten Tholey. 2001. Neredeyse minimal alanda verimli minimal perfect hashing. Annual Symposium on Theoretical Aspects of Computer Science içinde. Springer, 317–326.

[22] Guy Jacobson. 1989. Alan açısından verimli statik ağaçlar ve grafikler. 30th Annual Symposium on Foundations of Computer Science içinde. IEEE Computer Society, 549–554.

[23] Antoine Limasset, Guillaume Rizk, Rayan Chikhi ve Pierre Peterlongo. 2017. Devasa anahtar kümeleri için hızlı ve ölçeklenebilir minimal perfect hashing. 16th International Symposium on Experimental Algorithms, Cilt 11 içinde, 1–11. https://github.com/rizkg/BBHash

[24] Yi Lu, Balaji Prabhakar ve Flavio Bonomi. 2006. Ağ uygulamaları için perfect hashing. 2006 IEEE International Symposium on Information Theory içinde. IEEE, 2774–2778.

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

[26] Kurt Mehlhorn. 1982. Perfect ve universal hash fonksiyonlarının program boyutu üzerine. 23rd Annual Symposium on Foundations of Computer Science içinde. IEEE, 170–175.

[27] Ingo Müller, Peter Sanders, Robert Schulze ve Wei Zhou. 2014. Parmak izi kullanarak retrieval ve perfect hashing. International Symposium on Experimental Algorithms içinde. Springer, 138–149.

[28] Gonzalo Navarro. 2016. Compact Data Structures: A Practical Approach. Cambridge University Press.

[29] Rasmus Pagh. 1999. Hash and displace: minimal perfect hash fonksiyonlarının verimli değerlendirilmesi. Workshop on Algorithms and Data Structures içinde. Springer, 49–54.

[30] Giulio Ermanno Pibiri ve Rossano Venturini. 2017. Devasa n-gram veri kümeleri için verimli veri yapıları. Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval içinde. 615–624.

[31] Giulio Ermanno Pibiri ve Rossano Venturini. 2019. Devasa n-gram veri kümelerinin verimli biçimde işlenmesi. ACM Transactions on Information Systems (TOIS) 37, 2 (2019), 25:1–25:41.

[32] Robert Endre Tarjan ve Andrew Chi-Chih Yao. 1979. Seyrek bir tablonun depolanması. Communications of the ACM 22, 11 (1979), 606–611.