Answers are grounded in this paper and cite their sources.
Algorithmic analysis reveals that standard DBSCAN requires quadratic time complexity rather than sub-quadratic time, highlighting an open computational challenge in higher dimensions.
DBSCAN is a popular method for clustering multi-dimensional objects. Just as notable as the method's vast success is the research community's quest for its efficient computation. The original KDD'96 paper claimed an algorithm with O(n log n) running time, where n is the number of objects. Unfortunately, this is a mis-claim; and that algorithm actually requires O(n2) time. There has been a fix in 2D space, where a genuine O(n log n)-time algorithm has been found. Looking for a fix for dimensionality d ≥ 3 is currently an important open problem.
No takes yet. Share an insight, caveat, or question.
Gan et al. (2015) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: