Home // PATTERNS 2017, The Ninth International Conferences on Pervasive Patterns and Applications // View article

Trie Compression for GPU Accelerated Multi-Pattern Matching

Authors:
Xavier Bellekens
Amar Seeam
Christos Tachtatzis
Robert Atkinson

Keywords: Pattern Matching Algorithm; Trie Compression; Searching; Data Compression; GPU

Abstract:
Graphics Processing Units (GPU) allow for running massively parallel applications offloading the Central Processing Unit (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.

Pages: 93 to 96

Copyright: Copyright (c) IARIA, 2017

Publication date: February 19, 2017

Published in: conference

ISSN: 2308-3557

ISBN: 978-1-61208-534-0

Location: Athens, Greece

Dates: from February 19, 2017 to February 23, 2017