Standard

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).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Mishin, N, Berezun, D & Tiskin, A 2021, Efficient Parallel Algorithms for String Comparison. in 50th International Conference on Parallel Processing, ICPP 2021 - Main Conference Proceedings., 50, ACM International Conference Proceeding Series, Association for Computing Machinery, 50th International Conference on Parallel Processing, ICPP 2021, Virtual, Online, United States, 9/08/21. https://doi.org/10.1145/3472456.3472489, https://doi.org/10.1145/3472456.3472489

APA

Mishin, N., Berezun, D., & Tiskin, A. (2021). Efficient Parallel Algorithms for String Comparison. In 50th International Conference on Parallel Processing, ICPP 2021 - Main Conference Proceedings [50] (ACM International Conference Proceeding Series). Association for Computing Machinery. https://doi.org/10.1145/3472456.3472489, https://doi.org/10.1145/3472456.3472489

Vancouver

Mishin N, Berezun D, Tiskin A. Efficient Parallel Algorithms for String Comparison. In 50th International Conference on Parallel Processing, ICPP 2021 - Main Conference Proceedings. Association for Computing Machinery. 2021. 50. (ACM International Conference Proceeding Series). https://doi.org/10.1145/3472456.3472489, https://doi.org/10.1145/3472456.3472489

Author

Mishin, Nikita ; Berezun, Daniil ; Tiskin, Alexander. / Efficient Parallel Algorithms for String Comparison. 50th International Conference on Parallel Processing, ICPP 2021 - Main Conference Proceedings. Association for Computing Machinery, 2021. (ACM International Conference Proceeding Series).

BibTeX

@inproceedings{3ea41794e6854959b5d6f2168cb8c107,
title = "Efficient Parallel Algorithms for String Comparison",
abstract = "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.",
keywords = "bit-parallel algorithms, braid multiplication, divide-and-conquer, dynamic programming, longest common subsequence, parallel algorithms, parallel braid multiplication, semi-local string comparison, string algorithms",
author = "Nikita Mishin and Daniil Berezun and Alexander Tiskin",
note = "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.; 50th International Conference on Parallel Processing, ICPP 2021 ; Conference date: 09-08-2021 Through 12-08-2021",
year = "2021",
month = aug,
day = "9",
doi = "10.1145/3472456.3472489",
language = "English",
series = "ACM International Conference Proceeding Series",
publisher = "Association for Computing Machinery",
booktitle = "50th International Conference on Parallel Processing, ICPP 2021 - Main Conference Proceedings",
address = "United States",

}

RIS

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