c++ - ハミング距離に基づく高速NN類似性検索のためのLSH?

Question

多次元ベクトルに対する高速 NN 検索を調査しています。(特徴ベクトルを抽出して計算した後に類似の画像を検索するようなもの)

私は現在、キーポイントをビット文字列で記述するORBを使用しています。
2 つのディスクリプタを比較するには、ORB にハミング距離が必要です。

LSH がユークリッド距離 (L2) またはマナサン距離 (L1) に基づいてハッシュ テーブルを計算することを読みました。これは、LSHisn'tがハミング距離を必要とするベクトル比較のオプションであることを意味しますか?

編集

LSH は、最初のビット文字列の部分文字列に基づいてハッシュ テーブルを作成するため、ハミング距離で動作します。これが動作する理由です。

Answer 1

ハミング距離は、ブール値ベクトルに制限された L1 (マンハッタン) 距離に相当します。

Answer 2

いいえ、LSH は L1 または L2 (ユークリッド距離) に限定されません。これは、ハイパープレーンのパーティショニングまたはインデックス作成の高度な方法にすぎません。

LSH は、クエリ ベクトルに対する最も可能性の高い KNN ベクトルを見つけるのに役立ちます。その後、l1/l2/cosine/damming コードを使用して、詳細な類似度または距離の計算を行うことができます。