1

周期的な境界条件を持つ D 次元空間に N ポイントの点群があります。ここで、N は 500 から 10^8 の範囲で、D は 1 から 20 の範囲です。一緒。点群の各点について、その点に最も近い k 個を見つける必要があります。また、各ポイントからの距離、特に maxnorm 距離内にいくつのポイントが存在するかを調べる必要もあります。どのポイントが半径内にあるかを知る必要はありませんが、いくつあるかはわかりませんが、追加すると便利です。

私は kd-trees を試しましたが、それらはラッピング境界を処理しません。また、より大きなツリーの場合、複製は実行できません。さらに、高次元では遅くなります。

Vantage Point Trees に出会い、いくつかのコードを試してみましたが、kd ツリーよりも低速です。私が見つけたコードは再帰的な検索方法を使用していますが、バッチ処理はありません。プラス面の 1 つは、ラッピング条件をネイティブに処理できるため、重複する必要がないことです。

反復アプローチに変換し、バッチ検索ができるかどうかを確認することで、VP ツリーからさらにパフォーマンスを引き出すことができるかどうかを確認しようとしていますが、考えがありました。これらのデータ構造はすべて、任意のクエリ ポイントの最近傍を見つけるために機能しますが、クエリ ポイントはポイント クラウド内のポイントに制限されています。この制限により、よりパフォーマンスの高い構造が可能になる可能性があると思います（おそらくある種のナビゲーションメッシュですか？）。これを処理する構造を検索しようとしましたが、私のgoogle-fuは失敗しています。だから、誰かが次を処理できるデータ構造を知っているかどうか疑問に思っています:

  • 500 ～ 10^8 ポイントなど、少数および多数のポイントを処理する
  • 最大 20 次元を処理
  • 周期的な境界で作業する (つまり、平らなトーラス)
  • maxnorm距離で作業します（ソフト要件。ユークリッドは、手動で選別できる潜在的なリストを提供できますが、maxnormが優先されます）
  • クエリ ポイントまでの k-NN を検索し、クエリ ポイントまでの距離でいくつのポイントが存在するかを検索できます
  • クエリ ポイントは構造内のポイントであり、任意のポイントではありません
  • クエリはバッチ処理できます。つまり、点群のすべての点について k 番目の NN を見つける必要があります。また、各点 i について、d[i] 内にいくつの点が存在するかを調べる必要があります。つまり、各ポイントには異なる検索半径があります。
  • 挿入または削除をサポートする必要はありません。

ありがとう

4

2 に答える 2

2

あなたの非常に複雑な問題に対する完全で明確な答えがあるとは思えないので、私の考えを共有します。問題の仕様は、うまく連携しない多くのものを組み合わせています (高次元、非ユークリッド メトリック、まったく異なる種類のクエリ)。アルゴリズムが一般的なケースを想定する必要がある場合、必然的に遅くなります。

まず、適切なデータ構造が知られている特殊なケースを整理しましょう。

  • 次元が 1 の場合は、並べ替えられたマップを使用します。
  • ディメンションが 2 ～ 3 (おそらく 4) の場合、並べ替えられたルックアップと地理データベースが最適です。 https://en.wikipedia.org/wiki/R-tree
  • ポイントの次元が高いが相関が非常に強い場合、次元削減により、ポイント クラウドをそのような低次元のポイント クラウドにマッピングし、問題を簡単なものに減らすことができます。 https://en.wikipedia.org/wiki/Dimensionality_reduction
  • ポイント数が 10^6 未満の場合、ブルート フォースが最も安価です。すべてのポイントのメトリックを使用して距離を計算し、k 個の結果に対して部分的な並べ替えを行うだけです。これらの単純なキャッシュ コヒーレント計算は、ツリー構造を使用するよりも高速です。 http://en.cppreference.com/w/cpp/algorithm/partial_sort
  • k が制限されている場合 (k <= 20 など)、クエリ時間を最適化する場合は、すべての結果を含むテーブルを事前計算します。
  • 周期的な次元がほとんどない場合は、それらを処理するために kd-tree アルゴリズムを適応させる必要があると思います (Vantage Point Trees の次元と同様に、それらの次元に対してより複雑な比較ノードを追加します)。

これがすべて当てはまらない場合 (実用的なアプリケーションを念頭に置いている場合は、私たちと共有してください)、あなたのケースは非常に一般的です。

あなたが言及したアルゴリズムに加えて、Geometric Near-Neighbor Access trees (GNAT) も試してみてください。 http://infolab.stanford.edu/~sergey/near.html それらは一般的なメトリック (あなたのものを含む) に適用され、不均一な分布も処理します。

また、皆さんの期待は非常に高いと思います。ユークリッド メトリックのみで問題を解決する優れた kd-tree 実装 (たとえば、https://github.com/mariusmuja/flann ) と比較できます。これに時間がかかる場合は、より一般的なメトリクスがより速く解決されると期待するべきではありません。

確かに、より一般的な方法では、クエリがクラウド内のポイントであるという制約を使用できません。そのような解決策があれば非常に興味があります。

于 2016-05-12T09:01:34.457 に答える