Prague Stringology Conference 2023
Tamanna Chhabra, Sukhpal Singh Ghuman and Jorma Tarhio
Approximate String Searching with AVX2 and AVX-512
| Abstract: |
| We present new algorithms for the k mismatches version of approximate string matching. Our algorithms utilize the SIMD (Single Instruction Multiple Data) instruction set extensions, particularly AVX2 and AVX-512 instructions. Our approach is an extension of an earlier algorithm for exact string matching with SSE2 and AVX2. In addition, we modify this exact string matching algorithm to work with AVX-512. We demonstrate the competitiveness of our solutions by practical experiments. Our experimental results show that our algorithms outperform earlier algorithms for both exact and approximate string matching on various benchmark data sets. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |