Memory-Efficient Submodular Maximization for Data Streams

This direction is merged into another direction: streaming submodular maximization. Its last version stays readable and citable here.

Version 1 of 148 papers61 conceptsfrozen 2026-10-04

In modern data science, we are often tasked with selecting a representative subset from a massive, fast-moving stream of information. Whether it is summarizing a 24-hour news cycle, selecting the most informative sensors in a global network, or curating a diverse set of movie recommendations, the goal is the same: maximize "coverage" or "diversity" while staying within a strict memory budget.

Mathematically, these problems are framed as submodular maximization. Submodular functions capture the intuitive law of diminishing returns—the marginal value of adding an item to a small set is greater than its marginal value when added to a larger set. While "greedy" algorithms work well for static datasets, they fail in streaming environments where we cannot look back at the whole stream.

The Thresholding Intuition

The core challenge of streaming submodular maximization is that we must decide whether to keep or discard an item the moment it arrives. If we are too picky, we end up with an empty set; if we are too lenient, we fill our memory with mediocre items early on.

The breakthrough solution, exemplified by SIEVE-STREAMING++ by Ehsan Kazemi and colleagues, is to use thresholding. Instead of comparing an item to every other item, the algorithm sets a "utility bar." If an item’s marginal contribution to the current set exceeds this threshold, it is accepted.

To handle the fact that we don't know the optimal threshold in advance, these algorithms maintain a small number of parallel instances, each with a different threshold. This allows the system to achieve the "Holy Grail" of a $1/2$-approximation ratio while using memory that scales only with the size of the desired output ($O(k)$), rather than the length of the stream.

Sliding Windows and Recency

In many real-world applications, data has a shelf life. A news recommendation system shouldn't care about articles from three years ago. This leads to the sliding window model, where only the most recent $W$ items are relevant.

Alessandro Epasto, Silvio Lattanzi, and Morteza Zadimoghaddam demonstrated in Submodular Optimization over Sliding Windows that you don't need to store the entire window to maintain a high-quality summary. By storing a polylogarithmic fraction of the elements—sometimes less than 1% of the window—it is possible to maintain a near-optimal summary. The intuition here is to keep a "sketch" of the data: a collection of items that were highly valuable when they arrived and haven't yet been superseded by newer, better items.

Robustness to Deletions

A newer challenge in this field is deletion-robustness. In the era of privacy regulations like GDPR, users may request that their data be deleted (the "right to be forgotten"). If a user's data was a key part of your summary, how do you replace it without re-processing the entire stream?

Research by Slobodan Mitrović in Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach and Morteza Zadimoghaddam in Deletion-Robust Submodular Maximization at Scale addresses this by maintaining redundancy. Instead of just picking the best $k$ items, these algorithms maintain a "shortlist" or "stash" of promising candidates. If a primary item is deleted, the algorithm can immediately swap in a high-quality backup from its buffer. Remarkably, the memory required for this scales logarithmically with the number of deletions, making it practical for massive scales.

Handling Complex Constraints

Real-world problems rarely have simple "pick $k$ items" constraints. We might have a knapsack constraint (items have different costs) or a matroid constraint (we need a certain number of items from different categories).

Alina Ene and Huy L. Nguyen have pushed the boundaries of what is possible in these constrained settings. In Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints, they show that even for "non-monotone" functions—where adding an item might actually decrease the total value (e.g., by making a set less diverse)—it is possible to maintain a sub-linear memory footprint.

Their work often utilizes a primal-dual framework or a dual-threshold buffering system, which provides a "second chance" for high-potential data points. As shown in Stream Clipper by Jeff Bilmes and Tianyi Zhou, these managed buffers allow streaming algorithms to achieve utility scores nearly identical to offline greedy algorithms.

The Power of Random Order

Finally, the order in which data arrives matters. While adversarial orderings can force algorithms into poor decisions, Paul Liu and Jan Vondrák showed in Cardinality constrained submodular maximization for random streams that if items arrive in a random order, we can achieve the optimal $(1 - 1/e)$ approximation ratio.

By using memory that scales linearly with the cardinality constraint and the inverse of the error tolerance, these methods bridge the gap between theoretical guarantees and practical, large-scale deployment. The intuition is that in a random stream, the early items are likely representative of the whole, allowing the algorithm to set its thresholds much more accurately than in a worst-case scenario.

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_memory_efficient_submodular_maximization_da45620d,
  title = {Memory-Efficient Submodular Maximization for Data Streams},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-efficient-submodular-maximization-for-data-streams/rdr_da45620d5bb4484dab6388e5c77a2e75},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_memory_efficient_submodular_maximization_da45620d_v1,
  title = {Memory-Efficient Submodular Maximization for Data Streams},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-efficient-submodular-maximization-for-data-streams/rdr_da45620d5bb4484dab6388e5c77a2e75/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}