MMH With Arbitrary Modulus Is Always Almost-universal

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

[Paper]    
Independent NEURIPS

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 $\mathrm{△}$-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${}^{\ast }$ is $\frac{1}{p}$-almost-$\mathrm{△}$-universal, where $p$ is the smallest prime divisor of $n$. This bound is tight.

Similar Work

• The Power Of Hashing With Mersenne Primes
• Coveringlsh Locality-sensitive Hashing Without False Negatives
• Explicit Orthogonal Arrays And Universal Hashing With Arbitrary Parameters
• Asymmetric Deep Semantic Quantization For Image Retrieval