移动物体的近似,增量最近邻算法

Question

赏金

这个问题提出了几个问题.赏金将回答整体上的问题.

---

这是我一直在玩的问题.

注意我对不在欧几里得空间的解决方案特别感兴趣.

有一组Actors形成一个大小为K的人群.d(ActorA,ActorB)对于任何两个演员来说,距离很容易计算(解决方案应该适用于'距离'的各种定义)并且我们可以找到任何给定Actor使用的N个最近邻居的集合任何一种已建立的算法.

这个邻居集在第一瞬间是正确的,但是Actors总是在移动,我想维护每个Actor的N个最近邻居的进化列表.我感兴趣的是近似解决方案,它比完美解决方案更有效.

1. 在引入错误之后,解决方案应该收敛到正确性.
2. 如果错误变得太大而有时执行完全重新计算是可以接受的,但检测这些错误应该是便宜的.

到目前为止,我一直在使用一个朋友的朋友算法:

recompute_nearest (Actor A)
{
    Actor f_o_f [N*N];
    for each Actor n in A.neighbours
        append n to f_o_f if n != A and n not in f_o_f

    Distance distances [N*N];
    for 0 <= i < f_o_f.size
        distances [i] = distance (A, f_o_f [i])

    sort (f_o_f, distances)
    A .neighbours = first N from f_o_f
}

当人群缓慢移动且N适当大时,这表现得相当好.它在小错误之后收敛,满足第一个标准,但是

• 我没有很好的方法来检测大错误,
• 我没有关于错误大小和频率的定量描述,
• 它在实践中趋同但我不能证明它总会如此.

你能帮忙解决这些问题吗？

另外,你知道任何表现良好的替代方法吗？

• 当人群快速移动时
• 当一些演员快速移动时,
• 当N很小时,
• 当人群在某些地方稀疏而在其他地方密集时,
• 或者使用特定的空间索引算法？

我正在努力的扩展是在一个邻居快速移动的情况下,将朋友的朋友概括为一个朋友的朋友.我怀疑这不能很好地扩展,如果没有量化错误,很难得出正确的参数.

我欢迎所有的建议!这是一个有趣的小问题:-)

---

值得注意的建议到目前为止

Fexvez:取样随机的额外邻居,样本大小取决于Agent的速度.从即将搬入的地区取样可能也会有所帮助.

当代理speed*delta_time超过距离最远的已知邻居的距离时,对邻居进行重新采样.

维护Delaunay三角剖分,它是最近邻图的超集.仅考虑一个最近邻居.

David Mount的ANN库 似乎无法处理移动的物体.

Answer 1

统计学中一种非常简单且非常快速的方法是使用随机线性投影.这些可以帮助您快速确定群集和邻居.通过更多投影,您可以获得更高的准确性(我相信,解决有关错误的问题).

本文对几种方法进行了广泛的定量分析,包括与RLP相关的新方法(DPES).

本文讨论了RLP的使用,即使在移动点的背景下也包括用于距离保持.

本文讨论了RLP的运动规划,并详细介绍了几种启发式方法.

RLP方法是:

1. 非常快
2. 导致可调节精度和速度的近似值
3. 距离和角度保持(可证明)
4. 轻松扩展到大尺寸和大量物体
5. 有助于降低维数
6. 导致紧凑的投影(例如,可以投射到分层二进制分区)
7. 灵活:你可以投射到你认为对你有益的任何空间 - 通常是R ^ d,但是投射到2 ^ d(即维度d的二进制空间)也是允许的,只会降低给定的准确度#预测.
8. 统计上有趣

嵌入到一个低维空间后,邻居的计算是很容易的,因为这是,比方说,在同样的区域分级(如果bin中的预测成网格)很可能是在原来的空间接近的预测.

虽然原始数据的维度很小(甚至10很小),但是快速投影到预选网格的能力对于识别和计算邻居非常有用.

最后,您只需更新那些位置(或相对位置,如果您居中和缩放数据)已更改的对象.

对于相关的工作,请查看Johnson-Lindenstrauss引理.