EUVIMEDEUVIMED entdecken
Crossref

Meep Hashing: Ultrafast and Compact Minimal Perfect Hashing for Practical Large-Scale Lookup Systems

Shouqian Shi, Diancheng Luo, Jacques Liao, Yi Liu, Xingsheng Zhao, Matthew Fahrbach, Chen Qian

Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-22

DOI: 10.1145/3802087 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Shouqian Shi und 6 weiteren Autor:innen. Die Arbeit nennt 46 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Minimal perfect hashing (MPH) is a class of algorithms that maps a set of N keys to the range {0, 1, …, N -1} without collisions. MPH is widely employed in modern large-scale applications including distributed storage indexes, network packet classification, genomic encoding in Bioinformatics, etc. In practice, these systems are often augmented with alien-key filters to ensure robustness against unexpected inputs. This paper introduces Meep hashing, a novel minimal perfect hashing algorithm designed for ultrafast lookup with an integrated alien-key filtering mechanism. Among existing lookup systems, Meep achieves the lowest on-average and tail lookup latency while maintaining a memory footprint comparable to the most compact perfect hashing data structures. It supports configurable target false positive rates for alien-key filtering, enabling flexible trade-offs between accuracy and efficiency. The performance advantages of Meep are realized through a hybrid orchestration of Cuckoo-based and probing-based hashing techniques, combined with a collision resolution strategy that handles four distinct collision types with minimal or zero additional overhead. We implement Meep and evaluate its efficacy in lookup speed, memory footprint, and construction time using microbenchmarks. Experimental results show that Meep hashing is consistently 50% to 200% faster than the other MPHs and 100% faster than the other MHTs. Meep achieves more than 7 billion queries per second under Zipfian query key distribution on a single machine with 20 parallel lookup threads.

Zitieren

APA

Shi, S., Luo, D., Liao, J., Liu, Y., Zhao, X., Fahrbach, M., & Qian, C. (2026). Meep Hashing: Ultrafast and Compact Minimal Perfect Hashing for Practical Large-Scale Lookup Systems. Proceedings of the ACM on Management of Data, 4(3), 1-22. https://doi.org/10.1145/3802087

Vancouver

Shi S, Luo D, Liao J, Liu Y, Zhao X, Fahrbach M, et al. Meep Hashing: Ultrafast and Compact Minimal Perfect Hashing for Practical Large-Scale Lookup Systems. Proceedings of the ACM on Management of Data. 2026;4(3):1-22. doi:10.1145/3802087

BibTeX
@article{Shi2026,
  author = {Shi, Shouqian and Luo, Diancheng and Liao, Jacques and Liu, Yi and Zhao, Xingsheng and Fahrbach, Matthew and Qian, Chen},
  title = {Meep Hashing: Ultrafast and Compact Minimal Perfect Hashing for Practical Large-Scale Lookup Systems},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--22},
  doi = {10.1145/3802087}
}
Kostenlos starten →