How Compression and Approximation Affect Efficiency in String Distance Measures
Real-world data often comes in compressed form. Analyzing compressed data directly (without decompressing it) can save space and time by orders of magnitude. In this work, we focus on fundamental sequence comparison problems and try to quantify the gain in time complexity when the underlying data is...
Сохранить в:
| Главные авторы: | , , , |
|---|---|
| Формат: | Статья |
| Опубликовано: |
2021
|
| Предметы: | |
| Online-ссылка: | https://arxiv.org/abs/2112.05836 http://arxiv.org/abs/2112.05836 |
| Метки: |
Нет меток, Требуется 1-ая метка записи!
|
| _version_ | 1879173429777661952 |
|---|---|
| author | Ganesh, Arun Kociumaka, Tomasz Lincoln, Andrea Saha, Barna |
| author_browse | Ganesh, Arun Kociumaka, Tomasz Lincoln, Andrea Saha, Barna |
| author_facet | Ganesh, Arun Kociumaka, Tomasz Lincoln, Andrea Saha, Barna |
| author_sort | Ganesh, Arun |
| building | arXiv |
| collection | Acceso abierto |
| description | Real-world data often comes in compressed form. Analyzing compressed data directly (without decompressing it) can save space and time by orders of magnitude. In this work, we focus on fundamental sequence comparison problems and try to quantify the gain in time complexity when the underlying data is highly compressible. We consider grammar compression, which unifies many practically relevant compression schemes. For two strings of total length $N$ and total compressed size $n$, it is known that the edit distance and a longest common subsequence (LCS) can be computed exactly in time $\tilde{O}(nN)$, as opposed to $O(N^2)$ for the uncompressed setting. Many applications need to align multiple sequences simultaneously, and the fastest known exact algorithms for median edit distance and LCS of $k$ strings run in $O(N^k)$ time. This naturally raises the question of whether compression can help to reduce the running time significantly for $k \geq 3$, perhaps to $O(N^{k/2}n^{k/2})$ or $O(Nn^{k-1})$. Unfortunately, we show lower bounds that rule out any improvement beyond $Ω(N^{k-1}n)$ time for any of these problems assuming the Strong Exponential Time Hypothesis.
At the same time, we show that approximation and compression together can be surprisingly effective. We develop an $\tilde{O}(N^{k/2}n^{k/2})$-time FPTAS for the median edit distance of $k$ sequences. In comparison, no $O(N^{k-Ω(1)})$-time PTAS is known for the median edit distance problem in the uncompressed setting. For two strings, we get an $\tilde{O}(N^{2/3}n^{4/3})$-time FPTAS for both edit distance and LCS. In contrast, for uncompressed strings, there is not even a subquadratic algorithm for LCS that has less than a polynomial gap in the approximation factor. Building on the insight from our approximation algorithms, we also obtain results for many distance measures including the edit, Hamming, and shift distances. |
| first_indexed | 2026-10-15T23:57:09Z |
| 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-2112.05836</identifier><datestamp>2021-12-14</datestamp>
<dc:title>How Compression and Approximation Affect Efficiency in String Distance Measures</dc:title>
<dc:creator>Ganesh, Arun</dc:creator>
<dc:creator>Kociumaka, Tomasz</dc:creator>
<dc:creator>Lincoln, Andrea</dc:creator>
<dc:creator>Saha, Barna</dc:creator>
<dc:subject>Data Structures and Algorithms</dc:subject>
<dc:description>Real-world data often comes in compressed form. Analyzing compressed data directly (without decompressing it) can save space and time by orders of magnitude. In this work, we focus on fundamental sequence comparison problems and try to quantify the gain in time complexity when the underlying data is highly compressible. We consider grammar compression, which unifies many practically relevant compression schemes. For two strings of total length $N$ and total compressed size $n$, it is known that the edit distance and a longest common subsequence (LCS) can be computed exactly in time $\tilde{O}(nN)$, as opposed to $O(N^2)$ for the uncompressed setting. Many applications need to align multiple sequences simultaneously, and the fastest known exact algorithms for median edit distance and LCS of $k$ strings run in $O(N^k)$ time. This naturally raises the question of whether compression can help to reduce the running time significantly for $k \geq 3$, perhaps to $O(N^{k/2}n^{k/2})$ or $O(Nn^{k-1})$. Unfortunately, we show lower bounds that rule out any improvement beyond $Ω(N^{k-1}n)$ time for any of these problems assuming the Strong Exponential Time Hypothesis.
At the same time, we show that approximation and compression together can be surprisingly effective. We develop an $\tilde{O}(N^{k/2}n^{k/2})$-time FPTAS for the median edit distance of $k$ sequences. In comparison, no $O(N^{k-Ω(1)})$-time PTAS is known for the median edit distance problem in the uncompressed setting. For two strings, we get an $\tilde{O}(N^{2/3}n^{4/3})$-time FPTAS for both edit distance and LCS. In contrast, for uncompressed strings, there is not even a subquadratic algorithm for LCS that has less than a polynomial gap in the approximation factor. Building on the insight from our approximation algorithms, we also obtain results for many distance measures including the edit, Hamming, and shift distances. </dc:description>
<dc:description>accepted to SODA 2022</dc:description>
<dc:date>2021-12-10</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2112.05836</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2112.05836</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2112.05836 |
| institution | arXiv |
| last_indexed | 2026-10-15T23:57:09Z |
| publishDate | 2021 |
| publishDateRange | 2021 |
| publishDateSort | 2021 |
| record_format | oai_dc |
| spelling | arxiv-2112.058362021-12-14 How Compression and Approximation Affect Efficiency in String Distance Measures Ganesh, Arun Kociumaka, Tomasz Lincoln, Andrea Saha, Barna Data Structures and Algorithms Real-world data often comes in compressed form. Analyzing compressed data directly (without decompressing it) can save space and time by orders of magnitude. In this work, we focus on fundamental sequence comparison problems and try to quantify the gain in time complexity when the underlying data is highly compressible. We consider grammar compression, which unifies many practically relevant compression schemes. For two strings of total length $N$ and total compressed size $n$, it is known that the edit distance and a longest common subsequence (LCS) can be computed exactly in time $\tilde{O}(nN)$, as opposed to $O(N^2)$ for the uncompressed setting. Many applications need to align multiple sequences simultaneously, and the fastest known exact algorithms for median edit distance and LCS of $k$ strings run in $O(N^k)$ time. This naturally raises the question of whether compression can help to reduce the running time significantly for $k \geq 3$, perhaps to $O(N^{k/2}n^{k/2})$ or $O(Nn^{k-1})$. Unfortunately, we show lower bounds that rule out any improvement beyond $Ω(N^{k-1}n)$ time for any of these problems assuming the Strong Exponential Time Hypothesis. At the same time, we show that approximation and compression together can be surprisingly effective. We develop an $\tilde{O}(N^{k/2}n^{k/2})$-time FPTAS for the median edit distance of $k$ sequences. In comparison, no $O(N^{k-Ω(1)})$-time PTAS is known for the median edit distance problem in the uncompressed setting. For two strings, we get an $\tilde{O}(N^{2/3}n^{4/3})$-time FPTAS for both edit distance and LCS. In contrast, for uncompressed strings, there is not even a subquadratic algorithm for LCS that has less than a polynomial gap in the approximation factor. Building on the insight from our approximation algorithms, we also obtain results for many distance measures including the edit, Hamming, and shift distances. accepted to SODA 2022 2021-12-10 text https://arxiv.org/abs/2112.05836 http://arxiv.org/abs/2112.05836 |
| spellingShingle | Data Structures and Algorithms Ganesh, Arun Kociumaka, Tomasz Lincoln, Andrea Saha, Barna How Compression and Approximation Affect Efficiency in String Distance Measures |
| title | How Compression and Approximation Affect Efficiency in String Distance Measures |
| title_full | How Compression and Approximation Affect Efficiency in String Distance Measures |
| title_fullStr | How Compression and Approximation Affect Efficiency in String Distance Measures |
| title_full_unstemmed | How Compression and Approximation Affect Efficiency in String Distance Measures |
| title_short | How Compression and Approximation Affect Efficiency in String Distance Measures |
| title_sort | how compression and approximation affect efficiency in string distance measures |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2112.05836 http://arxiv.org/abs/2112.05836 |
| work_keys_str_mv | AT ganesharun howcompressionandapproximationaffectefficiencyinstringdistancemeasures AT kociumakatomasz howcompressionandapproximationaffectefficiencyinstringdistancemeasures AT lincolnandrea howcompressionandapproximationaffectefficiencyinstringdistancemeasures AT sahabarna howcompressionandapproximationaffectefficiencyinstringdistancemeasures |