# Self-Balancing, Memory Efficient, Dynamic Metric Space Data Maintenance, for Rapid Multi-Kernel Estimation

arXiv: https://arxiv.org/abs/2504.18003 · HTML: https://mlsanity.com/paper/2504.18003/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 25 Apr 2025.

## Builds on (most cited first, 9 of 9)

- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [Octree Generating Networks: Efficient Convolutional Architectures for High-resolution 3D Outputs](https://mlsanity.com/paper/1703.09438/) (2017)
- [Deep Reinforcement Learning in Large Discrete Action Spaces](https://mlsanity.com/paper/1512.07679/) (2015)
- [OT-Flow: Fast and Accurate Continuous Normalizing Flows via Optimal Transport](https://mlsanity.com/paper/2006.00104/) (2020)
- [Variational Autoencoder with Learned Latent Structure](https://mlsanity.com/paper/2006.10597/) (2020)
- [Fast Approximate Geodesics for Deep Generative Models](https://mlsanity.com/paper/1812.08284/) (2018)
- [ikd-Tree: An Incremental K-D Tree for Robotic Applications](https://mlsanity.com/paper/2102.10808/) (2021)
- [Learned Indexes with Distribution Smoothing via Virtual Points](https://mlsanity.com/paper/2408.06134/) (2024)
- [i-Octree: A Fast, Lightweight, and Dynamic Octree for Proximity Search](https://mlsanity.com/paper/2309.08315/) (2023)

## Abstract (arXiv)

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.