我想使用数据结构对时空数据（x、y、z、时间）进行排序。
目前，处理算法搜索一组 4D (x,y,z,time) 点，给定球面 (3d) 空间半径和线性 (1d) 时间半径，标记每个点，哪些其他点在这些半径内。原因是处理后，我可以在 O(1) 时间内询问任何 4D 点的所有邻居。
然而在一些常见的空间和时间半径配置中，算法的第一次运行大约需要 12 个小时。信不信由你，与我们行业中的现有产品相比，这实际上速度很快。不过，我想帮助加快初始运行速度，所以我想知道：kd-tree是否适合 4D 时空数据？
请注意，我不是在寻找最近邻搜索或 k-最近邻搜索的实现。
更多信息：
一个示例数据集有 450,000 个 4D 点。
一些数据集是时间密集的，因此按时间排序肯定会节省处理时间，但仍会导致许多距离检查。
时间由 Excel 样式的日期表示，典型范围在 30,000-39,000（大约）之间。空间范围有时是较高的值，有时是较低的值，但每个空间坐标之间的范围与时间相似（例如 maxX-minX ~ maxT-minT）。
更多信息：
我想我会添加一些稍微不相关的数据，以防有人处理过类似的数据集。
基本上，我正在处理表示由多个传感器记录和证实的时空事件的数据。涉及错误，因此仅包括满足错误阈值的事件。
这些数据集的时间跨度介于 5-20 年的数据之间。
对于真正的旧数据（> 8 年），事件通常在空间上非常密集，原因有两个：1）当时可用的传感器相对较少，2）传感器被放置在一起，以便附近的事件可以正确以低误差证实。可以记录更多事件，但它们的错误太高
对于较新的数据（<8 年），事件通常非常时间密集，原因恰恰相反：1）通常有许多传感器可用，2）传感器以固定间隔放置在更远的距离上。
因此，通常不能说数据集只有时间密集或空间密集（仅包含新数据的数据集除外）。
结论
我显然应该在这个网站上问更多问题。
我将在接下来测试几个解决方案，其中包括 4d kd-tree、3d kd-tree，然后是时间距离检查（由 Drew Hall 建议），以及我拥有的当前算法。另外，有人建议我使用另一种称为 TSP（时间空间分区）树的数据结构，它使用八叉树作为空间，在每个节点上使用 bsp 作为时间，所以我也可以对其进行测试。
假设我记得，我一定会发布一些关于不同时间/空间半径配置的分析基准。
谢谢大家