02/02/2021

Almost Linear Time Density Level Set Estimation via DBSCAN

Hossein Esfandiari, Vahab Mirrokni, Peilin Zhong

Keywords:

Abstract Paper Similar Papers

Abstract: In this work we focus on designing a fast algorithm for lambda-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 lambda-density level set with near-optimal Hausdorff distance, i.e., with rate O~(n^{-1/(2 * beta+D)}). However, to achieve this near-optimal rate, the current fastest DBSCAN algorithm needs near quadratic running time. This running time is not very practical for giant datasets. Usually when we are working with very 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 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.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948671
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 15:07 
 0
 0
 0
 0
 13:56 
 0
 0
 0
 1
 5:14 
 0
 0
 0
 0
 3:05 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 15:00 
 0
 0
 0
 0
 14:16 
 0
 0
 0
 0
 18:12 
 0
 0
 0
 0
 3:02 
 0
 0
 0
 0
 15:14 
 0
 0
 0
 0
 13:00 
 0
 0
 0
 0
 3:24 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 13:13 
 0
 0
 0
 0
 18:12 
 0
 0
 0
 0
 4:50 
 0
 0
 0
 0
 13:54 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 15:04 
 0
 0
 0
 0
 3:13 
 0
 0
 0
 0
 13:19 
 0
 0
 0
 0
 3:19 
 0
 0
 0
 0
 14:56 
 0
 0
 0
 0
 15:03 
 0
 0
 0
 0
 15:38 
 0
 0
 0
 0
 15:04 
 0
 0
 0
 0
 19:34 
 0
 0
 0
 0
 15:34 
 0
 0
 0
 0
 12:19 
 0
 0
 0
 0
 15:27 
 0
 0
 0
 0
 9:41 
 0
 0
 0
 0
 7:50 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 11:17 
 0
 0
 0
 0
 9:48 
 0
 0
 0
 0
 11:22 
 0
 0
 0
 0
 8:56 
 0
 0
 0
 0
 12:53 
 0
 0
 0
 0
 14:56 
 0
 0
 0
 0
 3:20