Stable distributions, pseudorandom generators, embeddings and data stream computation

This paper shows how to maintain (using only O(log n//spl epsiv//sup 2/) words of storage) a sketch C(p) of a point p/spl isin/l/ sub 1//sup n/ under dynamic updates of its coordinates, such that given sketches C( p) and C(q) one can estimate |p-q|/sub 1/ up to a factor of (1+/spl ePSiv/) with large probability.

Abstract

In this paper we show several results obtained by combining the use of stable distributions with pseudorandom generators for bounded space. In particular: we show how to maintain (using only O(log n//spl epsiv//sup 2/) words of storage) a sketch C(p) of a point p/spl isin/l/sub 1//sup n/ under dynamic updates of its coordinates, such that given sketches C(p) and C(q) one can estimate |p-q|/sub 1/ up to a factor of (1+/spl epsiv/) with large probability. We obtain another sketch function C' which maps l/sub 1//sup n/ into a normed space l/sub 1//sup m/ (as opposed to C), such that m=m(n) is much smaller than n; to our knowledge this is the first dimensionality reduction lemma for l/sub 1/ norm we give an explicit embedding of l/sub 2//sup n/ into l/sub l//sup nO(log n)/ with distortion (1+1/n/sup /spl theta/(1)/) and a non-constructive embedding of l/sub 2//sup n/ into l/sub 1//sup O(n)/ with distortion (1+/spl epsiv/) such that the embedding can be represented using only O(n log/sup 2/ n) bits (as opposed to at least n/sup 2/ used by earlier methods).