The encyclopedia · R&D & Science · Technical decision · 1996
DBSCAN found clusters of any shape without being told how many
Ester, Kriegel, Sander and Xu clustered by local density, so arbitrary shapes emerged and noise stayed out.
University of Munich
The solution
Classic clustering assumed you knew the number of clusters and that they were blob-shaped around centroids. For spatial databases, Ester, Kriegel, Sander and Xu wanted clustering with minimal domain knowledge, arbitrary shapes and good efficiency at scale.
Their answer, DBSCAN, defines density locally: a core point has at least MinPts neighbours within radius Eps, and a cluster is everything density-reachable from a core point. Border points attach without extending the cluster; isolated points become noise.
The KDD-96 paper showed this handled arbitrary shapes, needed only two parameters, and could use spatial indexes to run efficiently on large data. The same density notion still underlies modern spatial clustering.
Why it worked
- Local density adapts to any cluster shape
- No need to choose the number of clusters
- Noise gets labeled instead of forced into a cluster
- Only two intuitive parameters to set
What can be applied
Don't impose a count or shape on clusters — define them by local density. Two intuitive parameters replace guessing k, outliers get a label, and the scan scales to large databases.
Aftermath
DBSCAN became the standard density-based clustering algorithm, shipped in scikit-learn and most data platforms, and remains one of the most-cited papers from KDD-96.
Sources
spotted an error? The archive wants to know.