In the world of big data, we often have to make decisions on the fly. Streaming algorithms are designed for this: they process data one element at a time, using very little memory, and never looking back. For years, researchers believed there was a fundamental "speed limit" to how well these algorithms could perform. For submodular maximization—a common framework for tasks like data summarization—that limit was a $1/2$-approximation. If you wanted to pick the best subset of items from a stream, you could only guarantee getting at least half the value of the true optimal set.
However, recent research has revealed that this limit isn't a property of the problem itself, but rather a consequence of assuming the worst about our data. By shifting the assumption from adversarial ordering (where an opponent arranges the data to trick the algorithm) to random ordering, a new class of algorithms is breaking through these theoretical ceilings.
The Adversarial Bottleneck
To understand why random order helps, we first have to understand why adversarial order hurts. Imagine you are trying to pick the 10 most representative images from a stream of millions. In an adversarial stream, the "best" images might all arrive at the very end. If your memory is already full of mediocre images you saw earlier, you have no way of knowing that better ones are coming, and no room to keep them if you did.
This is why, as Ethan R. Elenberg, Amin Karbasi, and colleagues point out in Streaming Weak Submodularity: Interpreting Neural Networks on the Fly, constant-factor approximations are mathematically impossible for certain functions under adversarial ordering. The algorithm simply cannot distinguish between a "good" item and a "great" item that hasn't arrived yet.
Randomness as a Representative Sample
The core intuition behind the random-order model is that any prefix of the stream is a representative sketch of the whole. If data arrives in a random permutation, the first 10% of the stream likely contains a similar distribution of values and features as the remaining 90%.
In Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams, Ashkan Norouzi-Fard, Jakub Tarnawski, and their co-authors leverage this to break the 0.5 barrier. Their algorithm, SALSA, uses the early part of the stream to estimate the potential value of items, setting a "threshold" that helps the algorithm decide which items are worth keeping later on. Because the stream is random, the threshold calculated from the beginning remains valid until the end.
Simulating Multiple Passes in One
Perhaps the most powerful trick enabled by random ordering is the ability to simulate multi-pass algorithms using only a single pass. Many high-quality optimization methods are iterative: they look at the data, update a model, and then look at the data again. In a standard stream, this is impossible.
However, if the stream is randomly ordered, we can partition it into sequential blocks. Each block acts as a fresh, independent sample of the global dataset. As Praneeth Kacham and David P. Woodruff demonstrate in Approximating the Top Eigenvector in Random Order Streams, you can treat these blocks as iterations. You use Block 1 to get a rough estimate of the top eigenvector, use Block 2 to refine it, and so on. By the time you reach the end of the stream, you have performed the equivalent of a multi-pass iterative process, all while only seeing each data point once.
Efficiency Across Domains
This "random-order dividend" extends across various complex structures:
- Graphs: In Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs, Slobodan Mitrović and Theodore Pan show that random edge arrival allows single-pass algorithms to mimic "peeling" strategies that usually require multiple passes, drastically reducing the memory needed to find dense communities.
- Matroids: For more complex constraints, Paul Liu 0001 shows in Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms that partitioning a random stream into windows for local search allows algorithms to reach optimal approximation thresholds that were previously thought to be out of reach for streaming settings.
By moving away from the "worst-case" mindset and embracing the statistical properties of random arrival, these researchers have turned the limitation of a single pass into a powerful tool for scalable optimization.