kd-树是否适用于4D时空数据(x，y，z，time)？

Question

我想使用一个数据结构来排序时空数据(x，y，z，time).

目前，一个处理算法搜索一组4D (x，y，z，时间)点，给定一个球面(3d)空间半径和一个线性(1d)时间半径，标记每个点，其他点在这些半径内。原因是，经过处理后，我可以在O(1)时间内询问它的所有邻居的任何4D点。

然而，在一些常见的空间和时间半径配置中，该算法的第一次运行时间约为12小时。信不信由你，与我们的行业相比，这实际上是快速的。尽管如此，我还是想帮助加快初始运行速度，因此我想知道：是一个适用于4D时空数据的 kd树 ？。

请注意，我是，而不是，我正在寻找最近邻搜索或k最近邻搜索的实现。

更多信息：

一个示例数据集有45万个4D点。

有些数据集是时间密集的，因此按时间排序当然会节省处理，但仍然会导致许多距离检查。

时间用Excel格式的日期表示，典型的范围在30,000到39,000之间(大约).空间范围有时是较高的值，有时是较低的值，但每个空间坐标之间的范围与时间相似(例如，minX~ maxT-minT)。

更多信息：

我想我应该添加一些稍微无关紧要的数据，以防有人处理过类似的数据集。

基本上，我使用的数据代表了由多个传感器记录和证实的时空事件。涉及错误，因此只包括满足错误阈值的事件。

这些数据集的时间跨度为5-20年数据。

对于真正的老数据(>8岁)，事件往往空间密度很大，原因有两个: 1)当时可用的传感器相对较少，2)传感器放置在一起，以使附近的事件得到适当的证实，误差较小。可以记录更多的事件，但是它们的错误太高了。

对于较新的数据(<8岁)，事件往往时间非常密集，原因相反：( 1)通常有许多传感器可用，2)传感器的放置间隔较长。

因此，数据集通常不能说是时间稠密或空间密集(但只包含新数据的数据集除外)。

结论

我显然应该在这个网站上问更多的问题。

接下来我将测试几个解决方案，其中包括4d kd树，一个3d kd树，然后是时间距离检查(由Drew Hall建议)，以及我现在的算法。此外，我还提出了另一种数据结构TSP (时间空间分区)树，它使用八叉树作为空间，在每个节点上使用bsp作为时间，所以我也可以对其进行测试。

假设我还记得，我肯定会在不同的时间/空间半径配置上发布一些分析基准。

谢谢大家

Answer 1

为了对我的评论作一点补充，上面的回答是：

根据文献，kd-树需要欧几里德坐标的数据。它们可能不是严格必要的，但它们确实是足够的:保证所有的坐标都是欧几里得的，确保适用正常的空间规则，并使按其位置很容易地划分点和建立树结构成为可能。

时间有点奇怪。在狭义相对论的规则下，当你使用时间坐标时，你使用的是Minkowski度量，而不是标准的欧几里德度量。这就造成了各种各样的问题(其中最严重的是破坏“同时”的含义)，通常会使人们害怕时间坐标。这种恐惧是没有充分根据的，因为除非你知道你在研究物理，否则你的时间坐标在实践中几乎肯定是欧几里得。

坐标是欧几里德意味着什么？它应该独立于所有其他坐标。说时间是欧几里德坐标意味着你可以回答“这两个点在时间上紧密相连吗？”只看他们的时间坐标，忽略任何额外的信息。很容易理解为什么没有该属性可能会破坏一个按其坐标值划分点的方案；如果两个点的时间坐标可能完全不同，但仍然被认为是“近在时”，那么按时间坐标对它们进行排序的树将不能很好地工作。

欧几里德时间坐标的一个例子是在单个一致时区中指定的任何时间(如UTC时间)。如果你有两个时钟，一个在纽约，一个在东京，你知道，如果你有两个标有"12:00世界协调时“的测量值，那么它们是同时进行的。但是如果测量是在当地时间进行的，比如"12:00纽约时间“和"12:00东京时间”，你必须使用关于城市位置和时区的额外信息来计算两次测量之间的间隔时间。

因此，只要你的时间坐标是一致测量和正常的，它将是欧几里德，这意味着它将在kd树或类似的数据结构中工作得很好。

Answer 2

你还没有给出足够的信息来回答这个问题。

但可以肯定的是，一般来说，kd-树非常适合4(或5或6或.)维度数据--如果空间分布(或者在您的情况下是空间/时间分布)允许自己进行kd树分解。换句话说，这取决于(听起来熟悉吗？)。

kd-树只是空间分解的一种方法，适合于特定的局部搜索。当你进入更高的维度时，维度问题的诅咒当然会出现在你的头上，但是4d并不是很糟糕(你可能至少需要几百分)。

为了知道这是否对你有用，你必须分析一些其他的标准。是近似值的NN搜索足够好(这可以帮助很多)。树平衡很可能很昂贵吗？等。

Answer 3

如果将索引存储到在时间维度中排序的点，那么您不能首先在一维时间维度中执行初始剪枝，从而减少距离计算的数量吗？(或者说这是不是过于简单化了？)