Among the basic cognitive skills of the biological brain in humans and other mammals, a fundamental one is the ability to recognize inexact patterns in a sequence of objects or events. Accelerating inexact string matching procedures is of utmost importance when dealing with practical applications where huge amounts of data must be processed in real time, as usual in bioinformatics or cybersecurity. Inexact matching procedures can yield multiple shadow hits, which must be filtered, according to some criterion, to obtain a concise and meaningful list of occurrences. The filtering procedures are often computationally demanding and are performed offline in a post-processing phase. This paper introduces a novel algorithm for online approximate string matching (OASM) able to filter shadow hits on the fly, according to general purpose priority rules that greedily assign priorities to overlapping hits. A field-programmable gate array (FPGA) hardware implementation of OASM is proposed and compared with a serial software version. Even when implemented on entry-level FPGAs, the proposed procedure can reach a high degree of parallelism and superior performance in time compared to the software implementation, while keeping low the usage of logic elements. This makes the developed architecture very competitive in terms of both performance and cost of the overall computing system.

A novel algorithm for online inexact string matching and its FPGA implementation / Cinti, Alessandro; Bianchi, Filippo Maria; Martino, Alessio; Rizzi, Antonello. - In: COGNITIVE COMPUTATION. - ISSN 1866-9956. - 2:(2020), pp. 369-387. [10.1007/s12559-019-09646-y]

A novel algorithm for online inexact string matching and its FPGA implementation

Cinti, Alessandro;Bianchi, Filippo Maria;Martino, Alessio;Rizzi, Antonello
2020

Abstract

Among the basic cognitive skills of the biological brain in humans and other mammals, a fundamental one is the ability to recognize inexact patterns in a sequence of objects or events. Accelerating inexact string matching procedures is of utmost importance when dealing with practical applications where huge amounts of data must be processed in real time, as usual in bioinformatics or cybersecurity. Inexact matching procedures can yield multiple shadow hits, which must be filtered, according to some criterion, to obtain a concise and meaningful list of occurrences. The filtering procedures are often computationally demanding and are performed offline in a post-processing phase. This paper introduces a novel algorithm for online approximate string matching (OASM) able to filter shadow hits on the fly, according to general purpose priority rules that greedily assign priorities to overlapping hits. A field-programmable gate array (FPGA) hardware implementation of OASM is proposed and compared with a serial software version. Even when implemented on entry-level FPGAs, the proposed procedure can reach a high degree of parallelism and superior performance in time compared to the software implementation, while keeping low the usage of logic elements. This makes the developed architecture very competitive in terms of both performance and cost of the overall computing system.
2020
FPGA; approximate string matching; dynamic programming; systolic arrays
01 Pubblicazione su rivista::01a Articolo in rivista
A novel algorithm for online inexact string matching and its FPGA implementation / Cinti, Alessandro; Bianchi, Filippo Maria; Martino, Alessio; Rizzi, Antonello. - In: COGNITIVE COMPUTATION. - ISSN 1866-9956. - 2:(2020), pp. 369-387. [10.1007/s12559-019-09646-y]
File allegati a questo prodotto
File Dimensione Formato  
Cinti_A-Novel-Algorithm_2020.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 2.78 MB
Formato Adobe PDF
2.78 MB Adobe PDF   Contatta l'autore
Cinti_Post-print_A-Novel-Algorithm_2019.pdf

accesso aperto

Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 2.74 MB
Formato Adobe PDF
2.74 MB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1276957
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 17
social impact