Leveraging Random Order to Break Streaming Limits

This direction is merged into another direction: adversarial arrival order. Its last version stays readable and citable here.

Version 1 of 114 papers22 conceptsfrozen 2026-10-04

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:

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.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_leveraging_random_order_to_break_streami_05c9c56d,
  title = {Leveraging Random Order to Break Streaming Limits},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/leveraging-random-order-to-break-streaming-limits/rdr_05c9c56d46b54b30bd2eaa8429661ed3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_leveraging_random_order_to_break_streami_05c9c56d_v1,
  title = {Leveraging Random Order to Break Streaming Limits},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/leveraging-random-order-to-break-streaming-limits/rdr_05c9c56d46b54b30bd2eaa8429661ed3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}