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

ABSTRACT

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

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 2: S. Ar , M. Blum , B. Codenotti , P. Gemmell, Checking approximate computations over the reals, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.786-795, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167288]
• 3: Bonnie Berger, The Fourth Moment Method, SIAM Journal on Computing, v.26 n.4, p.1188-1207, Aug. 1997 [doi>10.1137/S0097539792240005]
• 4: Bo Brinkman , Moses Charikar, On the Impossibility of Dimension Reduction in \ell _1, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.514, October 11-14, 2003
• 5: Broder, A. 1998. Filtering near-duplicate documents. In Proceedings of FUN.
• 6: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 7: Chambers, J. M., Mallows, C. L., and Stuck, B. W. 1976. A method for simulating stable random variables. J. Amer. Statist. Assoc. 71, 340--344.
• 8: Finding Interesting Associations without Support Pruning, Proceedings of the 16th International Conference on Data Engineering, p.489, February 28-March 03, 2000
• 9: Cormode, G. 2003. Stable distributions for stream computations: It's as easy as 0,1,2. In Proceedings of the Workshop on Management and Processing of Data Streams.
• 10: Cormode, G., Datar, M., Indyk, P., and Muthukrishnan, S. 2002a. Comparing data streams using hamming norms. In Proceedings of the International Conference on Very Large Databases (VLDB).
• 11: Fast Mining of Massive Tabular Data via Approximate Distance Computations, Proceedings of the 18th International Conference on Data Engineering, p.605, February 26-March 01, 2002
• 12: Cormode, G., and Muthukrishnan, S. 2003. Estimating dominance norms of multiple data streams. In Proceedings of the European Symposium on Algorithms.
• 13: Mayur Datar , Aristides Gionis , Piotr Indyk , Rajeev Motwani, Maintaining stream statistics over sliding windows: (extended abstract), Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.635-644, January 06-08, 2002, San Francisco, California
• 14: Mayur Datar , Nicole Immorlica , Piotr Indyk , Vahab S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997857]
• 15: Lars Engebretsen , Piotr Indyk , Ryan O'Donnell, Derandomized dimensionality reduction with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.705-712, January 06-08, 2002, San Francisco, California
• 16: Joan Feigenbaum , Yuval Ishai , Tal Malkin , Kobbi Nissim , Martin Strauss , Rebecca N. Wright, Secure Multiparty Computation of Approximations, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.927-938, July 08-12, 2001
• 17: Feigenbaum, J., Ishai, Y., Malkin, T., Nissim, K., Strauss, M. J., and Wright, R. N. 2001b. Secure multiparty computation of approximations. http://eprint.iacr.org/2001/024/.
• 18: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, An Approximate L1-Difference Algorithm for Massive Data Streams, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.501, October 17-18, 1999
• 19: Figiel, T., Lindenstrauss, J., and Milman, V. D. 1977. The dimension of almost spherical sections of convex bodies. Acta Math. 139, 53--94.
• 20: Freivalds, R. 1979. Fast probabilistic algorithms. In Proceedings of the Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 74, Springer-Verlag, New York.
• 21: Anna C. Gilbert , Sudipto Guha , Piotr Indyk , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509966]
• 22: Henzinger, M., Raghavan, P., and Rajagopalan, S. 1998. Computing on data streams. Technical Note 1998-011, Digital Systems Research Center, Palo Alto, CA.
• 23: Piotr Indyk, Dimensionality reduction techniques for proximity problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.371-378, January 09-11, 2000, San Francisco, California, United States
• 24: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 25: Piotr Indyk, Algorithms for dynamic geometric problems over data streams, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007413]
• 26: Piotr Indyk , Nick Koudas , S. Muthukrishnan, Identifying Representative Trends in Massive Time Series Data Sets Using Sketches, Proceedings of the 26th International Conference on Very Large Data Bases, p.363-372, September 10-14, 2000
• 27: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 28: Piotr Indyk , David Woodruff, Optimal approximations of the frequency moments of data streams, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060621]
• 29: Johnson, W., and Lindenstrauss, J. 1984. Extensions of lipshitz mapping into hilbert space. Contemp. Math. 26, 189--206.
• 30: Johnson, W., and Schechtman, G. 1982. Embedding lmp into ln1. Acta Math. 149, 71--85.
• 31: Lindenstrauss, J., and Milman, V. D. 1993. The local theory of normed spaces and its applications to convexity. In Handbook of Convex Geometry, P. M. Gruber and J. M. Wills, eds Elsevier, Amsterdam, The Netherlands, 1149--1220.
• 32: Linial, N., London, E., and Rabinovich, Y. 1994. The geometry of graphs and some of its algorithmic applications. In Proceedings of 35th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 577--591.
• 33: Matoušek, J. 2004. Collection of open problems on low-distortion embeddings of finite metric spaces. Available at http://kam.mff.cuni.cz/~matousek/metrop.ps.gz|.
• 34: Maurer, A. 2003. A bound on the deviation probability for sums of non-negative random variables. J. Ineq. Pure Applied Math. 4, 1, Art. 15.
• 35: Muthukrishnan, S. 2003. Data streams: Algorithms and applications (invited talk at SODA'03). Available at http://athos.rutgers.edu/~muthu/stream-1-1.ps.
• 36: N. Nisan, Pseudorandom generators for space-bounded computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.204-212, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100242]
• 37: Noam Nisan, RL⊆SC, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.619-623, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129772]
• 38: D. Sivakumar, Algorithmic derandomization via complexity theory, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509996]
• 39: Nitin Thaper , Sudipto Guha , Piotr Indyk , Nick Koudas, Dynamic multidimensional histograms, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564741]
• 40: Hal Wasserman , Manuel Blum, Software reliability via run-time result-checking, Journal of the ACM (JACM), v.44 n.6, p.826-849, Nov. 1997 [doi>10.1145/268999.269003]
• 41: Zolotarev, V. 1986. One-Dimensional Stable Distributions. Vol. 65 of Translations of Mathematical Monographs, American Mathematical Society.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
data streams, dimensionality reduction, embeddings, norms, sketching