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

• URL: http://arxiv.org/abs/2504.18003v1
• Date: Fri, 25 Apr 2025 01:15:53 GMT
• Title: Self-Balancing, Memory Efficient, Dynamic Metric Space Data Maintenance, for Rapid Multi-Kernel Estimation
• Authors: Aditya S Ellendula, Chandrajit Bajaj,
• Abstract summary: We present a dynamic self-balancing octree data structure that enables efficient neighborhood maintenance in evolving metric spaces.<n>Our approach yields exponential speedups while preserving accuracy, particularly in high-dimensional spaces.
• Score: 2.6756996523251964
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Towards Generalizable Trajectory Prediction Using Dual-Level Representation Learning And Adaptive Prompting [107.4034346788744]
  Existing vehicle trajectory prediction models struggle with generalizability, prediction uncertainties, and handling complex interactions.<n>We propose Perceiver with Register queries (PerReg+), a novel trajectory prediction framework that introduces: (1) Dual-Level Representation Learning via Self-Distillation (SD) and Masked Reconstruction (MR), capturing global context and fine-grained details; (2) Enhanced Multimodality using register-based queries and pretraining, eliminating the need for clustering and suppression; and (3) Adaptive Prompt Tuning during fine-tuning, freezing the main architecture and optimizing a small number of prompts for efficient adaptation.
  arXiv  Detail & Related papers  (2025-01-08T20:11:09Z)
• MATEY: multiscale adaptive foundation models for spatiotemporal physical systems [2.7767126393602726]
  We propose two adaptive tokenization schemes that dynamically adjust patch sizes based on local features.<n>We evaluate the performance of a proposed multiscale adaptive model, MATEY, in a sequence of experiments.<n>We also demonstrate fine-tuning tasks featuring different physics that models pretrained on PDE data.
  arXiv  Detail & Related papers  (2024-12-29T22:13:16Z)
• LD-EnSF: Synergizing Latent Dynamics with Ensemble Score Filters for Fast Data Assimilation with Sparse Observations [3.583387803440918]
  We introduce Latent Dynamics EnSF (LD-EnSF), a novel methodology that completely avoids the full dynamics evolution.<n>We also propose a new method for encoding sparse observations into the latent space using Long Short-Term Memory (LSTM) networks.
  arXiv  Detail & Related papers  (2024-11-28T18:27:11Z)
• LOCAL: Learning with Orientation Matrix to Infer Causal Structure from Time Series Data [51.47827479376251]
  LOCAL is a highly efficient, easy-to-implement, and constraint-free method for recovering dynamic causal structures.<n>Asymptotic Causal Learning Mask (ACML) and Dynamic Graph Learning (DGPL)<n>Experiments on synthetic and real-world datasets demonstrate that LOCAL significantly outperforms existing methods.
  arXiv  Detail & Related papers  (2024-10-25T10:48:41Z)
• CCDSReFormer: Traffic Flow Prediction with a Criss-Crossed Dual-Stream Enhanced Rectified Transformer Model [32.45713037210818]
  We introduce Criss-Crossed Dual-Stream Enhanced Rectified Transformer model (CCDSReFormer) It includes three innovative modules: Enhanced Rectified Spatial Self-attention (ReSSA), Enhanced Rectified Delay Aware Self-attention (ReDASA) and Enhanced Rectified Temporal Self-attention (ReTSA) These modules aim to lower computational needs via sparse attention, focus on local information for better traffic dynamics understanding, and merge spatial and temporal insights through a unique learning method.
  arXiv  Detail & Related papers  (2024-03-26T14:43:57Z)
• Hybrid Transformer and Spatial-Temporal Self-Supervised Learning for Long-term Traffic Prediction [1.8531577178922987]
  We propose a model that combines hybrid Transformer and self-supervised learning. The model enhances its adaptive data augmentation by applying data augmentation techniques at the sequence-level of the traffic. We design two self-supervised learning tasks to model the temporal and spatial dependencies, thereby improving the accuracy and ability of the model.
  arXiv  Detail & Related papers  (2024-01-29T06:17:23Z)
• Efficient Architecture Search via Bi-level Data Pruning [70.29970746807882]
  This work pioneers an exploration into the critical role of dataset characteristics for DARTS bi-level optimization. We introduce a new progressive data pruning strategy that utilizes supernet prediction dynamics as the metric. Comprehensive evaluations on the NAS-Bench-201 search space, DARTS search space, and MobileNet-like search space validate that BDP reduces search costs by over 50%.
  arXiv  Detail & Related papers  (2023-12-21T02:48:44Z)
• Performance Embeddings: A Similarity-based Approach to Automatic Performance Optimization [71.69092462147292]
  Performance embeddings enable knowledge transfer of performance tuning between applications. We demonstrate this transfer tuning approach on case studies in deep neural networks, dense and sparse linear algebra compositions, and numerical weather prediction stencils.
  arXiv  Detail & Related papers  (2023-03-14T15:51:35Z)
• Dynamic Spatial Sparsification for Efficient Vision Transformers and Convolutional Neural Networks [88.77951448313486]
  We present a new approach for model acceleration by exploiting spatial sparsity in visual data. We propose a dynamic token sparsification framework to prune redundant tokens. We extend our method to hierarchical models including CNNs and hierarchical vision Transformers.
  arXiv  Detail & Related papers  (2022-07-04T17:00:51Z)
• Towards Structured Dynamic Sparse Pre-Training of BERT [4.567122178196833]
  We develop and study a straightforward, dynamic always-sparse pre-training approach for BERT language modeling task. We demonstrate that training remains FLOP-efficient when using coarse-grained block sparsity, making it particularly promising for efficient execution on modern hardware accelerators.
  arXiv  Detail & Related papers  (2021-08-13T14:54:26Z)
• Adaptive Latent Space Tuning for Non-Stationary Distributions [62.997667081978825]
  We present a method for adaptive tuning of the low-dimensional latent space of deep encoder-decoder style CNNs. We demonstrate our approach for predicting the properties of a time-varying charged particle beam in a particle accelerator.
  arXiv  Detail & Related papers  (2021-05-08T03:50:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.