Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Efficient Parallel Algorithms for String Comparison. / Mishin, Nikita; Berezun, Daniil; Tiskin, Alexander.
50th International Conference on Parallel Processing, ICPP 2021 - Main Conference Proceedings. Association for Computing Machinery, 2021. 50 (ACM International Conference Proceeding Series).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Efficient Parallel Algorithms for String Comparison
AU - Mishin, Nikita
AU - Berezun, Daniil
AU - Tiskin, Alexander
N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2021/8/9
Y1 - 2021/8/9
N2 - The longest common subsequence (LCS) problem on a pair of strings is a classical problem in string algorithms. Its extension, the semi-local LCS problem, provides a more detailed comparison of the input strings, without any increase in asymptotic running time. Several semi-local LCS algorithms have been proposed previously; however, to the best of our knowledge, none have yet been implemented. In this paper, we explore a new hybrid approach to the semi-local LCS problem. We also propose a novel bit-parallel LCS algorithm. In the experimental part of the paper, we present an implementation of several existing and new parallel LCS algorithms and evaluate their performance.
AB - The longest common subsequence (LCS) problem on a pair of strings is a classical problem in string algorithms. Its extension, the semi-local LCS problem, provides a more detailed comparison of the input strings, without any increase in asymptotic running time. Several semi-local LCS algorithms have been proposed previously; however, to the best of our knowledge, none have yet been implemented. In this paper, we explore a new hybrid approach to the semi-local LCS problem. We also propose a novel bit-parallel LCS algorithm. In the experimental part of the paper, we present an implementation of several existing and new parallel LCS algorithms and evaluate their performance.
KW - bit-parallel algorithms
KW - braid multiplication
KW - divide-and-conquer
KW - dynamic programming
KW - longest common subsequence
KW - parallel algorithms
KW - parallel braid multiplication
KW - semi-local string comparison
KW - string algorithms
UR - http://www.scopus.com/inward/record.url?scp=85117197272&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/172a1dbe-6e8a-3cc6-a659-1ecbaf2f4745/
U2 - 10.1145/3472456.3472489
DO - 10.1145/3472456.3472489
M3 - Conference contribution
T3 - ACM International Conference Proceeding Series
BT - 50th International Conference on Parallel Processing, ICPP 2021 - Main Conference Proceedings
PB - Association for Computing Machinery
T2 - 50th International Conference on Parallel Processing, ICPP 2021
Y2 - 9 August 2021 through 12 August 2021
ER -
ID: 90974852