Efficient clustering techniques are required for knowledge discovery in large databases. The efforts of scientists have contributed to the development of many clustering algorithms.

This research paper considers the class of density-based clustering algorithms and presents all details, both theoretical and technical, on SOPTICS--speedy OPTICS--a random-projection-based version of the popular OPTICS algorithm. The authors extend their previous work [1] in order to show theoretical arguments on the performance of SOPTICS.

In nine sections and an appendix, the reader will find a valuable description of basic density-based clustering algorithms; the technique of random projections; the steps of the proposed algorithm (including pseudocode); and theoretical results on the speed of algorithms used in different steps like partitioning, neighborhood identification, density estimate, and so on. Starting with the seventh section, a deep analysis is conducted on SOPTICS. Twelve theorems are developed to prove different aspects of the proposed strategy. In section 8, an empirical evaluation is described related to both runtime and clustering quality over ten datasets. SOPTICS showed clear performance advantages when compared against basic OPTICS, OPTICS with locality sensitive hashing, and DeLi-Clu.

The Java implementation of SOPTICS is available at the second author’s website [2], and the previous version can be found as included by the ELKI project [3].

Even for a long paper, it is to the authors’ merit that they include only the necessary background and references for a good understanding of the context, proofs, and SOPTICS.

I highly recommend this contribution to data scientists, researchers in data mining, and students pursuing master’s or PhD degrees doing research in the knowledge discovery field.