Personal tools
You are here: Home CG seminar Fall 2017 Near-optimal (Euclidean) metric compression
« November 2017 »
November
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
2627282930
Log in


Forgot your password?
 

Near-optimal (Euclidean) metric compression

Wednesday, January 25th, 2017 16:10

Schreiber 309

underline

Near-optimal (Euclidean) metric compression

Tal Wagner, MIT

Abstract:

n the Metric Sketching (a.k.a. Distance Oracle) problem, we are given a finite metric space, and our goal is to store all the pairwise distances, up to a small relative error, with as little space as possible. For Euclidean metrics, a famous dimensionality reduction theorem of Johnson and Lindenstrauss yields a sketch of size O(log(n)) numbers per point, or O(log^2(n)) bits per point. We show this can improved to O(log(n)) bits per point, which is tight. We also provide tight bounds for sketching arbitrary metrics with relative error approaching 1.
 
I will present our sketching scheme, and then discuss some extensions, applications and empirical results that we obtained since the publication of this work.
 
Joint work with Piotr Indyk.

 

Document Actions