我想使用一种数据结构来对时空数据(x、y、z和时间)进行排序。
目前，处理算法搜索一组4D(x、y、z、时间)点，给定一个球形(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树、3D kd树后跟时间距离检查（由Drew Hall建议），以及我目前拥有的算法。此外，我还被建议使用另一种数据结构，称为TSP（时间空间分区）树，它使用八叉树进行空间分区，并在每个节点上使用BSP进行时间分区，因此我也可能会测试它。
假设我记得，我一定会发布一些关于不同时间/空间半径配置的性能基准测试。
谢谢大家。
目前，处理算法搜索一组4D(x、y、z、时间)点，给定一个球形(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树、3D kd树后跟时间距离检查（由Drew Hall建议），以及我目前拥有的算法。此外，我还被建议使用另一种数据结构，称为TSP（时间空间分区）树，它使用八叉树进行空间分区，并在每个节点上使用BSP进行时间分区，因此我也可能会测试它。
假设我记得，我一定会发布一些关于不同时间/空间半径配置的性能基准测试。
谢谢大家。