Fast Euclidean OPTICS with Bounded Precision in Low Dimensional Space

Abstract

OPTICS is a popular method for visualizing multidimensional clusters. All the existing implementations of this method have a time complexity ofO(n2)-where n is the size of the input dataset-and thus, may not be suitable for datasets of large volumes. This paper alleviates the problem by resorting to approximation with guarantees. The main result is a new algorithm that runs in O(n logn) time under anyfixed dimensionality, and computes a visualization that has provably small discrepancies from that of OPTICS. As a side product, our algorithm gives an index structure that occupies linear space, and supports the cluster group-by query with nearoptimal cost. The quality of the cluster visualizat..