MMH* With Arbitrary Modulus Is Always Almost-universal | Awesome Learning to Hash Add your paper to Learning2Hash

Awesome Learning to Hash

A Webpage dedicated to the latest research on Hash Function Learning. Maintained by Sean Moran.

Stay Updated

Contact Sean Moran about this survey or website. Made with Jekyll and Hyde.

MMH* With Arbitrary Modulus Is Always Almost-universal

Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan . Information Processing Letters 2020 – 10 citations

[Paper]   Search on Google Scholar   Search on Semantic Scholar
Evaluation Hashing Methods

Universal hash functions, discovered by Carter and Wegman in 1979, are of great importance in computer science with many applications. MMH(^) is a well-known (\triangle)-universal hash function family, based on the evaluation of a dot product modulo a prime. In this paper, we introduce a generalization of MMH(^), that we call GMMH(^), using the same construction as MMH(^) but with an arbitrary integer modulus (n>1), and show that GMMH(^*) is (\frac{1}{p})-almost-(\triangle)-universal, where (p) is the smallest prime divisor of (n). This bound is tight.

Similar Work