提出一种自平衡八叉树，高效维护动态空间中的邻近关系。
Self-Balancing, Memory Efficient, Dynamic Metric Space Data Maintenance, for Rapid Multi-Kernel Estimation
- 设计可自平衡的双参数八叉树，支持对数时间更新与查询。
- 在高维空间中实现指数级加速，保持精度不变。
- 适合需要实时空间索引的生成模型与KNN分类任务。
我们提出一种动态自平衡八叉树数据结构，用于在演化的度量空间中高效维护邻域关系，这是现代机器学习系统的关键挑战。许多学习和生成模型作为动力系统运行，其表示在训练过程中持续演化，需要快速、自适应的空间组织。我们的双参数八叉树支持对数时间的更新与查询，避免了数据分布变化时的昂贵全重建。我们在四个场景中验证其有效性：(1) 加速斯坦因变分梯度下降，支持更多粒子且开销更低；(2) 实现对数复杂度的实时增量KNN分类；(3) 支持高效动态索引与检索，适用于检索增强生成；(4) 通过联合优化输入与潜在空间提升采样效率。所有应用中，该方法均实现指数级加速并保持准确率，尤其在高维空间中维护自适应空间结构至关重要。
原文摘要 · Abstract (English)
We present a dynamic self-balancing octree data structure that enables efficient neighborhood maintenance in evolving metric spaces, a key challenge in modern machine learning systems. Many learning and generative models operate as dynamical systems whose representations evolve during training, requiring fast, adaptive spatial organization. Our two-parameter octree supports logarithmic-time updates and queries, eliminating the need for costly full rebuilds as data distributions shift. We demonstrate its effectiveness in four areas: (1) accelerating Stein variational gradient descent by supporting more particles with lower overhead; (2) enabling real-time, incremental KNN classification with logarithmic complexity; (3) facilitating efficient, dynamic indexing and retrieval for retrieval-augmented generation; and (4) improving sample efficiency by jointly optimizing input and latent spaces. Across all applications, our approach yields exponential speedups while preserving accuracy, particularly in high-dimensional spaces where maintaining adaptive spatial structure is critical.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。