Research map / Learning theory and algorithms / Clustering
Sliding Window Algorithms for k-Clustering Problems
Michele Borassi, Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, Morteza Zadimoghaddam
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed sliding-window sketch instead of SODA16 | k-clustering · COVER and SHUTTLE | space use: 5.23; 6.04; 5.07; 15.32 space decrease factor | Improved |
| Use the proposed sliding-window sketch instead of SODA16 | k-clustering · COVER and SHUTTLE | update speed: 10.88; 13.10; 9.09; 15.14 speed-up factor | Improved |
| Use the proposed sliding-window sketch instead of SODA16 | k-clustering · COVER and SHUTTLE | clustering cost ratio: 99.5%; 95.1%; 106.8%; 118.9% | Mixed |
| Store a sketch rather than recomputing k-means++ over the full window | COVERTYPE, W=40000 · k=10, k=20, and k=40 | window points stored: 3.5% (0.39%); 6.5% (0.87%); 11.3% (1.74%) | Improved |
| Store a sketch rather than recomputing k-means++ over the full window | COVERTYPE, W=40000 · k=10, k=20, and k=40 | update time: 0.45% (0.29%); 0.93% (0.63%); 1.58% (1.23%) | Improved |
| Use the proposed algorithm instead of random sampling at the same storage budget | clustering on the evaluated datasets · S1 | V-Measure: 0.933 -> 0.969 | Improved |
| Use the proposed algorithm instead of k-means++ | clustering · S1 | V-Measure: 0.969 -> 0.969 | No clear effect |
Closest papers by meaning
- Near-Optimal $k$-Clustering in the Sliding Window Model (NeurIPS 2023 · similarity 0.92)
- Dynamic k-center clustering with lifetimes (NeurIPS 2026 · similarity 0.89)
- Consistent k-Clustering (ICML 2017 · similarity 0.88)
- Improved Learning-augmented Algorithms for k-means and k-medians Clustering (ICLR 2023 · similarity 0.88)
- Fair Clustering in the Sliding Window Model (ICLR 2025 · similarity 0.88)
- Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
