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.展开更多
文摘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.
