  Minwise hashing is the standard technique in the context of search and
databases for efficiently estimating set (e.g., high-dimensional 0/1 vector)
similarities. Recently, b-bit minwise hashing was proposed which significantly
improves upon the original minwise hashing in practice by storing only the
lowest b bits of each hashed value, as opposed to using 64 bits. b-bit hashing
is particularly effective in applications which mainly concern sets of high
similarities (e.g., the resemblance >0.5). However, there are other important
applications in which not just pairs of high similarities matter. For example,
many learning algorithms require all pairwise similarities and it is expected
that only a small fraction of the pairs are similar. Furthermore, many
applications care more about containment (e.g., how much one object is
contained by another object) than the resemblance. In this paper, we show that
the estimators for minwise hashing and b-bit minwise hashing used in the
current practice can be systematically improved and the improvements are most
significant for set pairs of low resemblance and high containment.
