giz*_*gok 12 python kdtree scipy
我有一组要为其构建KD树的点.一段时间后,我想定期为这个KDTree添加几点.在scipy实现中有没有办法做到这一点
Ano*_*sse 16
kd-tree的问题在于它们不是为更新而设计的.
虽然您可以在某种程度上轻松插入对象(如果您使用基于指针的表示,它需要比基于数组的树更多的内存),并使用诸如逻辑删除消息之类的技巧进行删除,执行此类更改将降低树的性能.
我不知道逐步重新平衡kd树的好方法.对于一维树木,你有红黑树,B树,B*树,B +树等等.由于旋转轴因此不同的分类,这些显然不适用于kd树.所以最后,使用kd-tree,最好只收集更改,并不时进行完整的树重建.那么至少这部分树会很好.
但是,存在类似的结构(在我的实验中经常优于kd树!):R*-tree.它不是执行二进制分割,而是使用矩形边界框来收集对象,并且已经将很多想法用于使树成为动态数据结构.这也是R*-tree比R-tree执行得更好的地方:它对kNN搜索有更聪明的分割,并且它执行增量重新平衡以改善其结构.