Streaming Algorithms

Follow this topic Ask about this topic

Streaming algorithms study how to process data as it arrives without storing or repeatedly revisiting the entire dataset, which matters when data is too large, fast-changing, or costly to retain. Core approaches include sketches, sampling, and coresets for compact summaries, alongside online optimization and state-tracking methods for tasks such as PCA, clustering, regression, and reinforcement learning. Current work also applies these ideas to real-time systems, where memory, computation, communication, and latency are tightly constrained. A central challenge is balancing accuracy and formal guarantees against limited resources, especially when the data distribution changes or the stream contains outliers.

Latest papers

61 papers9 papers in the last four weeks, up 80% on the four weeks before. 0.1% of all new papers.

The Cost of Working Memory in Streaming Mean Estimation
Oct 29, 2026Zeyu Wu, Zihao Wang, Minghua DengStreaming Algorithms Minimax Estimation
Frame-Wise Streaming for Efficient Learned Speech Compression
Oct 15, 2026Yuhan Liu, Jun Xu, Fengxi Zhang +2Neural Audio Codecs Speech Processing
School of Information Science and Electronic Engineering, Shanghai Jiao Tong University
Online Tokenization with Optimal Delay in Linear Time
Oct 13, 2026Mina Dalirrooyfard, Christopher YeTokenization Subword Tokenization
Morgan Stanley · University of California San Diego
Asymptotic Risk of Learning-Rate Schedules for Least-Squares Regression with Discretely Distributed Features
Oct 12, 2026Noé Colomban, Francis Bach, Fabian SchaippLearning Rate Scheduling Stochastic Gradient Descent
Inria - École Normale Supérieure PSL Research University
Sustainable Cloud-Fog-Edge Systems for Smart Buildings: Algorithmic Adaptation under Memory Constraints and Dynamic Orchestration Strategies
Oct 9, 2026Mamadou Sow, Christophe CerinEdge-Cloud Computing Edge Computing
University Sorbonne Paris Nord LIPN, UMR CNRS 7030 Villetaneuse, France · University Sorbonne Paris Nord LIPN, UMR CNRS 7030 INRIA DATAMOVE Paris/Grenoble, France
Rethinking Tabular Foundation Models On Data Streams
Oct 4, 2026Nilesh Verma, Daniel Nowak-Assis, Afonso Lourenço +4Tabular Foundation Models Tabular ICL
AI Institute, University of Waikato, New Zealand · LIP6, CNRS, Sorbonne Universit´e, France · GECAD, Polytechnic of Porto, Portugal
Factorized Delayed Streams Modeling for LLM-based Streaming ASR
Oct 3, 2026Tatsunari Takagi, Kai Washizaki, Atsushi Kojima +3Streaming ASR Speech Language Models
SB Intuitions · Toyohashi University of Technology
ArrivalBench: Agent-Generated Data Pipelines Are Correct Once and Wrong Under Time
Oct 1, 2026Pranay KothariAI Agent Benchmarks LLM Agent Evaluation
Department of Computer Science, University of Oxford
Streaming algorithms for robust max-min diversification
Oct 1, 2026Andrea Pietracaprina, Geppino Pucci, Stefano ZanonCoreset Selection Approximation Algorithms
Department of Information Engineering, University of Padova, Italy
Component-Weighted Centroid Search for Exact Incremental BPE
Sep 30, 2026Harshit Verma, Rex YingSubword Tokenization Byte-Pair Encoding
Yale University
Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy
Sep 22, 2026Anming Gu, Syamantak Kumar, Kevin Tian +1Principal Component Analysis Differential Privacy
University of Texas at Austin
Look Less, Hear Better: Jointly Rewarded GRPO for Streaming ASR
Sep 16, 2026Xiuwen ZhengStreaming ASR Speech Language Models
University of Illinois Urbana-Champaign
Rotation-Based Subspace Tracking for Robust Kernel PCA on Streaming Data
Sep 14, 2026Kris Lokere, John FossacecaPrincipal Component Analysis Streaming Algorithms
Harvard University, Cambridge, MA, USA · George Washington University, Washington, DC, USA
Parameterized and Streaming Algorithms for Euclidean Fair $k$ -Center Clustering
Sep 6, 2026Zeyu Lin, Chaoqi Jia, Longkun Guo +1Clustering Approximation Algorithms
School of Mathematics and Statistics, Fuzhou University, Fuzhou 350116, China · School of Accounting, Information Systems and Supply Chain, RMIT University, VIC 3000, Australia
Towards Stream Learning on Embedded Systems: Benchmarking the Memory Consumption of Stream Learning Methods
Aug 31, 2026Sebastian Buschjäger, Nuwan Gunasekara, Heitor Murilo GomesEdge ML Streaming Algorithms
Lamarr Institute, Dortmund, Germany · Lamarr Institute, Halmstad University, Sweden · Victoria University of Wellington, New Zealand
RECAST: Recent & Context-Aware Sampling for Test-Time Adaptation in Streaming Biosignals
Aug 28, 2026Yong-Yeon Jo, Junho Song, Joon-myoung KwonAdaptive Sampling Continual Test-Time Adaptation
Medical AI Co., Ltd. Seoul, Republic of Korea
Constrained Hyperparameter Optimization for Streaming Data
Aug 25, 2026Bruno Veloso, João GamaHyperparameter Optimization Constrained Optimization
FEP - School of Economics and Management, University of Porto, Porto, Portugal · INESC TEC, Porto, Portugal
When to Retrain: An Empirical Study of Retraining Policies for Streaming ML Under Concept Drift, Budget, and Latency Constraints
Aug 19, 2026Sawan DasariDrifting Models Concept Drift
Prof-K: Probabilistic One-Pass Filtering for Efficient Top-k Selection
Aug 12, 2026Tadeusz Dziarmaga, Witold Sikora, Łukasz Struski +2Streaming Algorithms
Jagiellonian University
Adaptive Data Admission and Retention for Streaming Federated Learning
Jul 27, 2026Zhuoyi Zhao, Ben LiangAdaptive Sampling Federated Learning
University of Toronto · Toronto, ON, Canada
Online Variance Reduction for Domain Adaptation on Streaming Data
Jul 22, 2026Andrea NapoliDomain Adaptation Maximum Mean Discrepancy
Department of Electronics and Computer Science University of Southampton, UK
Panache: One-Pass Motif Discovery at Every Window Length
Jul 20, 2026Tej Sanibh RanadeStreaming Algorithms
Independent Researcher
RT-Tango: Real-Time Distributed Binaural Speech Enhancement for Low-Power Hearing Aid Devices
Jul 2, 2026Z. Benslimane, P. Chouteau, M. Poreba +4Speech Processing Speech Enhancement
Universit´e Paris-Saclay, CEA, List, F-91120 Palaiseau, France · Universit´e de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Online TT-ALS for Streaming Tensor Decomposition with Incremental Orthogonalization
Jun 30, 2026Hiroki Takeda, Yuto Miyatake, Daisuke FurihataTensor Decomposition TT Decomposition
Department of Pure and Applied Mathematics, The University of Osaka, Japan · D3 Center, The University of Osaka, Japan
Space-Efficient Language Generation in the Limit
Jun 24, 2026Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov +2Automata Learning Streaming Algorithms
EPFL, Switzerland · Stanford University, USA
Latency-Configurable Streaming Speech Enhancement via Asymmetric Temporal Padding
Jun 18, 2026Yunsik Kim, Yoonyoung ChungSpeech Enhancement Streaming Algorithms
Department of Electrical Engineering, Pohang University of Science and Technology (POSTECH), Pohang 37673, Republic of Korea · Intus Co. Ltd., Pohang 37673, Republic of Korea
Renewable Lasso without Batch-Number Constraints: A Gradient-Enhanced Approach
Jun 10, 2026Junzhuo Gao, Ling Peng, Xu Guo +1Generalized Linear Models Streaming Algorithms
a Department of Mathematics, City University of Hong Kong, Hong Kong, China · e CityUHK Shenzhen Research Institute, Shenzhen, China[stat.ML] · b School of Statistics and Data Science, Jiangxi University of Finance and Economics, Nanchang, Jiangxi, China +2
SSR-Merge: Subspace Signal Routing for Training-Free LoRA Merging in Diffusion Models
Jun 9, 2026Zhengxuan Wei, Yi Dong, Zonghui Li +6Low-Rank Adaptation Diffusion Models
School of Intelligence Science and Technology, Nanjing University, China · vivo BlueImage Lab, vivo Mobile Communication Co., Ltd., China · ShanghaiTech University +2
Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits
Jun 8, 2026Vladimir Braverman, Chen Wang, Liudeng Wang +1Multi-Armed Bandits Best-Arm Identification
Johns Hopkins University · Rensselaer Polytechnic Institute · Texas A&M University
Towards Tight Bounds for Streaming Attention
Jun 5, 2026Justin Y. Chen, Ying Feng, Piotr Indyk +3Efficient Attention KV-Cache Compression
MIT · EPFL

Oct 29, 2026J/K move · Enter open · S save

The Cost of Working Memory in Streaming Mean Estimation

Zeyu Wu, Zihao Wang, Minghua Deng

Streaming Algorithms Minimax Estimation Information-Theoretic Lower Bounds

Open paper AskPDF arXiv

A streaming estimator must compute from the evidence that fits in memory. We determine when storing an accurate mean is easier than computing it. For Gaussian mean estimation over the Euclidean unit ball in

\mathbb{R}^d

, we establish the minimax rate under squared error with

K

persistent states, a known horizon, and a public time index:

\min\{1, K^{-2/d}+\frac{d}{n} (1+\frac{\log(ed)}{1+(\log K)/d})\}

. Unrestricted computation followed by

K

-level encoding has rate

\min\{1,d/n+K^{-2/d}\}

. At a fixed sufficiently small error, statistically optimal sample size therefore requires order

d\log d

working bits, while order

d

bits suffice to store the answer. The lower bound tracks repeated state compression through an entropy potential obtained by Gaussian smoothing. A matching construction combines a multiscale modular counter with workspace reused across coordinate groups. In one dimension, it attains the terminal rate

n^{-1}+K^{-2}

. Any fixed confidence requirement that the realized loss not exceed the zero baseline preserves these rates. Increasing confidence creates a further memory requirement: at fixed nontrivial risk in every fixed dimension, failure probability

e^{-γn}

requires and permits order

\log n

working states for sufficiently small fixed

γ>0

. In the scalar problem, a fixed terminal alphabet suffices under the same protection. These bounds separate the memory needed to represent an answer from the memory needed to accumulate evidence and validate a decision.