6 citations · 6 across the 2 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2021
Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence
Xin Li, Yu Zheng
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…
cs.DS2020
Space Efficient Deterministic Approximation of String Measures
Kuan Cheng, Zhengzhong Jin, Xin Li +1
We study approximation algorithms for the following three string measures that are widely used in practice: edit distance (ED), longest common subsequence (LCS), and longest increa…