PHOBIC：优化桶尺寸与交错编码的完美哈希

ACM Transactions on Algorithms · 2026-09-24 · 期刊论文

• 一句话结论：结论方向：PHOBIC在相同查询时间与构建吞吐下较PTHash空间效率提升0.17 bits/key，并给出期望桶尺寸的近似最优刻画，证据档位为C，属算法理论与实现层面的性能报告。
• 研究设计与做法：设计与做法：在PTHash基础上重新刻画期望桶尺寸的最优选择（精确到低阶项），并引入跨数据结构分区的种子编码方案与GPU并行化；实验比较对象为PTHash，具体数据集、键规模与硬件配置材料未报告。
• 主要结果：主要结果：相同查询时间与构建吞吐下，PHOBIC比PTHash空间效率高0.17 bits/key；在快速查询配置下，GPU实现可在28 ns/key构建2.17 bits/key的MPHF，CPU查询时间为37 ns。
• 机制或解释：机制解释：作者认为PTHash按桶尺寸非递增顺序放置并启发式地将60%键分配到30%桶中造成桶尺寸分布不均衡，而PHOBIC通过刻画最优期望桶尺寸改进构建吞吐，交错编码则支持跨分区种子存储。
• 局限与边界：局限与边界：材料未报告测试数据集规模与多样性、与除PTHash外其他MPHF方法的比较、GPU型号及可复现实验细节，也未报告利益冲突；结论的普适性受所选配置限制。
• 可否落地：可否落地：对生物信息学与数据库等需快速查询MPHF的场景，PHOBIC提供了空间效率与构建吞吐的改进方案（证据支持其在报告配置下的性能优势），但实际系统集成收益仍需按具体工作负载评估，尚不足以下普遍结论。

🔗 打开原文

Stefan Hermann, Hans‐Peter Lehmann, Giulio Ermanno Pibiri 等

本文摘自《每日前沿研究简报 · 2026-09-26》「信息科学」。本内容仅用于研究信息整理与科普交流，不构成医疗建议。