Single-Pass Optimization for Memory-Constrained Data Streams

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

Version 1 of 145 papers45 conceptsfrozen 2026-10-04

In the era of terabyte-scale genomics and high-velocity sensor networks, data often arrives as a "firehose"—a continuous stream that is too massive to store in its entirety. Traditional algorithms, which assume the luxury of multiple passes over a static dataset, become unusable. Instead, researchers are developing a new class of algorithms designed to process data in a single pass using a memory footprint that is significantly smaller than the total input size.

The core challenge of this research direction is making immediate, often irrevocable decisions about which information to keep and which to discard, while still providing mathematical guarantees that the final result is close to the global optimum.

The Memory-Accuracy Trade-off

The fundamental constraint in streaming environments is the inability to revisit past data. As Graham Cormode explores in Sequence distance embeddings, complex metrics like edit distance are difficult to compute when you cannot see both sequences at once. The solution is to "embed" or "sketch" the data—transforming high-dimensional objects into compact summaries (like sparse vectors) where simple calculations can approximate complex relationships.

This sketching philosophy extends to clustering. Standard $k$-means (Lloyd’s algorithm) requires multiple passes over the data to update cluster centers. However, Michael Shindler, Alex Wong, and Adam Meyerson demonstrate in Fast and Accurate k-means For Large Datasets that it is possible to maintain an accurate clustering by processing points sequentially and storing only a small set of weighted "coreset" points.

Irrevocable Decisions and Submodular Maximization

A recurring theme in this field is the "irrevocable decision" problem: when a data point arrives, the algorithm must decide immediately whether to include it in the solution or discard it forever. This is particularly difficult for submodular maximization, a framework used for tasks like document summarization or sensor placement where adding an item has "diminishing returns."

To solve this, Roie Levin and David Wajc in Streaming Submodular Matching Meets the Primal-Dual Method utilize primal-dual frameworks to set dynamic thresholds. If an incoming item's marginal contribution exceeds a certain value, it is kept. Alina Ene and Huy Nguyen have further refined these techniques in Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints, proving that we can achieve near-optimal results even when we can't see the future of the stream.

Identifying the Best from the Rest

In many applications, the goal isn't just to summarize the stream, but to find the "best" items within it. This is the focus of streaming Multi-Armed Bandits (MAB). In Optimal Streaming Algorithms for Multi-Armed Bandits, Tianyuan Jin and colleagues address the problem of identifying the highest-performing options when memory is so limited it can only store a single "active" candidate at a time.

Similarly, Maryam Aliakbarpour and Adam Smith look at Hypothesis Selection with Memory Constraints, asking how we can distinguish between many competing scientific theories using only a few bits of storage. The intuition here is to maintain a "summary statistic" that is just informative enough to eliminate poor hypotheses as data flows by.

Real-World Impact: Genomics and Beyond

The practical necessity of these algorithms is most evident in biology. Modern DNA sequencers produce terabytes of data that exceed the RAM of even powerful workstations. Benjamin Coleman and Anshumali Shrivastava show in One-Pass Diversified Sampling with Application to Terabyte-Scale Genomic Sequence Streams how hashing-based sketches can downsample these streams in real-time. By preserving rare but important sequences while discarding redundant ones, they reduce memory usage by 1000x compared to traditional batch methods.

Whether it is Paul Bertone optimizing genomic DNA tiling arrays or Wenbin Li developing One-Pass Metric Learning for video anomaly detection, the shared goal is the same: transforming the "curse" of massive, streaming data into a manageable computational task through clever, memory-efficient summaries.

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_single_pass_optimization_for_memory_cons_7cb7e860,
  title = {Single-Pass Optimization for Memory-Constrained Data Streams},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/single-pass-optimization-for-memory-constrained-data-streams/rdr_7cb7e860375e4442a66eee73eb750597},
  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_single_pass_optimization_for_memory_cons_7cb7e860_v1,
  title = {Single-Pass Optimization for Memory-Constrained Data Streams},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/single-pass-optimization-for-memory-constrained-data-streams/rdr_7cb7e860375e4442a66eee73eb750597/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}