Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance

Michael E. Saks, C. Seshadhri

TL;DR

This paper introduces a highly space-efficient streaming algorithm that provides a $(1 + \delta)$-multiplicative approximation for the "distance to monotonicity" (how many elements you must remove to make a sequence sorted). By cleverly "forgetting" parts of a standard dynamic programming state, the authors achieve polylogarithmic space complexity, significantly improving upon previous algorithms that could only manage a factor-2 approximation in similar space.

What Problem Does This Paper Address?

In the world of big data, we often encounter "streaming" scenarios where we can only look at data once, from left to right, and cannot store the whole thing. Two classic problems in this space are finding the Longest Increasing Subsequence (LIS) and the Longest Common Subsequence (LCS).

While finding the exact LIS is easy with $O(n \log n)$ time, doing it in a stream with limited memory is hard. Specifically, the authors look at the distance to monotonicity (DM), which is $n$ minus the length of the LIS. Previous polylogarithmic-space algorithms were "blunt instruments"—they couldn't distinguish between an LIS of length $n/2$ and an LIS of length $n$. This paper seeks a "fine-grained" approximation $(1+\delta)$ using minimal memory.

Methods

The core of the paper is a randomized "forgetting" version of a classic dynamic program.

  1. The "Forgetting" DP: A standard DP for LIS keeps track of the best possible LIS ending at every previous index. To save space, this algorithm maintains a small, evolving set of "active" indices $R$.
  2. Probabilistic Pruning: At each time step $t$, the algorithm adds the current element to $R$. Crucially, it then deletes each existing index $i$ in $R$ with a specific probability $\alpha(i, t)$. This probability is designed so that the density of remembered indices decays as we move further back in time (roughly $1/(t-i)$).
  3. Poset Framework: The authors generalize the problem to finding the Minimum-Defect Path in a partially ordered set (poset). This abstraction allows them to apply the same "forgetting" logic to other problems, like the Asymmetric Edit Distance, where one string is fixed (random access) and the other is streaming.

Datasets

As a theoretical computer science paper, it does not use empirical datasets. Instead, the authors provide rigorous mathematical proofs of the algorithm's performance bounds (space complexity and error probability) across all possible input sequences of length $n$.

Key Insights and Ideas

  • Trading Space for Accuracy: The "aha moment" is the realization that we don't need to remember every previous DP state to get a good approximation. By keeping a "fading memory" of the stream, we can still estimate the distance to monotonicity very accurately.
  • The Power of Asymmetry: For the Edit Distance problem, the authors show that if you have random access to one string (the "fixed" string), you can approximate the edit distance to a streaming "input" string much more efficiently than in the standard two-stream model.
  • Simplicity: Despite the complex analysis, the LIS approximation algorithm is remarkably simple—only about three lines of pseudocode. It essentially implements a "sketch" of a dynamic programming table.

Key Results

  • Distance to Monotonicity: Provides a $(1 + \delta)$-multiplicative approximation using only $O(\frac{\log^2 n}{\delta})$ space. This is a major qualitative jump from the previous best polylog-space result (a 2-approximation).
  • Asymmetric Edit Distance:
    • Randomized: Achieves an additive $\delta n$ approximation using $O(\frac{k \log^2 n}{\delta})$ space, where $k$ is the maximum number of times any single symbol appears in the fixed string.
  • Deterministic: Provides a $\sqrt{n}$-space deterministic algorithm for cases where $k$ is large, beating the randomized version's dependence on symbol frequency.

Limitations and Future Work

  • The "k" Dependency: The randomized LCS/Edit Distance algorithm's space complexity depends on $k$ (symbol frequency). If a single character (like 'e') appears many times in a string, the space requirement grows.
  • LIS vs. DM: While the algorithm approximates the distance to monotonicity $(n - LIS)$ very well, it is less effective at approximating the LIS length itself when the LIS is very small (e.g., $O(\sqrt{n})$).
  • Open Questions: The authors point out that achieving a constant factor approximation for LIS length in $o(\sqrt{n})$ space remains a major open problem in the streaming community.

Summary updated

Abstract

Approximating the length of the longest increasing sequence (LIS) of an array is a well-studied problem. We study this problem in the data stream model, where the algorithm is allowed to make a single left-to-right pass through the array and the key resource to be minimized is the amount of additional memory used. We present an algorithm which, for any δ > 0, given streaming access to an array of length n provides a (1 + δ)-multiplicative approximation to the distance to monotonicity (n minus the length of the LIS), and uses only O((log2 n)/δ) space. The previous best known approximation using polylogarithmic space was a multiplicative 2-factor. The improved approximation factor reflects a qualitative difference between our algorithm and previous algorithms: previous polylogarithmic space algorithms could not reliably detect increasing subsequences of length as large as n/2, while ours can detect increasing subsequences of length βn for any β > 0. More precisely, our algorithm can be used to estimate the length of the LIS to within an additive δn for any δ > 0 while previous algorithms could only achieve additive error n(1/2 − o(1)). Our algorithm is very simple, being just 3 lines of pseudocode, and has a small update time. It is essentially a polylogarithmic space approximate implementation of a classic dynamic program that computes the LIS. We also show how our technique can be applied to other problems solvable by dynamic programs. For example, we give a streaming algorithm for approximating LCS(x, y), the length of the longest common subsequence between strings x and y, each of length n. Our algorithm works in the asymmetric setting (inspired by [AKO10]), in which we have random access to y and streaming access to x, and runs in small space provided that no single symbol appears very often in y. More precisely, it gives an additive-δn approximation to LCS(x, y) (and hence also to E(x, y) = n − LCS(x, y), the edit distance between x and y when insertions and deletions, but not substitutions, are allowed), with space complexity O(k(log2 n)/δ), where k is the maximum number of times any one symbol appears in y. We also provide a deterministic 1-pass streaming algorithm that outputs a (1 + δ)-multiplicative approximation for E(x, y) (which is also an additive δn-approximation), in the asymmetric setting, and uses ) space. All these algorithms are obtained by carefully trading space and accuracy within a standard dynamic program.
BibTeX
@inproceedings{saks2013space,
  author = {Michael E. Saks and C. Seshadhri},
  title = {{Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance}},
  booktitle = {SODA},
  year = {2013},
  doi = {10.1137/1.9781611973105.122},
}

Loading related content...

Figure