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

Question

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

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

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

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

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

Answer 1

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

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

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

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