GPU acceleration of Levenshtein distance computation between long strings
Castells-Rufas, David (Universitat Autònoma de Barcelona. Departament de Microelectrònica i Sistemes Electrònics)

Fecha:	2023
Resumen:	Computing edit distance for very long strings has been hampered by quadratic time complexity with respect to string length. The WFA algorithm reduces the time complexity to a quadratic factor with respect to the edit distance between the strings. This work presents a GPU implementation of the WFA algorithm and a new optimization that can halve the elements to be computed, providing additional performance gains. The implementation allows to address the computation of the edit distance between strings having hundreds of millions of characters. The performance of the algorithm depends on the similarity between the strings. For strings longer than million characters, the performance is the best ever reported, which is above TCUPS for strings with similarities greater than 70% and above one hundred TCUPS for 99. 9% similarity.
Ayudas:	Agencia Estatal de Investigación RTI2018-095209-B-C22 Agència de Gestió d'Ajuts Universitaris i de Recerca 2017/SGR-1624
Nota:	Altres ajuts: acords transformatius de la UAB
Derechos:	Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial, la distribució, la comunicació pública de l'obra i la creació d'obres derivades, fins i tot amb finalitats comercials, sempre i quan es reconegui l'autoria de l'obra original.
Lengua:	Anglès
Documento:	Article ; recerca ; Versió publicada
Materia:	Levenshtein distance ; Edit distance ; WFA algorithm ; GPU ; Parallel processing
Publicado en:	Parallel Computing, Vol. 116 (July 2023) , art. 103019, ISSN 0167-8191

DOI: 10.1016/j.parco.2023.103019

11 p, 1.3 MB

El registro aparece en las colecciones:
Artículos > Artículos de investigación
Artículos > Artículos publicados