2

私はすでにこの質問を読みましたが、残念ながら役に立ちませんでした。

私が理解していないのは、どのバケットが高次元空間クエリ ベクトルに割り当てられるかを理解した後で何をするかということですq。局所性に依存するファミリ関数のセットを使用して、低次元 (次元) ハッシュ コードh_1,h_2,...,h_nに変換したとします。qnc

次に、割り当てられcたバケットのインデックスでありq、(うまくいけば) 最も近い隣人にも割り当てられます。たとえば、100 個のベクトルがあるとします。

さて、 の NN を見つけるために行うことは、これら100個のベクトルqの間の距離を計算することですが、それは正しいですか? つまり、 の使用はインデックス作成のためだけです (どのバケットに割り当てるかを決定するためだけに使用されます) ですね。qcq

この調査 (セクション 2.2) で説明されているように、「ハッシュ テーブル ルックアップ」(前述のアプローチ) に代わる別の解決策は「高速距離近似」ですc。データセット内の各要素に関連するハッシュ コード。ハッシュコードが低次元空間にあり、距離の計算が高速であるため、これは高速であると想定されています（たとえば、ハッシュコード空間がバイナリの場合、XOR演算子を使用してハミングをすばやく計算できます2 つのハッシュ コード間の距離）。

さて、私が疑問に思っているのは、2つの方法の利点/欠点は何ですか? 他のアプローチではなく、あるアプローチを使用する必要があるのはなぜですか?

4

1 に答える 1

2

最初に説明した方法は、近似最近傍検索を説明しています。はい、 bin 内の他の 100 個のアイテムをチェックするだけで最高のパフォーマンスがc得られますが、他の隣接するバケットで適切な候補を見逃すリスクが高くなります。

緯度/経度座標の単純なハッシュ スキームはGeohashです。同じ Geohash ブロック内のアイテムを調べることで最寄りのショップを見つけることができますが、グリッド境界の近くでは不正確な結果が生じる可能性があります。

高速距離近似の一例は、ここで見つけることができます。これは、十分に小さいハミング距離で画像の一致を見つけます ( pHashを使用します)。ハッシュの長さはわずか 64 ビットであるため、ラップトップ GPU は 1 秒あたり 7 億回の比較を実行できます。すべての画像がチェックされ、インデックスやハッシュのデータ構造は使用されないことに注意してください。このようにして、すべての一致を取得することが保証されます (pHash スペース内)。

于 2016-06-14T07:50:55.067 に答える