Tight results for clustering and summarizing data streams

ABSTRACT

In this paper we investigate algorithms and lower bounds for summarization problems over a single pass data stream. In particular we focus on histogram construction and K-center clustering. We provide a simple framework that improves upon all previous algorithms on these problems in either the space bound, the approximation factor or the running time. The framework uses a notion of "streamstrapping" where summaries created for the initial prefixes of the data are used to develop better approximation algorithms. We also prove the first non-trivial lower bounds for these problems. We show that the stricter requirement that if an algorithm accurately approximates the error of every bucket or every cluster produced by it, then these upper bounds are almost the best possible. This property of accurate estimation is true of all known upper bounds on these problems.

REFERENCES

• 1: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy, The Aqua approximate query answering system, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.574-576, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: Vijay Arya , Naveen Garg , Rohit Khandekar , Adam Meyerson , 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]
• 3: Michela Bertolotto , Max J. Egenhofer, Progressive vector transmission, Proceedings of the 7th ACM international symposium on Advances in geographic information systems, p.152-157, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/320134.320172]
• 4: C. Buragohain, N. Shrivastava, and S. Suri. Space efficient streaming algorithms for the maximum error histogram. Proc of. ICDE, pages 1026--1035, 2007.
• 5: Kaushik Chakrabarti , Eamonn Keogh , Sharad Mehrotra , Michael Pazzani, Locally adaptive dimensionality reduction for indexing large time series databases, ACM Transactions on Database Systems (TODS), v.27 n.2, p.188-228, June 2002 [doi>10.1145/568518.568520]
• 6: 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]
• 7: Moses Charikar , Liadan O'Callaghan , Rina Panigrahy, Better streaming algorithms for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780548]
• 8: Julia Chuzhoy , Sudipto Guha , Eran Halperin , Sanjeev Khanna , Guy Kortsarz , Robert Krauthgamer , Joseph (Seffi) Naor, Asymmetric k-center is log^* n-hard to approximate, Journal of the ACM (JACM), v.52 n.4, p.538-551, July 2005 [doi>10.1145/1082036.1082038]
• 9: Minos Garofalakis , Phillip B. Gibbons, Wavelet synopses with error guarantees, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564746]
• 10: Sudipto Guha, Space efficiency in synopsis construction algorithms, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 11: S. Guha and B. Harb. Approximation algorithms for wavelet transform coding of data streams. IEEE Trans. of Info. Theory, 2008.
• 12: 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]
• 13: Sudipto Guha , Nick Koudas , Kyuseok Shim, Approximation and streaming algorithms for histogram construction problems, ACM Transactions on Database Systems (TODS), v.31 n.1, p.396-438, March 2006 [doi>10.1145/1132863.1132873]
• 14: Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003 [doi>10.1109/TKDE.2003.1198387]
• 15: Sudipto Guha , Kyuseok Shim, A Note on Linear Time Algorithms for Maximum Error Histograms, IEEE Transactions on Knowledge and Data Engineering, v.19 n.7, p.993-997, July 2007 [doi>10.1109/TKDE.2007.1039]
• 16: Sudipto Guha , Kyuseok Shim , Jungchul Woo, REHIST: relative error histogram construction algorithms, Proceedings of the Thirtieth international conference on Very large data bases, p.300-311, August 31-September 03, 2004, Toronto, Canada
• 17: Dorit S. Hochbaum , David B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM (JACM), v.33 n.3, p.533-550, July 1986 [doi>10.1145/5925.5933]
• 18: Yannis E. Ioannidis, Universality of Serial Histograms, Proceedings of the 19th International Conference on Very Large Data Bases, p.256-267, August 24-27, 1993
• 19: H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel, Optimal Histograms with Quality Guarantees, Proceedings of the 24rd International Conference on Very Large Data Bases, p.275-286, August 24-27, 1998
• 20: Panagiotis Karras , Dimitris Sacharidis , Nikos Mamoulis, Exploiting duality in summarization with deterministic guarantees, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281235]
• 21: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 22: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 23: A. Meyerson, Online Facility Location, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.426, October 14-17, 2001