Trie compression for GPU accelerated multi-pattern matching

Xavier Bellekens, Amar Seeam, Christos Tachtatzis, Robert Atkinson

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    65 Downloads (Pure)


    Graphics Processing Units (GPU) allow for running massively parallel applications offloading the CPU from computationally intensive resources, however GPUs have a limited amount of memory. In this paper a trie compression algorithm for massively parallel pattern matching is presented demonstrating 85% less space requirements than the original highly efficient parallel failure-less Aho-Corasick, whilst demonstrating over 22 Gbps throughput. The algorithm presented takes advantage of compressed row storage matrices as well as shared and texture memory on the GPU.
    Original languageEnglish
    Title of host publicationProceedings of the 9th International Conferences on Pervasive Patterns and Applications
    PublisherInternational Academy, Research, and Industry Association (IARIA)
    ISBN (Print)9781612085340
    Publication statusPublished - 28 Feb 2017
    EventPATTERNS 2017: The Ninth International Conferences on Pervasive Patterns and Applications - Athens, Greece
    Duration: 19 Feb 201623 Feb 2016

    Publication series

    ISSN (Print)2308-3557


    ConferencePATTERNS 2017


    • Pattern matching algorithm
    • Trie compression
    • Searching
    • Data compression
    • GPU


    Dive into the research topics of 'Trie compression for GPU accelerated multi-pattern matching'. Together they form a unique fingerprint.

    Cite this