Near-optimal (euclidean) metric compression
he 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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2018
|
| Online Access: | http://hdl.handle.net/1721.1/115312 https://orcid.org/0000-0002-7983-9524 https://orcid.org/0000-0002-9455-6864 |