High Dimensional Clustering with r-nets

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 r-nets, which rigorously captures the properties of clustering. We devise algorithms that improve the runtime of approximating r-nets in high-dimensional spaces with `1 and `2 metrics from Õ(dn2−Θ( √ ) ) to Õ(dn + n2−α ), where α = Ω( 1/3 /log(1/ )). 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. , (1 + )-approximate kth-nearest neighbor distance, (4 + )-approximate Min-Max clustering, (4+ )-approximate k-center clustering. In addition, we build an algorithm that (1 + )-approximates greedy permutations in time Õ((dn + n2−α ) · log Φ) where Φ is the spread of the input. This algorithm is used to (2 + )-approximate k-center with the same time complexity.

Authors

• Georgia Avarikioti
• Alain Ryser
• Yuyi Wang CRRC Zhuzhou Institute, China
• Roger Wattenhofer ETH Zurich

Keywords

No keywords are indexed for this paper.