On the Hardness and Approximation of Euclidean DBSCAN

DOI10.1145/3083897zbMath1474.68420OpenAlexW2740025111MaRDI QIDQ5012582

Yufei Tao, Junhao Gan

Publication date: 25 November 2021

Published in: ACM Transactions on Database Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3083897

zbMATH Keywords

computational geometrydensity-based clusteringDBSCANHopcroft hardness

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications ⋮ On the approximation of Euclidean SL via geometric method ⋮ Anytime parallel density-based clustering ⋮ $$\mathtt {IP.LSH.DBSCAN}$$: Integrated Parallel Density-Based Clustering Through Locality-Sensitive Hashing ⋮ Density-based clustering in MapReduce with guarantees on parallel time, space, and solution quality

This page was built for publication: On the Hardness and Approximation of Euclidean DBSCAN