TY - JOUR AU - Avarikioti, Georgia AU - Ryser, Alain AU - Wang, Yuyi AU - Wattenhofer, Roger PY - 2019/07/17 Y2 - 2024/03/28 TI - High Dimensional Clustering with r-nets JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 33 IS - 01 SE - AAAI Technical Track: Machine Learning DO - 10.1609/aaai.v33i01.33013207 UR - https://ojs.aaai.org/index.php/AAAI/article/view/4189 SP - 3207-3214 AB - <p>Clustering, a fundamental task in data science and machine learning, groups a set of objects in such a way that objects in the same cluster are closer to each other than to those in other clusters. In this paper, we consider a well-known structure, so-called <em>r</em>-nets, which rigorously captures the properties of clustering. We devise algorithms that improve the runtime of approximating <em>r</em>-nets in high-dimensional spaces with<sub>1</sub> and <em>`</em><sub>2</sub> metrics from, where . These algorithms are also used to improve a framework that provides approximate solutions to other high dimensional distance problems. Using this framework, several important related problems can also be solved efficiently, e.g.,pproximate <em>k</em>th-nearest neighbor distance-approximate Min-Max clustering,-approximate <em>k</em>-center clustering. In addition, we build an algorithm that-approximates greedy permutations in time <em>O</em><sup>˜</sup>((<em>dn</em>+<em>n</em><sup>2−<em>α</em></sup>)·logΦ) where Φ is the spread of the input. This algorithm is used to -approximate <em>k</em>-center with the same time complexity.</p> ER -