The identification of design pattern instances is important for program understanding and software maintenance. Aiming at the mining of design patterns in existing systems, this paper proposes a subgraph isomorphism a...The identification of design pattern instances is important for program understanding and software maintenance. Aiming at the mining of design patterns in existing systems, this paper proposes a subgraph isomorphism approach to discover several design patterns in a legacy system at a time. The attributed relational graph is used to describe design patterns and legacy systems. The sub-graph isomorphism approach consists of decomposition and composition process. During the decomposition process, graphs corresponding to the design patterns are decomposed into sub-graphs, some of which are graphs corresponding to the elemental design patterns. The composition process tries to get sub-graph isomorphism of the matched graph if sub-graph isomorphism of each subgraph is obtained. Due to the common structures between design patterns, the proposed approach can reduce the matching times of entities and relations. Compared with the existing methods, the proposed algorithm is not linearly dependent on the number of design pattern graphs. Key words design pattern mining - attributed relational graph - subgraph isomorphism CLC number TP 311.5 Foundation item: Supported by the National Natural Science Foundation of China (60273075) and the Science Foundation of Naval University of Engineering (HGDJJ03019)Biography: LI Qing-hua (1940-), male, Professor, research direction: parallel computing.展开更多
Graph pattern matching(GPM)can be used to mine the key information in graphs.Exact GPM is one of the most commonly used methods among all the GPM-related methods,which aims to exactly find all subgraphs for a given qu...Graph pattern matching(GPM)can be used to mine the key information in graphs.Exact GPM is one of the most commonly used methods among all the GPM-related methods,which aims to exactly find all subgraphs for a given query graph in a data graph.The exact GPM has been widely used in biological data analyses,social network analyses and other fields.In this paper,the applications of the exact GPM were first introduced,and the research progress of the exact GPM was summarized.Then,the related algorithms were introduced in detail,and the experiments on the state-of-the-art exact GPM algorithms were conducted to compare their performance.Based on the experimental results,the applicable scenarios of the algorithms were pointed out.New research opportunities in this area were proposed.展开更多
Expo 2010 Shanghai China was a successful, splendid, and unforgettable event, leaving us with valuable experi- ences. The visitor flow pattern of the Expo is investigated in this paper. The Hurst exponent, the mean va...Expo 2010 Shanghai China was a successful, splendid, and unforgettable event, leaving us with valuable experi- ences. The visitor flow pattern of the Expo is investigated in this paper. The Hurst exponent, the mean value, and the standard deviation of visitor volume indicate that the visitor flow is fractal with long-term stability and correlation as well as obvious fluctuation in a short period. Then the time series of visitor volume is converted into a complex network by using the visibility algorithm. It can be inferred from the topological properties of the visibility graph that the network is scale-free, small-world, and hierarchically constructed, confirming that the time series are fractal and a close relationship exists among the visitor volumes on different days. Furthermore, it is inevitable that will be some extreme visitor volumes in the original visitor flow, and these extreme points may appear in a group to a great extent. All these properties are closely related to the feature of the complex network. Finally, the revised linear regression is performed to forecast the next-day visitor volume based on the previous 10-day data.展开更多
Pattern recognition is a task of searching particular patterns or features in the given input. The data mining, computer networks, genetic engineering, chemical structure analysis, web services etc. are few rapidly gr...Pattern recognition is a task of searching particular patterns or features in the given input. The data mining, computer networks, genetic engineering, chemical structure analysis, web services etc. are few rapidly growing applications where pattern recognition has been used. Graphs are very powerful model applied in various areas of computer science and engineering. This paper proposes a graph based algorithm for performing the graphical symbol recognition. In the proposed approach, a graph based filtering prior to the matching is performed which significantly reduces the computational complexity. The proposed algorithm is evaluated using a large number of input drawings and the simulation results show that the proposed algorithm outperforms the existing algorithms.展开更多
The graph can contain huge amount of data. It is heavily used for pattern recognition and matching tasks like symbol recognition, information retrieval, data mining etc. In all these applications, the objects or under...The graph can contain huge amount of data. It is heavily used for pattern recognition and matching tasks like symbol recognition, information retrieval, data mining etc. In all these applications, the objects or underlying data are represented in the form of graph and graph based matching is performed. The conventional algorithms of graph matching have higher complexity. This is because the most of the applications have large number of sub graphs and the matching of these sub graphs becomes computationally expensive. In this paper, we propose a graph based novel algorithm for fingerprint recognition. In our work we perform graph based clustering which reduces the computational complexity heavily. In our algorithm, we exploit structural features of the fingerprint for K-means clustering of the database. The proposed algorithm is evaluated using realtime fingerprint database and the simulation results show that our algorithm outperforms the existing algorithm for the same task.展开更多
It is difficult to analyze semantic relations automatically, especially the semantic relations of Chinese special sentence patterns. In this paper, we apply a novel model feature structure to represent Chinese semanti...It is difficult to analyze semantic relations automatically, especially the semantic relations of Chinese special sentence patterns. In this paper, we apply a novel model feature structure to represent Chinese semantic relations, which is formalized as ＂recursive directed graph＂. We focus on Chinese special sentence patterns, including the complex noun phrase, verb-complement structure, pivotal sentences, serial verb sentence and subject-predicate predicate sentence. Feature structure facilitates a richer Chinese semantic information extraction when compared with dependency structure. The results show that using recursive directed graph is more suitable for extracting Chinese complex semantic relations.展开更多
This paper presents modeling tools based on Boolean satisfiability (SAT) to solve problems of test generation for combinational circuits. It exploits an added layer to maintain circuit-related information and value ju...This paper presents modeling tools based on Boolean satisfiability (SAT) to solve problems of test generation for combinational circuits. It exploits an added layer to maintain circuit-related information and value justification relations to a generic SAT algorithm. It dovetails binary decision graphs (BDD) and SAT techniques to improve the efficiency of automatic test pattern generation (ATPG). More specifically, it first exploits inexpensive reconvergent fanout analysis of circuit to gather information on the local signal correlation by using BDD learning, then uses the above learned information to restrict and focus the overall search space of SAT-based ATPG. Its learning technique is effective and lightweight. The experimental results demonstrate the effectiveness of the approach.展开更多
多功能雷达(Multi Function Radar,MFR)通过波形捷变与波束自适应调度实现多任务协同,这给雷达工作模式识别带来了诸多挑战。现有识别方法依赖脉冲序列局部时域特征,难以有效解析不同工作模式的生成机理,面对脉冲丢失、脉内参数相近等...多功能雷达(Multi Function Radar,MFR)通过波形捷变与波束自适应调度实现多任务协同,这给雷达工作模式识别带来了诸多挑战。现有识别方法依赖脉冲序列局部时域特征,难以有效解析不同工作模式的生成机理,面对脉冲丢失、脉内参数相近等复杂情况,识别性能急剧下降。考虑到多功能雷达波束扫描过程对脉冲组序列幅值信息的影响,提出一种基于空时联合图卷积网络的多功能雷达工作模式识别方法。该网络模型首先通过引入动态规整模块量化相邻波位信号的辐射特性相似度,构造具有物理可解释性的空域邻接矩阵;然后将一维脉冲组序列映射为二维图结构,融合脉冲频率、信号幅度等节点特征,形成空时联合表征;最后,设计分层图卷积核,通过多层信息传递机制,提取深层空时特征,完成雷达工作模式识别。对比实验表明,在脉冲丢失等非理想情况下所提方法的平均识别率仍能达到93.38%,具有更好的泛化性和鲁棒性。展开更多
文摘The identification of design pattern instances is important for program understanding and software maintenance. Aiming at the mining of design patterns in existing systems, this paper proposes a subgraph isomorphism approach to discover several design patterns in a legacy system at a time. The attributed relational graph is used to describe design patterns and legacy systems. The sub-graph isomorphism approach consists of decomposition and composition process. During the decomposition process, graphs corresponding to the design patterns are decomposed into sub-graphs, some of which are graphs corresponding to the elemental design patterns. The composition process tries to get sub-graph isomorphism of the matched graph if sub-graph isomorphism of each subgraph is obtained. Due to the common structures between design patterns, the proposed approach can reduce the matching times of entities and relations. Compared with the existing methods, the proposed algorithm is not linearly dependent on the number of design pattern graphs. Key words design pattern mining - attributed relational graph - subgraph isomorphism CLC number TP 311.5 Foundation item: Supported by the National Natural Science Foundation of China (60273075) and the Science Foundation of Naval University of Engineering (HGDJJ03019)Biography: LI Qing-hua (1940-), male, Professor, research direction: parallel computing.
文摘Graph pattern matching(GPM)can be used to mine the key information in graphs.Exact GPM is one of the most commonly used methods among all the GPM-related methods,which aims to exactly find all subgraphs for a given query graph in a data graph.The exact GPM has been widely used in biological data analyses,social network analyses and other fields.In this paper,the applications of the exact GPM were first introduced,and the research progress of the exact GPM was summarized.Then,the related algorithms were introduced in detail,and the experiments on the state-of-the-art exact GPM algorithms were conducted to compare their performance.Based on the experimental results,the applicable scenarios of the algorithms were pointed out.New research opportunities in this area were proposed.
基金Project supported by the National Natural Science Foundation of China (Grant No. 70871082)the Shanghai Leading Academic Discipline Project, China (Grant No. S30504)the Science and Technology Innovation Foundation of Shanxi Agricultural University, China (Grant No. 201208)
文摘Expo 2010 Shanghai China was a successful, splendid, and unforgettable event, leaving us with valuable experi- ences. The visitor flow pattern of the Expo is investigated in this paper. The Hurst exponent, the mean value, and the standard deviation of visitor volume indicate that the visitor flow is fractal with long-term stability and correlation as well as obvious fluctuation in a short period. Then the time series of visitor volume is converted into a complex network by using the visibility algorithm. It can be inferred from the topological properties of the visibility graph that the network is scale-free, small-world, and hierarchically constructed, confirming that the time series are fractal and a close relationship exists among the visitor volumes on different days. Furthermore, it is inevitable that will be some extreme visitor volumes in the original visitor flow, and these extreme points may appear in a group to a great extent. All these properties are closely related to the feature of the complex network. Finally, the revised linear regression is performed to forecast the next-day visitor volume based on the previous 10-day data.
文摘Pattern recognition is a task of searching particular patterns or features in the given input. The data mining, computer networks, genetic engineering, chemical structure analysis, web services etc. are few rapidly growing applications where pattern recognition has been used. Graphs are very powerful model applied in various areas of computer science and engineering. This paper proposes a graph based algorithm for performing the graphical symbol recognition. In the proposed approach, a graph based filtering prior to the matching is performed which significantly reduces the computational complexity. The proposed algorithm is evaluated using a large number of input drawings and the simulation results show that the proposed algorithm outperforms the existing algorithms.
文摘The graph can contain huge amount of data. It is heavily used for pattern recognition and matching tasks like symbol recognition, information retrieval, data mining etc. In all these applications, the objects or underlying data are represented in the form of graph and graph based matching is performed. The conventional algorithms of graph matching have higher complexity. This is because the most of the applications have large number of sub graphs and the matching of these sub graphs becomes computationally expensive. In this paper, we propose a graph based novel algorithm for fingerprint recognition. In our work we perform graph based clustering which reduces the computational complexity heavily. In our algorithm, we exploit structural features of the fingerprint for K-means clustering of the database. The proposed algorithm is evaluated using realtime fingerprint database and the simulation results show that our algorithm outperforms the existing algorithm for the same task.
基金Supported by the National Natural Science Foundation of China(61202193,61202304)the Major Projects of Chinese National Social Science Foundation(11&ZD189)+2 种基金the Chinese Postdoctoral Science Foundation(2013M540593,2014T70722)the Accomplishments of Listed Subjects in Hubei Prime Subject Developmentthe Open Foundation of Shandong Key Lab of Language Resource Development and Application
文摘It is difficult to analyze semantic relations automatically, especially the semantic relations of Chinese special sentence patterns. In this paper, we apply a novel model feature structure to represent Chinese semantic relations, which is formalized as ＂recursive directed graph＂. We focus on Chinese special sentence patterns, including the complex noun phrase, verb-complement structure, pivotal sentences, serial verb sentence and subject-predicate predicate sentence. Feature structure facilitates a richer Chinese semantic information extraction when compared with dependency structure. The results show that using recursive directed graph is more suitable for extracting Chinese complex semantic relations.
基金Supported by Joint Research Fund for Overseas Chinese Young Scholars (No. 50128503) and National Natural Science Foundation of China (No. 50390060)
文摘This paper presents modeling tools based on Boolean satisfiability (SAT) to solve problems of test generation for combinational circuits. It exploits an added layer to maintain circuit-related information and value justification relations to a generic SAT algorithm. It dovetails binary decision graphs (BDD) and SAT techniques to improve the efficiency of automatic test pattern generation (ATPG). More specifically, it first exploits inexpensive reconvergent fanout analysis of circuit to gather information on the local signal correlation by using BDD learning, then uses the above learned information to restrict and focus the overall search space of SAT-based ATPG. Its learning technique is effective and lightweight. The experimental results demonstrate the effectiveness of the approach.
文摘多功能雷达(Multi Function Radar,MFR)通过波形捷变与波束自适应调度实现多任务协同,这给雷达工作模式识别带来了诸多挑战。现有识别方法依赖脉冲序列局部时域特征,难以有效解析不同工作模式的生成机理,面对脉冲丢失、脉内参数相近等复杂情况,识别性能急剧下降。考虑到多功能雷达波束扫描过程对脉冲组序列幅值信息的影响,提出一种基于空时联合图卷积网络的多功能雷达工作模式识别方法。该网络模型首先通过引入动态规整模块量化相邻波位信号的辐射特性相似度,构造具有物理可解释性的空域邻接矩阵;然后将一维脉冲组序列映射为二维图结构,融合脉冲频率、信号幅度等节点特征,形成空时联合表征;最后,设计分层图卷积核,通过多层信息传递机制,提取深层空时特征,完成雷达工作模式识别。对比实验表明,在脉冲丢失等非理想情况下所提方法的平均识别率仍能达到93.38%,具有更好的泛化性和鲁棒性。
