Almost Linear Time Density Level Set Estimation via DBSCAN

In this work we focus on designing a fast algorithm for λdensity level set estimation via DBSCAN clustering. Previous work (Jiang ICML’17, and Jang and Jiang ICML’19) shows that under some natural assumptions DBSCAN and its variant DBSCAN++ can be used to estimate the λ-density level set with near-optimal Hausdorff distance, i. e. , with rate e O(n−1/(2β+D) ). However, to achieve this near-optimal rate, the current fastest DBSCAN algorithm needs near quadratic running time. This running time is not practical for large datasets. Usually when we are working with large datasets we desire linear or almost linear time algorithms. With this motivation, in this work, we present a modified DBSCAN algorithm with near optimal Hausdorff distance for density level set estimation with e O(n) running time. In our empirical study, we show that our algorithm provides significant speedup over the previous algorithms, while achieving comparable solution quality.

Authors

• Hossein Esfandiari
• Vahab Mirrokni
• Peilin Zhong

Keywords

No keywords are indexed for this paper.