Research map / Learning theory and algorithms / Clustering

Space-Optimal Streaming Algorithms via Efficient Encodings

NeurIPS 2026 · Learning theory and algorithms › Clustering · approach: Coresets and dynamic clustering

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes space-optimal streaming coreset constructions by using efficient encodings, improving on merge-and-reduce and online sensitivity sampling, which need more space than an optimal coreset.

Problem

Maintaining a small weighted subset (coreset) of a streaming point set in R^d that approximates objective values for a class of query functions, using space close to the size of an optimal coreset.

Approach

Uses efficient encodings so that the streaming algorithm's space matches the size of an optimal coreset, whereas merge-and-reduce and online sensitivity sampling incur overhead beyond that size.

Key results

• Abstract states prior methods (merge-and-reduce, online sensitivity sampling) required more space than the size of an optimal coreset; the proposed approach addresses this gap (specific numbers not stated in provided text).

Limitations

• Full text unavailable; limitations not determinable from abstract.

Experimental setup

Baselines: merge-and-reduce online sensitivity sampling

Builds on: merge-and-reduce online sensitivity sampling

Closest papers by meaning

• Clustering High Dimensional Dynamic Data Streams (ICML 2017 · similarity 0.90)
• High-Dimensional Geometric Streaming for Nearly Low Rank Data (ICML 2024 · similarity 0.89)
• Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost (NeurIPS 2023 · similarity 0.88)
• Learning-Augmented Streaming Algorithms for Correlation Clustering (NeurIPS 2025 · similarity 0.87)
• Faster Approximation Algorithms for k-Center via Data Reduction (ICML 2025 · similarity 0.85)
• Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs (NeurIPS 2026 · similarity 0.85)