Ultrametrics are representations of data that emphasize hierarchical properties and are widely used in data visualization and clustering. In the Ultrametric Embedding problem, we are given $n$ points in a metric space and must output an ultrametric that best preserves the distance between points in the original data (more precisely, we want to minimize the worst-case distortion). Farach et al. gave an exact $O(n²)$-time algorithm for this problem. Their algorithm is optimal, but it does not scale to very large datasets. Therefore, recent work has focused on obtaining subquadratic algorithms by approximating an optimal solution for *Euclidean* metrics, resulting in a $\sqrt{2}c$-approximation algorithm that runs in time $n^{1+O(1/c^2)}$. In this talk, I will present our algorithm that achieves an arbitrarily precise approximation in subquadratic time for Euclidean metrics, namely it outputs a (1+c)-approximation of the best ultrametric embedding in time $Õ(n^{1+1/c)$.
Our result is based on two constructions that may be of independent interest for approximation algorithms on high-dimensional Euclidean data. The first is a $Õ(n^{1+1/c^2})$ time algorithm for computing a *uniformly approximate* minimum spanning tree of Euclidean metrics, using a BFS guided by Locality Sensitive Hashing (LSH). The second is a dynamic data structure for approximate farthest neighbor in Euclidean spaces. This construction uses random projections and allows to i) query the farthest point in a cluster and ii) merge two clusters, both in $Õ(n^{1/c^2})$ time.
Joint work with Guillaume Lagarde (LaBRI).
[Gabriel Bathie] (LaBRI)
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .