Dynamic DBSCAN with Euler Tour Sequences

• URL: http://arxiv.org/abs/2503.08246v1
• Date: Tue, 11 Mar 2025 10:08:39 GMT
• Title: Dynamic DBSCAN with Euler Tour Sequences
• Authors: Seiyun Shin, Ilan Shomorony, Peter Macgregor,
• Abstract summary: We propose a fast and dynamic algorithm for Density-Based Spatial Clustering of Applications with Noise (DBSCAN)<n>Traditional DBSCAN algorithms become computationally expensive when applied to dynamic datasets.<n>Our algorithm leverages the Euler Tour Trees data structure, enabling dynamic clustering updates without the need to reprocess the entire dataset.
• Score: 13.448072954894219
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a fast and dynamic algorithm for Density-Based Spatial Clustering of Applications with Noise (DBSCAN) that efficiently supports online updates. Traditional DBSCAN algorithms, designed for batch processing, become computationally expensive when applied to dynamic datasets, particularly in large-scale applications where data continuously evolves. To address this challenge, our algorithm leverages the Euler Tour Trees data structure, enabling dynamic clustering updates without the need to reprocess the entire dataset. This approach preserves a near-optimal accuracy in density estimation, as achieved by the state-of-the-art static DBSCAN method (Esfandiari et al., 2021) Our method achieves an improved time complexity of $O(d \log^3(n) + \log^4(n))$ for every data point insertion and deletion, where $n$ and $d$ denote the total number of updates and the data dimension, respectively. Empirical studies also demonstrate significant speedups over conventional DBSCANs in real-time clustering of dynamic datasets, while maintaining comparable or superior clustering quality.

Related papers

• DBSCAN in domains with periodic boundary conditions [44.99833362998488]
  We present a method for applying a clustering algorithm to data embedded in a periodic domain based on the DBSCAN algorithm.<n>We demonstrate the workings of the proposed method using synthetic data in one, two and three dimensions and also apply it to a real-world example involving the clustering of bubbles in a turbulent flow.
  arXiv  Detail & Related papers  (2025-01-28T12:26:07Z)
• Score-matching-based Structure Learning for Temporal Data on Networks [17.166362605356074]
  Causal discovery is a crucial initial step in establishing causality from empirical data and background knowledge.<n>Current score-matching-based algorithms are primarily designed to analyze independent and identically distributed (i.i.d.) data.<n>We have developed a new parent-finding subroutine for leaf nodes in DAGs, significantly accelerating the most time-consuming part of the process: the pruning step.
  arXiv  Detail & Related papers  (2024-12-10T12:36:35Z)
• Dynamic data summarization for hierarchical spatial clustering [2.8470354623829577]
  HDBSCAN finds meaningful patterns in spatial data by considering density and spatial proximity.<n>We present an exact algorithm that maintains density information and updates the clustering hierarchy of HDBSCAN during point insertions and deletions.
  arXiv  Detail & Related papers  (2024-11-26T06:36:43Z)
• Optimizing VarLiNGAM for Scalable and Efficient Time Series Causal Discovery [5.430532390358285]
  Causal discovery is designed to identify causal relationships in data. Time series causal discovery is particularly challenging due to the need to account for temporal dependencies and potential time lag effects. This study significantly improves the feasibility of processing large datasets.
  arXiv  Detail & Related papers  (2024-09-09T10:52:58Z)
• DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs [59.434893231950205]
  Dynamic graph learning aims to uncover evolutionary laws in real-world systems. We propose DyG-Mamba, a new continuous state space model for dynamic graph learning. We show that DyG-Mamba achieves state-of-the-art performance on most datasets.
  arXiv  Detail & Related papers  (2024-08-13T15:21:46Z)
• CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestion [8.036012885171166]
  We introduce CANDY, a benchmark tailored for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestion. CANDY comprehensively assesses a wide range of AKNN algorithms, integrating advanced optimizations such as machine learning-driven inference. Our evaluations across diverse datasets demonstrate that simpler AKNN baselines often surpass more complex alternatives in terms of recall and latency.
  arXiv  Detail & Related papers  (2024-06-28T04:46:11Z)
• TimeGraphs: Graph-based Temporal Reasoning [64.18083371645956]
  TimeGraphs is a novel approach that characterizes dynamic interactions as a hierarchical temporal graph. Our approach models the interactions using a compact graph-based representation, enabling adaptive reasoning across diverse time scales. We evaluate TimeGraphs on multiple datasets with complex, dynamic agent interactions, including a football simulator, the Resistance game, and the MOMA human activity dataset.
  arXiv  Detail & Related papers  (2024-01-06T06:26:49Z)
• 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)
• Sparse-DySta: Sparsity-Aware Dynamic and Static Scheduling for Sparse Multi-DNN Workloads [65.47816359465155]
  Running multiple deep neural networks (DNNs) in parallel has become an emerging workload in both edge devices. We propose Dysta, a novel scheduler that utilizes both static sparsity patterns and dynamic sparsity information for the sparse multi-DNN scheduling. Our proposed approach outperforms the state-of-the-art methods with up to 10% decrease in latency constraint violation rate and nearly 4X reduction in average normalized turnaround time.
  arXiv  Detail & Related papers  (2023-10-17T09:25:17Z)
• Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
  We propose two strategies to learn from large-scale unlabeled data. The first strategy performs a local neighborhood sampling to reduce the dataset size in each without violating neighborhood relationships. A second strategy leverages a novel Re-Ranking technique, which has a lower time upper bound complexity and reduces the memory complexity from O(n2) to O(kn) with k n.
  arXiv  Detail & Related papers  (2023-07-26T16:19:19Z)
• Deep Cellular Recurrent Network for Efficient Analysis of Time-Series Data with Spatial Information [52.635997570873194]
  This work proposes a novel deep cellular recurrent neural network (DCRNN) architecture to process complex multi-dimensional time series data with spatial information. The proposed architecture achieves state-of-the-art performance while utilizing substantially less trainable parameters when compared to comparable methods in the literature.
  arXiv  Detail & Related papers  (2021-01-12T20:08:18Z)

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.