Anytime OPTICS: An efficient approach for hierarchical density-based clustering

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

OPTICS is a fundamental data clustering technique that has been widely applied in many fields. However, it suffers from performance degradation when faced with large datasets and expensive distance measures because of its quadratic complexity in terms of both time and distance function calls. In this paper, we introduce a novel anytime approach to tackle the above problems. The general idea is to use a sequence of lower-bounding (LB) distances of the true distance measure to produce multiple approximations of the true reachability plot of OPTICS. The algorithm quickly produces an approximation result using the first LB distance. It then continuously refines the results with subsequent LB distances and the results from the previous computations. At any time, users can suspend and resume the algorithm to examine the results, enabling them to stop the algorithm whenever they are satisfied with the obtained results, thereby saving computational cost. Our proposed algorithms, called Any-OPTICS and Any-OPTICS-XS, are built upon this anytime scheme and can be applied for many complex datasets. Our experiments show that Any-OPTICS obtains very good clustering results at early stages of execution, leading to orders of magnitudes speed up. Even when run to the final distance measure, the cumulative runtime of Any-OPTICS is faster than OPTICS and its extensions.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - 21st International Conference, DASFAA 2016, Proceedings
EditorsShamkant B. Navathe, Weili Wu, Shashi Shekhar, Xiaoyong Du, X. Sean Wang, Hui Xiong
Number of pages16
PublisherSpringer VS
Publication year2016
ISBN (print) 978-3-319-32024-3
ISBN (Electronic)978-3-319-32025-0
Publication statusPublished - 2016
Event21st International Conference on Database Systems for Advanced Applications, DASFAA 2016 - Dallas, United States
Duration: 16 Apr 201619 Apr 2016


Conference21st International Conference on Database Systems for Advanced Applications, DASFAA 2016
LandUnited States
SeriesLecture Notes in Computer Science (LNCS)

See relations at Aarhus University Citationformats

ID: 110155279