問題タブ [approximate-nn-searching]

大きな 3D ポイント データセット内の隣接ノードの正確な数を見つけようとしています。目標は、データセットの各ポイントが、指定された半径の領域内のすべての可能な近隣を取得することです。FLANNは、ブルートフォース検索と比較して、より低い次元のデータが正確な隣人を取得できることを保証しますが、そうではないようです。隣人はさらなる計算に不可欠であるため、正確な数が必要です。半径を少し大きくしてテストしましたが、これが問題ではないようです。FLANNまたは他のC++ライブラリを使用して正確な隣人を計算する方法を知っている人はいますか?

コード：

最も人気のあるクエリをキャッシュし、新しいクエリがキャッシュ内で同様のクエリを見つけて同じ結果を返そうとするシステムを実装したいと考えています。可能な限り一般的なものにしたいので (クエリは短いテキスト、画像、さらにはオーディオ トラックでもかまいません)、ベクトル空間でのクエリの表現に基づく近似最近傍 (ANN) アプローチを使用します。

私の質問は次のとおりです。クエリをベクトルとして表現する最も効率的な方法は何ですか (ANN の入力として使用されます)。

免責事項: 私はニューラル ネットワークやディープ ラーニングについて何も知りません。

Product Quantization を使用したVLAD および Fisher ベクトルは、適切な画像検索に近似最近傍を使用する方法の良い例です。ただし、Neural Networks のアプローチが Bag of Words や VLAD よりも正確であることが証明されています。

私の質問は次のとおりです。

1. NN 記述子の作成は、従来のアプローチ (VLAD や Fisher Vector など) よりも高速ですか?
2. 似たような画像を見つけるために、従来の ANN アプローチを NN コードで使用できますか? そうでない場合、NN コードはどのように索引付けされますか?
3. NN コード間の類似性を測定するためにメトリック距離を使用できますか?

ANN 検索は、効率の点で NN 検索よりも優れていることが知られており、一部の手法では、コンパクトな表現からストレージ スペースを削減します。しかし、有効性に関してはどうなるでしょうか？網羅的検索で最近傍を見つけなくても、同じパフォーマンスを達成することは可能ですか?

非常に高いレベルでは、これは最近傍探索問題に似ています。

ウィキから:「空間 M 内の点の集合 S とクエリ点 q ∈ M が与えられた場合、S 内で q に最も近い点を見つける」。

しかし、いくつかの重要な違いがあります。仕様:

• 各点は k 個の変数によって記述されます。
• 変数はすべて数値ではありません。混合データ型: string、int など。
• 未知のすべての変数のすべての可能な値 - しかし、それらは合理的に小さなセットから来ています。
• 検索するデータセットには、すべての k 変数に対して同じ値を持つ複数のポイントがあります。
• これを見る別の方法は、多くの重複ポイントがあることです。
• 各ポイントについて、重複の数を頻度として呼び出しましょう。
• クエリ ポイント q が与えられた場合、p の頻度が少なくとも 15 になるような最近傍 p を見つける必要があります。

NNS や統計的分類、ベスト ビン マッチに関しては、さまざまなアルゴリズムがあるようです。

私はすべてのバリエーションで少し迷っています。使用できる標準アルゴリズムは既にありますか。または、いずれかを変更する必要がありますか?