paper/

b-Bit minwise hashing

\[resemble(s, t) = \frac{\#(s \cap t)}{\#(s \cup t)}\]

これの利用例として、重複した web page の発見とか.

しかしながら、intersectionなんかに時間がかかりすぎる.

そのためのよくある手法が、Minwise hashing

\[Pr ( \min \pi(S) = \min \pi(T) ) = resemble(S, T)\]

その時に、イコールを見るのに、下bビットだけしかcheckしない.

\(b = 1\) で十分いい.

\(b < 1\) の場合も考えられる. 例えば、2bitをxorなどで1bitに圧縮して、その1bitを見る????? いみふ