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

Question

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

我开始研究这个问题，并发现(如果我错了，请纠正我)，当维度的数量比向量的数量小得多时，kd-tree可以做到这一点。性能可以是深次线性的(O(log(N)。

问题是，结构将很快发生变化。在程序的运行过程中，每个向量可能会发生数千次变化。此外，向量不需要保持它们的近似位置或规模。整个结构可以通过R^n“旅行”。

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

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

Answer 1

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

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

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

您还应该查看可用于多维树的文献。你肯定会找到对数据结构进行更有效操作的建议，或者你还没有考虑过的建议。不过，我还不能推荐文学作品。