Abstract | ||
---|---|---|
In this work we focus on designing a fast algorithm for A-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 A-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 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 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. |
Year | Venue | DocType |
---|---|---|
2021 | THIRTY-FIFTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THIRTY-THIRD CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE AND THE ELEVENTH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE | Conference |
Volume | ISSN | Citations |
35 | 2159-5399 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hossein Esfandiari | 1 | 88 | 15.38 |
VAHAB S. MIRROKNI | 2 | 4309 | 287.14 |
Peilin Zhong | 3 | 99 | 10.36 |