lnu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
PaREM: a Novel Approach for Parallel Regular Expression Matching
Linnaeus University, Faculty of Technology, Department of Computer Science.
Linnaeus University, Faculty of Technology, Department of Computer Science.
2014 (English)In: 2014 IEEE 17th International Conference on Computational Science and Engineering (CSE), IEEE Press, 2014, p. 690-697Conference paper, Published paper (Refereed)
Abstract [en]

Regular expression matching is essential for many applications, such as finding patterns in text, exploring substrings in large DNA sequences, or lexical analysis. However, sequential regular expression matching may be time-prohibitive for large problem sizes. In this paper, we describe a novel algorithm for parallel regular expression matching via deterministic finite automata. Furthermore, we present our tool PaREM that accepts regular expressions and finite automata as input and automatically generates the corresponding code for our algorithm that is amenable for parallel execution on shared-memory systems. We evaluate our parallel algorithm empirically by comparing it with a commonly used algorithm for sequential regular expression matching. Experiments on a dual-socket shared-memory system with 24 physical cores show speed-ups of up to 21× for 48 threads.

Place, publisher, year, edition, pages
IEEE Press, 2014. p. 690-697
National Category
Engineering and Technology Information Systems
Research subject
Computer and Information Sciences Computer Science, Computer Science
Identifiers
URN: urn:nbn:se:lnu:diva-41014DOI: 10.1109/CSE.2014.146ISI: 000380512100111Scopus ID: 2-s2.0-84925250594ISBN: 978-1-4799-7980-6 (print)OAI: oai:DiVA.org:lnu-41014DiVA, id: diva2:796452
Conference
17th International Conference on Computational Science and Engineering (CSE), 19-21 Dec. 2014, Chengdu
Available from: 2015-03-19 Created: 2015-03-19 Last updated: 2018-02-16Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopushttp://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7023656

Authority records BETA

Memeti, SuejbPllana, Sabri

Search in DiVA

By author/editor
Memeti, SuejbPllana, Sabri
By organisation
Department of Computer Science
Engineering and TechnologyInformation Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 128 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf