Space lower bounds for distance approximation in the data stream model

ABSTRACT

(MATH) We consider the problem of approximating the distance of two d-dimensional vectors x and y in the data stream model. In this model, the 2d coordinates are presented as a "stream" of data in some arbitrary order, where each data item includes the index and value of some coordinate and a bit that identifies the vector (x or y) to which it belongs. The goal is to minimize the amount of memory needed to approximate the distance. For the case of L^p-distance with p &egr; [1,2], there are good approximation algorithms that run in polylogarithmic space in d (here we assume that each coordinate is an integer with O(log d) bits). Here we prove that they do not exist for pρ2. In particular, we prove an optimal approximation-space tradeoff of approximating L^&infty; distance of two vectors. We show that any randomized algorithm that approximates L^&infty; distance of two length d vectors within factor of d^&dgr; requires ω(d^1—4&dgr;) space. As a consequence we show that for pρ2/(1—4&dgr;), any randomized algorithm that approximate L^p distance of two length d vectors within a factor d^&dgr; requires ω(d ^{1— 2< \over _p—4&dgr;}) space.The lower bound follows from a lower bound on the two-party one-round communication complexity of this problem. This lower bound is proved using a combination of information theory and Fourier analysis.

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: L. Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory (preliminary version). FOCS 1986 337--347.
• 3: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar, Information Theory Methods in Communication Complexity, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.93, May 21-24, 2002
• 4: Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. Personal communication.
• 5: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 6: 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
• 7: Jessica H. Fong , Martin Strauss, An Approximate Lp-Difference Algorithm for Massive Data Streams, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, p.193-204, February 01, 2000
• 8: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 9: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 10: Balasubramanian Kalyanasundaram and Georg Schnitger. The Probabilistic Communication Complexity of Set Intersection (preliminary Version) Proc. of 2nd Structure in Complexity Theory 1987 41--49.
• 11: W. B. Johnson and J. Lindenstrauss. Extensions of Lipshitz mapping into Hilbert space. Contemporary (MATH)ematics, 26(1984) 189--206.
• 12: A. A. Razborov, On the distributional complexity of disjointness, Theoretical Computer Science, v.106 n.2, p.385-390, Dec. 1992 [doi>10.1016/0304-3975(92)90260-M]
• 13: A. C. Yao. Lower bounds by probabilistic arguments. FOCS 1983 420--428.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Boundary representations

General Terms:
Algorithms, Experimentation, Performance, Theory