Conference Proceedings

Fast Euclidean OPTICS with Bounded Precision in Low Dimensional Space

Junhao Gan, Yufei Tao

Proceedings / ACM-SIGMOD International Conference on Management of Data. ACM-Sigmod International Conference on Management of Data | Association for Computing Machinery (ACM) | Published : 2018

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..

View full abstract

Grants

Awarded by CUHK


Funding Acknowledgements

The research of Yufei Tao was partially supported by a direct grant (Project Number: 4055079) from CUHK and by a Faculty Research Award from Google.