Space Efficient Deterministic Approximation of String Measures
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 increasing sequence (LIS). All three problems can be solved exactly by standard algorithms that run in polynomial time with ro...
Збережено в:
| Автори: | , , , |
|---|---|
| Формат: | Стаття |
| Опубліковано: |
2020
|
| Предмети: | |
| Онлайн доступ: | https://arxiv.org/abs/2002.08498 http://arxiv.org/abs/2002.08498 |
| Теги: |
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| _version_ | 1879172406640115712 |
|---|---|
| author | Cheng, Kuan Jin, Zhengzhong Li, Xin Zheng, Yu |
| author_browse | Cheng, Kuan Jin, Zhengzhong Li, Xin Zheng, Yu |
| author_facet | Cheng, Kuan Jin, Zhengzhong Li, Xin Zheng, Yu |
| author_sort | Cheng, Kuan |
| building | arXiv |
| collection | Acceso abierto |
| description | 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 increasing sequence (LIS). All three problems can be solved exactly by standard algorithms that run in polynomial time with roughly $Θ(n)$ space, where $n$ is the input length, and our goal is to design deterministic approximation algorithms that run in polynomial time with significantly smaller space.
Towards this, we design several algorithms that achieve $1+ε$ or $1-ε$ approximation for all three problems, where $ε>0$ can be any constant and even slightly sub constant. Our algorithms are flexible and can be adjusted to achieve the following two regimes of parameters: 1) space $n^δ$ for any constant $δ>0$ with running time essentially the same as or slightly more than the standard algorithms; and 2) space $\mathsf{polylog}(n)$ with (a larger) polynomial running time, which puts the approximation versions of the three problems in Steve's class (\textbf{SC}). Our algorithms significantly improve previous results in terms of space complexity, where all known results need to use space at least $Ω(\sqrt{n})$. Some of our algorithms can also be adapted to work in the asymmetric streaming model [SS13], and output the corresponding sequence. Furthermore, our results can be used to improve a recent result by Farhadi et. al. [FHRS20] about approximating ED in the asymmetric streaming model, reducing the running time from being exponential in [FHRS20] to a polynomial.
Our algorithms are based on the idea of using recursion as in Savitch's theorem [Sav70], and a careful adaption of previous techniques to make the recursion work. Along the way we also give a new logspace reduction from longest common subsequence to longest increasing sequence, which may be of independent interest. |
| first_indexed | 2026-10-15T23:40:49Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-2002.08498</identifier><datestamp>2020-07-28</datestamp>
<dc:title>Space Efficient Deterministic Approximation of String Measures</dc:title>
<dc:creator>Cheng, Kuan</dc:creator>
<dc:creator>Jin, Zhengzhong</dc:creator>
<dc:creator>Li, Xin</dc:creator>
<dc:creator>Zheng, Yu</dc:creator>
<dc:subject>Data Structures and Algorithms</dc:subject>
<dc:description>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 increasing sequence (LIS). All three problems can be solved exactly by standard algorithms that run in polynomial time with roughly $Θ(n)$ space, where $n$ is the input length, and our goal is to design deterministic approximation algorithms that run in polynomial time with significantly smaller space.
Towards this, we design several algorithms that achieve $1+ε$ or $1-ε$ approximation for all three problems, where $ε>0$ can be any constant and even slightly sub constant. Our algorithms are flexible and can be adjusted to achieve the following two regimes of parameters: 1) space $n^δ$ for any constant $δ>0$ with running time essentially the same as or slightly more than the standard algorithms; and 2) space $\mathsf{polylog}(n)$ with (a larger) polynomial running time, which puts the approximation versions of the three problems in Steve's class (\textbf{SC}). Our algorithms significantly improve previous results in terms of space complexity, where all known results need to use space at least $Ω(\sqrt{n})$. Some of our algorithms can also be adapted to work in the asymmetric streaming model [SS13], and output the corresponding sequence. Furthermore, our results can be used to improve a recent result by Farhadi et. al. [FHRS20] about approximating ED in the asymmetric streaming model, reducing the running time from being exponential in [FHRS20] to a polynomial.
Our algorithms are based on the idea of using recursion as in Savitch's theorem [Sav70], and a careful adaption of previous techniques to make the recursion work. Along the way we also give a new logspace reduction from longest common subsequence to longest increasing sequence, which may be of independent interest. </dc:description>
<dc:date>2020-02-19</dc:date>
<dc:date>2020-07-24</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2002.08498</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2002.08498</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2002.08498 |
| institution | arXiv |
| last_indexed | 2026-10-15T23:40:49Z |
| publishDate | 2020 |
| publishDateRange | 2020 |
| publishDateSort | 2020 |
| record_format | oai_dc |
| spelling | arxiv-2002.084982020-07-28 Space Efficient Deterministic Approximation of String Measures Cheng, Kuan Jin, Zhengzhong Li, Xin Zheng, Yu Data Structures and Algorithms 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 increasing sequence (LIS). All three problems can be solved exactly by standard algorithms that run in polynomial time with roughly $Θ(n)$ space, where $n$ is the input length, and our goal is to design deterministic approximation algorithms that run in polynomial time with significantly smaller space. Towards this, we design several algorithms that achieve $1+ε$ or $1-ε$ approximation for all three problems, where $ε>0$ can be any constant and even slightly sub constant. Our algorithms are flexible and can be adjusted to achieve the following two regimes of parameters: 1) space $n^δ$ for any constant $δ>0$ with running time essentially the same as or slightly more than the standard algorithms; and 2) space $\mathsf{polylog}(n)$ with (a larger) polynomial running time, which puts the approximation versions of the three problems in Steve's class (\textbf{SC}). Our algorithms significantly improve previous results in terms of space complexity, where all known results need to use space at least $Ω(\sqrt{n})$. Some of our algorithms can also be adapted to work in the asymmetric streaming model [SS13], and output the corresponding sequence. Furthermore, our results can be used to improve a recent result by Farhadi et. al. [FHRS20] about approximating ED in the asymmetric streaming model, reducing the running time from being exponential in [FHRS20] to a polynomial. Our algorithms are based on the idea of using recursion as in Savitch's theorem [Sav70], and a careful adaption of previous techniques to make the recursion work. Along the way we also give a new logspace reduction from longest common subsequence to longest increasing sequence, which may be of independent interest. 2020-02-19 2020-07-24 text https://arxiv.org/abs/2002.08498 http://arxiv.org/abs/2002.08498 |
| spellingShingle | Data Structures and Algorithms Cheng, Kuan Jin, Zhengzhong Li, Xin Zheng, Yu Space Efficient Deterministic Approximation of String Measures |
| title | Space Efficient Deterministic Approximation of String Measures |
| title_full | Space Efficient Deterministic Approximation of String Measures |
| title_fullStr | Space Efficient Deterministic Approximation of String Measures |
| title_full_unstemmed | Space Efficient Deterministic Approximation of String Measures |
| title_short | Space Efficient Deterministic Approximation of String Measures |
| title_sort | space efficient deterministic approximation of string measures |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2002.08498 http://arxiv.org/abs/2002.08498 |
| work_keys_str_mv | AT chengkuan spaceefficientdeterministicapproximationofstringmeasures AT jinzhengzhong spaceefficientdeterministicapproximationofstringmeasures AT lixin spaceefficientdeterministicapproximationofstringmeasures AT zhengyu spaceefficientdeterministicapproximationofstringmeasures |