Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
复制标题
在真正的次二次时间中近似编辑距离：Quantum 和 MapReduce
DOI：
10.1145/3456807
复制
发表时间：
2021
影响因子：
2.5
通讯作者：
Seddighin, Saeed
中科院分区：
文献类型：
--
作者：
Boroujeni, Mahdi;Ehsani, Soheil;Ghodsi, Mohammad;Hajiaghayi, Mohammadtaghi;Seddighin, Saeed
两个字符串之间的编辑距离定义为将一个字符串转换为另一个字符串所需的插入、删除和替换的最小数量。在次二次时间内近似编辑距离是“组合模式匹配领域中最大的未解决问题之一”[37]。我们的主要结果是一个量子常数近似算法计算的编辑距离在真正的次二次时间。更确切地说，我们给出一个<？时间复杂度O（n^{1.810}）量子算法，其在因子3内近似编辑距离。我们进一步推广这一结果的<？时间复杂度O（n^{1.708}）在一个较大的常数因子内近似编辑距离的量子算法。我们的解决方案基于一个在并行设置中近似编辑距离的框架。这个框架需要一个黑盒算法，它可以同时计算几个较小字符串的距离。对于量子算法，我们减少了黑盒tometric估计，并提供了有效的算法来近似它。我们进一步表明，这个框架使我们能够近似编辑距离在分布式设置。为此，我们提供了一个MapReduce算法近似编辑距离内的一个因素<？TeX $1+\n $？>，具有次线性的许多机器和次线性的存储器。此外，我们的算法运行在对数轮数。
Theedit distancebetween two strings is defined as the smallest number ofinsertions,deletions, andsubstitutionsthat need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is “one of the biggest unsolved problems in the field of combinatorial pattern matching” [37]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an <?TeX $O(n^{1.810})$?> quantum algorithm that approximates the edit distance within a factor of 3. We further extend this result to an <?TeX $O(n^{1.708})$?> quantum algorithm that approximates the edit distance within a larger constant factor.Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box tometric estimationand provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of <?TeX $1+\epsilon$?>, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.
登录
查看更多内容
DOI：
10.5555/1109557.1109644
发表时间：
2006-01
期刊：
--
影响因子：
--
作者：
Tugkan Batu;Funda Ergün;S. C. Sahinalp
通讯作者：
Tugkan Batu;Funda Ergün;S. C. Sahinalp
编辑距离的平滑复杂度
DOI：
10.1145/2344422.2344434
发表时间：
2008
期刊：
ACM Trans. Algorithms
影响因子：
--
作者：
Alexandr Andoni;Robert Krauthgamer
通讯作者：
Robert Krauthgamer
量子傅里叶变换和有限群量子双偶的链接不变量的复杂性
影响因子：
2.4
作者：
H. Krovi;A. Russell
通讯作者：
A. Russell
DOI：
10.1109/sfcs.2001.959878
发表时间：
2001
期刊：
Proceedings 2001 IEEE International Conference on Cluster Computing
影响因子：
--
作者：
P. Indyk
通讯作者：
P. Indyk
DOI：
--
发表时间：
1997
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
R. Beals
通讯作者：
R. Beals