检索结果-内蒙古大学图书馆

High performance parallel kmp algorithm on a heterogeneous architecture

CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS 2020年第3期23卷 2205-2217页

作者： Park, Neungsoo Park, Soeun Lee, Myungho Konkuk Univ Dept Comp Sci & Engn Seoul South Korea Myongji Univ Dept Comp Sci & Engn Yongin Kyungkido South Korea

String matching algorithm is widely used in many application areas such as bio-informatics, network intrusion detection, computer virus scan, among many others. Knuth-Morris-Pratt (kmp) algorithm is commonly used for its fast execution time compared with many other string matching algorithms when applied to large input texts. However, the performance of the kmp algorithm is limited when the input text size increases significantly beyond a certain limit. In this paper, we propose a high performance parallel kmp algorithm on the Heterogeneous High Performance Computing (HPC) architecture based on the general-purpose multicore microprocessor and the manycore graphic processing unit (GPU) using OpenCL as the General Purpose computing using Graphic Processing Unit (GPGPU) platform. The proposed parallel kmp algorithm mainly focuses on optimizing the CPU-GPU memory hierarchy by overlapping the data transfer between the CPU memory and the GPU memory with the string matching operations on the GPU. It also optimizes the allocation of the work-groups and the work-items, and places the pattern data and the failure table in the on-chip local memory of the GPU. Exploiting multiple GPUs further the performance improvements. The experimental results show that the optimized parallel kmp algorithm leads up to 15.25 times speedup compared with the version before our optimization techniques were applied.

关键词： kmp algorithm GPGPU OpenCL Heterogeneous computing Computation communication overlapping

来源：评论

学校读者我要写书评

暂无评论

High Performance Parallel kmp algorithm on a Heterogeneous Architecture 3

High Performance Parallel KMP Algorithm on a Heterogeneous A...

引用

3rd IEEE International Workshops on Foundations and Applications of Self* Systems (FAS*W)

作者： Park, Soeun Kim, Daehee Park, Neungsoo Lee, Myungho Konkuk Univ Dept Comp Sci & Engn Seoul South Korea Myongji Univ Dept Comp Sci & Engn Yongin Kyungkido South Korea

ISBN: (纸本)9781538651759

String matching algorithm is widely used in many application areas such as bio-informatics, network intrusion detection, computer virus scan, among many others. kmp (Knuth-Morris-Pratt) algorithm is commonly used for its fast execution time compared with many other string matching algorithms when applied to large input texts. However, the performance of the kmp algorithm is limited when the input text size increases significantly beyond a certain limit. In this paper, we propose a high performance parallel kmp algorithm on the Heterogeneous High Performance Computing (HPC) architecture based on the general-purpose multicore microprocessor and the Graphic Processing Unit (GPU) using OpenCL as the GPGPU (General Purpose computing using Graphic Processing Unit) platform. The proposed parallel kmp algorithm mainly focuses on optimizing the CPU-GPU memory hierarchy by overlapping the data transfer between the CPU memory and the GPU memory with the string matching operations on the GPU. It also optimizes the allocation of the work-groups and the work-items, and places the pattern data and the Failure Table to the on-chip shared-memory of the GPU. The experimental results show that the optimized parallel kmp algorithm leads up to 8 times faster execution time.

关键词： kmp algorithm heterogeneous computing computation communication overlapping GPGPU OpenCL

来源：评论

学校读者我要写书评

暂无评论

Application of kmp algorithm in Customized Flow Analysis 3

Application of KMP Algorithm in Customized Flow Analysis

引用

3rd IEEE International Conference on Computer and Communications (ICCC)

作者： Meng, Qingzhu Lei, Zhenming He, Dazhong Wang, Huan Beijing Univ Posts & Telecommun Beijing Key Lab Network Syst Architecture & Conve Beijing Lab Adv Informat Networks Beijing Peoples R China Haohandata Technol Co Ltd Beijing Peoples R China

ISBN: (纸本)9781509063529

Internet technology has developed rapidly today, the Internet has become an indispensable part of the way everyone online more and more diverse, there are PC, mobile phones, flat and even watches, etc .;and the speed of the network with the increase in bandwidth and rapid growth The The traffic data completely records the behavior of each person online, if you can effectively use the flow of data analysis, it will be a huge treasure. The usage of virtualization technology can improve the utilization rate of data center equipment and bring convenience to cloud computing applications [1]. Based on the analysis of traffic, this paper introduces the basic idea of traffic analysis system, what is custom traffic analysis, and then explores how to improve the efficiency of traffic analysis. kmp algorithm is proposed for initialization based on the K-means partition algorithm[2], experiments show that kmp algorithm significantly reduces the disparity between the initial solution and the actual solution[3], so you can consider using it to improve efficiency ,such as the application of kmp algorithm in traffic analysis.

关键词： traffic analysis flow kmp algorithm

来源：评论

学校读者我要写书评

暂无评论

Parallelization of kmp String Matching algorithm

Parallelization of KMP String Matching Algorithm

引用

World Congress on Computer and Information Technologies (WCCIT)

作者： Alzoabi, Ubaid S. Alosaimi, Naser M. Bedaiwi, Abdullah S. Alabdullatif, Abdullatif M. King Saud Univ Coll Comp & Informat Sci Dept Comp Sci Riyadh Saudi Arabia

ISBN: (纸本)9781479904624

Knuth Morris-Pratt (kmp) algorithm is one of the most popular strings searching algorithm. The parallelism of kmp is one of research topic over last two years. In our paper we simulated two current parallel algorithms with our new proposed parallel algorithm. Our simulation result presents improvement of our proposed parallel algorithm.

关键词： component kmp algorithm String matching parallelism parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

A fast algorithm for order-preserving pattern matching

引用

INFORMATION PROCESSING LETTERS 2015年第2期115卷 397-402页

作者： Cho, Sukhyeun Na, Joong Chae Park, Kunsoo Sim, Jeong Seop Inha Univ Dept Comp & Informat Engn Inchon 402751 South Korea Sejong Univ Dept Comp Sci & Engn Seoul 143747 South Korea Seoul Natl Univ Sch Comp Sci & Engn Seoul 151742 South Korea

Given a text T and a pattern P, the order-preserving pattern matching (OPPM) problem is to find all substrings in T which have the same relative orders as P. The OPPM has been studied in the fields of finding some patterns affected by relative orders, not by their absolute values. In this paper, we present a method of deciding the order-isomorphism between two strings even when there are same characters. Then, we show that the bad character rule of the Horspool algorithm for generic pattern matching problems can be applied to the OPPM problem and we present a space-efficient algorithm for computing shift tables for text search. Finally, we combine our bad character rule with the kmp-based algorithm to improve the worst-case running time. We give experimental results to show that our algorithm is about 2 to 6 times faster than the kmp-based algorithm in reasonable cases. (C) 2014 Published by Elsevier B.V.

关键词： Analysis of algorithms Order-preserving pattern matching Order-isomorphism Horspool algorithm kmp algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for Computing the Statistics of Pattern Matching

引用

IEEE ACCESS 2021年 9卷 114965-114976页

作者： Zhang, Danna Jin, Kai Sun Yat Sen Univ Sch Intelligent Syst Engn Shenzhen 510275 Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China

Pattern matching is a fundamental problem in theoretical computer science. The algorithms for pattern matching and the study on the statistics of pattern matching have found enormous applications in practical elds. In this paper, we revisit the Markov embedding approach for studying pattern matching in repeated experiments. For any pattern of length m over alphabet Sigma, we show that the mean and variance of the waiting time of the pattern in iid experiments can be computed in O(m) time based on Markov embedding technique, improving over the O(|Sigma| m) and O(m(2)) naive bounds. Our method extends to computing the k -th moment of the waiting time, and it extends to computing other related statistics about pattern matching in repeated experiments, and it also extends to the case of Markov dependent experiments.

关键词： Pattern matching statistics failure function Markov chain kmp algorithm automaton

来源：评论

学校读者我要写书评

暂无评论

Order-preserving matching

引用

THEORETICAL COMPUTER SCIENCE 2014年 525卷 68-79页

作者： Kim, Jinil Eades, Peter Fleischer, Rudolf Hong, Seok-Hee Iliopoulos, Costas S. Park, Kunsoo Puglisi, Simon J. Tokuyama, Takeshi Seoul Natl Univ Inst Comp Technol Dept Comp Sci & Engn Seoul South Korea Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia Fudan Univ SCS Shanghai 200433 Peoples R China Fudan Univ IIPL Shanghai 200433 Peoples R China German Univ Technol Oman Dept Appl Informat Technol Muscat Oman Kings Coll London Dept Informat London WC2R 2LS England Curtin Univ Digital Ecosyst & Business Intelligence Inst Perth WA Australia Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 980 Japan

We introduce a new string matching problem called order-preserving matching on numeric strings, where a pattern matches a text if the text contains a substring of values whose relative orders coincide with those of the pattern. Order-preserving matching is applicable to many scenarios such as stock price analysis and musical melody matching in which the order relations should be matched instead of the strings themselves. Solving order-preserving matching is closely related to the representation of order relations of a numeric string. We define the prefix representation and the nearest neighbor representation of the pattern, both of which lead to efficient algorithms for order-preserving matching. We present efficient algorithms for single and multiple pattern cases. For the single pattern case, we give an O(n logm) time algorithm and optimize it further to obtain O(n+m logm) time. For the multiple pattern case, we give an O(n logm) time algorithm. (C) 2013 Elsevier B.V. All rights reserved.

关键词： String matching Numeric string Order relation Multiple pattern matching kmp algorithm Aho-Corasick algorithm

来源：评论

学校读者我要写书评

暂无评论

A Chaotic Image Encryption Scheme Based on Genetic Central Dogma and kmp Method

引用

INTERNATIONAL JOURNAL OF BIFURCATION AND CHAOS 2022年第12期32卷 2250186-2250186页

作者： Sha, Yuwen Bo, Sun Yang, Chenxiao Mou, Jun Jahanshahi, Hadi Dalian Polytech Univ Sch Informat Sci & Engn Dalian 116034 Peoples R China Univ Manitoba Dept Mech & Mfg Engn Winnipeg MB Canada

In this paper, an image cryptosystem based on genetic central dogma (GCD), Knuth-Morria-Pratt (kmp) algorithm and a chaotic system is developed. The kmp algorithm is firstly used to bind DNA strings to obtain the next array, which participates in the design of the chaotic initial condition, and then the secure chaotic sequences are produced by employing the sliding idea in pattern string matching. In the present procedure, a DNA-level two-way pixel's shuffle is achieved by a shared stack push operation and it is adopted in the permutation module for the purpose of accelerating the overall pixel's shuffle. Subsequently, the pixel values are substituted by simulating the process of protein synthesis in GCD, in which the DNA replication and RNA replication form the basis of the DNA-triploid mutation and new RNA mutation rules, respectively. Experimental simulations and extensive cryptanalysis fully vindicate that superior security effects in addition to satisfactory low time complexity can be simultaneously obtained by the proposed confusion-substitution scheme.

关键词： Genetic central dogma kmp algorithm DNA-triploid mutation RNA mutation confusion-substitution

来源：评论

学校读者我要写书评

暂无评论

A Single-pattern Matching algorithm Base on Twice Jumps in the Intrusion Detection Systems 12

A Single-pattern Matching Algorithm Base on Twice Jumps in t...

引用

12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD)

作者： Yang, Zhongming Lin, Shen Comp Engn Tech Coll Guangdong Inst Sci & Technol Guangdong Prov Key Lab Petrochem Zhuhai 519090 Guangdong Peoples R China Shenzhen Youfang Technol Co Ltd Shenzhen 518109 Guangdong Peoples R China

ISBN: (纸本)9781467376822

The pattern matching algorithm is one of the core algorithms used in the intrusion detection system. The classical snort system has completed the matching for characteristic string of intrusion through the BM single-pattern algorithm. In actual application, the Sunday algorithm has a efficiency higher than the BM algorithm. In this text, an extra jump array was added to the jump arrays of the Sunday algorithm. When it appears unequal characters during the procedure of matching, make twice jumps successively and help decrease the redundant matching to a greater extent. This text describes how to realize twice-jumps algorithm and its analysis and experimental verification show the accuracy and efficiency of the improved algorithm compared with the Sunday algorithm.

关键词： string matching BM algorithm BF algorithm kmp algorithm Sunday algorithm

来源：评论

学校读者我要写书评

暂无评论

Poster: A YC_Sunday algorithm Based on Improved Sunday algorithm 9

Poster: A YC_Sunday Algorithm Based on Improved Sunday Algor...

引用

9th International Conference on Communications and Networking in China (CHINACOM 2014)

作者： Yang, Zhongming Shen, Lin Yang, Yaru Guangdong Univ Petrochem Technol Maoming Guangdong Peoples R China Guangdong Prov Key Lab Petrochem Equipment Fault Maoming Guangdong Peoples R China Shenzhen Youfang Technol Co Ltd Shenzhen Guangdong Peoples R China Guangdong Maoming Petr Grp Co Ltd Maoming Guangdong Peoples R China

This article improved the Sunday substring searching algorithm, an extra jump arry be created, when a mismatching occurs, the pattern string will jump twice, more redundant matching be reduced. This article describes ... 详细信息

ISBN: (纸本)9781479959709

关键词： string matching kmp algorithm Sunday algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：