Stable distributions, pseudorandom generators, embeddings, and data stream computation

作者: Piotr Indyk

DOI: 10.1145/1147954.1147955

关键词:

摘要: In this article, we show several results obtained by combining the use of stable distributions with pseudorandom generators for bounded space. particular:---We that, any p ∈ (0, 2], one can maintain (using only O(log n/e2) words storage) a sketchC(q) point q lnp under dynamic updates its coordinates. The sketch has property given C(q) and C(s), estimate Vq − sVp up to factor (1 e) large probability. This solves main open problem Feigenbaum et al. [1999].---We that aforementioned sketching approach directly translates into an approximate algorithm fixed linear mapping A, x ℜn y ℜm, estimates VAx yVp in O(n m) time, 2]. generalizes earlier Wasserman Blum [1997] which worked case = 2.---We obtain another function C′ probabilistically embeds ln1 normed spacelm1. embedding guarantees if set m log(1/δ)O(1/e), then pair points q, s ln1, distance between does not increase more than constant probability, it decrease probability 1 δ. is known dimensionality reduction theorem l1 norm. fact, stronger theorems type (i.e., guarantee very low expansion as well contraction) cannot exist [Brinkman Charikar 2003].---We give explicit ln2 lnO(log n)1 distortion 1/nΘ(1)).

参考文章(43)
Andreas Maurer, A bound on the deviation probability for sums of non-negative random variables. Journal of Inequalities in Pure & Applied Mathematics. ,vol. 4, ,(2003)
Piotr Indyk, Ji_í Matou_ek, Low-Distortion Embeddings of Finite Metric Spaces Handbook of Discrete and Computational Geometry, Second Edition. pp. 177- 196 ,(2004) , 10.1201/9781420035315.CH8
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J. Strauss, Rebecca N. Wright, Secure Multiparty Computation of Approximations international colloquium on automata languages and programming. pp. 927- 938 ,(2001) , 10.1007/3-540-48224-5_75
P. Indyk, Algorithmic applications of low-distortion geometric embeddings international conference on cluster computing. pp. 10- 33 ,(2001) , 10.1109/SFCS.2001.959878
Piotr Indyk, Nick Koudas, S. Muthukrishnan, Identifying Representative Trends in Massive Time Series Data Sets Using Sketches very large data bases. pp. 363- 372 ,(2000)
V. M. Zolotarev, One-dimensional stable distributions ,(1986)
Graham Cormode, S. Muthukrishnan, Estimating Dominance Norms of Multiple Data Streams european symposium on algorithms. pp. 148- 160 ,(2003) , 10.1007/978-3-540-39658-1_16
Moses Charikar, Bo Brinkman, On the Impossibility of Dimension Reduction in \ell _1 foundations of computer science. pp. 514- 523 ,(2003)
Rūsiņš Freivalds, Fast probabilistic algorithms Mathematical Foundations of Computer Science 1979. pp. 57- 69 ,(1979) , 10.1007/3-540-09526-8_5
Piotr Indyk, Mayur Datar, Graham Cormode, S. Muthukrishnan, Comparing data streams using Hamming norms (how to zero in) very large data bases. pp. 335- 345 ,(2002)