有没有办法在Scipy中向KD树实现添加点 [英] Is there any way to add points to KD tree implementation in Scipy

问题描述

我有一组要为其构建 KD 树的点.一段时间后，我想定期向此 KDTree 添加更多点.在 scipy 实现中有什么方法可以做到这一点

I have a set of points for which I want to construct KD Tree. After some time I want to add few more points to this KDTree periodically. Is there any way to do this in scipy implementation

推荐答案

k-d-trees 的问题在于它们不是为更新而设计的.

The problem with k-d-trees is that they are not designed for updates.

虽然您可以稍微轻松地插入对象(如果您使用基于指针的表示，它比基于数组的树需要更多的内存)，并使用墓碑消息等技巧进行删除，但执行此类更改将降级树的性能.

While you can somewhat easily insert objects (if you use a pointer based representation, which needs substantially more memory than an array-based tree), and do deletions with tricks such as tombstone messages, doing such changes will degrate the performance of the tree.

我不知道增量重新平衡 k-d 树的好方法.对于一维树，你有红黑树、B 树、B* 树、B+ 树等等.由于旋转轴和不同的排序，这些显然不适用于 k-d-trees.所以最后，对于 k-d-tree，最好只收集更改，并不时进行完整的树重建.那么至少这棵树的这一部分会相当不错.

I am not aware of a good method for incrementally rebalancing a k-d-tree. For 1-dimensional trees you have red-black-trees, B-trees, B*-trees, B+-trees and such things. These don't obviously work with k-d-trees because of the rotating axes and thus different sorting. So in the end, with a k-d-tree, it may be best to just collect changes, and from time to time do a full tree rebuild. Then at least this part of the tree will be quite good.

但是，存在一个类似的结构(在我的实验中，它的性能通常优于 k-d-tree！):R*-tree.它没有执行二进制拆分，而是使用矩形边界框来收集对象，并且花了很多心思使树成为动态数据结构.这也是 R*-tree 比 R-tree 表现更好的地方:它对 kNN 搜索进行了更巧妙的拆分，并执行增量重新平衡以改进其结构.

However, there exists a similar structure (that in my experiments often outperforms the k-d-tree!): the R*-tree. Instead of performing binary splits, it uses rectangular bounding boxes to collect objects, and a lot of thought was put into making the tree a dynamic data structure. This is also where the R*-tree performs much better than the R-tree: it has a much more clever split for kNN search, and it performs incremental rebalancing to improve its structure.

这篇关于有没有办法在Scipy中向KD树实现添加点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！