Is Min-Wise Hashing Optimal for Summarizing Set Intersection?

Min-wise hashing is an important method for estimating the size of the intersection of sets, based on a succinct summary (a “min-hash”) independently computed for each set. One application is estimation of the number of data points that satisfy the conjunction of m ≥ 2 simple predicates, where a min-hash is available for the set of points satisfying each predicate. This has applications in query optimization and for approximate computation of COUNT aggregates. In this paper we address the question: How many bits is it neces-sary to allocate to each summary in order to get an estimate with 1 ± ε relative error? The state-of-the-art technique for minimizing the encoding size, for any desired estimation error, is b-bit min-wise hashing due to Li and König (Com-munications of the ACM, 2011). We give new lower and upper bounds: • Using information complexity arguments, we show that b-bit min-wise hashing is space optimal for m = 2 predicates in the sense that the estimator’s variance is within a constant factor of the smallest possible among all summaries with the given space usage. But for con-junctions of m> 2 predicates we show that the perfor-mance of b-bit min-wise hashing (and more generally any method based on “k-permutation ” min-hash) de-teriorates as m grows. • We describe a new summary that nearly matches our lower bound for m ≥ 2. It asymptotically outper-form all k-permutation schemes (by around a factor Ω(m / logm)), as well as methods based on subsam-pling (by a factor Ω(lognmax), where nmax is the max-imum set size)