Minhash LSH のメモ
syoyoRefinedWeb とかでは 1 ドキュメント(文章)あたり 9,000 hashes を計算している...
入力のドキュメントが多いと, たとえば 1 億ドキュメントあると, 1 hash 4 byte としても, 0.1B * 9000 * 4 / (1024 * 1024 * 1024) ~= 3.4 TB の領域が必要となる.
syoyoMinhash LSH
そこで, minhash を b x r(band x row)に分けて, band ごとにさらに hash を計算し, その hash の index(bin index) が同じであるかどうかで一致をとるかを minhash LSH(locally-sensitive hashing) という.
hashing したあとのテーブルサイズ(bin サイズ)は bucket(!= band)で指定される.
band ごとに使う hash 関数は, コサイン距離やユークリッド距離を考慮したハッシュ関数(binning 関数)を使うっぽい.
テキスト処理であれば FNV などの簡単なものでいいらしい.
(=> この場合は LSH とは言わない?)
FNV などでのハッシュ関数利用は, 実質的には次元削減を行っている. たとえば band = 20, row = 450(合計 9,000), bucket サイズが 45(45 hashes と同じデータサイズ)であれば, 20 x 45 = 900 個の hash ぶんのストレージで済む(データサイズ 1/10).
bucket の大きさの取り方は...? よくわからない. 小さいと一致が多くなってしまうし(false positive が増える), 大きいとデータ削減にならない.
syoyoJaccard 係数算出してチェック
bucket を比較的小さく取った場合は, 実際に Jaccard 係数(および必要であれば Edit Similarity)を算出して重複判定するとよいであろう.
たとえば LLM 向けのデータセットでは, minhash dedup で重複判定されるのは高々 10 % 程度くらいで, 9 割以上が一致しないあると想定されるから, bucket を小さめにとって(重複判定が増えるがそれほど計算量は増えなさそう)もいいかもしれません.
あとはストレージコストを下げるのであれば b-bit minhash という手もある.
実質 bucket サイズの小さい minhash LSH は b-bit minhash とほぼ同等な感じがあります.
しかし b-bit minhash は計算するハッシュの数が増えるのと, ハッシュ値に対してハッシュ取るのに比べて衝突確率が増えそうなので, 重複の確率(false positive の率)と計算量を考えると minhash + LSH のほうがいいかもしれません.
syoyoメモリ効率よくする
ストレージに余裕があるがメモリは一定サイズに収めたいとき.
値はハッシュであるので, ハッシュの先頭 8 bit でフォルダ分けしてハッシュ値データを書き出すのも手であろう.
0xa0b1c2d4 -> フォルダ a
0xdeadbeef -> フォルダ d
重複判定もこのフォルダ単位で行える. ソートなり set で重複判定すれば良い.
(結合した)ハッシュ値がどのドキュメントに対応するかのインデックスが必要だが, lz4 or zstd でそれなりに圧縮できストレージは節約できるであろう