Title: An efficient method for batch updates in OPTICS cluster ordering

Authors: Dhruv Kumar; Poonam Goyal; Navneet Goyal

Addresses: Department of Computer Science, Birla Institute of Technology and Science, Pilani, 333 031, India ' Department of Computer Science, Birla Institute of Technology and Science, Pilani, 333 031, India ' Department of Computer Science, Birla Institute of Technology and Science, Pilani, 333 031, India

Abstract: DBSCAN is one of the popular density-based clustering algorithms, but requires re-clustering the entire data when the input parameters are changed. OPTICS overcomes this limitation. In this paper, we propose a batch-wise incremental OPTICS algorithm which performs efficient insertion and deletion of a batch of points in a hierarchical cluster ordering, which is the output of OPTICS. Only a couple of algorithms are available in the literature on incremental versions of OPTICS. This can be attributed to the sequential access patterns of OPTICS. The existing incremental algorithms address the problem of incrementally updating the hierarchical cluster ordering for point-wise insertion/deletion, but these algorithms are only good for infrequent updates. The proposed incremental OPTICS algorithm performs batch-wise insertions/deletions and is suitable for frequent updates. It produces exactly the same hierarchical cluster ordering as that of classical OPTICS. Real datasets have been used for experimental evaluation of the proposed algorithm and results show remarkable performance improvement over the classical and other existing incremental OPTICS algorithms.

Keywords: OPTICS; incremental clustering; batch updates; density-based clustering.

DOI: 10.1504/IJDATS.2018.090631

International Journal of Data Analysis Techniques and Strategies, 2018 Vol.10 No.1, pp.57 - 80

Received: 19 Jun 2015
Accepted: 24 Jun 2016
Published online: 25 Mar 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article