时间：2018.03.25，14:30 — 16:30
题目一：Fast Euclidean DBSCAN in Low Dimensional Space
DBSCAN is a highly successful density-based clustering method for multi-dimensional points, which has been widely used in both academia and industry. Its seminal paper won the Test-of-Time Award at KDD 2014, and it has gained over 11,000 citations at Google Scholar. Nowadays, computing DBSCAN clusters has become a fundamental problem in both database and data mining area. Despite the importance and popularity of DBSCAN, its computational hardness was unknown until the publication of our work at SIGMOD 2015. This talk will first focus on the problem of computing DBSCAN clusters on a set of points in low dimensional space under the Euclidean distance. Specifically, it will involve: (i) the computational hardness of the DBSCAN problem; (ii) the notion of ρ-approximate DBSCAN and (iii) the non-trivial theoretical guarantees provided by the ρ-approximate DBSCAN on both result quality and efficiency. This talk will further discuss the algorithmic principles for dynamic clustering under the semantic of DBSCAN, including the computational hardness results on the problem in different scenarios and the corresponding solutions.
题目二：A Polynomial Kernel for Diamond-Free Editing
An $H$-free editing problem asks whether we can edit at most $k$ edges to make a graph contain no induced copy of the fixed graph $H$. We obtain a polynomial kernel for this problem when $H$ is a diamond. The incompressibility dichotomy for $H$ being a 3-connected graph and the classical complexity dichotomy suggest that except for $H$ being a complete/empty graph, $H$-free editing problems admit polynomial kernels only for a few small graphs $H$. Therefore, we believe that our result is an essential step toward a complete dichotomy on the compressibility of $H$-free editing. Additionally, we give a cubic-vertex kernel for the diamond-free edge deletion problem, which is far simpler than the previous kernel of the same size for the problem.
Dr Gan obtained his PhD degree under the supervision of Professor Yufei Tao in School of Information Technology and Electrical Engineering (ITEE) at The University of Queensland (UQ) in 2017. Currently, he is a Post-doctoral Research Fellow in the same school at UQ. His research interests are in practical algorithms with non-trivial theoretical guarantees, especially algorithms for solving problems on massive data. Dr Gan has five papers at SIGMOD and one article at TODS, both being considered the most prestigious publication venues in the field of database and data management. As an early career researcher, Dr Gan has achieved several notable achievements. First, Dr Gan won the Best-Paper Award at SIGMOD 2015, which is considered one of the highest honors in the database field. Second, Dr Gan's PhD thesis was awarded the 2018 CORE John Makepeace Bennett (Australasian Distinguished Doctoral Dissertation) Award, which is presented to the (only one) best PhD thesis over all areas (not limited to database) in computer science in Australasia during the year.
Dr. Ye is a Postdoctoral Fellow working with Dr. Yixin Cao at The Hong Kong Polytechnic University. Dr. Ye obtained the Ph.D. degree from The Chinese University of Hong Kong under the supervision of Prof. Leizhen Cai in 2016. Before that, Dr. Ye received the bachelor degree in Computer Science and Technology from Zhejiang University.