Enabling DBSCAN for Very Large-Scale High-Dimensional Spaces
DBSCAN is one of the most important non-parametric unsupervised data analysis tools. By applying DBSCAN to a dataset, two key analytical results can be obtained: (1) clustering data points based on density distribution and (2) identifying outliers in the dataset. However, the time complexity of the DBSCAN algorithm is $O(n^2 \beta)$, where $n$ is the number of data points and $\beta = O(D)$, with $D$ representing the dimensionality of the data space. As a result, DBSCAN becomes computationally infeasible when both $n$ and $D$ are large. In this paper, we propose a DBSCAN method based on spectral data compression, capable of efficiently processing datasets with a large number of data points ($n$) and high dimensionality ($D$). By preserving only the most critical structural information during the compression process, our method effectively removes substantial redundancy and noise. Consequently, the solution quality of DBSCAN is significantly improved, enabling more accurate and reliable results.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringData CompressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Dynamic DBSCAN with Euler Tour Sequences
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, bec…
ClusteringDensity EstimationBlock-Diagonal Guided DBSCAN Clustering
Cluster analysis plays a crucial role in database mining, and one of the most widely used algorithms in this field is DBSCAN. However, DBSCAN has several limitations, such as difficulty in handling high-dimensional large…
ClusteringAdaptive and Robust DBSCAN with Multi-agent Reinforcement Learning
DBSCAN, a well-known density-based clustering algorithm, has gained widespread popularity and usage due to its effectiveness in identifying clusters of arbitrary shapes and handling noisy data. However, it encounters cha…
ClusteringDeep Reinforcement LearningMulti-agent Reinforcement Learningreinforcement-learning+1IPD:An Incremental Prototype based DBSCAN for large-scale data with cluster representatives
DBSCAN is a fundamental density-based clustering technique that identifies any arbitrary shape of the clusters. However, it becomes infeasible while handling big data. On the other hand, centroid-based clustering is impo…
ClusteringGeometric reconstructions of density based clusterings
DBSCAN* and HDBSCAN* are well established density based clustering algorithms. However, obtaining the clusters of very large datasets is infeasible, limiting their use in real world applications. By exploiting the geomet…
Clustering