Explicit Min-wise Hash Families with Optimal Size

We study explicit constructions of min-wise hash families and their extension to \(k\)-min-wise hash families. Informally, a min-wise hash family guarantees that for any fixed subset \(X \subseteq [N]\), every element in \(X\) has an equal chance to have the smallest value among all elements in \(X\); a \(k\)-min-wise hash family guarantees this for every subset of size \(k\) in \(X\). Min-wise hash is widely used in many areas of computer science such as sketching, web page detection, and \(\ell_0\) sampling. For applications like similarity estimation and rarity estimation, the space complexity of their streaming algorithms is roughly equal to the number of random bits used to construct such families.