Longest prefix matching using bloom filters

We introduce the first algorithm that we are aware of to employ Bloom filters for longest prefix matching (LPM). The algorithm performs parallel queries on Bloom filters, an efficient data structure for membership queries, in order to determine address prefix membership in sets of prefixes sorted by prefix length. We show that use of this algorithm for Internet Protocol (IP) routing lookups results in a search engine providing better performance and scalability than TCAM-based approaches. The key feature of our technique is that the performance, as determined by the number of dependent memory accesses per lookup, can be held constant for longer address lengths or additional unique address prefix lengths in the forwarding table given that memory resources scale linearly with the number of prefixes in the forwarding table. Our approach is equally attractive for Internet Protocol Version 6 (IPv6) which uses 128-bit destination addresses, four times longer than IPv4. We present a basic version of our approach along with optimizations leveraging previous advances in LPM algorithms. We also report results of performance simulations of our system using snapshots of IPv4 BGP tables and extend the results to IPv6. Using less than 2 Mb of embedded RAM and a commodity SRAM device, our technique achieves average performance of one hash probe per lookup and a worst case of two hash probes and one array access per lookup.     

一种提高模式匹配速度的新方法

在分析了经典的BM算法以及一些重要的改进算法的基础上,根据首字符唯一的特点提出了一种新的模式匹配算法--BMX算法。该算法利用模式串首字符的唯一性,通过判断文本串后一位是否在模式串中出现以及下一位字符和模式串首字符的比较,能使最大位移量提升到,出现概率也显著提高。实验结果表明,BMX算法能够最大限度地跳过坏字符,大大减少了匹配次数和字符的比较个数,加快了匹配速度,效率优于BM、BMH、BMHS等算法。     

On the relation of order-statistics filters and template matching:optimal morphological pattern recognition

In this paper, we investigate methods for optimal morphological pattern recognition. The task of optimal pattern recognition is posed as a solution to a hypothesis testing problem. A minimum probability of error decision rule-maximum a posteriori filter-is sought. The classical solution to the minimum probability of error hypothesis testing problem, in the presence of independent and identically distributed noise degradation, is provided by template matching (TM). A modification of this task, seeking a solution to the minimum probability of error hypothesis testing problem, in the presence of composite (mixed) independent and identically distributed noise degradation, is demonstrated to be given by weighted composite template matching (WCTM). As a consequence of our investigation, the relationship of the order-statistics filter (OSF) and TM-in both the standard as well as the weighted and composite implementations-is established. This relationship is based on the thresholded cross-correlation representation of the OSF. The optimal order and weights of the OSF for pattern recognition are subsequently derived. An additional outcome of this representation is a fast method for the implementation of the OSF.     

HTS microstrip matching networks and filters

High-temperature superconducting (HTS) YBCO microstrip bandpass filters and microstrip impedance matching networks were fabricated, tested and compared with the predicted performance. Vector corrected measurements of these circuits were performed at cryogenic temperatures. Comparisons of the insertion loss for the HTS and corresponding Au filters are presented, as well as the predicted noise figure for the low-noise amplifiers using HTS and Au matching networks     

Bit-sequential array for pattern matching

This letter presents the design and analysis of a bit-sequential array for pattern matching applications. The architecture makes multiple use of each data sample, has built-in concurrency and pipelining, and is based on a highly modular design with only nearest neighbor connections between array modules. The array computes all occurrences of a pattern of length m, in the string of length n, in O(m + n) time and O(m) hardware. The pattern and the string are fed in sequentially and the match indicators come out in the same fashion, leading to a significant reduction in silicon area.     

夜间图像匹配中的斑状噪声预处理

夜间图像匹配中,实时夜间图像中的斑状噪声影响了边缘相关匹配的性能。在分析了斑状噪声特点的基础上,提出了一种新的基于标记的噪声预处理方法,先标记出图像中的斑状噪声点,在匹配时被标记的噪声点不参与相关统计,从而达到消除斑状噪声对匹配影响的目的。该方法与传统的中值滤波、均值滤波等方法相比,更能提高相关匹配的性能,试验结果验证了该方法的有效性。     

一种新型分组过滤器的存储和匹配方案设计

PF(分组过滤器)是EPS(演进型分组系统)的重要组成部分。在详细分析EPS中PF存储方案的基础上,给出了一种新的基于EPS承载的PF储存和匹配方法,将PF按照对应的承载标识存储到承载信息单元中,同时为了实现基于PF优先级的IP分组数据包匹配,建立了按照优先级排序的PF信息表,利用PF信息表可以快速地找到对应优先级的PF存储位置,完成IP数据包的匹配。     

Reconfigurable approximate pattern matching architectures for nanotechnology

Approximate pattern matching is comparing an input pattern with a target pattern with a specified error tolerance. This ability to compensate for real-world sensor errors makes approximate pattern matching an ideal choice for a wide range of applications. This paper shows that two n-bit patterns may be matched with a single stage nanotechnology architecture using 2n+1 unit area resonant tunneling diodes (RTDs) and one RTD of 1.5 times the unit area. This architecture is reconfigurable for any target pattern and any error tolerance. We analyze current and power characteristics of the architecture and develop configurations to minimize the same. The robustness of the architecture to variations in device characteristics is also investigated.     

A recursive MISD architecture for pattern matching

Many applications require searching for multiple patterns in large data streams for which there is no preprocessed index to rely on for efficient lookups. An multiple instruction stream-single data stream (MISD) VLSI architecture that is based on a recursive divide and conquer approach to pattern matching is proposed. This architecture allows searching for multiple patterns simultaneously. The patterns can be constructed much like regular expressions, and add features such as requiring subpatterns to match in a specific order with some fuzzy distance between them, and the ability to allow errors according to prescribed thresholds, or ranges of such. The current implementation permits up to 127 simultaneous patterns at a clock frequency of 100 MHz, and does 1.024/spl times/10/sup 11/ character comparisons per second.     

Strategies for design automation of high speed digital filters

Optimization techniques for DSP circuits are described based on the design experience with a number of high-speed digital filter chips. These designs show that efficient high speed digital filter designs can be achieved using several optimizations at the architecture, circuit, and layout level. The problems of automating these optimizations in a general DSP synthesis environment are discussed, and possible CAD solutions are proposed.     

具有目标增强功能的模式识别相关滤波器

提出一种改进模式识别相关滤波器的设计方法。它有两个特点：（１） 采用拉普拉斯算子增强输入图像边缘;（２） 滤波器的设计是基于增强后的目标而不是原始目标。计算机模拟结果表明,采用新的方法可以锐化相关峰并得到更好的识别效果。     

On the fly pattern matching for intrusion detection with Snort

Intrusion Detection Systems are becoming necessary tools for system administrators to protect their network. However they find more and more difficulties with high speed networks. To enhance their capacity and deal with evasion techniques, frequently used by hackers, we have introduced a new method to filter the network traffic. The detection method, while being stateful, processes each packet as soon as it is received. We have employed this strategy after a new classification of detection rules. Then, we have used efficient multisearch methods and suitable datastructure for signatures. The method has been successfully implemented as an extension of the Intrusion Detection System “Snort”.     

Quantum-based exact pattern matching algorithms for biological sequences

In computational biology, desired patterns are searched in large text databases, and an exact match is preferable. Classical benchmark algorithms obtain competent solutions for pattern matching in time, whereas quantum algorithm design is based on Grover's method, which completes the search in time. This paper briefly explains existing quantum algorithms and defines their processing limitations. Our initial work overcomes existing algorithmic constraints by proposing the quantum-based combined exact (QBCE) algorithm for the pattern-matching problem to process exact patterns. Next, quantum random access memory (QRAM) processing is discussed, and based on it, we propose the QRAM processing-based exact (QPBE) pattern-matching algorithm. We show that to find all occurrences of a pattern, the best case time complexities of the QBCE and QPBE algorithms are , and the exceptional worst case is bounded by . Thus, the proposed quantum algorithms achieve computational speedup. Our work is proved mathematically and validated with simulation, and complexity analysis demonstrates that our quantum algorithms are better than existing pattern-matching methods.     

Context-dependent multilevel pattern matching for lossless image compression

In this paper, the multilevel pattern matching (MPM) code for compression of one-dimensional (1D) sequences is first generalized to compress two-dimensional (2D) images, resulting in a 2D multilevel pattern matching (MPM) code. It is shown that among all images of n pixels, the worst case redundancy of the 2D MPM code against any finite-template-based arithmetic code is O(1//spl radic/logn). This result contrasts unfavorably with the fact that among all 1D sequences of length n, the MPM code has a worst case redundancy of O(1/logn) against any finite-state arithmetic code; this is caused by the so-called 2D boundary effect. To alleviate the 2D boundary effect, we extend the 2D MPM code to the case of context modeling, yielding a context-dependent 2D MPM code. It is shown that among all images of n pixels, the context-dependent 2D MPM code has an O(1/logn) worst case redundancy against any finite-template-based arithmetic code satisfying a mild condition; this redundancy is better than that of the 2D MPM code without context models. Experimental results demonstrate that the context-dependent 2D MPM code significantly outperforms the 2D MPM code without context models for bi-level images. It is also demonstrated that, in terms of compression rates, the context-dependent 2D MPM code performs significantly better than the progressive coding mode of JBIG1 for both textual and bi-level images, and better than or comparably to the sequential coding mode of JBIG1 and JBIG2. In addition to its excellent compression performance, the context-dependent 2D MPM code allows progressive transmission of images.     

High speed and silicon-saving adaptive tuning system for high frequency Gm-C filters

In this paper, a novel adaptive tuning system used in Gm-C continuous time (CT) filters has been presented. The novelty of this method is the generation of quasi-gradient functions for the adaptive algorithm. By this method we have implemented the fully adaptive tuning algorithm on chip, and received more than 95% precision for the all characteristics of Gm-C filter. All the circuit level simulations and prototype fabrication have been done using 0.6 μ CMOS technology of AMS.     

New systolic realisation of recursive digital filters for high speed applications

A new systolic array for realising an arbitrary order recursive digital filter suitable for high speed filtering is presented. Besides being modular, regular, and having nearest neighbour interconnections, the proposed array has slightly faster response time, reduced number of basic cells, and other possible advantages such as faster throughput rate, and reduced number of delay elements as compared to those of a previous realisation method.<>     

Solution of pattern matching inspection problem for grainy metallayers

In this paper, we demonstrate a new method of improving the defect controllability of grainy metal layers, for example, Hot-Al-Cu wiring, by enhancing the practical sensitivity of in-line inspectors. The problem in increasing practical sensitivity is the nuisance counts caused by grain boundaries, which do not cause electrical failures. We propose a method of decreasing the signal from the grain boundaries. On the grayscale images taken by pattern matching inspectors, grain boundaries are observed as gray on Hot-Al-Cu wiring, which is observed as white. If the illumination brightness is increased, the gray level of the grain boundaries becomes higher and saturates at the upper limit of grayscale, i.e., white. On the other hand, the gray level of the wiring stays white. Thus the signal, the grayscale difference between the grain boundaires and the wiring, can be decreased to almost zero. We call this phenomenon the "saturation effect." Our experimental results prove that the saturation effect due to illumination brightness optimization successfully cancels the nuisance counts caused by grain boundaries. The practical sensitivity limit is enhanced from 0.8 to 0.4 μm. This solution will greatly improve the defect controllability of grainy metal layers     

一种快速模式匹配算法及其在IDS中的应用

模式匹配算法是基于规则的入侵检测系统的核心.对snort的模式匹配原理及其基础BM算法做了描述,在此基础上提出了一种效率更高的2CBM算法,通过每次比较两个字符,并在失配时参考两个Shift值来跳转,实现了更好的向右跳跃性.分析了算法的时间复杂度,基于snort进行了算法验证与测试.新算法极大地提高了匹配效率.     

BM模式匹配算法的研究和改进

模式匹配算法在数字通信、入侵检测等多种领域都有着广泛的应用,BM算法以其高效的匹配过程成为模式匹配算法中应用最为广泛的算法之一。尽管如此,BM算法的效率还是可以再提高的。本文在介绍经典BM算法及其改进的BMH、BMHS算法的基础上,通过整合、改进后,提出了一种新的改进的IBMH算法。在对以上算法进行复杂度分析以后,再通过具体的实验验证。结果表明IBMH算法在比较次数、运行时间、稳定性等方面明显优于BM、BMH以及BMHS等算法。