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.
- 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$.
- 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)$).
- 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