我在 7 维空间中有大约 10^4 个点。对于某个应用程序，我需要对此输入进行 ~10^6 范围查询，以查找位于给定范围内的所有点。在此应用程序中，所有查询都使用相同的范围大小。这个问题的合适数据结构是什么？
kd-tree 似乎很合适，但对于 7 维和小输出大小，它的查询时间复杂度几乎是线性的。另一种解决方案是范围树，但对于此应用程序中的少量输入而言，构建它似乎过于复杂。此外，我没有看到任何这些结构利用范围是恒定大小这一事实来发挥它们的优势。例如，如果这是一个 1D 问题，则所有查询都将要求位于大小为 10 的范围内的点，例如，沿数轴的不同位置。