局所性を考慮したハッシュ

コンピュータサイエンスにおいて、局所性感知ハッシュ法( LSH ) は、類似の入力項目を高い確率で同じ「バケット」にハッシュするファジーハッシュ法です。 ^[1] (バケットの数は、入力項目の可能な全体よりもはるかに少ないです。) ^[1]類似の項目が同じバケットに入るため、この手法はデータクラスタリングや最近傍検索に使用できます。ハッシュ衝突が最小化されるのではなく最大化される点で、従来のハッシュ法とは異なります。あるいは、この手法は高次元データの次元を削減する方法と見なすこともできます。つまり、高次元の入力項目を、項目間の相対距離を維持しながら低次元バージョンに削減することができます。

ハッシュベースの近似最近傍探索アルゴリズムは、通常、2つの主要なハッシュ方法のいずれかを使用します。1つは、局所性敏感ハッシュ（LSH）などのデータ非依存方法、もう1つは局所性保存ハッシュ（LPH）などのデータ依存方法です。^{[2] [3]}

局所性保存ハッシュ法は、ランダムルーティングとユニバーサルハッシュ法を使用してメモリ競合とネットワーク輻輳を軽減する超並列アルゴリズムの実装において、データパイプラインを容易にする方法として当初考案されました。^{[4] [5]}

関数の有限族はLSH族^{[1] [6] [7]}として定義される 。 ${\displaystyle {\mathcal {F}}}$${\displaystyle h\colon M\to S}$

• 距離 空間、${\displaystyle {\mathcal {M}}=(M,d)}$
• 閾値、${\displaystyle r>0}$
• 近似係数、${\displaystyle c>1}$
• および確率${\displaystyle p_{1}>p_{2}}$

次の条件を満たす場合。任意の 2 つの点と、一様にランダムに選択されたハッシュ関数について: ${\displaystyle a,b\in M}$${\displaystyle h}$${\displaystyle {\mathcal {F}}}$

• の場合、（つまり、aとbが）少なくとも の確率で衝突し、${\displaystyle d(a,b)\leq r}$${\displaystyle h(a)=h(b)}$${\displaystyle p_{1}}$
• の場合、確率は最大で です。${\displaystyle d(a,b)\geq cr}$${\displaystyle h(a)=h(b)}$${\displaystyle p_{2}}$

このような家族は「-敏感」と呼ばれます。 ${\displaystyle {\mathcal {F}}}$${\displaystyle (r,cr,p_​​{1},p_{2})}$

あるいは^[8]類似度関数が与えられたアイテムの集合U上にLSH族を定義することも可能である。この設定では、LSHスキームはハッシュ関数Hの族とH上の確率分布Dと結合したもので、Dに従って選択された関数は各に対してを満たす。 ${\displaystyle \phi \colon U\times U\to [0,1]}$ ${\displaystyle h\in H}$${\displaystyle Pr[h(a)=h(b)]=\phi (a,b)}$${\displaystyle a,b\in U}$

-敏感なファミリーが与えられた場合、のAND構築またはOR構築によって新しいファミリーを構築することができます。^[1]${\displaystyle (d_{1},d_{2},p_{1},p_{2})}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {G}}}$${\displaystyle {\mathcal {F}}}$

AND 構築を作成するには、ハッシュ関数gの新しいファミリを定義します。ここで、各関数gはからのk 個のランダム関数から構築されます。ハッシュ関数 に対して、に対してすべて である場合に限り、 であるといえます。 のメンバーは任意の に対して独立に選択されるため、は -敏感なファミリです。 ${\displaystyle {\mathcal {G}}}$${\displaystyle h_{1},\ldots ,h_{k}}$${\displaystyle {\mathcal {F}}}$${\displaystyle g\in {\mathcal {G}}}$${\displaystyle g(x)=g(y)}$${\displaystyle h_{i}(x)=h_{i}(y)}$${\displaystyle i=1,2,\ldots ,k}$${\displaystyle {\mathcal {F}}}$${\displaystyle g\in {\mathcal {G}}}$${\displaystyle {\mathcal {G}}}$${\displaystyle (d_{1},d_{2},p_{1}^{k},p_{2}^{k})}$

OR 構築を作成するには、ハッシュ関数gの新しいファミリを定義します。ここで、各関数g はからのk 個のランダム関数から構築されます。ハッシュ関数 に対して、iの 1 つ以上の値に対してである場合に限り、 となります。 のメンバーは任意の に対して独立に選択されるため、は -敏感なファミリです。 ${\displaystyle {\mathcal {G}}}$${\displaystyle h_{1},\ldots ,h_{k}}$${\displaystyle {\mathcal {F}}}$${\displaystyle g\in {\mathcal {G}}}$${\displaystyle g(x)=g(y)}$${\displaystyle h_{i}(x)=h_{i}(y)}$${\displaystyle {\mathcal {F}}}$${\displaystyle g\in {\mathcal {G}}}$${\displaystyle {\mathcal {G}}}$${\displaystyle (d_{1},d_{2},1-(1-p_{1})^{k},1-(1-p_{2})^{k})}$

LSH は、次のようないくつかの問題領域に適用されています。

• 重複検出^[9]
• 階層的クラスタリング^{[10] [11]}
• ゲノムワイド関連研究^[12]
• 画像の類似性の識別
  • ビジュアルランク
• 遺伝子発現類似性の同定^[要出典]
• オーディオ類似性の識別
• 最近傍探索
• オーディオフィンガープリント^[13]
• デジタルビデオフィンガープリンティング
• 並列計算における共有メモリ構成^{[4] [5]}
• データベース管理システムにおける物理的なデータ構成^[14]
• 完全結合ニューラルネットワークの訓練^{[15] [16]}
• コンピュータセキュリティ^[17]
• 機械学習^[18]

LSH 族を構築する最も簡単な方法の 1 つは、ビット サンプリングです。^[7]このアプローチは、d次元ベクトル上のハミング距離に有効です。ここで、ハッシュ関数の族は、座標の 1 つ、つまり、上の点のすべての投影の族に過ぎません。ここで、は の 番目の座標です。からのランダム関数は、入力点からランダム ビットを選択するだけです。この族には、次のパラメーターがあります: 、。つまり、ハミング距離が最大 である任意の2 つのベクトルは、少なくとも の確率でランダム の下で衝突します。ハミング距離が 以上の任意のベクトルは、最大 の確率で衝突します。 ${\displaystyle \{0,1\}^{d}}$${\displaystyle {\mathcal {F}}}$${\displaystyle d}$${\displaystyle {\mathcal {F}}=\{h\colon \{0,1\}^{d}\to \{0,1\}\mid h(x)=x_{i}{\text{ ある }}i\in \{1,\ldots ,d\}\}} に対して$${\displaystyle x_{i}}$${\displaystyle i}$${\displaystyle x}$${\displaystyle h}$${\displaystyle {\mathcal {F}}}$${\displaystyle P_{1}=1-R/d}$${\displaystyle P_{2}=1-cR/d}$${\displaystyle x,y}$${\displaystyle R}$${\displaystyle h}$${\displaystyle P_{1}}$${\displaystyle x,y}$${\displaystyle cR}$${\displaystyle P_{2}}$

U が、列挙可能な項目の基底集合S のサブセットで構成され、対象の類似度関数がJaccard インデックス Jであるとします。πがSのインデックス上の順列である場合、とします。π の可能な選択ごとに、入力セットをSの要素にマッピングする単一のハッシュ関数h が定義されます。 ${\displaystyle A\subseteq S}$${\displaystyle h(A)=\min _{a\in A}\{\pi (a)\}}$

関数族H をそのような関数すべての集合として定義し、D を一様分布とします。2 つの集合が与えられた場合、 πの最小値が内にあるイベントに正確に対応するイベントが内にあります。hは一様ランダムに選択されたため、Jaccard 指数の LSH スキームを定義します。 ${\displaystyle A,B\subseteq S}$${\displaystyle h(A)=h(B)}$${\displaystyle A\cup B}$${\displaystyle A\cap B}$${\displaystyle Pr[h(A)=h(B)]=J(A,B)\,}$${\displaystyle (H,D)\,}$

n個の要素を持つ対称群のサイズはn ! であるため、完全な対称群から真にランダムな順列を選択することは、中程度の大きさのnに対しても実行不可能です。この事実のため、「最小値独立」な順列の族、つまり、ランダムに選択されたπの下でドメインの各要素が最小値になる確率が等しい順列族を見つけるための重要な研究が行われてきました。最小値独立な順列族のサイズは少なくとも であり、^[19]この上限は厳密であることが確立されています。^[20]${\displaystyle \operatorname {lcm} \{\,1,2,\ldots ,n\,\}\geq e^{n-o(n)}}$

最小独立族は実際の応用には大きすぎるため、最小独立性の2つの変形概念が導入されました。制限付き最小独立順列族と近似最小独立族です。制限付き最小独立性は、最大でk の特定の集合に制限された最小独立性プロパティです。^[21] 近似最小独立性は、最大で固定されたεだけプロパティと異なります。^[22]

Nilsimsaは、スパム対策に使用される局所性に敏感なハッシュアルゴリズムです。^[23] Nilsimsaの目的は、2つの類似したメッセージのダイジェストが互いに類似するように、電子メールメッセージのハッシュダイジェストを生成することです。この論文では、Nilsimsaが3つの要件を満たしていると示唆されています。

1. 各メッセージを識別するダイジェストは、自動的に生成できる変更に対して大幅に変化してはなりません。
2. エンコードは意図的な攻撃に対して堅牢でなければなりません。
3. エンコーディングでは、誤検知のリスクが極めて低く抑えられる必要があります。

この論文では、さまざまなファイルタイプを対象にテストを実施し、NilsimsaハッシュはTLSH、Ssdeep、Sdhashなどの他の類似性ダイジェスト方式と比較して、誤検出率が著しく高いことが判明しました。^[24]

TLSHは、セキュリティやデジタルフォレンジックのさまざまなアプリケーション向けに設計された、局所性に敏感なハッシュアルゴリズムです。^[17] TLSHの目的は、ダイジェスト間の距離が短いほど、対応するメッセージが類似している可能性が高いことを示すように、メッセージのハッシュダイジェストを生成することです。

TLSHの実装はオープンソースソフトウェアとして利用可能である。^[25]

モーゼス・チャリカー^[8]によるLSHのランダム射影法であるSimHash （arccos ^[26]とも呼ばれる）は、ベクトル間のコサイン距離の近似値を使用する。この手法はNP完全最大カット問題を近似するために使用された。^[8]

この手法の基本的な考え方は、最初に ランダムな超平面（通常の単位ベクトルrによって定義される）を選択し、その超平面を使用して入力ベクトルをハッシュすることです。

入力ベクトルvとrで定義された超平面が与えられた場合、 とします。つまり、 は 超平面vのどちら側にあるかによって異なります。このようにして、ランダムな超平面rの可能な各選択肢は、ハッシュ関数 として解釈できます。 ${\displaystyle h(v)=\operatorname {sgn}(v\cdot r)}$${\displaystyle h(v)=\pm 1}$${\displaystyle h(v)}$

二つのベクトルu,vの間に角度がある場合、次の式が成り立つ。 ${\displaystyle \theta (u,v)}$

${\displaystyle Pr[h(u)=h(v)]=1-{\frac {\theta (u,v)}{\pi }}.}$

との比は のとき少なくとも 0.87856 なので、^{[8] [27]} 2 つのベクトルがランダム超平面の同じ側にある確率はそれらの間の コサイン距離にほぼ比例します。${\displaystyle {\frac {\theta (u,v)}{\pi }}}$${\displaystyle 1-\cos(\theta (u,v))}$${\displaystyle \theta (u,v)\in [0,\pi ]}$

ハッシュ関数 ^[28]は、 d次元ベクトルを 整数の集合にマッピングします。この関数ファミリの各ハッシュ関数は、ランダムなと の選択によってインデックス付けされます。ここで、 は安定した分布から独立して選択されたエントリを持つd次元ベクトルであり、 は 範囲[0,r]から一様に選択された実数です。 が固定されている場合、 ハッシュ関数はによって与えられます。 ${\displaystyle h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }}):{\mathcal {R}}^{d}\to {\mathcal {N}}}$${\displaystyle {\boldsymbol {\upsilon }}}$${\displaystyle \mathbf {a} }$${\displaystyle b}$${\displaystyle \mathbf {a} }$${\displaystyle b}$${\displaystyle \mathbf {a} ,b}$${\displaystyle h_{\mathbf {a} ,b}}$${\displaystyle h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }})=\left\lfloor {\frac {\mathbf {a} \cdot {\boldsymbol {\upsilon }}+b}{r}}\right\rfloor }$

データに適合させるために、ハッシュ関数の他の構築方法が提案されている。 ^[29] 特に、k平均法ハッシュ関数は、投影ベースのハッシュ関数よりも実際には優れていますが、理論的な保証はありません。

セマンティックハッシュは、入力項目をアドレスにマッピングし、近い入力ほど意味的類似性が高くなるようにする手法です。^{[30]ハッシュコードは、}人工ニューラルネットワークまたはグラフィカルモデルのトレーニングによって見つけられます。^[要出典]

LSH の主な用途の 1 つは、効率的な近似最近傍検索アルゴリズムの手法を提供することです。LSH ファミリを考えてみましょう。アルゴリズムには、幅パラメータkとハッシュ テーブルの数Lという 2 つの主なパラメータがあります。 ${\displaystyle {\mathcal {F}}}$

最初のステップでは、ハッシュ関数gの新しいファミリを定義します。ここで、各関数g は、からk個の関数を連結することによって取得されます。つまり、ランダムハッシュ関数gは、からランダムに選択されたk 個のハッシュ関数を連結することによって取得されます。次に、アルゴリズムは、それぞれがランダムに選択された異なるハッシュ関数gに対応するL 個のハッシュテーブルを構築します。 ${\displaystyle {\mathcal {G}}}$${\displaystyle h_{1},\ldots ,h_{k}}$${\displaystyle {\mathcal {F}}}$${\displaystyle g(p)=[h_{1}(p),\ldots ,h_{k}(p)]}$${\displaystyle {\mathcal {F}}}$

前処理ステップでは、データセットSのすべてのn d次元ポイントをL 個のハッシュ テーブルのそれぞれにハッシュします。結果のハッシュ テーブルにはn 個の非ゼロ エントリしかないため、標準のハッシュ関数を使用して、各ハッシュ テーブルで使用されるメモリの量を削減できます。 ${\displaystyle O(n)}$

クエリ ポイントqが与えられると、アルゴリズムはL 個のハッシュ関数g を反復します。検討対象の各gについて、 qと同じバケットにハッシュされたデータ ポイントを取得します。 qから距離cR以内のポイントが見つかる とすぐに、プロセスは停止します。

パラメータkとL が与えられている場合、アルゴリズムには次のパフォーマンス保証があります。

• 前処理時間: 、ここでt は入力点pで関数を評価する時間です。${\displaystyle O(nLkt)}$${\displaystyle h\in {\mathcal {F}}}$
• スペース:データ ポイントを格納するためのスペース。${\displaystyle O(nL)}$
• クエリ時間: ;${\displaystyle O(L(kt+dnP_{2}^{k}))}$
• アルゴリズムは、少なくとも確率で、qから距離cR以内の点を見つけることに成功します(距離R以内に点が存在する場合) 。${\displaystyle 1-(1-P_{1}^{k})^{L}}$

固定された近似比と確率およびに対して、および（ ）を設定できます。この場合、次のパフォーマンス保証が得られます。 ${\displaystyle c=1+\epsilon }$${\displaystyle P_{1}}$${\displaystyle P_{2}}$${\displaystyle k=\left\lceil {\tfrac {\log n}{\log 1/P_{2}}}\right\rceil }$${\displaystyle L=\lceil P_{1}^{-k}\rceil =O(n^{\rho }P_{1}^{-1})}$${\displaystyle \rho ={\tfrac {\log P_{1}}{\log P_{2}}}}$

• 前処理時間: ;${\displaystyle O(n^{1+\rho }P_{1}^{-1}kt)}$
• スペース:データ ポイントを格納するためのスペース。${\displaystyle O(n^{1+\rho }P_{1}^{-1})}$
• クエリ時間: ;${\displaystyle O(n^{\rho }P_{1}^{-1}(kt+d))}$

tが大きい場合、ハッシュ時間を から短縮することが可能です。これは^[31]と^[32]によって示され、 ${\displaystyle O(n^{\rho })}$

• クエリ時間: ;${\displaystyle O(t\log ^{2}(1/P_{2})/P_{1}+n^{\rho }(d+1/P_{1}))}$
• 空間：;${\displaystyle O(n^{1+\rho }/P_{1}+\log ^{2}(1/P_{2})/P_{1})}$

また、係数が非常に大きくなる場合もあります。これは、たとえばJaccard類似度データで発生します。このデータでは、最も類似した近傍であっても、クエリとのJaccard類似度が非常に低いことがよくあります。^[33]では、クエリ時間（ハッシュコストは含まない）を1に削減し、同様にスペース使用量を 削減する方法が示されました。${\displaystyle 1/P_{1}}$${\displaystyle O(n^{\rho }/P_{1}^{1-\rho })}$

• ブルームフィルタ – 近似集合メンバーシップのデータ構造
• 次元の呪い - 多くの側面（「次元」）を持つデータを分析するときに生じる困難
• 特徴ハッシュ – ハッシュ関数を使用して特徴をベクトル化する
• フーリエ変換
• Geohash  – 2008 年に発明されたパブリック ドメイン ジオコーディング
• 多重線形部分空間学習 - 次元削減へのアプローチ
• 主成分分析 – データ分析の方法
• ランダムインデックス^[34]
• ローリングハッシュ – ハッシュ関数の種類
• 特異値分解 – 行列分解
• 疎分散メモリ – メモリの数学的モデル
• ウェーブレット圧縮 – データの圧縮と分析に使用される数学的手法Pages displaying short descriptions of redirect targets

• Samet, H. (2006)多次元およびメトリックデータ構造の基礎. Morgan Kaufmann. ISBN 0-12-369446-9 
• Indyk, Piotr ; Motwani, Rajeev ; Raghavan, Prabhakar ; Vempala, Santosh (1997)。「多次元空間における局所性保存ハッシュ」。第29 回 ACM コンピューティング理論シンポジウム議事録。STOC '97。pp. 618–625。CiteSeerX 10.1.1.50.4927。doi :  10.1145 / 258533.258656。ISBN 978-0-89791-888-6. S2CID  15693787。
• Chin, Andrew (1994). 「汎用並列計算のための局所性保存ハッシュ関数」(PDF) . Algorithmica . 12 (2–3): 170–181. doi :10.1007/BF01185209. S2CID  18108051.

• Alex Andoni の LSH ホームページ
• LSHKIT: C++ 局所性を考慮したハッシュ ライブラリ
• オプションでRedis経由で永続性をサポートするPython Locality Sensitive Hashingライブラリ
• Caltech 大規模画像検索ツールボックス: Kd-Trees、階層型 K-Means、および反転ファイル検索アルゴリズムに加えて、いくつかの LSH ハッシュ関数を実装する Matlab ツールボックス。
• Slash: 球状 LSH を実装した C++ LSH ライブラリ (著者: Terasawa, K., Tanaka, Y)
• LSHBOX: 大規模な画像検索のための局所性感知ハッシュのオープンソース C++ ツールボックス。Python と MATLAB もサポートします。
• SRS: p 安定ランダム射影に基づくメモリ内、スペース効率の高い近似最近傍クエリ処理アルゴリズムの C++ 実装
• TLSH は Github でオープンソース化されています
• TLSH (Trend Micro Locality Sensitive Hashing) の JavaScript ポートが node.js モジュールとしてバンドルされています
• TLSH (Trend Micro Locality Sensitive Hashing) の Java ポートが Maven パッケージとしてバンドルされました