2026/01/21 by Shuchi Chawla, Arnold Filtser, Kristin Sheridan +1
Computer Science · #cs.DS
We develop low distortion embeddings with outliers from arbitrary metrics into hierarchically separated trees (HSTs). In particular, we develop an efficient algorithm that for any ε>0, given an input metric (X,d), and a probabilistic embedding of all but k points from X into HSTs with distortion c, samples from a probabilistic embedding of all but O(\frackεlog k) points into HSTs that achieves distortion at most (32+ε)c. Our results are based on two key technical components. First, we extend an algorithm of Munagala et al. [2023] for minimizing the distortion of embeddings without outliers into HSTs to the setting with outliers. We combine this with new results on bi-Lipschitz extensions into trees and ℓ1 space. In particular, we show that any probabilistic embedding into HSTs can be extended to k additional points with only a factor O(log k) of additional distortion. This bi-Lipschitz extension result utilizes a new probabilistic partitioning scheme that we call onion partitioning.