Fast Parameterless Density-Based Clustering via Random Projections

back to overview


Vlachos, M., & Schneider, J. (2013). Fast Parameterless Density-Based Clustering via Random Projections. Paper presented at the Conference on Information and Knowledge Management (CIKM).

Publication type

Paper in Conference Proceedings


Clustering offers significant insights in data analysis. Density-based algorithms have emerged as flexible and efficient techniques, able to discover high-quality –and potentially irregularly shaped– clusters. We present two fast density-based clustering algorithms based on random projections. Both algorithms demonstrate one to two orders of magnitude speedup compared to equivalent state-of-art density based techniques, even for modest-size datasets. We give a comprehensive analysis of both our algorithms and show runtime of O(dN log^2 N), for a d-dimensional dataset. Our first algorithm can be viewed as a fast variant of the OPTICS density-based algorithm, but using a softer definition of density combined with sampling. The second algorithm is parameter-less, and identifies areas separating clusters.


Organizational Units

  • Institute of Information Systems
  • Hilti Chair of Business Process Management