动态数据下快速更新聚类，效率远超传统DBSCAN。
Dynamic DBSCAN with Euler Tour Sequences
- 用欧拉回路树结构实现增量式聚类，无需重算全部数据。
- 每次增删数据点的时间复杂度为O(d log³n + log⁴n)，显著降低开销。
- 适合实时处理海量动态数据的场景，如传感器网络、在线监控。
我们提出一种快速且动态的密度聚类算法，可高效支持在线数据更新。传统DBSCAN针对批处理设计，在数据持续变化的大规模应用中计算成本过高。为此，新算法利用欧拉回路树数据结构，实现聚类结果的动态更新而无需重新处理整个数据集。该方法在密度估计精度上接近当前最优静态DBSCAN（Esfandiari等，2021），每次数据点插入或删除的时间复杂度为O(d log³n + log⁴n)，其中n为总更新次数，d为数据维度。实证研究显示，在动态数据实时聚类任务中，该方法相比传统DBSCAN有显著提速，同时保持相当或更优的聚类质量。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。