Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.15470 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912865856782336 |
|---|---|
| author | Chawla, Shuchi Sheridan, Kristin |
| author_facet | Chawla, Shuchi Sheridan, Kristin |
| contents | In this paper, we consider outlier embeddings into HSTs. In particular, for metric $(X,d)$, let $k$ be the size of the smallest subset of $X$ such that all but that subset (the ``outlier set'') can be probabilistically embedded into the space of HSTs with expected distortion at most $c$. Our primary result is showing that there exists an efficient algorithm that takes in $(X,d)$ and a target distortion $c$ and samples from a probabilistic embedding with at most $O(\frac k ε\log^2k)$ outliers and distortion at most $(32+ε)c$, for any $ε>0$. In order to facilitate our results, we show how to find good nested embeddings into HSTs and combine this with an approximation algorithm of Munagala et al. [MST23] to obtain our results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_15470 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Nested and outlier embeddings into trees Chawla, Shuchi Sheridan, Kristin Data Structures and Algorithms In this paper, we consider outlier embeddings into HSTs. In particular, for metric $(X,d)$, let $k$ be the size of the smallest subset of $X$ such that all but that subset (the ``outlier set'') can be probabilistically embedded into the space of HSTs with expected distortion at most $c$. Our primary result is showing that there exists an efficient algorithm that takes in $(X,d)$ and a target distortion $c$ and samples from a probabilistic embedding with at most $O(\frac k ε\log^2k)$ outliers and distortion at most $(32+ε)c$, for any $ε>0$. In order to facilitate our results, we show how to find good nested embeddings into HSTs and combine this with an approximation algorithm of Munagala et al. [MST23] to obtain our results. |
| title | Nested and outlier embeddings into trees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.15470 |