8 algorithm math search multidimensional-array data-structures
我想使用数据结构来排序时空数据(x,y,z,时间).
目前,处理算法搜索一组4D(x,y,z,时间)点,给定球形(3d)空间半径和线性(1d)时间半径,标记每个点,其他点在这些半径内.原因是在处理之后,我可以在O(1)时间内为所有邻居询问任何4D点.
然而,在空间和时间半径的一些常见配置中,算法的第一次运行大约需要12小时.信不信由你,与我们行业中存在的情况相比,这实际上是快速的.不过,我想帮助加快初始运行,所以我想知道:是一个kd树适合四维时空数据？
请注意,我不是在寻找最近邻搜索或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作为时间,所以我也可以测试它.
假设我记得,我一定会在不同的时间/空间半径配置上发布一些分析基准.
谢谢大家
在我的评论上稍微扩展一下上面的答案:
根据文献,kd-tree需要具有欧几里德坐标的数据.它们可能不是绝对必要的,但它们肯定是足够的:保证所有坐标都是欧几里德确保正常的空间规则适用,并且可以根据它们的位置轻松划分点并构建树结构.
时间有点奇怪.在狭义相对论规则下,当您使用时间坐标时,使用Minkowski度量,而不是标准欧几里德度量.这导致了各种各样的问题(其中最严重的是破坏了"同时性"的含义),并且通常使人们害怕时间坐标.然而,这种恐惧并不是很有根据,因为除非你知道你正在研究物理学,否则你的时间坐标几乎肯定会在实践中成为欧几里得.
坐标是欧几里德是什么意思？它应该独立于所有其他坐标.说时间是欧几里德坐标意味着你可以回答"这两点是否在时间上紧密相连？"的问题.通过看只在自己的时间坐标,忽略任何额外的信息.很容易理解为什么不让该属性破坏一个用坐标值划分点的方案; 如果两个点可以具有完全不同的时间坐标但仍然被认为是"接近时间",那么按时间坐标对它们进行排序的树将不会很好地工作.
欧几里德时间坐标的一个示例是在单个一致时区(如UTC时间)中指定的任何时间.如果您有两个时钟,一个在纽约,一个在东京,您知道如果您有两个标记为"12:00 UTC"的测量,那么它们是同时拍摄的.但是如果测量是在当地时间进行的,那么一个人说"纽约时间12:00",一个是"东京时间12:00",你必须使用关于城市的位置和时区的额外信息来弄清楚两次测量之间经过了多长时间.
因此,只要你的时间坐标一直被测量和理智,它就会是欧几里德,这意味着它在kd树或类似的数据结构中可以正常工作.