Skip to content

Who Invented DBSCAN?

Sander Joerg was among the team of founding researchers who invented DBSCAN algorithm in the 1990s. Image: Courtesy of AI4Society Forum

1- DBSCAN History

DBSCAN is a relatively new machine learning algorithm which was invented by Martin Ester, Hans-Peter Kriegel, Jörg Sander and Xiaowei Xu in 1996. 

DBSCAN is a non-parametric, density based algorithm and its name stands for Density-based spatial clustering.

In 2014 SIKDD awarded the algorithm the Test of Time award which can be found here. Since the introduction of DBSCAN its originally published paper has been cited almost 900 times. The original paper can be found here.

Since its introduction, density-based clustering has become one of the prominent clustering paradigms. Many data mining textbooks cover the DBSCAN clustering algorithm, and several third party implementations of DBSCAN exist (e.g. in WEKA, ELKI, and GNU R). Since the publication of DBSCAN, density-based clustering has been extensively studied (as the citation counts for the paper support), and has been successfully used in many applications.

SIKDD, Test of Time Award, Jan-2014

In addition to bagging, Random Forest uses a random feature selection method first coined by Tin Kam Ho in 1998. You can access Tin’s impressive original paper here

2- Roots from Decision Trees

DBSCAN has attracted lots of research interest over the years since its introduction in 1996. This is understandable based on its uniqueness and pioneering character for clustering arbitrary shapes.

One aspect of DBSCAN has also been discussed thoroughly and that is the time complexity. There has been quite a few suggestions for improving the DBSCAN algorithm especially to address its somewhat high time complexity. Some of the suggested clustering models based on DBSCAN are named:

  • DD_DBSCAN
  • FDBSCAN
  • IDBSCAN
  • VDBSCAN

You can see a critical assessment of these suggestions in a research paper published by Saif ur Rehman, Sohail Asghar and Simon Fong. You can read the full text here.

3- Summary

We have discussed the roots of DBSCAN algorithm and how it became popular worldwide and attracted lots of interest from researchers.

We have also covered the original paper that introduced DBSCAN clustering algorithm as well as other papers that has tried to identify potential opportunities to improve DBSCAN algorithm.