Streaming Submodular Maximization with Sublinear Memory

179 concepts80 papers1 proposal

Imagine you are tasked with creating a real-time video summary from a continuous live camera feed, or selecting a representative subset of sensor nodes across a massive, expanding network. In these scenarios, data arrives sequentially in an endless stream. You cannot store the entire history of the stream due to strict hardware memory limits, yet you must make immediate, irrevocable decisions about which data points to keep and which to discard.

Mathematically, these problems are often framed as submodular function maximization. A set function $f$ is submodular if it satisfies the property of diminishing returns: adding an element to a small set provides greater or equal marginal utility than adding that same element to a larger superset.

In an offline setting, a simple greedy algorithm—which repeatedly scans the entire dataset and picks the item with the highest marginal gain—yields excellent approximation guarantees. However, as noted by Chien-Chung Huang et al. in Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint, traditional offline optimization techniques fail in streaming environments because they require random access to the full dataset or demand excessive memory.

To scale to massive datasets, a new paradigm has emerged: streaming submodular maximization. The core goal of this research direction is to design single-pass algorithms that achieve provable approximation ratios while maintaining a sublinear memory footprint—often scaling only with the size of the desired output set ($k$) rather than the length of the stream ($n$).

The Core Mechanism: Adaptive Thresholding

How can an algorithm decide whether to accept an item without knowing what items will arrive in the future? If it sets the bar for acceptance too low, it will fill its memory budget $k$ immediately with mediocre items. If it sets the bar too high, it will reject good items early on and end up with an empty or under-filled budget.

The foundational solution to this dilemma is thresholding. Instead of comparing an item to all other items, the algorithm evaluates whether an item's marginal utility exceeds a fixed value $\tau$. If it does, the item is added to the running solution.

To make this work without prior knowledge of the stream's contents, algorithms employ adaptive thresholding. The algorithm maintains a collection of parallel instances, each running with a different guess for the optimal value ($OPT$). As the stream progresses, these guesses are dynamically updated or filtered.

For example, Zhengchen Yang et al. in Online Submodular Maximization via Adaptive Thresholds demonstrate that an adaptive thresholding framework can maintain strong theoretical performance while restricting memory usage to be strictly proportional to the number of items being selected ($O(k)$). By evaluating each item against a mathematically optimized, evolving threshold, the system avoids the need to store past elements to validate new ones.

Buffering, Stashing, and Dynamic Swapping

While adaptive thresholding prevents the algorithm from filling up too early with low-quality items, it can still suffer from information loss if spectacular items arrive late in the stream after the budget is exhausted. To overcome this, modern streaming algorithms introduce a buffer or stash to enable item swapping.

Instead of making completely irrevocable choices, the algorithm maintains an active candidate set. When a new item arrives, its marginal utility is compared against the items already stored in the buffer. If the new item provides a significant enough boost to the objective function, it is swapped in, and a lower-value item is evicted.

[Incoming Element] ──> (Evaluate Marginal Utility)
                             │
                             ├──> Exceeds Threshold? ──> [Add to Buffer]
                             │
                             └──> Better than Existing? ──> [Swap & Evict Lowest]

This swap-heavy approach underpins many state-of-the-art streaming frameworks. Honglian Wang et al. in Streaming Stochastic Submodular Maximization with On-Demand User Requests show that maintaining active candidate sets and performing item swaps based on marginal utility allows for high-quality subset selection without storing the entire history of the data stream.

To keep memory sublinear, the size of this secondary buffer must be carefully controlled. Aravind Reddy et al. proved in One-Pass Algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes that by scaling the stash size logarithmically relative to the objective function's potential improvement, algorithms can achieve performance competitive with offline methods while keeping memory growth sublinear. For more complex structural constraints, such as matroids, Paul Liu 0001 et al. in Streaming Submodular Maximization Under Matroid Constraints introduced "fractional swapping" techniques, which update fractional memberships rather than binary choices to break traditional approximation barriers.

Overcoming Non-Monotonicity and Complex Constraints

The streaming problem becomes significantly harder when the objective function is non-monotone (meaning the addition of an item can actually decrease the total value, such as in directed graph cuts or diverse data summarization) or when complex constraints (like fairness or multi-category budgets) are enforced.

In the non-monotone setting, early choices can actively harm later performance. To address this, Chandra Chekuri et al. in Streaming Algorithms for Submodular Function Maximization combined thresholding with randomized buffering to achieve the first single-pass streaming algorithms for non-monotone functions under complex $p$-matchoid constraints, using near-optimal $O(k \log k)$ space. To generalize these successes, Ran Haba et al. in Streaming Submodular Maximization under a k-Set System Constraint designed a mathematical framework that systematically converts streaming algorithms designed for monotone functions into ones capable of handling non-monotone functions.

When fairness constraints are introduced—such as ensuring balanced demographic representation in a data summary—achieving a feasible solution in a single pass can become mathematically impossible under strict memory limits. As shown by Marwa El Halabi et al. in Fairness in Streaming Submodular Maximization over a Matroid Constraint, enforcing strict fairness lower bounds can force an algorithm to require exponential memory. The authors resolved this by demonstrating that relaxing the fairness bounds by a small constant factor allows streaming algorithms to operate within polynomial memory limits while still providing provable performance guarantees.

Resilience Against Deletions and Temporal Decay

A final, critical facet of streaming submodular maximization is robustness over time. In real-world streams, data is dynamic: elements may be explicitly deleted due to privacy regulations (like the "right to be forgotten"), or they may naturally expire due to temporal decay.

If an algorithm selects an optimal subset of size $k$, and an adversary subsequently deletes a portion of those selected items, the remaining set could be highly sub-optimal. To prevent this, robust streaming algorithms must build redundancy into their memory buffers without blowing up their space complexity.

Slobodan Mitrović et al. addressed this in Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach by introducing a partitioned thresholding strategy that maintains a small, highly redundant summary of data that remains effective even after adversarial deletions.

Crucially, this redundancy does not require linear memory scaling. Work by Morteza Zadimoghaddam et al. in Deletion-Robust Submodular Maximization at Scale and Ehsan Kazemi et al. in Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints proved that robust summaries can be designed such that memory requirements scale logarithmically with the number of potential deletions.

For streams characterized by continuous temporal decay rather than discrete deletions, Junzhou Zhao et al. in Submodular Optimization over Streams with Inhomogeneous Decays showed that algorithms can entirely avoid storing historical data by using a calculated "compensation value" to estimate the potential utility of expired items, achieving massive speedups and low memory footprints.

By combining adaptive thresholding, intelligent candidate buffering, and mathematical relaxations of constraints, streaming submodular maximization successfully bridges the gap between theoretical optimization and the memory-constrained realities of big data infrastructure.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_streaming_submodular_maximization_02e1893a,
  title = {streaming submodular maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/streaming-submodular-maximization/rdr_02e1893a822c400991ea3de141d11054},
  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_streaming_submodular_maximization_02e1893a_v1,
  title = {streaming submodular maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/streaming-submodular-maximization/rdr_02e1893a822c400991ea3de141d11054/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake