作者: Piotr Indyk
关键词:
摘要: 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)).