Better streaming algorithms for clustering problems

ABSTRACT

We study clustering problems in the streaming model, where the goal is to cluster a set of points by making one pass (or a few passes) over the data using a small amount of storage space. Our main result is a randomized algorithm for the k--Median problem which produces a constant factor approximation in one pass using storage space O(k poly log n). This is a significant improvement of the previous best algorithm which yielded a 2^O(1/ε) approximation using O(n^ε) space. Next we give a streaming algorithm for the k--Median problem with an arbitrary distance function. We also study algorithms for clustering problems with outliers in the streaming model. Here, we give bicriterion guarantees, producing constant factor approximations by increasing the allowed fraction of outliers slightly.

REFERENCES

• 1: Miklós Ajtai , T. S. Jayram , Ravi Kumar , D. Sivakumar, Approximate counting of inversions in a data stream, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509964]
• 2: N. Alon , S. Dar , M. Parnas , D. Ron, Testing of clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.240, November 12-14, 2000
• 3: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 4: Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
• 5: Vijay Arya , Naveen Garg , Rohit Khandekar , Kamesh Munagala , Vinayaka Pandit, Local search heuristic for k-median and facility location problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.21-29, July 2001, Hersonissos, Greece [doi>10.1145/380752.380755]
• 6: Ziv Bar-Yosseff , Ravi Kumar , D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 06-08, 2002, San Francisco, California
• 7: Moses Charikar , Chandra Chekuri , Tomás Feder , Rajeev Motwani, Incremental clustering and dynamic information retrieval, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.626-635, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258657]
• 8: Moses Charikar , Sudipto Guha, Improved Combinatorial Algorithms for the Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.378, October 17-18, 1999
• 9: Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.1-10, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301257]
• 10: Moses Charikar , Samir Khuller , David M. Mount , Giri Narasimhan, Algorithms for facility location problems with outliers, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.642-651, January 07-09, 2001, Washington, D.C., United States
• 11: Moses Charikar , Rina Panigrahy, Clustering to minimize the sum of cluster diameters, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.1-10, July 2001, Hersonissos, Greece [doi>10.1145/380752.380753]
• 12: M. Dyer and A. M. Frieze. A simple heuristic for the p--center problem. Operations Research Letters, v. 3, 1985.
• 13: J. Feigenbaum, S. Kannan, M. Strauss, and M. Viswanathan. An approximate L1-difference algorithm for massive data streams. Proc. FOCS, 2000.
• 14: 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]
• 15: Sudipto Guha , Nick Koudas , Kyuseok Shim, Data-streams and histograms, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.471-475, July 2001, Hersonissos, Greece [doi>10.1145/380752.380841]
• 16: S. Guha , N. Mishra , R. Motwani , L. O'Callaghan, Clustering data streams, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.359, November 12-14, 2000
• 17: O. Kariv and S. L. Hakimi. An algorithmic approach to network location problems, part ii: p-medians. SIAM Journal of Appl. Math, v. 37, 1979.
• 18: M. Henzinger, P. Raghavan, and S. Rajagopalan. Computing on data streams. In DIMACS series in Discrete Mathematics and Theoretical Computer Science, v. 50, 1999.
• 19: D. S. Hochbaum and D. B. Shmoys. A best possible approximation algorithm for the k--Center problem. Mathematics of Operations Research, v. 10, 1985.
• 20: Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301366]
• 21: Piotr Indyk, A Sublinear Time Approximation Scheme for Clustering in Metric Spaces, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.154, October 17-18, 1999
• 22: 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
• 23: Kamal Jain , Vijay V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM (JACM), v.48 n.2, p.274-296, March 2001 [doi>10.1145/375827.375845]
• 24: Madhukar R. Korupolu , C. Greg Plaxton , Rajmohan Rajaraman, Analysis of a local search heuristic for facility location problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.1-10, January 25-27, 1998, San Francisco, California, United States
• 25: Jyh-Han Lin , Jeffrey Scott Vitter, Approximation algorithms for geometric median problems, Information Processing Letters, v.44 n.5, p.245-249, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90208-D]
• 26: Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
• 27: Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Random sampling techniques for space efficient online computation of order statistics of large datasets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.251-262, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 28: R. R. Mettu , C. G. Plaxton, The online median problem, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.339, November 12-14, 2000
• 29: R. Mettu and C. G. Plaxton. Optimal time bounds for approximate clustering. Proc. UAI, 2002.
• 30: A. Meyerson, Online Facility Location, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.426, October 14-17, 2001
• 31: A. Meyerson, L. O'Callaghan and S. Plotkin. Approximating k--Median: A sampling-based approach. Unpublished manuscript, 2001.
• 32: Nina Mishra , Dan Oblinger , Leonard Pitt, Sublinear time approximate clustering, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.439-447, January 07-09, 2001, Washington, D.C., United States
• 33: Mikkel Thorup, Quick k-Median, k-Center, and Facility Location for Sparse Graphs, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.249-260, July 08-12, 2001
• 34: Neal E. Young, K-medians, facility location, and the Chernoff-Wald bound, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.86-95, January 09-11, 2000, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
clustering, k-median, streaming algorithm