We study the problem of computing low-distortion embeddings in the streaming model. We present streaming algorithms that, given an n-point metric space M, compute an embedding of M into an n-point metric space M' that preserves a (1-σ)-fraction of the distances with small distortion (σ is called the slack). Our algorithms use space polylogarithmic in n and the spread of the metric. Within such space limitations, it is impossible to store the embedding explicitly. We bypass this obstacle by computing a compact representation of M', without storing the actual bijection from M into M'.
展开▼
