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

Question

我想在 3 到 20 个维度上存储 50 到 10000 个向量。我想知道在哪个结构中存储向量，以便能够快速解决最近邻或近似最近邻问题。我将使用欧几里德、曼哈顿、最大和加权曼哈顿度量。

我开始研究这个问题并发现(如果我错了请纠正我)当维度的数量远小于向量的数量时，kd 树就会做到这一点。性能可以是深度次线性的 (O(log(n)))。

问题是结构变化非常快。每个向量在程序运行过程中可以变化数千次。此外，矢量不需要保持它们的大致位置或比例。整个结构可以“穿越”R^n。

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

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

Answer 1

你应该做一个 amortized analysis在不同数据结构上运行的算法。结果将根据您正在使用的特定数据结构上的操作顺序而有所不同。

我建议也看看 R-tree .查看静态网格可能也是一个好主意，因为如果对数据结构的更新比查询更频繁，则更新该结构可能会执行得相当好。

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

您还应该查看有关多维树的文献。您肯定会在其中找到对数据结构或您尚未考虑过的数据结构进行更有效操作的建议。但是我还不能推荐文学作品。