Research map / Learning theory and algorithms / Clustering
Improved Error Bounds for Tree Representations of Metric Spaces
Samir Chowdhury, Facundo Mémoli, Zane T Smith
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace cardinality-based covering bound with doubling-dimension bound in Gromov's tree embedding (Theorem 7) | Gromov's embedding into tree metrics · theoretical distortion bound | l-infinity distortion bound | Improved |
| Replace cardinality-based bound with ultrametricity-based bound for single linkage hierarchical clustering (Theorem 4 vs. dimension bound in Theorem 8) | SLHC ultrametric embedding · theoretical distortion bound | l-infinity distortion bound | Improved |
| Gromov-style cardinality bound replaced by doubling-dimension bound; claimed strictly better, arbitrarily so on constructed example | Gromov's embedding bound on constructed line-times-two-point space · Proposition 11 example family (X_n = V x L_n) | distortion bound | Improved |
Closest papers by meaning
- New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering (ICML 2024 · similarity 0.86)
- Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity (NeurIPS 2025 · similarity 0.86)
- Tree-Wasserstein Distance for High Dimensional Data with a Latent Feature Hierarchy (ICLR 2025 · similarity 0.84)
- Low-Distortion Clustering with Ordinal and Limited Cardinal Information (AAAI 2024 · similarity 0.84)
- Fast unsupervised ground metric learning with tree-Wasserstein distance (ICLR 2025 · similarity 0.84)
- On the cohesion and separability of average-link for hierarchical agglomerative clustering (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
