Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence
Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence
复制标题
DOI：
10.4230/lipics.fsttcs.2021.27
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Xin Li;Yu Zheng
中科院分区：
文献类型：
--
作者：
Xin Li;Yu Zheng
在本文中，我们研究了 Saks 和 Seshadhri [SS13] 提出的非对称流模型中的编辑距离 (ED) 和最长公共子序列 (LCS)。作为随机访问模型和流式模型之间的中间模型，该模型允许对一个字符串进行流式访问，并对另一个字符串进行随机访问。我们的第一个主要贡献是对非对称流模型中 ED 和 LCS 的空间下界进行系统研究。之前，尽管可以从 [SW07][GG10][EJ08] 中最长递增子序列 (LIS) 的下限推断出有关 LCS 的一些下限，但在此上下文中没有明确说明的结果。然而这些界限只适用于大字母表大小。在本文中，我们开发了几种新技术来处理一般的 ED 和小字母表大小的 LCS，从而为这两个问题建立了强大的下界。特别是，我们的 ED 下限在非对称流模型中提供了编辑距离和汉明距离之间的指数分离。我们的下限还扩展到标准流模型中的 LIS 和最长非递减序列 (LNS)。与之前的结果一起，我们的界限为这两个问题提供了几乎完整的图景。作为我们的第二个主要贡献，我们给出了非对称流模型中 ED 和 LCS 的改进算法。对于 ED，我们将 [FHRS20][CJLZ20] 中常数因子近似算法的空间复杂度从 $\tilde{O}(\frac{n^\delta}{\delta})$ 提高到 $O(\frac{d^\delta}{\delta}\;\mathsf{polylog}(n))$，其中 $n$ 是每个字符串的长度，$d$ 是两个字符串之间的编辑距离。对于 LCS，我们在二进制字母表上给出第一个 $1/2+\epsilon$ 近似算法，其中空间 $n^{\delta}$ 对于任何常数 $\delta>0$。
In this paper, we study edit distance (ED) and longest common subsequence (LCS) in the asymmetric streaming model, introduced by Saks and Seshadhri [SS13]. As an intermediate model between the random access model and the streaming model, this model allows one to have streaming access to one string and random access to the other string. Our first main contribution is a systematic study of space lower bounds for ED and LCS in the asymmetric streaming model. Previously, there are no explicitly stated results in this context, although some lower bounds about LCS can be inferred from the lower bounds for longest increasing subsequence (LIS) in [SW07][GG10][EJ08]. Yet these bounds only work for large alphabet size. In this paper, we develop several new techniques to handle ED in general and LCS for small alphabet size, thus establishing strong lower bounds for both problems. In particular, our lower bound for ED provides an exponential separation between edit distance and Hamming distance in the asymmetric streaming model. Our lower bounds also extend to LIS and longest non-decreasing sequence (LNS) in the standard streaming model. Together with previous results, our bounds provide an almost complete picture for these two problems. As our second main contribution, we give improved algorithms for ED and LCS in the asymmetric streaming model. For ED, we improve the space complexity of the constant factor approximation algorithms in [FHRS20][CJLZ20] from $\tilde{O}(\frac{n^\delta}{\delta})$ to $O(\frac{d^\delta}{\delta}\;\mathsf{polylog}(n))$, where $n$ is the length of each string and $d$ is the edit distance between the two strings. For LCS, we give the first $1/2+\epsilon$ approximation algorithm with space $n^{\delta}$ for any constant $\delta>0$, over a binary alphabet.