2026/07/29 by Xue Chen, Shengtang Huang, Xin Li
Computer Science · #cs.DS
arxiv created 2026/07/29 · arxiv updated 2026/07/30
Min-wise hashing and its k-min-wise extension are fundamental tools in sampling, sketching, and similarity estimation. A standard approach to constructing such families is bounded independence. For ordinary min-wise hashing, the required degree of independence is fully understood: Θ(log 1/δ)-wise independence is both sufficient and necessary. For k-min-wise hashing, however, the best previous result only showed that O(kloglog1/δ+log1/δ)-wise independence suffices, with no matching lower bound. We give a tight characterization of the amount of bounded independence required for k-min-wise hashing, proving that Θ(k+log1/δ)-wise independence is both sufficient and necessary. This improves the previous upper bound and provides a matching lower bound. Consequently, the standard construction of bounded-independent hash families has seed length O((k+log1/δ)log(N/δ)). In particular, for any polynomially small error δ and any k=Ω(log N), it achieves the optimal seed length O(klog N). We also study random affine hash functions over \mathbbF2 and show that, despite being pairwise independent, they may incur multiplicative error Ω(log n) even for ordinary min-wise hashing.