Category Archives: Visualization

  • 0

讲座信息:Fast Euclidean OPTICS with Bounded Precision in Low Dimensional Space

Category : Visualization

时间: 12月20日 周四 下午14:00-16:00
题目: Fast Euclidean OPTICS with Bounded Precision in Low Dimensional Space
报告人: DR. JunHao Gan


OPTICS is a popular method for visualizing multidimensional clusters. Despite of the popularity of this method, somewhat surprisingly, the term of “valley”, which is used to capture clusters in the resulted visualizations, has been used on an intuitive basis throughout the literature. Moreover, all the existing implementations of OPTICS have a time complexity of O(n^2) — where n is the size of the input dataset — and thus, may not be suitable for datasets of large volumes.

In this talk, we will first formalize the concept of “valley”, by which rigorous measurement on the resemblance of two valleys becomes possible, and it lays down a foundation to alleviate the problem of computing OPTICS visualizations by resorting to approximation with guarantees. Then, we will show an algorithm that runs in O(n log n) time under any fixed dimensionality, and computes a visualization that has provably small discrepancies from that of OPTICS.


Dr Junhao Gan joined the School of Computing and Information Systems (CIS) at the University of Melbourne (UoM) as a lecturer (equivalent to Assistant Professor in US) in August 2018. Prior to that, he worked as a post-doctoral research fellow in the School of Information Technologies and Electrical Engineering (ITEE) at the University of Queensland (UQ) from 2017 to 2018, and obtained his PhD degree under the supervision of Prof. Yufei Tao in the same school at UQ in 2017. His research interests are in practical algorithms with non-trivial theoretical guarantees, especially algorithms for solving problems on massive data. Dr Gan has published 5 papers at SIGMOD, one journal at TODS and one article at JGAA. One of his papers won the Best Paper Award at SIGMOD 2015 which is considered as one of the highest honours in the database area, and his PhD thesis was awarded the CORE John Makepeace Bennett Award (Australasian Distinguished Doctoral Dissertation) 2018 that is presented to the best PhD thesis over all the areas in computer science finalised during the year in Australasia. Besides, Dr Gan also won the Discovery Early Career Research Award (DECRA) 2019 from Australian Research Council (ARC) which is one of the most competitive fellowships for early career researchers in Australia.