什么数据结构用于快速变化的最近邻居搜索？

Question

我想存储从3到20个维度的50到10 000个向量。我想知道在哪种结构中存储向量，以便能够快速求解最近邻或近似近邻问题。我将使用欧几里得，曼哈顿，马克斯和加权曼哈顿度量。

我开始读到这个问题，并发现（纠正我，如果我错了），当维数比这个向量的数量小得多时，kd-trees会这样做。性能可以是深度次线性的（O（log（n）））。

问题是，结构将变化非常迅速。每个矢量在程序过程中可以改变数千次。此外，矢量不需要保持它们的近似位置或比例。整个结构可以通过R^n“旅行”。

问题是，为了保持kd-tree的高性能，需要时不时的重新平衡。此操作可能与重建整个树一样昂贵。

如何解决kd-tree快速变化的问题？

Answer 1

您应该对在不同数据结构上运行的算法执行amortized analysis。结果将根据您正在使用的特定数据结构的操作顺序而变化。我建议也看看R-tree。查看静态网格也可能是一个好主意，因为如果数据结构的更新比查询更频繁，那么更新该结构可能会相当好地执行。

如果对数据结构的更新太频繁，那么最好不要每次更改都更新数据结构，而是先使用过时的数据结构，然后对所有更改的元素执行搜索。这样，您可以对数据结构进行批量更改，这可能会更有效。这是摊销分析也可以回答的一件事。

你也应该看看可用于多维树的文献。他们肯定会找到更有效的数据结构操作建议，或者你还没有想过的建议。但是我不能推荐文献。