Near-Optimal (Euclidean) Metric Compression
Near-Optimal (Euclidean) Metric Compression
复制标题
近乎最优（欧几里得）公制压缩
DOI：
10.1137/1.9781611974782.45
复制
发表时间：
2016
影响因子：
2
通讯作者：
Tal Wagner
中科院分区：
文献类型：
--
作者：
P. Indyk;Tal Wagner
公制草图绘制问题的定义如下。在给定n个点的度量和ϵ>；0的情况下，我们希望产生一个小尺寸的数据结构(草图)，该结构在给定任意一对点索引的情况下，将点之间的距离恢复到1+ϵ失真。在这篇文章中，我们考虑由L2和L1范数诱导的度量，它们的扩散(直径与最近的对距离之比)由Φ>；0有界。Johnson和Lindenstrauss的一个著名的降维定理给出了一个大小为O(ϵ−2log(Φn)n logn)的示意图，即每个点O(ϵ−2log(Φn)n logn)比特。我们证明了这个界并不是最优的，并且可以大幅度地提高到每点O(ϵ−2log(1/ϵ)·logn+loglogΦ)比特。此外，我们还证明了我们的界是紧的，直到一个log(1/ϵ)的因子。我们还考虑了一般度量的草图，并提供了每点大小为O(n log(1/ϵ)+log logΦ)比特的草图，我们表明这是最优的。
The metric sketching problem is defined as follows. Given a metric on n points, and ϵ > 0, we wish to produce a small size data structure (sketch) that, given any pair of point indices, recovers the distance between the points up to a 1 + ϵ distortion. In this paper we consider metrics induced by l2 and l1 norms whose spread (the ratio of the diameter to the closest pair distance) is bounded by Φ > 0. A well-known dimensionality reduction theorem due to Johnson and Lindenstrauss yields a sketch of size O(ϵ−2 log(Φn)n log n), i.e., O(ϵ−2 log(Φn)n log n) bits per point. We show that this bound is not optimal, and can be substantially improved to O(ϵ−2 log(1/ϵ) · log n + log log Φ) bits per point. Furthermore, we show that our bound is tight up to a factor of log(1/ϵ). We also consider sketching of general metrics and provide a sketch of size O(n log(1/ϵ) + log log Φ) bits per point, which we show is optimal.