Streaming Algorithms with Few State Changes

Rajesh Jayaram, David P. Woodruff, Samson Zhou

In this paper, we study streaming algorithms that minimize the number of changes made to their internal state (i.e., memory contents). While the design of streaming algorithms typi…