Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
3.7
2.3
Journals
Algorithms
Special Issues
Parallel String Matching Algorithms and Applications
share announcement

Parallel String Matching Algorithms and Applications

A special issue of Algorithms (ISSN 1999-4893).

Deadline for manuscript submissions: closed (31 December 2019) | Viewed by 5452

Special Issue Editors

Prof. Dr. Panagiotis D. Michailidis

E-Mail Website
Guest Editor
Department of Balkan, Slavic and Oriental Studies, Unversity of Macedonia, 156 Egnatia Str., 54636 Thessaloniki, Greece
Interests: algorithms on text searching; parallel and distributed computing; computational methods
Prof. Dr. Konstantinos Margaritis

E-Mail Website
Guest Editor
Department of Applied Informatics, Unversity of Macedonia, 156 Egnatia Str., 54636 Thessaloniki, Greece
Interests: parallel and distributed computing; string matching algorithms; computational intelligence
Special Issues, Collections and Topics in MDPI journals

Special Issue Information

Dear Colleagues,

We are glad to announce the upcoming Special Issue dedicated to parallel string-matching algorithms and applications. With the recent advances in big text data processing and applications, this Special Issue aims to provide a comprehensive view of the efficient design and implementation of string-matching algorithms for parallel and distributed computing environments (such as multicores, manycores, clusters, CPU/GPUs, grids, p2p, and clouds). We invite researchers and professionals to submit theoretical or practical contributions that aim to present ideas, techniques, and results of parallel computing in all aspects of string matching and related applications (exact/approximate string matching, single/multiple string matching, 2D string matching, and compressed string processing). Manuscripts that focus on research of sequential string-matching algorithms are welcome. Both original research and comprehensive review/survey papers are also welcome.

Topics of interest include but are not limited to the following areas:

- String matching algorithms (exact/approximate, single/mutiple, two-dimensional, text compression, etc.);

- Parallel string-matching algorithms using OpenMP and/or MPI;

- Parallel string-matching algorithms targeting GPUs and many-cores accelerators;

- Parallel string-matching applications exploiting FPGA;

- Distributed string matching algorithms;

- Performance study and analysis of large-scale string-matching applications;

- Libraries for string matching on parallel platforms;

- Applications of string matching in natural language processing, computational linguistics, information retrieval, text/opinion mining, text plagiarism, sentiment analysis, bioinformatics, computational biology, intrusion detection, security, etc.

Prof. Dr. Panagiotis D. Michailidis
Prof. Dr. Margaritis G.Konstantinos
Guest Editors

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Algorithms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 1600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

  • parallel computing
  • distributed computing
  • exact string matching
  • approximate string matching
  • multiple string matching
  • two-dimensional string matching
  • information retrieval
  • text mining
  • bioinformatics

Published Papers (1 paper)

Order results
Result details
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:

Research

18 pages, 1658 KiB  
Article
Accelerating Binary String Comparisons with a Scalable, Streaming-Based System Architecture Based on FPGAs
by Sarah Pilz, Florian Porrmann, Martin Kaiser, Jens Hagemeyer, James M. Hogan and Ulrich Rückert
Algorithms 2020, 13(2), 47; https://0-doi-org.brum.beds.ac.uk/10.3390/a13020047 - 21 Feb 2020
Cited by 7 | Viewed by 4538
Abstract
This paper is concerned with Field Programmable Gate Arrays (FPGA)-based systems for energy-efficient high-throughput string comparison. Modern applications which involve comparisons across large data sets—such as large sequence sets in molecular biology—are by their nature computationally intensive. In this work, we present a [...] Read more.
This paper is concerned with Field Programmable Gate Arrays (FPGA)-based systems for energy-efficient high-throughput string comparison. Modern applications which involve comparisons across large data sets—such as large sequence sets in molecular biology—are by their nature computationally intensive. In this work, we present a scalable FPGA-based system architecture to accelerate the comparison of binary strings. The current architecture supports arbitrary lengths in the range 16 to 2048-bit, covering a wide range of possible applications. In our example application, we consider DNA sequences embedded in a binary vector space through Locality Sensitive Hashing (LSH) one of several possible encodings that enable us to avoid more costly character-based operations. Here the resulting encoding is a 512-bit binary signature with comparisons based on the Hamming distance. In this approach, most of the load arises from the calculation of the O ( m ∗ n ) Hamming distances between the signatures, where m is the number of queries and n is the number of signatures contained in the database. Signature generation only needs to be performed once, and we do not consider it further, focusing instead on accelerating the signature comparisons. The proposed FPGA-based architecture is optimized for high-throughput using hundreds of computing elements, arranged in a systolic array. These core computing elements can be adapted to support other string comparison algorithms with little effort, while the other infrastructure stays the same. On a Xilinx Virtex UltraScale+ FPGA (XCVU9P-2), a peak throughput of 75.4 billion comparisons per second—of 512-bit signatures—was achieved, using a design with 384 parallel processing elements and a clock frequency of 200 MHz. This makes our FPGA design 86 times faster than a highly optimized CPU implementation. Compared to a GPU design, executed on an NVIDIA GTX1060, it performs nearly five times faster. Full article
(This article belongs to the Special Issue Parallel String Matching Algorithms and Applications)
►▼ Show Figures

Figure 1

Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-1
Back to TopTop