.png){kind=icon}
Return
GriT-DBSCAN: A spatial clustering algorithm for very large databases
.png){kind=icon}
OA
AI
DOI：10.1016/j.patcog.2023.109658.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
DBSCAN is a fundamental spatial clustering algorithm with numerous practical applications. However, a bottleneck of DBSCAN is its O (n 2 ) worst-case time complexity. To address this limitation, we propose a new grid-based algorithm for exact DBSCAN in Euclidean space called GriT-DBSCAN, which is based on the following two techniques. First, we introduce grid tree to organize the non-empty grids for the purpose of efficient non-empty neighboring grids queries. Second, by utilizing the spatial relationships among points, we propose a technique that iteratively prunes unnecessary distance calculations when determining whether the minimum distance between two sets is less than or equal to a certain threshold. We theoretically demonstrate that GriT-DBSCAN has excellent reliability in terms of time complexity. In addition, we obtain two variants of GriT-DBSCAN by incorporating heuristics, or by combining the second technique with an existing algorithm. Experiments are conducted on both synthetic and real-world data sets to evaluate the efficiency of GriT-DBSCAN and its variants. The results show that our algorithms outperform existing algorithms.
Keywords:
DBSCAN
Clustering
Indexing methods
Spatial databases
Journal
IF:
7.6
Papers:
1.4W
Citations:
4.5W
Organization
Cited Papers
ShareSaveFabrication and characterization of silver core and porous silica shell nanocomposite particles
PREAI
ShareSave
Unsupervised person re-identification via simultaneous clustering and mask prediction.png)
PATTERN RECOGNITION
PATTERN RECOGNITIONIF7.6
PREAI
ShareSaveShareSaveA local tangent plane distance-based approach to 3D point cloud segmentation via clusteringPATTERN RECOGNITION
PATTERN RECOGNITIONIF7.6
PREAI
ShareSaveA fast DBSCAN clustering algorithm by accelerating neighbor searching using Groups methodPATTERN RECOGNITION
PATTERN RECOGNITIONIF7.6
PREAI
ShareSaveShareSave
View more