Is min-wise hashing optimal for summarizing set intersection?
Rasmus Pagh, Morten Stöckel, David P. Woodruff · 2014
Min-wise hashing is an important method for estimating the size of the intersection of sets, based on a succinct summary (a "min-hash") of 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 application in query optimization and for approximate computation of COUNT aggregates.