類似度:

Jaccard係数 (resemblance):

                    sim(v,q)=|v∩q|/|v∪q|

両方のビットが完全に一致するのであれば1となり，そうでない場合は0以上1未満の値をとります．

コサイン類似度:

MinHash

大きな長所として特徴ベクトルの次元数が前もって分からない場合（加算無限）でも高速に動くこと，索引構築が各要素毎に独立に実行でき並列化が用意であること，そして索引自体が非常にコンパクトに保存できることが上げられます．

はじめに，適当なハッシュ関数hを用意します．（ハッシュ関数の値域は十分に大きく，衝突しないとします）．次にv中の各値をハッシュ関数を利用し，ハッシュ値h(a1),h(a2),…をもとめます．最後に，これらのハッシュ値の最小値min{h(a)|a∈v}を記録します.

さて，ランダムにハッシュ関数をとってきた時，二つの集合v, wのハッシュ関数による最小値が一致する確率 はどのようになるでしょうか．これが実はJaccard係数に一致します．

                sim(v,w)=P(min{h(a)|a∈v}=min{h(b)|b∈w})．

この性質を利用することで，二つのベクトルのJaccard係数は，ランダムなハッシュ関数による最小値が一致しているかどうかの確率により求められます．
この確率を経験確率より推定するために，k個のハッシュ関数を用意し，それぞれk個の最小値m1,m2,…,mkを求めておき，これらが何個一致したかを求め，それをkで割った値をJaccard推定量にします．
MinHashではハッシュ値が衝突しないようにハッシュ値の値域を大きめにとっていました．しかし，最小値しか記録しないとはいえ、これはサイズを多く必要とします.

b-bit Minwise Hashing

ハッシュ値の値域を小さくすることを考えます．例えば1ビットしか使わずハッシュ値に0, 1しか使わないことも考えられます．しかし，ハッシュ値の値域を小さくすると，今度はハッシュ値が衝突するようになって，さきほどのJaccard係数の 導出に利用していた式が成り立たなくなります．でも，その分ハッシュ関数の量は増やすことができるかもしれません．
基本的には，最小値が一致する確率に，ハッシュ関数が衝突して一致する確率の分が含まれるので，その分をさし引いたものが真に共通要素のハッシュ関数が最小値になる確率になります．それさえ求まればJaccard係数を導出することができます．