我们开发了将任意度量空间中的异常值低失真嵌入到分层分离树（HSTs）中的方法。具体而言，我们提出了一种高效算法，对于任意的 $\epsilon > 0$，给定输入度量 $(X,d)$ 以及对 $X$ 中除了 $k$ 个点的概率嵌入到 HSTs 中的失真为 $c$，该算法可以从概率嵌入中采样，嵌入除 $O(\frac{k}{\epsilon}\log k)$ 个点外的所有点，且失真最多为 $(32+\epsilon)c$。
我们的结果基于两个关键技术组件。首先，我们将 Munagala 等人 [2023] 的算法扩展到带有异常值的 HSTs 嵌入中，以最小化失真。我们结合了关于双利普希茨扩展到树和 $\ell_1$ 空间的新结果。特别地，我们证明了任何嵌入到 HSTs 的概率嵌入可以扩展到额外的 $k$ 个点，仅增加 $O(\log k)$ 的失真。这一双利普希茨扩展结果利用了一种新的概率分区方案，我们称之为洋葱分区。
博主点评： 该研究在处理异常值的低失真嵌入方面取得了重要进展，特别是在树结构中的应用。这种新的洋葱分区方法为进一步优化嵌入提供了新的思路，值得深入探讨与应用。