ミンハッシュ

コンピュータサイエンスとデータマイニングにおいて、MinHash（または最小独立順列局所性敏感ハッシュ方式）は、2つのセットの類似性を迅速に推定するための手法です。この方式は、1997年の会議でAndrei Broderによって発表され^{[ 1 ]} 、当初はAltaVista検索エンジンで重複するWebページを検出して検索結果から除外するために使用されました^{[ 2 ]} 。また、単語セットの類似性に基づいて文書をクラスタリングするなど、大規模なクラスタリング問題にも適用されています^[¹^{] 。}

ジャッカード類似度と最小ハッシュ値

ジャッカード類似度係数は、2つの集合間の類似性を示す指標としてよく用いられます。U $を$ 集合とし、 $A$ と $Bを$ $U$ の部分集合とすると、ジャッカード指数は、それらの共通部分の要素数と和集合の要素数の比として定義されます。

J(A,B)={{|A\cap B|} \over {|A\cup B|}}.

この値は、2 つの集合が互いに素な場合は 0 、等しい場合は 1、それ以外の場合は 0 から 1 の間の値をとります。2 つの集合の Jaccard 指数が 1 に近いほど、類似性が高い（つまり、共通する要素が相対的に多い）と言えます。MinHash の目的は、 $J (A, B)$ を明示的に計算することなく、迅速に推定することです。

$h を集合$ $U$ の要素を異なる整数にマッピングするハッシュ関数とし、 $perm を$ 集合 $U$ の要素のランダムな順列とする。また、 $U$ の任意の部分集合 $Sに対して、$ $h$ $min$ $($ $S$ $)を$ $h$ $\circ$ $perm$ に関して $S$ の最小要素、すなわち $h$ $($ $perm$ $($ $x$ $))$ の値が最小となる $S$ の要素 $x$ と定義する。（使用するハッシュ関数が擬似乱数性を持つと仮定される場合は、ランダムな順列は使用しない。）

ここで、 $h minを$ $A$ と $B の$ 両方に適用し、ハッシュ衝突がないと仮定すると、すべての要素の中で、値が等しい ( $h min (A) = h min (B) ) のは、$ $A\cup B$ 最小ハッシュ値を持つ要素は、交差部分にあります。 $A\cap B$ このことが真である確率はジャッカード係数と全く同じであるため、次のようになる。

{\text{Pr}}[h_{\text{min}}(A)=h_{\text{min}}(B)]=J(A,B),

つまり、 $h$ $min$ $($ $A$ $) =$ $h$ $min$ $($ $B$ $)$ が真である確率は、一様分布から $パームを$ 抽出すると仮定すると、類似度 $J$ $($ $A$ $,$ $B$ $)$ に等しくなります。言い換えれば、 $rが$ $h$ $min$ $($ $A$ $) =$ $h$ $min$ $($ $B$ $)$ のときに 1 、それ以外のときに 0 となる確率変数である場合、 $rは$ $J$ $($ $A$ $,$ $B$ $)$ の不偏推定量です。r $は$ 分散が大きすぎるため、単独では Jaccard 類似度の有用な推定量にはなりません。 $r$ は常にゼロかイチです。MinHash方式の考え方は、同じ方法で構築された複数の変数を平均化することで、このばらつきを低減することです。

アルゴリズム

ハッシュ関数を多数使用したバリアント

minhash スキームの最も単純なバージョンでは、 $k 個$ の異なるハッシュ関数を使用します。ここで、 $k$ は固定の整数パラメータであり、各セット $S$ は、これらの $k個の関数に対する$ $h$ $min$ $($ $S$ $)$ の $k$ 個の値によって表されます。

このバージョンのスキームを使用して $J (A, B)$ を推定するには、 $h$ $min$ $($ $A$ $) =$ $h$ $min$ $($ $B$ $)$ となるハッシュ関数の数を $y$ とし、 $y$ $/$ $k を推定値として使用します。この推定値は$ $k 個$ の異なる 0-1 確率変数の平均であり、それぞれは $h$ $min$ $($ $A$ $) =$ $h$ $min$ $($ $B$ $)$ のときに 1 、それ以外の場合は 0 となり、それぞれが $J$ $($ $A$ $,$ $B$ $)$ の不偏推定値です。したがって、それらの平均も不偏推定値であり、0-1 確率変数の和の標準偏差により、期待誤差は $O(1/$ $\sqrt$ $k$ $)$ となります。^[³^]

したがって、任意の定数 $ε > 0$ に対して、推定値の期待誤差が最大で $ε$ となるような定数 $k = O(1/ ε 2)$ が存在します。例えば、期待誤差が 0.05 以下となるように $J$ $($ $A$ $,$ $B$ $)を推定するには、400 回のハッシュが必要になります。$

単一のハッシュ関数を使用したバリアント

複数のハッシュ関数を計算すると計算コストが高くなる可能性があるが、関連する MinHash スキームのバージョンでは、単一のハッシュ関数のみを使用し、ハッシュ関数ごとに最小値を 1 つだけ選択するのではなく、各セットから複数の値を選択するためにそれを使用することで、このペナルティを回避している。h を $ハッシュ$ 関数とし、 $k を$ 固定整数とする。S が h の定義域内の k 個以上の値の任意のセットである場合 $、$ $h$ ( $k$ ) ( S ) を、h の最小値を持つ S の k 個の要素のサブセットとして定義する $。$ $この$ $サブセット$ $h$ $($ $k$ $)$ $($ S $)$ は $セット$ Sの $署名$ $として$ $使用$ $さ$ $れ$ $、$ $任意$ の $2$ つのセットの類似性は、それらの署名を比較することによって推定される。

具体的には、AとBを任意の 2 つの集合とします。このとき、 $X = h (k) (h (k) (A) \cup h (k) (B)) = h (k) (A \cup B)は$ $A$ $\cup$ $B$ のk個の要素の集合であり、h がランダム関数である場合、 k個の要素の任意の部分集合が等しい確率で選択されます。つまり、 $Xは$ $A$ $\cup$ $B$ の単純ランダムサンプルです。部分集合 $Y$ $=$ $X$ $\cap$ $h$ $($ $k$ $)$ $($ $A$ $)$ $\cap$ $h$ $($ $k$ $)$ $($ $B$ $)は、$ $X$ の要素のうち、共通部分 $A$ $\cap$ $B$ に属する要素の集合です。したがって、| $Y$ |/ $kは$ $J$ $($ $A$ $,$ $B$ $)$ の不偏推定量です。この推定器と複数のハッシュ関数によって生成される推定器との違いは、 $Xは$ 常に正確に $k$ 個の要素を持つのに対し、複数のハッシュ関数では、2つの異なるハッシュ関数が同じ最小値を持つ可能性があるため、サンプリングされる要素の数が少なくなる可能性がある点です。ただし、 $kが$ 集合のサイズに比べて小さい場合、この違いは無視できる程度です。

非復元抽出における標準的なチェルノフ境界によれば、この推定量の期待誤差は $O(1/ \sqrtk) で$ あり、多重ハッシュ関数方式の性能に匹敵する。

時間分析

推定値 $| Y | / k$ は、このスキームのどちらのバリアントでも、与えられたセットの 2 つのシグネチャから $O(k)$ の時間で計算できます。したがって、 $ε$ と $k$ が定数の場合、シグネチャから推定類似度を計算する時間も定数になります。各セットのシグネチャはセットのサイズに対して線形時間で計算できるため、多数のペアワイズ類似度を推定する必要がある場合、この方法は各セットのメンバーの完全な比較を行う場合と比較して、実行時間を大幅に節約できます。具体的には、セットサイズ $n$ の場合、多ハッシュバリアントは $O(n k) の$ 時間を必要とします。単一ハッシュバリアントは一般的に高速で、 $n$ $>>$ $k$ $を仮定すると、最小ハッシュ値のキューを維持するためにO(n)$ の時間が必要です。^[¹^]

重み付けを取り入れる

MinHashの計算に重みを導入するためのさまざまな手法が開発されてきた。最も単純な方法は、それを整数重みに拡張するものである。^{[ 4 ]} ハッシュ関数 $h$ を拡張して、セットの要素と整数の両方を受け入れるようにし、各項目の重みに応じて複数のハッシュを生成する。項目 $iが$ $n$ 回出現する場合、ハッシュを生成する。 $h(i,1),h(i,2),\ldots ,h(i,n)$ 拡張されたハッシュ値のセットに対して、元のアルゴリズムを実行します。そうすることで、衝突確率として重み付きジャッカード係数が得られます。

J_{\mathcal {W}}(x,y)={\frac {\sum _{i}\min(x_{i},y_{i})}{\sum _{i}\max(x_{i},y_{i})}}

実数重みに対してより優れた実行時間でこの衝突確率を実現するさらなる拡張機能が開発されており、1つは密なデータ用^{[ 5 ]} 、もう1つは疎なデータ用^{[ 6 ]である。}

別の拡張機能群では、指数分布ハッシュを使用します。0から1の間の均一乱数ハッシュは、累積分布関数（CDF）の逆変換によって指数分布に従うように変換できます。この方法は、指数変数の集合の最小値が持つ多くの優れた特性を活用しています。

H(x)={\underset {i}{\operatorname {arg\,min} }}{\frac {-\log(h(i))}{x_{i}}}

これにより、衝突確率として確率ジャッカード指数^{[ 7 ]が得られます。}

J_{\mathcal {P}}(x,y)=\sum _{x_{i}\neq 0 \atop y_{i}\neq 0}{\frac {1}{\sum _{j}\max \left({\frac {x_{j}}{x_{i}}},{\frac {y_{j}}{y_{i}}}\right)}}

最小値独立順列

上述のMinHashスキームを実装するには、ハッシュ関数 $hが$ $n$ 個の要素に対するランダムな順列を定義する必要があります。ここで $n$ は、比較対象となるすべての集合の和集合に含まれる異なる要素の総数です。しかし、 $n$ $!通りの異なる順列が存在するため、真にランダムな順列を指定するだけでも$ $Ω$ $($ $n$ $log$ $n$ $)$ ビットが必要となり、 $n$ の値が中程度であっても、これは非現実的なほど大きな数になります。このため、ユニバーサルハッシュ理論になぞらえて、「最小値独立」な順列の族を見つける研究が盛んに行われてきました。これは、ドメインの任意の部分集合に対して、どの要素も最小値になる確率が等しいことを意味します。最小値独立な順列の族には、少なくとも

\operatorname {lcm} (1,2,\cdots ,n)\geq e^{no(n)}

異なる順列が存在するため、単一の順列を指定するには $Ω (n)ビットが必要となり、依然として非現実的に大きい。$ ^{[ 2 ]}

実用的な最小値独立ハッシュ関数

上記の非実用性のため、最小値独立性の 2 つの変形概念が導入されました。制限付き最小値独立順列族と近似最小値独立族です。制限付き最小値独立性とは、最大で $k の$ 濃度を持つ特定の集合に制限された最小値独立性の性質です。^{[ 8 ]} 近似最小値独立性とは、完全な独立性から変動する確率が最大で固定 $ε$ であるものです。^{[ 9 ]}

1999年にPiotr Indykは^{[ 10 ]}、任意のk個の独立なハッシュ関数の族は、近似的に最小値独立でもあることを証明した。 $k$ 十分に大きい。特に定数がある。 $c,c'>0$ もし $k\geq c\log {\tfrac {1}{\epsilon }}$ 、それから

\Pr _{h\in {\mathcal {H}}}[h(x)<\min h(X)]={\frac {1}{|X|+1}}(1\pm \epsilon ),

すべてのセットについて $|X|\leq \epsilon nc'$ そして $x\not \in X$ （注：ここ） $(1\pm \epsilon )$ 確率はせいぜい要因であることを意味する $1+\epsilon$ 大きすぎる、そして最大 $1-\epsilon$ 小さすぎる。）

この保証は、とりわけ、MinHashアルゴリズムで必要とされるJaccard限界を与えるのに十分である。つまり、 $A$ そして $B$ 集合である場合、

\Pr _{h\in {\mathcal {H}}}[\min h(A)=\min h(B)]={\frac {|A\cap B|}{|A\cup B|}}\pm \epsilon .

k 個の独立したハッシュ関数は、 $k\log n$ ビットの場合、このアプローチは、完全に最小値で独立した順列を使用するよりもはるかに実用的です。

近似的に最小値独立性を提供するもう 1 つの実用的なハッシュ関数のファミリーは、表形式ハッシュです。

アプリケーション

MinHash の当初の用途は、Web ドキュメント内の単語の集合として表現される、それらのドキュメント間のほぼ重複する単語のクラスタリングと削除でした。^{[ 1 ]}^{[ 2 ]}^{[ 11 ]}同様の手法は、画像などの他のタイプのデータのクラスタリングとほぼ重複する単語の削除にも使用されています。画像データの場合、画像は、そこから切り取られたより小さなサブ画像の集合、またはより複雑な画像特徴記述の集合として表現できます。^{[ 12 ]}

データマイニングにおいて、Cohen ら (2001)は MinHash をアソシエーションルール学習のツールとして使用しています。各エントリに複数の属性を持つデータベース (データベースエントリごとに 1 行、属性ごとに 1 列を持つ0-1 行列として見なされる) が与えられた場合、彼らは MinHash に基づく Jaccard インデックスの近似値を使用して、頻繁に共起する属性の候補ペアを特定し、それらのペアのみのインデックスの正確な値を計算して、共起頻度が特定の厳密な閾値を下回るペアを決定します。^{[ 13 ]}

MinHash アルゴリズムはバイオインフォマティクスに応用されており、ゲノム配列の比較問題は、ウェブ上のドキュメントの比較問題と同様の理論的根拠に基づいています。MinHash ベースのツール^{[ 14 ]}^{[ 15 ]}を使用すると、全ゲノムシーケンスデータと参照ゲノムを迅速に比較できます(1 つのゲノムをRefSeqの 90000 個の参照ゲノムと比較するのに約 3 分)。また、種分類や、おそらく限定的な微生物のサブタイピングにも適しています。メタゲノミクス^{[ 14 ]}や、ゲノムアライメントとゲノムアセンブリのための MinHash 由来のアルゴリズムの使用にも応用されています。^{[ 16 ]} MinHash ベースのアルゴリズムを使用すると、正確な平均ヌクレオチド同一性 (ANI) 値を非常に効率的に生成できます。^{[ 17 ]}

その他の用途

MinHash スキームは、局所性に敏感なハッシュ化の一例と見なすことができます。局所性に敏感なハッシュ化とは、ハッシュ関数を使用してオブジェクトの大きなセットをより小さなハッシュ値にマッピングする一連の手法であり、2 つのオブジェクト間の距離が小さい場合、それらのハッシュ値は同じになる可能性が高くなります。この場合、セットのシグネチャはそのハッシュ値と見なすことができます。セット間のハミング距離やベクトル間のコサイン距離についても、局所性に敏感なハッシュ化手法が存在します。局所性に敏感なハッシュ化は、最近傍探索アルゴリズムにおいて重要な応用があります。 ^[¹⁸^]大規模な分散システム、特にMapReduceでは、点次元に依存しない類似性を計算するのに役立つ MinHash の修正バージョンが存在します。^[¹⁹^]

評価とベンチマーク

2006年にGoogleは、Minhashと SimHash ^[²¹^]アルゴリズムの性能を比較する大規模な評価を実施しました^{[ 20 ] 。2007年には、GoogleはWebクローリングの重複検出にSimhashを使用し}^[²²^] 、 GoogleニュースのパーソナライゼーションにMinhashとLSHを使用していると報告しました^[²³^{] 。}

参考文献

1 2 3 4 Broder, Andrei Z. (1998), "文書の類似性と包含について", Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171) (PDF) , IEEE , pp. 21–29 , CiteSeerX 10.1.1.24.779 , doi : 10.1109/SEQUEN.1997.666900 , ISBN 978-0-8186-8132-5S2CID 11748509、2015年1月31日にオリジナル（PDF）からアーカイブ、2014年1月18日に取得。
1 2 3 Broder, Andrei Z. ; Charikar, Moses; Frieze, Alan M. ; Mitzenmacher, Michael (1998), "Min-wise independent permutations", Proc. 30th ACM Symposium on Theory of Computing (STOC '98) , New York, NY, USA: Association for Computing Machinery , pp. 327– 336, CiteSeerX 10.1.1.409.9220 , doi : 10.1145/276698.276781 , ISBN 978-0897919623S2CID 465847 。
↑ Vassilvitskii, Sergey (2011), COMS 6998-12: 大規模データの取り扱い（講義ノート、コロンビア大学）（PDF）、2018年10月24日にオリジナル（PDF）からアーカイブ済み。
↑ Chum, Ondrej; Philbin, James; Zisserman, Andrew (2008)、「ほぼ重複する画像検出：min-Hashとtf-idf重み付け」（PDF）、BMVC、810：812–815
↑ Shrivastava, Anshumali (2016), "定数時間での正確な重み付き最小値ハッシュ", arXiv : 1602.08393 [ cs.DS ]
↑ Ioffe, Sergey (2010). "Improved Consistent Sampling, Weighted Minhash and L1 Sketching". 2010 IEEE International Conference on Data Mining (PDF) . pp. 246–255 . CiteSeerX 10.1.1.227.9749 . doi : 10.1109/ICDM.2010.80 . ISBN 978-1-4244-9131-5. S2CID 9970906 .
↑ Moulton, Ryan; Jiang, Yunjiang (2018), "Maximally Consistent Sampling and the Jaccard Index of Probability Distributions", 2018 IEEE International Conference on Data Mining (ICDM) , pp. 347–356 , arXiv : 1809.04052 , doi : 10.1109/ICDM.2018.00050 , ISBN 978-1-5386-9159-5S2CID 49746072
↑マトウシェク、イジー; Stojaković、Miloš (2003)、「順列の制限付き最小単位独立性について」、ランダム構造とアルゴリズム、23 (4): 397–408、CiteSeerX 10.1.1.400.6757、doi : 10.1002/rsa.10101、S2CID 1483449 。
↑ Saks, M. ; Srinivasan, A.; Zhou, S.; Zuckerman, D. (2000), "Low discrepancy sets yield approximate min-wise independent permutation families", Information Processing Letters , 73 ( 1– 2): 29– 32, CiteSeerX 10.1.1.20.8264 , doi : 10.1016/S0020-0190(99)00163-5 。
↑ Indyk, Piotr. 「ハッシュ関数のほぼ最小値独立な小さな族」 Journal of Algorithms 38.1 (2001): 84-90.
↑マナッセ、マーク（2012）。「最も近い近傍を効率的に決定する方法：蹄鉄、手榴弾、ウェブ検索、その他、近いだけで十分という状況」 。モーガン＆クレイプール。72ページ。ISBN 9781608450886。
↑ Chum, Ondřej; Philbin, James; Isard, Michael; Zisserman, Andrew (2007), "Scalable near identical image and shot detection", Proceedings of the 6th ACM International Conference on Image and Video Retrieval (CIVR'07) , pp. 549–556 , doi : 10.1145/1282280.1282359 , ISBN 9781595937339S2CID 3330908 ; Chum, Ondřej; Philbin, James; Zisserman, Andrew (2008)、「ほぼ重複する画像検出：min-hashとtf-idf重み付け」、英国機械視覚会議議事録（PDF）、第3巻、 4ページ。
↑ Cohen, E. ; Datar, M.; Fujiwara, S.; Gionis, A.; Indyk, P. ; Motwani, R. ; Ullman, JD ; Yang, C. (2001), "Finding interesting associations without support pruning", IEEE Transactions on Knowledge and Data Engineering , 13 (1): 64– 78, Bibcode : 2001IDSO...13...64C , CiteSeerX 10.1.1.192.7385 , doi : 10.1109/69.908981 。
1 2 Ondov, Brian D.; Treangen, Todd J.; Melsted, Páll; Mallonee, Adam B.; Bergman, Nicholas H.; Koren, Sergey; Phillippy, Adam M. (2016-06-20). "Mash: MinHash を使用した高速ゲノムおよびメタゲノム距離推定" . Genome Biology . 17 (1): 132. doi : 10.1186/s13059-016-0997-x . ISSN 1474-760X . PMC 4915045 . PMID 27323842 .
↑ 「sourmashへようこそ！ — sourmash 1.0 ドキュメント」。sourmash.readthedocs.io 。 2017年11月13日取得。
↑ Berlin, Konstantin; Koren, Sergey; Chin, Chen-Shan; Drake, James P; Landolin, Jane M; Phillippy, Adam M (2015-05-25). "Assembling large genomes with single-molecule sequencing and locality-sensitive hashing". Nature Biotechnology . 33 (6): 623– 630. Bibcode : 2015NatBi..33..623B . doi : 10.1038/nbt.3238 . ISSN 1546-1696 . PMID 26006009. S2CID 17246729 .
↑ Jain, Chirag; Rodriguez-R, Luis M.; Phillippy, Adam M.; Konstantinidis, Konstantinos T.; Aluru, Srinivas (2018年12月) 「9万個の原核生物ゲノムのハイスループットANI解析により明確な種境界が明らかに」 Nature Communications . 9 (1): 5114. Bibcode : 2018NatCo...9.5114J . doi : 10.1038 / s41467-018-07641-9 . PMC 6269478. PMID 30504855 .
↑ Andoni, Alexandr; Indyk, Piotr (2008), "高次元における近似最近傍探索のためのほぼ最適なハッシュアルゴリズム", Communications of the ACM , 51 (1): 117– 122, CiteSeerX 10.1.1.226.6905 , doi : 10.1145/1327452.1327494 , S2CID 6468963 。
↑ Zadeh, Reza; Goel, Ashish (2012), "Dimension Independent Similarity Computation", arXiv : 1206.2082 [ cs.DS ]。
↑ Henzinger, Monika (2006), "類似ウェブページの検出：アルゴリズムの大規模評価", Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval , pp. 284 , doi : 10.1145/1148170.1148222 , ISBN 978-1595933690S2CID 207160068 。
↑ Charikar, Moses S. (2002), "丸めアルゴリズムによる類似性推定手法", Proceedings of the 34th Annual ACM Symposium on Theory of Computing , pp. 380–388 , doi : 10.1145/509907.509965 , ISBN 978-1581134957S2CID 4229473 。
↑ Gurmeet Singh, Manku; Jain, Arvind; Das Sarma, Anish (2007)、「ウェブクローリングにおける類似コンテンツの検出」、第16回国際ワールドワイドウェブ会議議事録（PDF）、p. 141、doi : 10.1145/1242572.1242592、ISBN 9781595936547S2CID 1414324 。
↑ Das, Abhinandan S.; Datar, Mayur; Garg, Ashutosh; Rajaram, Shyam; et al. (2007), "Googleニュースパーソナライゼーション：スケーラブルなオンライン協調フィルタリング", Proceedings of the 16th International Conference on World Wide Web , p. 271, doi : 10.1145/1242572.1242610 , ISBN 9781595936547S2CID 207163129 。

[b97-1] 1 2 3 4 Broder, Andrei Z. (1998), "文書の類似性と包含について", Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171) (PDF) , IEEE , pp. 21–29 , CiteSeerX 10.1.1.24.779 , doi : 10.1109/SEQUEN.1997.666900 , ISBN 978-0-8186-8132-5S2CID 11748509、2015年1月31日にオリジナル（PDF）からアーカイブ、2014年1月18日に取得。

[bcfm-2] 1 2 3 Broder, Andrei Z. ; Charikar, Moses; Frieze, Alan M. ; Mitzenmacher, Michael (1998), "Min-wise independent permutations", Proc. 30th ACM Symposium on Theory of Computing (STOC '98) , New York, NY, USA: Association for Computing Machinery , pp. 327– 336, CiteSeerX 10.1.1.409.9220 , doi : 10.1145/276698.276781 , ISBN 978-0897919623S2CID 465847 。

[3] Vassilvitskii, Sergey (2011), COMS 6998-12: 大規模データの取り扱い（講義ノート、コロンビア大学）（PDF）、2018年10月24日にオリジナル（PDF）からアーカイブ済み。

[4] Chum, Ondrej; Philbin, James; Zisserman, Andrew (2008)、「ほぼ重複する画像検出：min-Hashとtf-idf重み付け」（PDF）、BMVC、810：812–815

[5] Shrivastava, Anshumali (2016), "定数時間での正確な重み付き最小値ハッシュ", arXiv : 1602.08393 [ cs.DS ]

[6] Ioffe, Sergey (2010). "Improved Consistent Sampling, Weighted Minhash and L1 Sketching". 2010 IEEE International Conference on Data Mining (PDF) . pp. 246–255 . CiteSeerX 10.1.1.227.9749 . doi : 10.1109/ICDM.2010.80 . ISBN 978-1-4244-9131-5. S2CID 9970906 .

[7] Moulton, Ryan; Jiang, Yunjiang (2018), "Maximally Consistent Sampling and the Jaccard Index of Probability Distributions", 2018 IEEE International Conference on Data Mining (ICDM) , pp. 347–356 , arXiv : 1809.04052 , doi : 10.1109/ICDM.2018.00050 , ISBN 978-1-5386-9159-5S2CID 49746072

[8] マトウシェク、イジー; Stojaković、Miloš (2003)、「順列の制限付き最小単位独立性について」、ランダム構造とアルゴリズム、23 (4): 397–408、CiteSeerX 10.1.1.400.6757、doi : 10.1002/rsa.10101、S2CID 1483449 。

[9] Saks, M. ; Srinivasan, A.; Zhou, S.; Zuckerman, D. (2000), "Low discrepancy sets yield approximate min-wise independent permutation families", Information Processing Letters , 73 ( 1– 2): 29– 32, CiteSeerX 10.1.1.20.8264 , doi : 10.1016/S0020-0190(99)00163-5 。

[10] Indyk, Piotr. 「ハッシュ関数のほぼ最小値独立な小さな族」 Journal of Algorithms 38.1 (2001): 84-90.

[11] マナッセ、マーク（2012）。「最も近い近傍を効率的に決定する方法：蹄鉄、手榴弾、ウェブ検索、その他、近いだけで十分という状況」 。モーガン＆クレイプール。72ページ。ISBN 9781608450886。

[12] Chum, Ondřej; Philbin, James; Isard, Michael; Zisserman, Andrew (2007), "Scalable near identical image and shot detection", Proceedings of the 6th ACM International Conference on Image and Video Retrieval (CIVR'07) , pp. 549–556 , doi : 10.1145/1282280.1282359 , ISBN 9781595937339S2CID 3330908 ; Chum, Ondřej; Philbin, James; Zisserman, Andrew (2008)、「ほぼ重複する画像検出：min-hashとtf-idf重み付け」、英国機械視覚会議議事録（PDF）、第3巻、 4ページ。

[13] Cohen, E. ; Datar, M.; Fujiwara, S.; Gionis, A.; Indyk, P. ; Motwani, R. ; Ullman, JD ; Yang, C. (2001), "Finding interesting associations without support pruning", IEEE Transactions on Knowledge and Data Engineering , 13 (1): 64– 78, Bibcode : 2001IDSO...13...64C , CiteSeerX 10.1.1.192.7385 , doi : 10.1109/69.908981 。

[:0-14] 1 2 Ondov, Brian D.; Treangen, Todd J.; Melsted, Páll; Mallonee, Adam B.; Bergman, Nicholas H.; Koren, Sergey; Phillippy, Adam M. (2016-06-20). "Mash: MinHash を使用した高速ゲノムおよびメタゲノム距離推定" . Genome Biology . 17 (1): 132. doi : 10.1186/s13059-016-0997-x . ISSN 1474-760X . PMC 4915045 . PMID 27323842 .

[15] 「sourmashへようこそ！ — sourmash 1.0 ドキュメント」。sourmash.readthedocs.io 。 2017年11月13日取得。

[16] Berlin, Konstantin; Koren, Sergey; Chin, Chen-Shan; Drake, James P; Landolin, Jane M; Phillippy, Adam M (2015-05-25). "Assembling large genomes with single-molecule sequencing and locality-sensitive hashing". Nature Biotechnology . 33 (6): 623– 630. Bibcode : 2015NatBi..33..623B . doi : 10.1038/nbt.3238 . ISSN 1546-1696 . PMID 26006009. S2CID 17246729 .

[17] Jain, Chirag; Rodriguez-R, Luis M.; Phillippy, Adam M.; Konstantinidis, Konstantinos T.; Aluru, Srinivas (2018年12月) 「9万個の原核生物ゲノムのハイスループットANI解析により明確な種境界が明らかに」 Nature Communications . 9 (1): 5114. Bibcode : 2018NatCo...9.5114J . doi : 10.1038 / s41467-018-07641-9 . PMC 6269478. PMID 30504855 .

[18] Andoni, Alexandr; Indyk, Piotr (2008), "高次元における近似最近傍探索のためのほぼ最適なハッシュアルゴリズム", Communications of the ACM , 51 (1): 117– 122, CiteSeerX 10.1.1.226.6905 , doi : 10.1145/1327452.1327494 , S2CID 6468963 。

[19] Zadeh, Reza; Goel, Ashish (2012), "Dimension Independent Similarity Computation", arXiv : 1206.2082 [ cs.DS ]。

[20] Henzinger, Monika (2006), "類似ウェブページの検出：アルゴリズムの大規模評価", Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval , pp. 284 , doi : 10.1145/1148170.1148222 , ISBN 978-1595933690S2CID 207160068 。

[21] Charikar, Moses S. (2002), "丸めアルゴリズムによる類似性推定手法", Proceedings of the 34th Annual ACM Symposium on Theory of Computing , pp. 380–388 , doi : 10.1145/509907.509965 , ISBN 978-1581134957S2CID 4229473 。

[22] Gurmeet Singh, Manku; Jain, Arvind; Das Sarma, Anish (2007)、「ウェブクローリングにおける類似コンテンツの検出」、第16回国際ワールドワイドウェブ会議議事録（PDF）、p. 141、doi : 10.1145/1242572.1242592、ISBN 9781595936547S2CID 1414324 。

[23] Das, Abhinandan S.; Datar, Mayur; Garg, Ashutosh; Rajaram, Shyam; et al. (2007), "Googleニュースパーソナライゼーション：スケーラブルなオンライン協調フィルタリング", Proceedings of the 16th International Conference on World Wide Web , p. 271, doi : 10.1145/1242572.1242610 , ISBN 9781595936547S2CID 207163129 。

[ 1 ]

[ 2 ]

[

[ 4 ]

[ 5 ]

[ 6 ]である。

[ 7 ]が得られます。

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 15 ]

[ 16 ]

[ 17 ]

[

[

[

[ 20 ] 。2007年には、GoogleはWebクローリングの重複検出にSimhashを使用し

[

[