7次元空間に約10 ^ 4ポイントがあります。特定のアプリケーションでは、特定の範囲内にあるすべてのポイントを見つけるために、この入力に対して ~10^6 の範囲クエリを作成する必要があります。このアプリケーションでは、すべてのクエリが同じ範囲サイズを使用しています。この問題に適したデータ構造は何ですか?
kd-tree が適しているように見えますが、7 次元で出力サイズが小さい場合、クエリの時間の複雑さはほぼ直線的です。もう 1 つの解決策はレンジ ツリーですが、このアプリケーションでは少数の入力に対して構成するには複雑すぎるようです。また、範囲が一定のサイズであるという事実を有利に利用しているこれらの構造は見当たりません。たとえば、これが 1D の問題である場合、クエリはすべて、たとえばサイズ 10 の範囲内にあるポイントを、数直線に沿ったさまざまな場所で求めることになります。