Improved Algorithms for Time Decay Streams

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.27OpenAlexW2978315961MaRDI QIDQ5875480

Enayat Ullah, Harry Lang, Vladimir Braverman, Samson Zhou

Publication date: 3 February 2023

Full work available at URL: https://arxiv.org/abs/1907.07574

zbMATH Keywords

approximation algorithmsstreaming algorithmsfacility location and clustering

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed streams algorithms for sliding windows
• Computing diameter in the streaming and sliding-window models
• Data streams. Models and algorithms.
• Frequent Directions: Simple and Deterministic Matrix Sketching
• Randomized Composable Core-sets for Distributed Submodular Maximization
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• On coresets for k-means and k-median clustering
• Better streaming algorithms for clustering problems
• Matrix approximation and projective clustering via volume sampling
• Time-decaying Sketches for Robust Aggregation of Sensor Data
• A PTAS for k-means clustering based on weak coresets
• Sampling Algorithms and Coresets for $\ell_p$ Regression
• Decomposable searching problems I. Static-to-dynamic transformation
• Clustering Problems on Sliding Windows
• Maintaining Stream Statistics over Sliding Windows
• Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.
• Numerical linear algebra in the streaming model
• Clustering on Sliding Windows in Polylogarithmic Space.
• Theoretical Computer Science
• Time-decaying sketches for sensor data aggregation
• A unified framework for approximating and clustering data
• GEOMETRIC OPTIMIZATION PROBLEMS OVER SLIDING WINDOWS
• Maintaining time-decaying stream aggregates
• Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering