skip to main content
10.1145/1060590.1060622acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

Coresets in dynamic geometric data streams

Published: 22 May 2005 Publication History

Abstract

A dynamic geometric data stream consists of a sequence of m insert/delete operations of points from the discrete space 1,…,Δd [26]. We develop streaming (1 + ε)-approximation algorithms for k-median, k-means, MaxCut, maximum weighted matching (MaxWM), maximum travelling salesperson (MaxTSP), maximum spanning tree (MaxST), and average distance over dynamic geometric data streams. Our algorithms maintain a small weighted set of points(a coreset) that approximates with probability 2/3 the current point set with respect to the considered problem during the m insert/delete operations of the data stream. They use poly (ε-1, log m, log Δ) space and update time per insert/delete operation for constant k and dimension dHaving a coreset one only needs a fast approximation algorithm for the weighted problem to compute a solution quickly. In fact, even an exponential algorithm is sometimes feasible as its running time may still be polynomial in n. For example one can compute in poly(log n, exp(O((1+log (1⁄ε)⁄ε)d-1))) time a solution to k-median and k-means [21] where n is the size of the current point set and k and d are constants. Finding an implicit solution to MaxCut can be done in poly(log n, exp((1⁄ε)O(1))) time. For MaxST and average distance we require poly(log n, ε-1) time and for MaxWM we require O(n3) time to do this.

References

[1]
N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. Proc 28th STOC, pp. 20--29, 1996.
[2]
Z. Bar-Yossef, T.S. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan. Counting distinct elements in a data stream. Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, pages 1-10, 2002.
[3]
A. Bagchi, A. Chaudhary, D. Eppstein and M. T. Goodrich. Deterministic sampling and range counting in geometric data streams. Proc 20th Annual Symposium on Computational Geometry (SoCG), pp. 144--151, 2004.
[4]
M. Charikar, C. Chekuri, T. Feder, and R. Motwani. Incremental clustering and dynamic information retrieval. Proc 29th STOC, 626--635, 1997.
[5]
M. Charikar, K. Chen, M. Farach-Colton. Finding Frequent Items in Data Streams. Proc. 29th ICALP, pp. 693--703, 2002.
[6]
T. M. Chan. Faster core-set constructions and data stream algorithms in fixed dimensions. Proc 20th Annual Symposium on Computational Geometry (SoCG), pp. 152--159, 2004.
[7]
T. Chan, B. Sadjad. Geometric Optimization Problems Over Sliding Windows. Proc 15th Annual International Symposium on Algorithms and Computation (ISAAC), pp. 246--258, 2004.
[8]
M. Charikar, L. O'Callaghan, and R. Panigrahy. Better streaming algorithms for clustering problems. Proc 35th STOC, pp. 30--39, 2003.
[9]
G. Cormode and S. Muthukrishnan. Radial histograms for spatial streams. DIMACS Technical Report 2003-11, 2003.
[10]
G. Cormode and S. Muthukrishnan. Improved Data Stream Summaries: The Count-Min Sketch and its Applications. Proc 6th Latin American Theoretical Informatics (LATIN), pp. 29--38, 2004.
[11]
G. Cormode and S. Muthukrishnan and I. Rozenbaum. Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Sampling. DIMACS Technical Report 2005-11, 2005.
[12]
J. Feigenbaum, S. Kannan, and J. Zhang. Computing diameter in the streaming and sliding window models. Technical Report YALEU/DCS/TR-1245, Yale University, 2002.
[13]
W. Fernandez de la Vega and C. Kenyon. A Randomized Approximation Scheme for Metric MAX-CUT. J. Comput. Syst. Sci., 63(4):531-541, 2001.
[14]
P. Flajolet and G. Martin. Probabilistic counting algorithms for data base applications. Journal of Computer and System Sciences, 31:182--209, 1985.
[15]
G. Frahling, P. Indyk, and C. Sohler. Sampling in Dynamic Data Streams and Applications. To appear in Proc 21st Symposium on Computational Geometry, 2005.
[16]
H. N. Gabow. Data structures for weighted matching and nearest common ancestors with linking Proc 1st SODA, 434--443, 1990.
[17]
O. Goldreich, S. Goldwasser, D. Ron. Property testing and its connection to learning and approximation. JACM, 45(4):653--750, 1998.
[18]
S. Guha, N. Mishra, R. Motwani, and L. O'Callaghan. Clustering data streams. Proc 41st FOCS, 359--366, 2000.
[19]
S. Gunguly, M. Garofalakis, R. Rastogi. Processing Set Expressions over Continuous Update Streams. Proc ACM SIGMOD, pp. 265--276, 2003.
[20]
S. Har-Peled and A. Kushal. Smaller Coresets for k-Median and k-Means Clustering. To appear in Proc 21st Symposium on Computational Geometry, 2005.
[21]
S. Har-Peled and S. Mazumdar. Coresets for k-means and k-medians and their applications. Proc 36th STOC, 291--300, 2004.
[22]
J. Hershberger and S. Suri. Adaptive sampling for geometric problems over data streams. Proc ACM Symposium on Principles of Database Systems (PODS), 2004.
[23]
P. Indyk. Personal communication, 2004.
[24]
P. Indyk. High-dimensional Computational Geometry. Phd. thesis, Stanford University, 2000.
[25]
P. Indyk. Better algorithms for high-dimensional proximity problems via asymmetric embeddings. Proc 14th SODA, pp. 539--545, 2003.
[26]
P. Indyk. Algorithms for Dynamic Geometric Problems over Data Streams. Proc 36th STOC, pp. 373--380, 2004.
[27]
P. Indyk. Better Algorithms for high-dimensional proximity problems via asymmetric embeddings. Proc 14th SODA, pages 539--545, 2003.
[28]
A. Meyerson. Online facility location. Proc FOCS, pp. 426--431, 2001.
[29]
S. Muthukrishnan. Data streams: Algorithms and applications (invited talk at SODA'03). Available at http://athos.rutgers.edu/~muthu/stream-1-1.ps, 2003.
[30]
R. Prim. Shortest Connection Networks and some Generalizations. Bell Systems Technical Journal, 36:1389--1401, 1957.
[31]
J. Schmidt, A. Siegel, and A. Srinivasan. Chernoff-Hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223--250, 1995.
[32]
S. Suri, C. D. Toth, and Y. Zhou. Range counting over multidimensional data streams. Proc 20th Annual Symposium on Computational Geometry, pp. 160--169, 2004.

Cited By

View all
  • (2024)Turnstile ℓp leverage score sampling with applicationsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693565(36797-36828)Online publication date: 21-Jul-2024
  • (2024)No dimensional sampling coresets for classificationProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692113(1008-1049)Online publication date: 21-Jul-2024
  • (2024)Streaming Algorithms for Geometric Steiner ForestACM Transactions on Algorithms10.1145/366366620:4(1-38)Online publication date: 5-Aug-2024
  • Show More Cited By

Index Terms

  1. Coresets in dynamic geometric data streams

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing
    May 2005
    778 pages
    ISBN:1581139608
    DOI:10.1145/1060590
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 22 May 2005

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. computational geometry
    2. data structures
    3. streaming algorithms

    Qualifiers

    • Article

    Conference

    STOC05
    Sponsor:
    STOC05: Symposium on Theory of Computing
    May 22 - 24, 2005
    MD, Baltimore, USA

    Acceptance Rates

    Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

    Upcoming Conference

    STOC '25
    57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    June 23 - 27, 2025
    Prague , Czech Republic

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)86
    • Downloads (Last 6 weeks)11
    Reflects downloads up to 09 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Turnstile ℓp leverage score sampling with applicationsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693565(36797-36828)Online publication date: 21-Jul-2024
    • (2024)No dimensional sampling coresets for classificationProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692113(1008-1049)Online publication date: 21-Jul-2024
    • (2024)Streaming Algorithms for Geometric Steiner ForestACM Transactions on Algorithms10.1145/366366620:4(1-38)Online publication date: 5-Aug-2024
    • (2024)MapReduce Algorithms for Robust Center-Based Clustering in Doubling MetricsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104966(104966)Online publication date: Aug-2024
    • (2024)On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their ApplicationsJournal of Computer and System Sciences10.1016/j.jcss.2024.103506(103506)Online publication date: Jan-2024
    • (2023)Replicable clusteringProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667829(39277-39320)Online publication date: 10-Dec-2023
    • (2023)Streaming Euclidean Max-Cut: Dimension vs Data ReductionProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585170(170-182)Online publication date: 2-Jun-2023
    • (2023)Streaming Euclidean MST to a Constant FactorProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585168(156-169)Online publication date: 2-Jun-2023
    • (2023)Brief Announcement: Streaming Balanced ClusteringProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591318(311-314)Online publication date: 17-Jun-2023
    • (2023)k-Center Clustering with Outliers in the MPC and Streaming Model2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS54959.2023.00090(853-863)Online publication date: May-2023
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media