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

Question

我想使用一种数据结构来对时空数据(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-tree、3d kd-tree 后跟时间距离检查(由 Drew Hall 建议)，以及我目前的算法。另外，有人建议我使用另一种称为 TSP(时空分区)树的数据结构，它使用一个八叉树来表示空间，在每个节点上使用一个 bsp 来表示时间，所以我也可以测试一下。

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

谢谢大家

Answer 1

稍微扩展一下我对上述答案的评论:

根据文献，kd-trees 需要具有欧几里得坐标的数据。它们可能不是绝对必要的，但它们肯定是足够的:保证所有坐标都是欧几里得坐标确保空间的正常规则适用，并且可以轻松地按位置划分点并构建树结构。

时间有点奇怪。根据狭义相对论的规则，当您使用时间坐标时，您使用的是闵可夫斯基度量，而不是标准的欧几里德度量。这导致了各种各样的问题(其中最严重的破坏了“同时性”的意义)，并且通常使人们害怕时间坐标。不过，这种恐惧并没有充分的根据，因为除非你知道你正在研究物理，否则你的时间坐标几乎肯定在实践中实际上是欧几里得。

坐标是欧几里得是什么意思？它应该独立于所有其他坐标。说时间是欧几里得坐标意味着你可以回答“这两点在时间上是否靠得很近？”这个问题。通过查看仅他们的时间坐标，并忽略任何额外信息。很容易理解为什么不具有该属性可能会破坏按坐标值划分点的方案；如果两个点可以具有截然不同的时间坐标但仍被视为“时间接近”，那么按时间坐标对它们进行排序的树将不会很好地工作。

欧几里德时间坐标的一个例子是在一个单一的、一致的时区(如 UTC 时间)中指定的任何时间。如果您有两个时钟，一个在纽约，一个在东京，您就会知道，如果您有两个标记为“12:00 UTC”的测量值，那么它们是同时进行的。但是如果测量是在本地时间进行的，那么一个是“纽约时间 12:00”，一个是“东京时间 12:00”，你必须使用关于城市的位置和时区的额外信息来计算两次测量之间经过了多少时间。

因此，只要您的时间坐标始终如一地被测量并且是理智的，它将是欧几里德的，这意味着它可以在 kd 树或类似的数据结构中正常工作。