2

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

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

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

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

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

4

1 回答 1

2

您应该对在不同数据结构上运行的算法进行摊销分析。结果将根据您正在使用的特定数据结构上的操作顺序而有所不同。

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

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

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

于 2013-01-04T07:18:25.253 回答