PHOBIC:通过优化桶大小和交织编码实现完美哈希

《ACM Transactions on Algorithms》:PHOBIC: Perfect Hashing with Optimized Bucket Sizes and Interleaved Coding

【字体: 大 中 小 】 时间:2026年09月26日 来源:ACM Transactions on Algorithms 1.4

编辑推荐:

   摘要AI摘要摘要摘要最小完美哈希函数(或MPHF)将一个包含 n 个键的集合映射到 [n]:={1,…,n},且无碰撞。此类函数在生物信息学和数据库等领域有广泛应用。本文重新审视了PTHash——一种专为快速查询设计的构造技术。PTHash将输入键分配到小桶中,并为每个桶搜索

  

摘要

摘要

最小完美哈希函数(或MPHF)将一个包含 n 个键的集合映射到 [n]:={1,…,n},且无碰撞。此类函数在生物信息学和数据库等领域有广泛应用。本文重新审视了PTHash——一种专为快速查询设计的构造技术。PTHash将输入键分配到小桶中,并为每个桶搜索一个哈希函数种子,使其键无碰撞地放置在输出域中。然后将所有种子的集合以压缩方式存储。由于前几个桶更容易放置,桶按大小非递增顺序处理。此外,PTHash启发式地产生桶大小的不平衡分布,将60%的键分配到30%的桶中。
我们的主要贡献是,在忽略低阶项的情况下,刻画了期望桶大小的一个最优选择,在理论和实践上都改善了空间高效配置的构造吞吐量。进一步的贡献包括一种新的种子编码方案,该方案跨越数据结构的不同分区工作,以及GPU并行化。
我们将我们的技术称为PHOBIC——具有优化桶大小和交错编码的完美哈希。与PTHash相比,PHOBIC在相同查询时间和构造吞吐量下,空间效率高0.17 bits/key。对于快速查询配置,我们的GPU实现可以在28 ns/key内以2.17 bits/key构造MPHF,该MPHF可以在CPU上以37 ns进行查询。

AI摘要

AI生成的摘要(实验性)

此摘要使用自动化工具生成,未由文章作者撰写或审阅。提供此摘要是为了支持发现,帮助读者评估相关性,并协助来自相邻研究领域的读者理解该工作。它旨在补充作者提供的摘要,后者仍然是论文的主要摘要。完整文章仍然是权威记录版本。 点击此处了解更多。

点击 此处 评论此摘要的准确性、清晰度和实用性。这样做将有助于改进和未来的重新生成版本。

AI生成的摘要

由自动系统基于已发表的文章文本生成。

版本创建于2026年9月24日。

本研究论文提出了PHOBIC,这是一种先进的最小完美哈希函数构造技术,通过优化的桶分配和压缩策略改进了PTHash。该工作在完美哈希的桶放置方面做出了若干理论和实践贡献。

论文首先建立了关于完美哈希通过桶放置的基础理论结果。作者证明了按非递增大小顺序处理桶是最小化构造时间的最优方法,这一做法之前被假设为正确但从未得到正式证明。他们建立了构造时间复杂度的下界为Ω(n×e^λ/λ)次哈希函数求值,并表明无论桶分配函数如何,空间消耗都趋近于每键log?(e)比特的理论下界。

核心贡献引入了一个最优桶分配函数,记为β*,通过确保放置每个桶的工作量大致相等来最小化构造时间。作者证明该函数在忽略低阶项的情况下是渐近最优的,实现了每键e^λ乘以(1+o(1))的预期构造成本。任何显著不同的分配函数都会导致更高的构造成本。最优函数与之前的方法相比,创建了越来越不平衡的桶大小分布,较大的桶按比例获得更多的键。

PHOBIC通过细粒度分区实现该理论,划分为大约2500个键子集,并在每个分区内独立构建MPHF。一种新颖的交错编码技术通过将所有分区中第i个桶的种子分组在一起进行种子压缩,因为这些种子遵循相同的统计分布。这使得可以为每个桶索引单独进行压缩调优,与均匀压缩方法相比,空间效率提高了最多每键0.06比特。

论文还提出了一种GPU实现,它自然地映射到细粒度分区架构。每个工作组处理一个分区,同时线程协作寻找最优种子。该实现通过精心设计的算法避免了控制流分歧,在现代图形硬件上实现了显著加速。

在1亿个随机键上的实验结果表明了PHOBIC的有效性。与具有相似空间占用和查询性能的PTHash相比,PHOBIC实现了每键0.17比特的空间效率提升和83倍的构造加速。仅优化的桶分配就为空间高效配置贡献了每键0.14比特的节省。GPU构造相比多线程CPU实现提供了62倍的加速,在扣除空闲功耗后能耗降低了26倍。

全面的比较显示,PHOBIC保持了PTHash每秒数千兆键的快速查询性能,同时显著改善了空间消耗和构造速度。该工作将理论优化与实际工程相结合,推动了完美哈希函数构造技术的发展。

相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号