Thread divergence free and space efficient GPU implementation of NFA AC

Yogesh, C (2015) Thread divergence free and space efficient GPU implementation of NFA AC. Masters thesis, Indian Institute of Technology Hyderabad.

CS13M1007.pdf - Submitted Version

Download (2MB) | Preview


Multipattern String Matching problem reports all occurrences of a given set or dictionary of patterns in a document. Multipattern string matching problems are used in databases, data mining, DNA and protein sequence analysis, Intrusion detection systems (IDS) for applications (APIDS), networks (NIDS), protocols (PIDS), Host-based IDS, antivirus softwares, and machine learning problems. Parallel algorithm for multipattern string matching can be useful for above mentioned application because by using parallel platforms large number of threads can be executed parallelly and these thread can search for patterns in parallel. One of the multipattern search algorithm is a Aho- Corasick (AC) is a multipattern search algorithm. AC algorithm has two versions : NFA AC and DFA AC. DFA AC and NFA AC have matching automata to perform multipattern searching. NFA AC automata takes less memory then DFA AC automata. Many parallel implementations for AC algorithm are available.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Thesis (Masters)
Uncontrolled Keywords: Intrusion detection systems, Aho- Corasick
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Library Staff
Date Deposited: 01 Jul 2015 06:24
Last Modified: 14 May 2019 11:17
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 1616 Statistics for this ePrint Item