让scipy的KD树支持插入和删除而无需重建。我学到的三件事 [P]

我构建了一个名为whitetree的小型库，用于处理不断到达的低维传感器数据的精确马氏距离最近邻搜索。这个想法并不新鲜。使用协方差的Cholesky因子进行白化，使马氏距离转化为欧氏距离，然后使用多个scipy cKDTree而不是一个，这样插入和删除就永远不需要完全重建。从中得出了三个测量结果，这些结果我还没有在任何地方明确看到过，因此我发布这些而不是推销。先说简要版本。在静态方面，它比sklearn的BallTree(mahalanobis)快40到300倍，比FAISS Flat在500k点时快7到60倍，在交错方面，它是唯一精确的选项，我发现在每次查询中能处理一次插入和一次删除。它只依赖于numpy和scipy，一个写线程和任意数量的读线程，结果在任何插入和删除混合后与静态cKDTree完全匹配（距离误差0.0）。教科书式的Bentley-Saxe在cKDTree上不起作用。cKDTree.query有固定的每次调用成本（在16点树上为1.6微秒，在50k点树上为3.2微秒），因此重要的是查询访问多少棵树，而不是它们有多大。二进制分解保持popcount(n)棵树，查询吞吐量降低到静态的20%到30%。几何尺寸比为32时，在百万点时有3或4棵树，并为批量保持47%到97%，单个查询保持20%到80%。FAISS的本机白化会降低召回率，但其搜索不会。PCAMatrix从1000*d子样本中以float32估计协方差。与float64暴力搜索相比，在条件数1e4时recall@10为0.967，在1e8时为0.841，在有1e4直流偏移的数据上为NaN。将相同的白化点交给IndexFlatL2，得分为1.000。我曾希望找到float64精度优势。但并没有。动态索引是否有帮助取决于更新和查询如何交错。在200k点的滑动窗口上，单线程，批量更新20k，中间有2000次查询，每批重建cKDTree（总计2.2秒）优于whitetree（14.9秒）。每一步都进行插入1 / 删除最早 / 查询1时，whitetree每秒约1,100步，FAISS IDMap2约20（remove_ids为O(n)），numpy 30到40，每次查询重建cKDTree约8步。简要设置。协方差使用float64，带有尺度相对的岭回归和Ledoit-Wolf收缩仅在n < 5d时使用。树按从大到小保存，每棵至少是下一棵的32倍，当新树破坏此规则时合并并重建。最大树的k-最近距离限定其余。删除使用墓碑。基准测试遵循ann-benchmarks和big-ann-benchmarks流式协议，召回率对比float64暴力搜索。代码、测试、基准脚本以及每个决策背后数字的设计说明位于https://github.com/whitetree-dev/whitetree。对于在流上运行精确低维kNN的人有一个问题。是否有我应该基准测试但遗漏的动态精确索引？我比较了FAISS IndexFlatL2与IDMap2、scipy cKDTree和sklearn BallTree每次查询重建，以及numpy暴力搜索。如果有什么在单核200k点上超过每秒~1,100次插入/删除/查询步骤，我想知道。