Show simple item record

dc.contributor.authorCinti, Alessandro
dc.contributor.authorBianchi, Filippo Maria
dc.contributor.authorRizzi, Antonello
dc.date.accessioned2020-03-05T13:22:59Z
dc.date.available2020-03-05T13:22:59Z
dc.date.issued2019-05-14
dc.description.abstractAmong 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.en_US
dc.identifier.citationCinti, A., Bianchi, F.M., Martino, A., Rizzi, A. (2019) A Novel Algorithm for Online Inexact String Matching and its FPGA Implementation.<i> Cognitive Computation</i>, 1-19en_US
dc.identifier.cristinIDFRIDAID 1721892
dc.identifier.doi10.1007/s12559-019-09646-y
dc.identifier.issn1866-9956
dc.identifier.issn1866-9964
dc.identifier.urihttps://hdl.handle.net/10037/17645
dc.language.isoengen_US
dc.publisherSpringer Natureen_US
dc.relation.journalCognitive Computation
dc.rights.accessRightsopenAccessen_US
dc.rights.holder© 2020 Springer Nature Switzerland AGen_US
dc.subjectVDP::Technology: 500::Information and communication technology: 550::Computer technology: 551en_US
dc.subjectVDP::Teknologi: 500::Informasjons- og kommunikasjonsteknologi: 550::Datateknologi: 551en_US
dc.titleA Novel Algorithm for Online Inexact String Matching and its FPGA Implementationen_US
dc.type.versionacceptedVersionen_US
dc.typeJournal articleen_US
dc.typeTidsskriftartikkelen_US
dc.typePeer revieweden_US


File(s) in this item

Thumbnail

This item appears in the following collection(s)

Show simple item record