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)

Date:	2023
Abstract:	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.
Grants:	Agencia Estatal de Investigación RTI2018-095209-B-C22 Agència de Gestió d'Ajuts Universitaris i de Recerca 2017/SGR-1624
Note:	Altres ajuts: acords transformatius de la UAB
Rights:	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.
Language:	Anglès
Document:	Article ; recerca ; Versió publicada
Subject:	Levenshtein distance ; Edit distance ; WFA algorithm ; GPU ; Parallel processing
Published in:	Parallel Computing, Vol. 116 (July 2023) , art. 103019, ISSN 0167-8191

DOI: 10.1016/j.parco.2023.103019

11 p, 1.3 MB

The record appears in these collections:
Articles > Research articles
Articles > Published articles