Faster two-dimensional pattern matching with rotations

The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O(n²m³)$\mathrm{O}(n^2{m}^3)$, where the size of the text is n×n$n\times n$ and the size of the pattern is m×m$m\times m$. In this paper we present a new algorithm for the problem whose running time is O(n²m²)$\mathrm{O}(n^2{m}^2)$.     

一种快速的单模式匹配算法

在对Boyer-Moore(BM)算法及其改进的Tuned Boyer-Moore(TunedBM)算法进行分析的基础上,提出了一种更加快速的单模式匹配算法--NFS.该算法利用当前尝试中匹配失败字符的位置信息进行更大的尝试位置移动,使算法具有更高的效率.实验结果表明,NFS算法的性能优于同类的其他算法,特别是在模式长度较短的情况下,优势更为明显.     

基于Extended Dewey编码的小枝模式匹配方法

XML数据库的查询优化技术是当前数据库领域中的一个研究热点,而小枝模式匹配又是其中的一个研究重点.在总结分析各种小枝模式匹配算法的基础上,提出了一种新的基于Extended Dewey编码的小枝模式匹配方法.该方法首先使用TJFast算法在XML文档的JoinGuide索引上进行预匹配,然后再扫描预匹配结果中的叶子结点序列就可以找出所有的匹配结果.最后,用实验的方法同其它算法作了比较,并对实验结果进行了分析.     

Real-time pattern matching using projection kernels

A novel approach to pattern matching is presented in which time complexity is reduced by two orders of magnitude compared to traditional approaches. The suggested approach uses an efficient projection scheme which bounds the distance between a pattern and an image window using very few operations on average. The projection framework is combined with a rejection scheme which allows rapid rejection of image windows that are distant from the pattern. Experiments show that the approach is effective even under very noisy conditions. The approach described here can also be used in classification schemes where the projection values serve as input features that are informative and fast to extract.     

Three-dimensional flow characterization using vector pattern matching

This paper describes a novel method for regional characterization of three-dimensional vector fields using a pattern matching approach. Given a three-dimensional vector field, the goal is to automatically locate, identify, and visualize a selected set of classes of structures or features. Rather than analytically defining the properties that must be fulfilled in a region in order to be classified as a specific structure, a set of idealized patterns for each structure type is constructed. Similarity to these patterns is then defined and calculated. Examples of structures of interest include vortices, swirling flow, diverging or converging flow, and parallel flow. Both medical and aerodynamic applications are presented in this paper.     

采用集合切分编码的大容量模式匹配算法*

针对现有模式匹配算法无法实现大容量模式集快速搜索的不足,提出了一种基于TCAM多字节状态机的模式匹配算法。利用TCAM的掩码特性,切分具有相同匹配字符串的状态集,提出了一种编号编码压缩机制。通过理论证明,集合切分编码利用状态机的已匹配信息,将编号存储改变为编号段存储,大幅压缩了具有相同转移字符串和目的状态的交叉转移路径,减少TCAM表项数目。经理论分析和实验仿真,该算法不仅具有高搜索速率,而且可以减少大量相似表项,降低TCAM存储资源消耗,从而支持大容量的模式集。     

XML twig pattern matching using version tree

A common problem of XML query algorithms is that execution time and input size grows rapidly as the size of XML document increases. In this paper, we propose a version-labeling scheme and TwigVersion algorithm to address this problem. The version-labeling scheme is utilized to identify all repetitive structures in XML documents, and the Version Tree is constructed to hold such version information. To process a query, TwigVersion generates a filter through the created Version Tree, and the final answer to the query can be retrieved from the database easily through the filtering process. Both theoretical proof and experimental results reported in this paper demonstrate that the concise structure of Version Tree and the reduced input size make TwigVersion outperform the existing approaches.     

基于字符和0/1码的DNA压缩模式匹配算法*

分析对DNA序列数据进行压缩和压缩模式匹配的重要性,采用0/1编码的非自适应算法进行压缩,提出两类压缩模式匹配思路,设计实现了四种算法,并进行了性能比较.     

高效的图模型点模式匹配算法

点模式匹配的概率图模型具有很好的匹配精度,但是计算复杂度较高,当隔离子中包含异常点（outlier）时匹配精度会受到较大的影响。为了提高匹配的速度和精度,提出了一种由粗到精的图模型点模式匹配算法。利用包含特征点的窗口,用标准化互相关方法对特征点进行粗匹配,以减少异常点的数量,提高后续匹配方法的速度和精度。提出了一种新的点模式匹配的概率图模型,这种图模型能综合利用特征点的位置信息和包含特征点的邻域的灰度信息。利用提出的概率图匹配方法对粗匹配所得到的点对进行分段匹配,得到精确的匹配结果。对光学图像和遥感图像的匹配实验显示该方法能显著减少点模式匹配时间,提高匹配的精度。     

A novel access control method using Morton number and prime factorization

A novel scheme used for controlling access requests in security information system is proposed. In the proposed method, the system administrator chooses distinct prime numbers representing each atomic access right as well as four large prime numbers for encryption. By setting these representative prime numbers as input parameters, the proposed method applies a one-way function combining the Morton number theory transferring into a single value to derive the encrypted compound privilege (ECP). With ECP, verification of right of access can be achieved easily and secretly. Meanwhile, the proposed scheme provides the following advantages: (1) the verification of right of access can be effectively implemented using the Morton sequence with coordinate transformation; (2) the problem of dynamic access control also can be effectively implemented; (3) integrity and confidentiality while controlling system resources can be ensured; (4) the proposed method can decrease the redundancy of the access matrix in some specific circumstances.     

A lossless ECG data compression technique using ASCII character encoding

A software based lossless ECG compression algorithm is developed here. The algorithm is written in the C-platform. The algorithm has applied to various ECG data of all the 12 leads taken from PTB diagnostic ECG database (PTB-DB). Here, a difference array has been generated from the corresponding input ECG data and this is multiplied by a large number to convert the number of arrays into integers. Then those integers are grouped in both forward and reverse direction, out of which few are treated differently. Grouping has been done in such a way that every grouped number resides under valid ASCII value. Then all the grouped numbers along with sign bit and other necessary information are converted into their corresponding ASCII characters. The reconstruction algorithm has also been developed in using the reversed logic and it has been observed that data is reconstructed with almost negligible difference as compared with the original (PRD 0.023%).     

Rotation-invariant pattern matching with color ring-projection

In this paper, we propose a rotation-invariant pattern-matching scheme for detecting objects in complex color images. The complexity and computational load for matching colored objects in arbitrary orientations are reduced significantly by the 1-D color ring-projection representation. It can rapidly select the possible locations of a reference template in the input scene by computing the normalized correlation of 1-D color ring-projection patterns. Objects in the candidate locations are then verified by the pixel-to-pixel template matching. To make the pixel-based matching invariant to rotation, a color feature is used as pixel density, and the axis of least second moment is employed to estimate the rotational angle of a colored pattern. The proposed method has shown promising result based on experiments on a variety of natural and industrial images.     

Robust real-time pattern matching using bayesian sequential hypothesis testing

This paper describes a method for robust real time pattern matching. We first introduce a family of image distance measures, the "Image Hamming Distance Family". Members of this family are robust to occlusion, small geometrical transforms, light changes and non-rigid deformations. We then present a novel Bayesian framework for sequential hypothesis testing on finite populations. Based on this framework, we design an optimal rejection/acceptance sampling algorithm. This algorithm quickly determines whether two images are similar with respect to a member of the Image Hamming Distance Family. We also present a fast framework that designs a near-optimal sampling algorithm. Extensive experimental results show that the sequential sampling algorithm performance is excellent. Implemented on a Pentium 4 3 GHz processor, detection of a pattern with 2197 pixels, in 640 x 480 pixel frames, where in each frame the pattern rotated and was highly occluded, proceeds at only 0.022 seconds per frame.     

Bidirectional deformable matching with application to handwritten character extraction

To achieve integrated segmentation and recognition in complex scenes, the model-based approach has widely been accepted as a promising paradigm. However, the performance is still far from satisfactory when the target object is highly deformed and the level of outlier contamination is high. In this paper, we first describe two Bayesian frameworks, one for classifying input patterns and another for detecting target patterns in complex scenes using deformable models. Then, we show that the two frameworks are similar to the forward-reverse setting of Hausdorff matching and that their matching and discriminating properties are complementary to each other. By properly combining the two frameworks, we propose a new matching scheme called bidirectional matching. This combined approach inherits the advantages of the two Bayesian frameworks. In particular, we have obtained encouraging empirical results on shape-based pattern extraction, using a subset of the CEDAR handwriting database containing handwritten words of highly varying shape.     

一种基于可排序视图的RDF模式匹配算法

随着语义网络中数据量的激增,在RDF数据集中高效查询数据已成为一个亟待解决的问题。传统的基于物化视图的RDF模式匹配方法虽然能降低表的自连接操作次数,加快查询模式重写过程,但在视图集中检索模式匹配的视图等价于子图同构这一NP-hard问题。为了减小查询模式重写代价,提高RDF模式匹配过程效率,引入可排序视图概念,设计包含映射发现算法contain及其扩展算法contain+,简化等长度模式间包含映射发现过程,同时保证模式间的匹配代价与输入数据的规模线性相关。此外,提出基于倒排表/MapReduce检索候选可排序视图的方法,实现RDF模式重写算法rewrite,用以处理不同规模数据集上的模式匹配问题。理论分析及实验证明,基于可排序视图的RDF模式匹配算法能有效地兼顾算法效率及算法可扩展性。     

Effective pattern matching of source code using abstract syntax patterns

Program understanding can be assisted by tools that match patterns in the program source. Lexical pattern matchers provide excellent performance and ease of use, but have a limited vocabulary. Syntactic matchers provide more precision, but may sacrifice performance, robustness, or power. To achieve more of the benefits of both models, we extend the pattern syntax of AWK to support matching of abstract syntax trees, as demonstrated in a tool called TAWK. Its pattern syntax is language‐independent, based on abstract tree patterns. As in AWK, patterns can have associated actions, which in TAWK are written in C for generality, familiarity, and performance. The use of C is simplified by high‐level libraries and dynamic linking. To allow processing of program files containing non‐syntactic constructs such as textual macros, mechanisms have been designed that allow matching of ‘language‐like’ macros in a syntactic fashion. We survey and apply prototypical approaches to concretely demonstrate the tradeoffs in program processing. Our results indicate that TAWK can be used to quickly and easily perform a variety of common software engineering tasks, and the extensions to accommodate non‐syntactic features significantly extend the generality of syntactic matchers. Copyright © 2005 John Wiley & Sons, Ltd.     

Efficient dominating sets in circulant graphs with domination number prime

Cayley graphs of finite cyclic group ${\mathbb{Z}}_n$ are called circulant graphs and denoted by $\mathrm{Cay}({\mathbb{Z}}_n,S)$. For $\mathrm{Cay}({\mathbb{Z}}_n,S)$ with $\frac{n}{|S|+1}$ prime, we give a necessary and sufficient condition for the existence of efficient dominating sets and characterize completely all its efficient dominating sets.     

The number of spanning trees of a graph with given matching number

The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. In this paper, we present sharp upper bounds for the number of spanning trees of a graph with given matching number.     

Visualizing temporal patterns in large multivariate data using textual pattern matching

Extracting and visualizing temporal patterns in large scientific data is an open problem in visualization research. First, there are few proven methods to flexibly and concisely define general temporal patterns for visualization. Second, with large time-dependent data sets, as typical with today's large-scale simulations, scalable and general solutions for handling the data are still not widely available. In this work, we have developed a textual pattern matching approach for specifying and identifying general temporal patterns. Besides defining the formalism of the language, we also provide a working implementation with sufficient efficiency and scalability to handle large data sets. Using recent large-scale simulation data from multiple application domains, we demonstrate that our visualization approach is one of the first to empower a concept driven exploration of large-scale time-varying multivariate data.