The Ester et al. 1996 Paper · Original DBSCAN Formulation

The 1996 KDD paper “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise” by Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu introduced DBSCAN and addressed a specific problem: spatial databases (Oracle Spatial, ESRI) were growing rapidly, and existing clustering algorithms (CLARANS, BIRCH) either assumed spherical clusters or couldn’t handle noise.

Key contributions: (1) The density-based cluster definition — a cluster is a maximal set of density-connected points. (2) The three-way point classification (core, border, noise). (3) The algorithm’s linear scalability claim — $O(n \log n)$ with R*-tree spatial indexing, which was state-of-the-art for its time. (4) Experimental validation on synthetic data (showing DBSCAN outperforming CLARANS on arbitrary-shaped clusters) and real SEQUOIA 2000 benchmark data (Earth science spatial data).

The paper has been cited over 30,000 times and won the 2014 KDD Test of Time Award. Modern implementations differ from the 1996 version primarily in the spatial index used (ball trees / kd-trees in scikit-learn rather than R*-trees; HDBSCAN entirely replaces the query mechanism with a minimum spanning tree approach).