License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.54
URN: urn:nbn:de:0030-drops-141236
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14123/
Cheng, Kuan ;
Farhadi, Alireza ;
Hajiaghayi, MohammadTaghi ;
Jin, Zhengzhong ;
Li, Xin ;
Rubinstein, Aviad ;
Seddighin, Saeed ;
Zheng, Yu
Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence
Abstract
The edit distance (ED) and longest common subsequence (LCS) are two fundamental problems which quantify how similar two strings are to one another. In this paper, we first consider these problems in the asymmetric streaming model introduced by Andoni, Krauthgamer and Onak [Andoni et al., 2010] (FOCS'10) and Saks and Seshadhri [Saks and Seshadhri, 2013] (SODA'13). In this model we have random access to one string and streaming access the other one. Our main contribution is a constant factor approximation algorithm for ED with memory Õ(n^δ) for any constant δ > 0. In addition to this, we present an upper bound of Õ _ε(√n) on the memory needed to approximate ED or LCS within a factor 1±ε. All our algorithms are deterministic and run in polynomial time in a single pass.
We further study small-space approximation algorithms for ED, LCS, and longest increasing sequence (LIS) in the non-streaming setting. Here, we design algorithms that achieve 1 ± ε approximation for all three problems, where ε > 0 can be any constant and even slightly sub-constant. Our algorithms only use poly-logarithmic space while maintaining a polynomial running time. This significantly improves previous results in terms of space complexity, where all known results need to use space at least Ω(√n). Our algorithms make novel use of triangle inequality and carefully designed recursions to save space, which can be of independent interest.
BibTeX - Entry
@InProceedings{cheng_et_al:LIPIcs.ICALP.2021.54,
author = {Cheng, Kuan and Farhadi, Alireza and Hajiaghayi, MohammadTaghi and Jin, Zhengzhong and Li, Xin and Rubinstein, Aviad and Seddighin, Saeed and Zheng, Yu},
title = {{Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {54:1--54:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14123},
URN = {urn:nbn:de:0030-drops-141236},
doi = {10.4230/LIPIcs.ICALP.2021.54},
annote = {Keywords: Edit Distance, Longest Common Subsequence, Longest Increasing Subsequence, Space Efficient Algorithm, Approximation Algorithm}
}
|
Keywords: |
|
Edit Distance, Longest Common Subsequence, Longest Increasing Subsequence, Space Efficient Algorithm, Approximation Algorithm |
|
Collection: |
|
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.07.2021 |
