2025-11-25T13:49:17.496621

PHast -- Perfect Hashing made fast

Beling, Sanders
Perfect hash functions give unique "names" to arbitrary keys requiring only a few bits per key. This is an essential building block in applications like static hash tables, databases, or bioinformatics. This paper introduces the PHast approach that combines the fastest available queries, very fast construction, and good space consumption (below 2 bits per key). PHast improves bucket-placement which first hashes each key k to a bucket, and then looks for the bucket seed s such that a placement function maps pairs (s,k) in a collision-free way. PHast can use small-range hash functions with linear mapping, fixed-width encoding of seeds, and parallel construction. This is achieved using small overlapping slices of allowed values and bumping to handle unsuccessful seed assignment. A variant we called PHast+ uses additive placement, which enables bit-parallel seed searching, speeding up the construction by an order of magnitude.
academic

PHast -- নিখুঁত হ্যাশিং দ্রুত করা

মৌলিক তথ্য

  • পেপার আইডি: 2504.17918
  • শিরোনাম: PHast -- নিখুঁত হ্যাশিং দ্রুত করা
  • লেখক: Piotr Beling (লোডজ বিশ্ববিদ্যালয়, পোল্যান্ড), Peter Sanders (কার্লসরুহে প্রযুক্তি প্রতিষ্ঠান, জার্মানি)
  • শ্রেণীবিভাগ: cs.DS cs.DB cs.PF
  • প্রকাশনার সময়: ২০২৫ সালের অক্টোবর ২২ (arXiv সংস্করণ)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2504.17918

সারসংক্ষেপ

নিখুঁত হ্যাশ ফাংশন নির্বিচারে কীগুলিকে অনন্য "নাম" প্রদান করে, প্রতি কী মাত্র কয়েকটি বিট প্রয়োজন। এটি স্ট্যাটিক হ্যাশ টেবিল, ডাটাবেস বা বায়োইনফরম্যাটিক্সের মতো অ্যাপ্লিকেশনে একটি অপরিহার্য উপাদান। এই পেপারটি PHast পদ্ধতি উপস্থাপন করে যা দ্রুততম উপলব্ধ প্রশ্নোত্তর, অত্যন্ত দ্রুত নির্মাণ এবং ভাল স্থান খরচ (প্রতি কী ২ বিটের নিচে) একত্রিত করে। PHast বাকেট-প্লেসমেন্ট উন্নত করে যা প্রথমে প্রতিটি কী k কে একটি বাকেটে হ্যাশ করে, তারপর বাকেট সিড s খুঁজে বের করে যাতে একটি প্লেসমেন্ট ফাংশন (s,k) জোড়গুলিকে সংঘর্ষ-মুক্ত উপায়ে ম্যাপ করে। PHast ছোট-পরিসর হ্যাশ ফাংশন, রৈখিক ম্যাপিং, বীজের নির্ধারিত-প্রস্থ এনকোডিং এবং সমান্তরাল নির্মাণ ব্যবহার করতে পারে। এটি অনুমতিপ্রাপ্ত মানগুলির ছোট ওভারল্যাপিং স্লাইস এবং অসফল বীজ নিয়োগ পরিচালনার জন্য বাম্পিং ব্যবহার করে অর্জিত হয়। PHast+ নামক একটি রূপান্তর যোগজ প্লেসমেন্ট ব্যবহার করে, যা বিট-সমান্তরাল বীজ অনুসন্ধান সক্ষম করে, নির্মাণকে একটি মাত্রার দ্বারা ত্বরান্বিত করে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার সংজ্ঞা

নিখুঁত হ্যাশ ফাংশন (PHF) একটি ফাংশন যা কী সেট {k₁, ..., kₙ} কে {0, ..., m-1} এ ম্যাপ করে। যখন m = n হয়, এটি ন্যূনতম নিখুঁত হ্যাশ ফাংশন (MPHF) বলা হয়। এটি ডাটাবেস, পাঠ্য সূচক এবং জৈব তথ্যবিজ্ঞান প্রয়োগের জন্য একটি গুরুত্বপূর্ণ নির্মাণ ব্লক।

গবেষণা প্রেরণা

  1. বহু-উদ্দেশ্য অপ্টিমাইজেশন চ্যালেঞ্জ: MPHF ডিজাইন স্থান খরচ, নির্মাণ সময় এবং প্রশ্নোত্তর সময়ের বহু-উদ্দেশ্য অপ্টিমাইজেশনের সম্মুখীন হয়
  2. তাত্ত্বিক নিম্ন সীমা: MPHF এর তাত্ত্বিক নিম্ন সীমা log₂ e ≈ 1.44 বিট প্রতি কী
  3. ব্যবহারিক চাহিদা: অনুশীলনে, PHF সাধারণত স্ট্যাটিক ডেটা কাঠামো ত্বরান্বিত করতে ব্যবহৃত হয়, তাই দ্রুত প্রশ্নোত্তর অত্যন্ত গুরুত্বপূর্ণ

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

  1. বাকেট প্লেসমেন্ট পদ্ধতি: CHD, FCH, PTHash, PHOBIC ইত্যাদি অ-রৈখিক বাকেট বরাদ্দ ফাংশন বা পরিবর্তনশীল-দৈর্ঘ্য বীজ এনকোডিং প্রয়োজন, যা প্রশ্নোত্তর গতি প্রভাবিত করে
  2. পুনরাবৃত্তিমূলক বিভাজন পদ্ধতি: যদিও স্থান দক্ষতা উচ্চ, কিন্তু প্রশ্নোত্তর সময় ধীর, পরিবর্তনশীল-দৈর্ঘ্য নেভিগেশন তথ্য ডিকোড করার প্রয়োজন
  3. ফিঙ্গারপ্রিন্ট পদ্ধতি: কমপক্ষে e বিট প্রতি কী প্রয়োজন, এবং প্রশ্নোত্তরের জন্য বিট ভেক্টরের র্যাঙ্ক অপারেশন প্রয়োজন
  4. সমান্তরাল নির্মাণ ওভারহেড: বিদ্যমান পদ্ধতির সমান্তরাল নির্মাণের জন্য অফসেট মান পুনরুদ্ধার করতে অতিরিক্ত প্রশ্নোত্তর পদক্ষেপ প্রয়োজন

মূল অবদান

  1. রৈখিক বাকেট ম্যাপিং: ছোট ওভারল্যাপিং স্লাইসে রৈখিক ম্যাপিংয়ের মাধ্যমে অ-রৈখিক বাকেট বরাদ্দ এড়িয়ে, ক্যাশ-বান্ধব মাল্টি-থ্রেডেড নির্মাণ বাস্তবায়ন করা
  2. বাম্পিং মেকানিজম: ছোট-পরিসর হ্যাশ ফাংশন এবং নির্ধারিত-প্রস্থ বীজ এনকোডিং ব্যবহার করতে অনুমতি দেয়, জটিল স্থানীয় অনুসন্ধান এড়ায়
  3. অনুমানমূলক বীজ বরাদ্দ: ন্যূনতম ফাংশন মান দখল করে এমন বীজ নির্বাচন করে স্থান খরচ হ্রাস করা
  4. PHast+ রূপান্তর: যোগজ প্লেসমেন্ট ফাংশন ব্যবহার করে বিট-সমান্তরাল বীজ অনুসন্ধান বাস্তবায়ন করা, নির্মাণ গতি একটি মাত্রার দ্বারা উন্নত করা
  5. ব্যাপক পরীক্ষামূলক মূল্যায়ন: বিদ্যমান পদ্ধতির সাথে বিস্তারিত কর্মক্ষমতা তুলনা

পদ্ধতির বিস্তারিত ব্যাখ্যা

কাজের সংজ্ঞা

n টি কীর একটি সেট দেওয়া, একটি নিখুঁত হ্যাশ ফাংশন f নির্মাণ করুন যাতে:

  • f একটি ইনজেকশন (সংঘর্ষ-মুক্ত)
  • প্রশ্নোত্তর সময় যতটা সম্ভব দ্রুত
  • নির্মাণ সময় যুক্তিসঙ্গত
  • স্থান খরচ কম (লক্ষ্য < 2 বিট প্রতি কী)

মূল অ্যালগরিদম আর্কিটেকচার

ম্যাপ-অর-বাম্প ফাংশন

PHast "ম্যাপ-অর-বাম্প" পদ্ধতির উপর ভিত্তি করে, n টি কীকে {0, 1, ..., m-1} এ ম্যাপ করে:

f(k) = {
  ⌊αh(k)⌋ + p(s, h(k))  যদি s > 0
  fallback_for_bumped(k)  অন্যথায়
}

যেখানে:

  • h(k) একটি u-বিট হ্যাশ ফাংশন (u = 64)
  • s = seeds⌊βh(k)⌋ হল বীজ
  • α, β হল স্কেলিং ফ্যাক্টর
  • p(s, h(k)) হল প্লেসমেন্ট ফাংশন

মূল প্রযুক্তিগত উপাদান

  1. রৈখিক বাকেট বরাদ্দ:
    • বাকেট সূচক: ⌊B/2ᵘ · cᵢ⌋
    • স্লাইস শুরু মান: ⌊(m-L+1)/2ᵘ · cᵢ⌋
    • আউটপুট মান: ⌊(m-L+1)/2ᵘ · cᵢ⌋ + p(s, cᵢ)
  2. উইন্ডোযুক্ত বীজ বরাদ্দ:
    • W = 256 আকারের স্লাইডিং উইন্ডো ব্যবহার করা
    • অগ্রাধিকার সারি দ্বারা বীজহীন বাকেট পরিচালনা
    • অগ্রাধিকার ফাংশন: ℓ(s) - 1024b (s হল বাকেট আকার, b হল বাকেট সূচক)
  3. বাম্পিং মেকানিজম:
    • বীজ খুঁজে পেতে না পারা বাকেটগুলি bumped হিসাবে চিহ্নিত করা হয় (বীজ মান 0)
    • প্রায় 1% বাকেট bumped, প্রত্যাশিত প্রশ্নোত্তর সময়ে খুব কম প্রভাব

PHast+ অপ্টিমাইজেশন

PHast+ দ্রুত নির্মাণ বাস্তবায়নের জন্য যোগজ প্লেসমেন্ট ফাংশন ব্যবহার করে:

p(s, c) = c mod L + s - 1        // সূত্র 3.2
p(s, c) = (c + δs) mod L         // সূত্র 3.3

বিট-সমান্তরাল বীজ অনুসন্ধান:

  • একযোগে 64টি ক্রমাগত বীজের সম্ভাব্যতা পরীক্ষা করা
  • সংঘর্ষ দ্রুত সনাক্ত করতে বিট অপারেশন ব্যবহার করা
  • নির্মাণ গতি প্রায় 10 গুণ উন্নত করা

সমান্তরাল নির্মাণ

  1. যোগাযোগ-মুক্ত সমান্তরালকরণ:
    • বীজ অ্যারে t টি ব্লক এবং t-1 টি ফাঁকে বিভক্ত করা
    • থ্রেডগুলি ব্লকে বীজ সমান্তরালভাবে গণনা করে
    • ফাঁক আকার: ⌈LB/(m-L+1)⌉ বাকেট
  2. ক্যাশ-বান্ধব ডিজাইন:
    • সূচক ক্রমে বাকেট প্রক্রিয়া করা
    • দখল বিটম্যাপ প্রতিনিধিত্ব করতে সার্কুলার বাফার ব্যবহার করা
    • ক্রমাগত মেমরি অ্যাক্সেস প্যাটার্ন

পরীক্ষামূলক সেটআপ

পরীক্ষামূলক পরিবেশ

  • হার্ডওয়্যার: AMD Ryzen 5600G @3.9GHz (6 কোর 12 থ্রেড)
  • ক্যাশ: 384KB/3MB/16MB L1/L2/L3
  • কম্পাইলার: Rust 1.84.1, GCC 12.2.0
  • থ্রেড সংখ্যা: 12 থ্রেড (মাল্টি-থ্রেড পরীক্ষার জন্য)

ডেটাসেট

  • র্যান্ডম পূর্ণসংখ্যা কী: 5×10⁷ এবং 5×10⁸ টি 64-বিট র্যান্ডম পূর্ণসংখ্যা
  • র্যান্ডম স্ট্রিং কী: 10-50 বাইট দৈর্ঘ্যের র্যান্ডম স্ট্রিং
  • হ্যাশ ফাংশন: GxHash (উচ্চ-কর্মক্ষমতা SIMD হ্যাশ)

তুলনা পদ্ধতি

  • বাকেট প্লেসমেন্ট: PTHash, PHOBIC, PtrHash
  • পুনরাবৃত্তিমূলক বিভাজন: SIMDRecSplit, Bipartite ShockHash
  • ফিঙ্গারপ্রিন্ট পদ্ধতি: FiPS, FMPH, FMPHGO
  • স্ট্যাটিক ফাংশন পুনরুদ্ধার: SicHash

মূল্যায়ন সূচক

  • স্থান খরচ: প্রতি কী বিট
  • প্রশ্নোত্তর সময়: প্রতি প্রশ্নোত্তর ন্যানোসেকেন্ড
  • নির্মাণ সময়: প্রতি কী ন্যানোসেকেন্ড
  • সমান্তরাল ত্বরণ অনুপাত: একক-থ্রেড বনাম মাল্টি-থ্রেড কর্মক্ষমতা অনুপাত

পরীক্ষামূলক ফলাফল

প্রধান কর্মক্ষমতা প্রদর্শন

প্রশ্নোত্তর কর্মক্ষমতা (5×10⁷ কী)

  • PHast: 9-22 ns/প্রশ্নোত্তর, স্থান 1.82-2.33 বিট/কী
  • PHast+: 10-15 ns/প্রশ্নোত্তর, স্থান 1.84-2.24 বিট/কী
  • PtrHash: 14-17 ns/প্রশ্নোত্তর, স্থান 2.12-2.99 বিট/কী
  • PTHash: 40-54 ns/প্রশ্নোত্তর, স্থান 2.11-3.19 বিট/কী

নির্মাণ কর্মক্ষমতা (5×10⁷ কী, একক-থ্রেড)

  • PHast+: 61-140 ns/কী (সর্বোত্তম কনফিগারেশন)
  • PHast: 133-5322 ns/কী (বীজ আকার সম্পর্কিত)
  • PtrHash: 75-192 ns/কী
  • FMPH: 40-57 ns/কী (কিন্তু বৃহত্তর স্থান)

সমান্তরাল ত্বরণ

  • PHast: 8.5-9.6 গুণ ত্বরণ (দক্ষ সমান্তরাল বীজ বরাদ্দ)
  • PHast+: 4.1-5.4 গুণ ত্বরণ
  • PtrHash: 3.6-5.1 গুণ ত্বরণ

পরামিতি অপ্টিমাইজেশন ফলাফল

সর্বোত্তম কনফিগারেশন (স্থান ন্যূনতমকরণ)

বীজ আকার SPHast λস্থান(বিট/কী)PHast+ λস্থান(বিট/কী)
84.71.915.352.09
106.051.856.351.90
127.351.817.41.82

বিচ্ছিন্নকরণ পরীক্ষা

  1. অনুমানমূলক বীজ নির্বাচন: অপসারণের পরে স্থান 1.92 থেকে 2.39 বিট/কী বৃদ্ধি পায়
  2. উইন্ডো আকার: W=1 এ স্থান 2.20 বিট/কী বৃদ্ধি পায়, W>256 কোন উল্লেখযোগ্য উন্নতি নেই
  3. স্লাইস সীমাবদ্ধতা: স্লাইস সীমাবদ্ধতা অপসারণের পরে স্থান উল্লেখযোগ্যভাবে বৃদ্ধি পায়
  4. বাকেট প্রক্রিয়াকরণ ক্রম: আকার অনুযায়ী হ্রাসক্রমে প্রক্রিয়া করা (CHD এর মতো) বৃহত্তর স্থান খরচের দিকে পরিচালিত করে

সম্পর্কিত কাজ

বাকেট প্লেসমেন্ট পদ্ধতির বিবর্তন

  1. CHD: রৈখিক বাকেট বরাদ্দ কিন্তু ধীর নির্মাণ, পরিবর্তনশীল-দৈর্ঘ্য বীজ এনকোডিং প্রয়োজন
  2. FCH/PTHash: সহজ অ-রৈখিক বাকেট বরাদ্দ, আংশিকভাবে সমস্যা হ্রাস করে
  3. PHOBIC: সর্বোত্তম বাকেট বরাদ্দ ফাংশন, কিন্তু ধীর প্রশ্নোত্তর
  4. PtrHash: প্রশ্নোত্তর-অপ্টিমাইজড PHOBIC রূপান্তর, স্থানীয় অনুসন্ধান ব্যবহার করে

অন্যান্য পদ্ধতির বিভাগ

  • ফিঙ্গারপ্রিন্ট পদ্ধতি: দ্রুত নির্মাণ কিন্তু বৃহত্তর স্থান, প্রশ্নোত্তরের জন্য র্যাঙ্ক অপারেশন প্রয়োজন
  • পুনরাবৃত্তিমূলক বিভাজন: স্থান তাত্ত্বিক নিম্ন সীমার কাছাকাছি কিন্তু ধীর প্রশ্নোত্তর
  • স্ট্যাটিক ফাংশন পুনরুদ্ধার: জটিল বহু-অবস্থান অনুসন্ধান প্রয়োজন

PHast এর অনন্যতা

PHast বাম্পিং মেকানিজমের মাধ্যমে পরিবর্তনশীল-দৈর্ঘ্য এনকোডিং এবং জটিল স্থানীয় অনুসন্ধান এড়ায়, একই সাথে রৈখিক বাকেট বরাদ্দের সরলতা বজায় রাখে।

উপসংহার এবং আলোচনা

প্রধান উপসংহার

  1. প্রশ্নোত্তর কর্মক্ষমতা: PHast তাত্ত্বিক সর্বোত্তমের কাছাকাছি প্রশ্নোত্তর সময় বাস্তবায়ন করে
  2. নির্মাণ দক্ষতা: PHast+ অত্যন্ত দ্রুত নির্মাণ গতি প্রদান করে
  3. স্থান দক্ষতা: দ্রুত প্রশ্নোত্তরের পূর্বশর্তে ভাল স্থান খরচ অর্জন করে
  4. সমান্তরাল-বান্ধব: অতিরিক্ত প্রশ্নোত্তর ওভারহেড ছাড়াই সমান্তরাল নির্মাণ

সীমাবদ্ধতা

  1. স্থান বনাম পুনরাবৃত্তিমূলক পদ্ধতি: এখনও পুনরাবৃত্তিমূলক বিভাজন পদ্ধতির তুলনায় প্রায় 0.4 বিট/কী পার্থক্য রয়েছে
  2. পরামিতি সংবেদনশীলতা: কী সংখ্যা এবং বীজ আকারের উপর ভিত্তি করে একাধিক পরামিতি সামঞ্জস্য করার প্রয়োজন
  3. তাত্ত্বিক বিশ্লেষণ: স্থান জটিলতার কঠোর তাত্ত্বিক প্রমাণের অভাব

পরীক্ষামূলক অপূর্ণতা

  1. ডেটাসেট একক: প্রধানত র্যান্ডম ডেটা ব্যবহার করে, বাস্তব অ্যাপ্লিকেশন ডেটা পরীক্ষার অভাব
  2. মেমরি শ্রেণীবিন্যাস: বিভিন্ন ক্যাশ স্তরের প্রভাব সম্পূর্ণভাবে বিশ্লেষণ করা হয়নি
  3. দীর্ঘমেয়াদী স্থিতিশীলতা: বৃহৎ-স্কেল দীর্ঘমেয়াদী ব্যবহারের কর্মক্ষমতা পরীক্ষা করা হয়নি

প্রভাব মূল্যায়ন

একাডেমিক অবদান

  1. তাত্ত্বিক মূল্য: প্রমাণ করে যে সহজ পদ্ধতি প্রকৌশল অপ্টিমাইজেশনের অধীনে প্রতিযোগিতামূলক
  2. পদ্ধতিবিদ্যা: ডেটা কাঠামো ডিজাইনের জন্য "জটিলতার পরিবর্তে সরলীকরণ" চিন্তাভাবনা প্রদান করে
  3. বেঞ্চমার্ক স্থাপনা: নিখুঁত হ্যাশিং প্রশ্নোত্তর কর্মক্ষমতার জন্য নতুন মান স্থাপন করে

ব্যবহারিক মূল্য

  1. সরাসরি প্রয়োগ: ডাটাবেস, সার্চ ইঞ্জিন ইত্যাদি দ্রুত প্রশ্নোত্তর প্রয়োজন এমন পরিস্থিতিতে ব্যবহার করা যায়
  2. প্রকৌশল রেফারেন্স: ক্যাশ-বান্ধব এবং সমান্তরালকরণ ডিজাইন অন্যান্য ডেটা কাঠামোতে প্রয়োগ করা যায়
  3. ওপেন সোর্স অবদান: Rust বাস্তবায়ন সম্প্রদায়কে উচ্চ-মানের সরঞ্জাম প্রদান করে

প্রযোজ্য পরিস্থিতি

আদর্শ প্রয়োগ

  1. স্ট্যাটিক হ্যাশ টেবিল: কী সেট স্থির, প্রশ্নোত্তর ঘন ঘন এমন পরিস্থিতি
  2. ডাটাবেস সূচক: দ্রুত কী-মূল্য অনুসন্ধান প্রয়োজন এমন ডাটাবেস সিস্টেম
  3. জৈব তথ্যবিজ্ঞান: k-mer সূচক ইত্যাদি প্রচুর প্রশ্নোত্তর প্রয়োজন এমন অ্যাপ্লিকেশন
  4. ক্যাশ সিস্টেম: অত্যন্ত দ্রুত প্রশ্নোত্তর প্রতিক্রিয়া প্রয়োজন এমন মেমরি ক্যাশ

সীমাবদ্ধতা শর্ত

  1. পর্যাপ্ত মেমরি: সম্পূর্ণ ডেটা কাঠামো সংরক্ষণের জন্য পর্যাপ্ত মেমরি প্রয়োজন
  2. স্ট্যাটিক ডেটা: ঘন ঘন আপডেট হওয়া গতিশীল পরিস্থিতির জন্য উপযুক্ত নয়
  3. প্রশ্নোত্তর-নিবিড়: প্রশ্নোত্তর ফ্রিকোয়েন্সি নির্মাণ ফ্রিকোয়েন্সির চেয়ে অনেক বেশি এমন অ্যাপ্লিকেশনের জন্য উপযুক্ত

তথ্যসূত্র

মূল সম্পর্কিত কাজ

  1. PHOBIC: Hermann et al. "নিখুঁত হ্যাশিং অপ্টিমাইজড বাকেট আকার এবং ইন্টারলিভড এনকোডিং সহ"
  2. PtrHash: Groot Koerkamp "PtrHash: RAM থ্রুপুটে ন্যূনতম নিখুঁত হ্যাশিং"
  3. PTHash: Pibiri & Trani "PTHash: FCH ন্যূনতম নিখুঁত হ্যাশিং পুনর্বিবেচনা"
  4. SIMDRecSplit: Bez et al. "RecSplit ভিত্তিক ন্যূনতম নিখুঁত হ্যাশ ফাংশনের উচ্চ কর্মক্ষমতা নির্মাণ"

তাত্ত্বিক ভিত্তি

  1. Fredman & Komlós: নিখুঁত হ্যাশ ফাংশনের তাত্ত্বিক নিম্ন সীমা
  2. Belazzougui et al.: বাকেট প্লেসমেন্ট পদ্ধতির ভিত্তি কাজ

PHast পেপার অ্যালগরিদম প্রকৌশল ক্ষেত্রে প্রদর্শন করে যে সমস্যার সারমর্ম এবং আধুনিক হার্ডওয়্যার বৈশিষ্ট্যের গভীর বোঝার মাধ্যমে, সহজ পদ্ধতি সাবধানে অপ্টিমাইজেশনের মাধ্যমে জটিল পদ্ধতির কর্মক্ষমতা অর্জন বা অতিক্রম করতে পারে। এটি ডেটা কাঠামো ডিজাইনের জন্য একটি গুরুত্বপূর্ণ অন্তর্দৃষ্টি প্রদান করে: কখনও কখনও সমস্যা সমাধানের চাবিকাঠি জটিলতা যোগ করা নয়, বরং সঠিক সরলীকরণ দিক খুঁজে পাওয়া।