Haoran Wang

Limited Independence Suffices for Large-k Min-wise Hashing

Min-wise hashing and its $k$-min-wise variant are standard tools in similarity estimation, sampling, sketching, and streaming. A $k$-min-wise family requires every prescribed $r$-subset of a fixed set, for $r\le k$, to appear as the $r$ smallest hash values with approximately the fully random probability, up to multipl...