开源 whitetree:免重建的动态精确最近邻索引,比 FAISS 快数十倍
monononon34 · reddit · 2026-09-14
作者发布开源库 whitetree，用于低维流式数据的精确 Mahalanobis 最近邻搜索：先用协方差 Cholesky 白化把 Mahalanobis 距离变成欧氏距离，再维护多棵尺寸几何比约 32 的 scipy cKDTree，使插入/删除无需全量重建。
关键测量结论：
- 静态查询比 sklearn BallTree(mahalanobis) 快 40–300 倍，比 FAISS Flat 快 7–60 倍（50 万点）。
- 教科书式 Bentley-Saxe 二分拆树在 cKDTree 上不奏效：cKDTree.query 有固定单次调用开销，查询性能取决于访问树的数量而非大小；二分方案只剩 20–30% 吞吐，几何比 32 的方案可保留 47–97%（批量）/20–80%（单查询）。
- FAISS 自带 PCAMatrix 白化会掉召回（条件数 1e8 时 recall@10=0.841，含大直流偏置时直接 NaN），但同样白化后的数据交给 IndexFlatL2 检索召回为 1.000——问题在白化估计而非搜索。
- 动态索引是否划算取决于更新与查询的交错模式：批量更新+查询场景下每批重建 cKDTree 反而更快（2.2s vs 14.9s）；而逐步 insert/delete/query 交错时 whitetree 达 1100 steps/s，远超 FAISS IDMap2（20，removeids 是 O(n)）。
纯 numpy/scipy 实现，单写多读线程安全，删除用墓碑标记，结果与静态 cKDTree 完全一致。代码与设计文档见 GitHub。
「研究」频道最新
- NLI 研究者 Yoav Goldberg 盛赞一篇 async/await 设计空间论文 — yoavgo · 2026-09-14
- 爆料称 Hodge 与 BSD 猜想或将宣布被 AI 攻克 — Dr_Singularity · 2026-09-14
- 论文剖析 async/await:各语言设计其实大相径庭 — yoavgo · 2026-09-14
- Grok 生成群论定理证明,声称攻克 Boone-Higman 未决情形 — Sauers_ · 2026-09-14
- PDE 学者谈 OpenAI 构造 Navier-Stokes 爆破证明:人类理解从此滞后于证明 — soumitrashukla9 · 2026-09-14
- NASA与IBM发布月面测绘AI，精准识别SpaceX火箭撞出的新陨石坑 — imjustnewatai · 2026-09-14