NDLI: GPU Based N-Gram String Matching Algorithm with Score Table Approach for String Searching in Many Documents

Please wait, while we are loading the content...

Journal of The Institution of Engineers (India): Series B : Volume 98

Journal of The Institution of Engineers (India): Series B : Volume 98, Issue 6, December 2017

Journal of The Institution of Engineers (India): Series B : Volume 98, Issue 5, October 2017

Circular Microstrip Antenna with Fractal Slots for Multiband Applications

Current Controller for Multi-level Front-end Converter and Its Digital Implementation Considerations on Three-level Flying Capacitor Topology

Development and Performance Assessment of White LED Dimmer

GPU Based N-Gram String Matching Algorithm with Score Table Approach for String Searching in Many Documents

Improved Performance of Radial Elliptical Low-Pass Filter for ISM Band

Modelling and Simulation of Single-Phase Series Active Compensator for Power Quality Improvement

Multiobjective Economic Load Dispatch in 3-D Space by Genetic Algorithm

Two Level Versus Matrix Converters Performance in Wind Energy Conversion Systems Employing DFIG

A Review Analysis of Inverter Topologies for Solar PV Applications Focused on Power Quality

Multi Dimensional Honey Bee Foraging Algorithm Based on Optimal Energy Consumption

Journal of The Institution of Engineers (India): Series B : Volume 98, Issue 4, August 2017

Journal of The Institution of Engineers (India): Series B : Volume 98, Issue 3, June 2017

Journal of The Institution of Engineers (India): Series B : Volume 98, Issue 2, April 2017

Journal of The Institution of Engineers (India): Series B : Volume 97

Journal of The Institution of Engineers (India): Series B : Volume 96

Journal of The Institution of Engineers (India): Series B : Volume 95

Journal of The Institution of Engineers (India): Series B : Volume 94

Journal of The Institution of Engineers (India): Series B : Volume 93

GPU Based N-Gram String Matching Algorithm with Score Table Approach for String Searching in Many Documents

Content Provider	Springer Nature Link
Author	Srinivasa, K. G. Shree Devi, B. N.
Copyright Year	2017
Abstract	String searching in documents has become a tedious task with the evolution of Big Data. Generation of large data sets demand for a high performance search algorithm in areas such as text mining, information retrieval and many others. The popularity of GPU’s for general purpose computing has been increasing for various applications. Therefore it is of great interest to exploit the thread feature of a GPU to provide a high performance search algorithm. This paper proposes an optimized new approach to N-gram model for string search in a number of lengthy documents and its GPU implementation. The algorithm exploits GPGPUs for searching strings in many documents employing character level N-gram matching with parallel Score Table approach and search using CUDA API. The new approach of Score table used for frequency storage of N-grams in a document, makes the search independent of the document’s length and allows faster access to the frequency values, thus decreasing the search complexity. The extensive thread feature in a GPU has been exploited to enable parallel pre-processing of trigrams in a document for Score Table creation and parallel search in huge number of documents, thus speeding up the whole search process even for a large pattern size. Experiments were carried out for many documents of varied length and search strings from the standard Lorem Ipsum text on NVIDIA’s GeForce GT 540M GPU with 96 cores. Results prove that the parallel approach for Score Table creation and searching gives a good speed up than the same approach executed serially.
Starting Page	467
Ending Page	476
Page Count	10
File Format	PDF
ISSN	22502106
Journal	Journal of The Institution of Engineers (India): Series B
Volume Number	98
Issue Number	5
e-ISSN	22502114
Language	English
Publisher	Springer India
Publisher Date	2017-09-22
Publisher Place	New Delhi
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	CUDA N-gram NVIDIA String searching String matching Communications Engineering, Networks Trigram GPGPU Score table
Content Type	Text
Resource Type	Article
Subject	Computer Science Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

iNFAnt:NFA pattern matching on GPGPU devices

Solution of Large Sparse System of Linear Equations over GF(2) on a Multi Node Multi GPU Platform

String Matching on a Multicore GPU Using CUDA

Many-core GPU computing with NVIDIA CUDA

Hash match on GPU

Direct GPU/FPGA communication Via PCI express

GpuCV: an opensource GPU-accelerated framework forimage processing and computer vision

Scalable Method of Searching for Full-period Nonlinear Feedback Shift Registers with GPGPU. New List of Maximum Period NLFSRs.

Multipattern string matching on a GPU

GPU Based N-Gram String Matching Algorithm with Score Table Approach for String Searching in Many Documents

Similar Documents

iNFAnt:NFA pattern matching on GPGPU devices

Solution of Large Sparse System of Linear Equations over GF(2) on a Multi Node Multi GPU Platform

String Matching on a Multicore GPU Using CUDA

Many-core GPU computing with NVIDIA CUDA

Hash match on GPU

Direct GPU/FPGA communication Via PCI express

GpuCV: an opensource GPU-accelerated framework forimage processing and computer vision

Scalable Method of Searching for Full-period Nonlinear Feedback Shift Registers with GPGPU. New List of Maximum Period NLFSRs.

Multipattern string matching on a GPU

GPU Based N-Gram String Matching Algorithm with Score Table Approach for String Searching in Many Documents