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

XWM: a high-speed matching algorithm for large-scale URL rules in wireless surveillance applications

MULTIMEDIA TOOLS AND APPLICATIONS 2020年第23-24期79卷 16245-16263页

作者： Zhang, Shuzhuang Sun, Yanbin Meng, Fanzhi Fu, Yunsheng Jia, Bowei wu, Zhigang Beijing Univ Posts & Telecommun Inst Network Technol Beijing 100786 Peoples R China Guangzhou Univ Cyberspace Inst Adv Technol Guangzhou 510006 Peoples R China China Acad Engineer Phys Inst Comp Applicat Mianyang 621900 Sichuan Peoples R China

Large-scale high-speed URL matching is a key operation in many network security systems and surveillance applications in Wireless Sensor Networks. Classic string matching algorithms are unsuitable for large-scale URL filtering due to speed or memory consumption. This paper proposes an extend wu-manber algorithm (XWM) which takes advantage of the encoding characteristics of the URL greatly to improve the matching performance of the algorithm. It first adopts the pattern string window selection method to optimize wu-manber's hash process, and then combines hash tables and associative containers to optimize the string comparison process. The experimental results on actual 10 million patterns show that XWM can achieve speeds that are twice as fast as traditional algorithms, especially when the shortest pattern string length is longer, it is more advantageous.

关键词： Multi-string matching URL matching wu-manber algorithm

来源：评论

学校读者我要写书评

暂无评论

BLAST: B-LAyered bad-character SHIFT tables for high-speed pattern matching

引用

IET INFORMATION SECURITY 2013年第3期7卷 195-202页

作者： Choi, Yoon-Ho Seo, Seung-Woo Kyonggi Univ Dept Convergence Secur Suwon 443370 South Korea Seoul Natl Univ Sch Elect Engn & Comp Sci Seoul 151744 South Korea

In this study, the authors propose a new multi-pattern matching algorithm, called BLAST (B-LAyered bad-character Shift Tables with a single-byte search unit), which considers space-time tradeoff in the context of shift values during the search. Here, the term bad character' is a character that causes a mismatch. While checking multiple bytes in scanning the text at a time, the BLAST algorithm overcomes the reduction of the average shift value in a typical search, which is caused by the dependency on the multi-byte search unit (MBSU) and the large frequency of the last character of the given patterns. From the theoretical analysis, the authors validate the correctness of the BLAST algorithm. Also, from the experimental results across different setups, the authors show that the BLAST algorithm provides the faster search time than the other algorithms. For example, the authors obtain an enhancement by as much as 212.41% on average for various numbers of attack patterns and attack traffic conditions compared with that of the modified wu-manber algorithm. In addition, it is shown that the BLAST algorithm drastically reduces the amount of memory required for constructing the shift table based on a MBSU from 64 KB to 1 KB.

关键词： search problems string matching text analysis computer network security B-layered bad-character SHIFT tables high-speed pattern matching multipattern matching algorithm space-time tradeoff shift values BLAST algorithm text scanning byte checking single-byte search unit single bad-character SHIFT table multibyte search unit MBSU pattern search time attack patterns attack traffic conditions wu-manber algorithm

来源：评论

学校读者我要写书评

暂无评论

An aggressive algorithm for multiple string matching

引用

INFORMATION PROCESSING LETTERS 2009年第11期109卷 553-559页

作者： Dai, Liuling Beijing Inst Technol Sch Comp Sci Beijing Lab Intelligent Informat Technol Beijing 100081 Peoples R China

A new algorithm based on the wu-manber algorithm for multiple string matching is presented in this paper. The algorithm eliminates the functional overlap of the table HASH and SHIFT, and computes the shift distances in an aggressive manner. After each test, the algorithm examines the character next to the scan window to maximize the shift distance. This idea is consistent with that of the quick-search (QS) algorithm. Experimental results on four alphabets show that the new algorithm is more efficient than wu-manber and other recent algorithms, particularly on short pattern sets and large alphabet. (C) 2009 Elsevier B.V. All rights reserved.

关键词： String matching Multiple string matching wu-manber algorithm Design of algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallelizing Exact and Approximate String Matching via Inclusive Scan on a GPU

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2017年第7期28卷 1989-2002页

作者： Mitani, Yasuaki Ino, Fumihiko Hagihara, Kenichi DWANGO Corp Ltd Dev Head Off Chuo Ku 4-12-15 Ginza Tokyo 1040061 Japan Osaka Univ Grad Sch Informat Sci & Technol 1-5 Yamadaoka Suita Osaka 5650871 Japan

In this study, to substantially improve the runtimes of exact and approximate string matching algorithms, we propose a tribrid parallel method for bit-parallel algorithms such as the Shift-Or andwu-manber algorithms. Our underlying idea is to interpret bit-parallel algorithms as inclusive-scan operations, which allow these bit-parallel algorithms to run efficiently on a graphics processing unit (GPU);we achieve this speed-up here because inclusive-scan operations not only eliminate duplicate searches between threads but also realize a GPU-friendly memory access pattern that maximizes memory read/write throughput. To realize our ideas, we first define two binary operators and then present a proof regarding the associativity of these operators, which is necessary for the parallelization of the inclusive-scan operations. Finally, we integrate the inclusive-scan scheme into a previous segmentation-based scheme to maximize search throughput, identifying the best tradeoff point between synchronization cost and duplicate work. Through our experiments, we compared our proposed method with previous segmentation-based methods and indexing-based sequence aligners. For online string matching, our proposed method performed 6.7-16.7 times faster than previous methods, achieving a search throughput of up to 1.88 terabits per second (Tbps) on a GeForce GTX TITAN X GPU. We therefore conclude that our proposed method is quite effective for decreasing the runtimes of online string matching of short patterns.

关键词： String matching bit-parallel algorithm inclusive scan shift-or algorithm wu-manber algorithm GPU

来源：评论

学校读者我要写书评

暂无评论

Bit-parallel approximate pattern matching: Kepler GPU versus Xeon Phi

引用

PARALLEL COMPUTING 2016年 54卷 128-138页

作者： Tuan Tu Tran Liu, Yongchao Schmidt, Bertil Johannes Gutenberg Univ Mainz Inst Informat D-55128 Mainz Germany Georgia Inst Technol Sch Computat Sci & Engn Atlanta GA 30332 USA

Approximate pattern matching (APM) targets to find the occurrences of a pattern inside a subject text allowing a limited number of errors. It has been widely used in many application areas such as bioinformatics and information retrieval. Bit-parallel APM takes advantage of the intrinsic parallelism of bitwise operations inside a machine word. This approach typically encodes non-deterministic finite automaton (NFA) states or value differences between adjacent cells of a dynamic programming matrix in the form of bit arrays. wu-manber (WM) is a well-known bit-parallel APM algorithm, which simulates an NFA and gains parallel efficiency by performing multiple state updates within a machine word. An important parameter is the machine word size (e.g. 32 or 64 bits for CPUs). Due to increasing vector capabilities, efficient mapping of bit-parallel APM algorithms onto modern high performance computing architectures is an interesting research topic. Prominent examples are Xeon Phi coprocessors and CUDA-enabled GPUs, which provide words of size 512 bits (by means of vector registers) and 1024 bits (by means of warps), respectively. In this paper, we investigate mappings of the WM algorithm onto these two accelerator types. Both architectures are able to achieve around two orders-of-magnitude speedups compared to a single-threaded CPU implementation. Moreover, our tile-based implementation on a GeForce Titan graphics card runs up to 2.9 x faster than our implementation on an Intel Xeon Phi 5110P. Source code is available at http://***. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Bit-parallel Approximate pattern matching wu-manber algorithm CUDA GPU Xeon Phi

来源：评论

学校读者我要写书评

暂无评论

An Improved Multi-Pattern Matching algorithm for Large-Scale Pattern Sets 10

An Improved Multi-Pattern Matching Algorithm for Large-Scale...

引用

10th International Conference on Computational Intelligence and Security CIS 2014

作者： Peng, Zhan Wang, Yuping Xue, Jinfeng Xidian Univ Sch Comp Sci & Technol Xian 710071 Peoples R China PLA Unit 68306 Xian 710608 Peoples R China

ISBN: (纸本)9781479974344

Multi-pattern matching algorithms are broadly used in many fields of computer science. However, the performance of the existing algorithms seriously degrades with the increasing of the number of patterns. In this paper, an improved multi-pattern matching algorithm based on the framework of the wu-manber (WM) algorithm is proposed to effectively deal with the large pattern sets. The WM algorithm is improved in two aspects. Firstly, the lengths of lists in the HASH table are balanced to reduce the number of candidate patterns;Secondly, a data structure called the "INDEX table" based on binary search is designed to reduce the time for finding candidate patterns. Experimental results show that our algorithm is efficient for large-scale pattern sets.

关键词： string matching multi-pattern matching wu-manber algorithm

来源：评论

学校读者我要写书评

暂无评论

q-gram hash comparison based multiple exact string matching algorithm for DNA sequences

JOURNAL OF THE FACULTY OF ENGINEERING AND ARCHITECTURE OF GA...

引用

JOURNAL OF THE FACULTY OF ENGINEERING AND ARCHITECTURE OF GAZI UNIVERSITY 2023年第2期38卷 875-888页

作者： Karcioglu, Abdullah Ammar Bulut, Hasan Ataturk Univ Engn Fac Dept Software Engn TR-25240 Erzurum Turkiye Ege Univ Engn Fac Dept Comp Engn TR-35000 Izmir Turkiye

The exact string matching algorithms are among the important study topics in computer science due to their various applications in many fields such as medicine, bioinformatics, and biology. New algorithms have been developed recently, and the string matching on the text has been accelerated. The string matching algorithms are divided into two parts, single and multiple. . The string matching algorithms are divided into two parts, single and multiple. The multiple exact string matching algorithms involve finding d number patterns (P) in a given text T. In this study, the wu-manber algorithm, one of the hash-based multiple exact string matching algorithms, is discussed. Although the wu-manber algorithm is effective, it has some limitations, such as hash collisions. In our study, a new approach has is proposed for these limitations. In the proposed approach, unlike the traditional wu-manber algorithm, the searching in the sequences is performed by q-gram hash comparison, using the hash function that removes hash collisions in DNA sequences. The proposed approach has been compared with the multiple exact string matching algorithms with the well-known algorithms in the literature on E. Coli and Human Chromosome1 datasets. As a result of the experimental studies, better results have been achieved in terms of performance metrics such as the average runtime, the average number of character and hash comparisons in the proposed approach compared to the wu-manber algorithm. Also, the proposed approach is shown to be more efficient than well-known algorithms, such as Aho Corasick (AC) and Commentz Walter (CW).

关键词： Multiple exact string matching pattern matching sequence analysis hash function wu-manber algorithm

来源：评论

学校读者我要写书评

暂无评论

DHSWM：改进的WM 多模式匹配算法

DHSWM：改进的WM 多模式匹配算法

引用

湖南省第三届研究生创新论坛——信息与控制工程的新理论和新技术分论坛

作者：胡勇刚刘卫国

针对WM 算法的查找效率随着模式集规模的增大而降低的问题，提出一种改进算法。在预处理阶段，改变原有Hash 表中的链表结构，采用双哈希法将模式串存放在Hash1 表中指定的区间，Hash 表中存放该存储区间的起始位置与区间大小;Prefix ... 详细信息

针对WM 算法的查找效率随着模式集规模的增大而降低的问题，提出一种改进算法。在预处理阶段，改变原有Hash 表中的链表结构，采用双哈希法将模式串存放在Hash1 表中指定的区间，Hash 表中存放该存储区间的起始位置与区间大小;Prefix 表用于判断模式集中是否存在与当前匹配窗口中文本前缀相同的模式;当Shift 表中出现移动值为0 时，根据后缀出现在模式串其他位置的信息计算匹配窗口可滑动的最大距离值并存于Shift1 表中。在查找阶段，采用双哈希法在Hash1 表的某一区间中查找模式串，避免了在大规模模式集情况下查找过长的模式链表，扩大了匹配操作后匹配窗口滑动的距离，减少了冗余的匹配操作，缩短了查找时间。实验表明，在模式集规模较大时，改进后的算法能显著地提高匹配速度，当模式串数目超过5000 条时，改进算法的查找时间要比WM算法缩短40％~47％。

关键词： intrusion detection pattern matching wu-manber algorithm double hash searching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：