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.展开更多
Based on the two path metrics being equal at a merged node in the trellis employed to describe a Viterbi detector for the detection of data encoded with a rate 6:8 balanced binary code in page-oriented optical memorie...Based on the two path metrics being equal at a merged node in the trellis employed to describe a Viterbi detector for the detection of data encoded with a rate 6:8 balanced binary code in page-oriented optical memories, the combined Viterbi detector scheme is proposed to improve raw biterror rate performance by mitigating the occurrence of a twobit reversing error event in an estimated codeword for the balanced code. The effectiveness of the detection scheme is verified for different data quantizations using Monte Carlo simulations. Key words holographic data storage - balanced code - modulation code - Viterbi algorithm - path metric CLC number TN 911. 21 Foundation item: Supported by National 973 Research Program of China (G1999033006)Biography: Chen Duan-rong (1960-), male, Lecturer, Ph. D candidate, research direction: coding and signal processing for the recording channel of holographic data storage.展开更多
Digital broadcasting system has become a high-light of research on computer application. To respond to the changes of the playbill in the broadcasting system in real time, the response time of the system must be studi...Digital broadcasting system has become a high-light of research on computer application. To respond to the changes of the playbill in the broadcasting system in real time, the response time of the system must be studied. There is scarcely the research on this area currently. The influence factors in the response time are analyzed; the model on the response time of the system service is built; how the influence factors affect the response time of the system service is validated; and four improvement measures are proposed to minimize the response time of system service.展开更多
For a data cube there are always constraints between dimensions or among attributes in a dimension, such as functional dependencies. We introduce the problem that when there are functional dependencies, how to use the...For a data cube there are always constraints between dimensions or among attributes in a dimension, such as functional dependencies. We introduce the problem that when there are functional dependencies, how to use them to speed up the computation of sparse data cubes. A new algorithm CFD (Computation by Functional Dependencies) is presented to satisfy this demand. CFD determines the order of dimensions by considering cardinalities of dimensions and functional dependencies between dimensions together, thus reduce the number of partitions for such dimensions. CFD also combines partitioning from bottom to up and aggregate computation from top to bottom to speed up the computation further. CFD can efficiently compute a data cube with hierarchies in a dimension from the smallest granularity to the coarsest one. Key words sparse data cube - functional dependency - dimension - partition - CFD CLC number TP 311 Foundation item: Supported by the E-Government Project of the Ministry of Science and Technology of China (2001BA110B01)Biography: Feng Yu-cai (1945-), male, Professor, research direction: database system.展开更多
We cleveloped a high-speed information retrieval system. The system hased on the IXP 2800 is one of the dedicute device. The velocity of the information retrieval is 6.8 Gb/s. The protocol support Telnet, FTP, SMTP, P...We cleveloped a high-speed information retrieval system. The system hased on the IXP 2800 is one of the dedicute device. The velocity of the information retrieval is 6.8 Gb/s. The protocol support Telnet, FTP, SMTP, POP3 etc. various networks protocols. The information retrieval supports the key word and the natural language process. This paper explains the hardware system, software system and the index of the performance. Key words network processor - IXP2800 - information retrieval - IXA CLC number TP 309 Foundation item: Supported by the National Natural Science Foundation of China (69873016 & 69972017) and the National High Technology Development Program of China (863-301-06-1)Biography: SHI Shu-dong (1963-), male, Ph. D. candidate, research direction: network & information security.展开更多
To meet the authorization administration requirements in a distributedcomputer network environment, this paper extends the role-based access control model with multipleapplication dimensions and establishes a new acce...To meet the authorization administration requirements in a distributedcomputer network environment, this paper extends the role-based access control model with multipleapplication dimensions and establishes a new access control model ED-RBAC(Extended Role Based AccessControl Model) for the distributed environment. We propose an extendable hierarchical authorizationassignment framework and design effective role-registeringi role-applying and role-assigningprotocol with symmetric and asymmetric cryptographic systems. The model can be used to simplifyauthorization administration in a distributed environment with multiple applications.展开更多
We propose a new approach to store and query XML data in an RDBMS basing on the idea of the numbering scheme and inverted list. O ur approach allows us to quickly determine the precedence, sibling and ancestor/ descen...We propose a new approach to store and query XML data in an RDBMS basing on the idea of the numbering scheme and inverted list. O ur approach allows us to quickly determine the precedence, sibling and ancestor/ descendant relationships between any pair of nodes in the hierarchy of XML, and utilize path index to speed up calculating of path expressions. Examples have de monstrated that our approach can effectively and efficiently support both XQuery queries and keyword searches. Our approach is also flexible enough to support X ML documents both with Schema and without Schema, and applications both retrieva l and update. We also present the architecture of middleware for application acc essing XML documents stored in relations, and an algorithm translating a given X ML document into relations effectively.展开更多
In this paper, the job shop scheduling problem concerned with minimizing make\|span is discussed, and a new local search algorithm is proposed for it. This local search method is based on an improved shifting bottlene...In this paper, the job shop scheduling problem concerned with minimizing make\|span is discussed, and a new local search algorithm is proposed for it. This local search method is based on an improved shifting bottleneck procedure and Tabu Search technique. This new local search is different from the previous Tabu Search (TS) proposed by other authors, which is because the improved shifting bottleneck procedure is a new technology that is provided by us for the problem, and two remarkable strategies--intensification and diversification of TS are modified. To demonstrate the performance, our algorithm has been tested on many common problem instances (benchmarks) with various sizes and levels of hardness and compared with other algorithms, especially the latest TS in the literatures. Computational experiments show that this algorithm is effective and efficient.展开更多
Computational gene structure prediction, which is valuable for finding new genes and understanding the composition of genomes, plays a very important role in various kinds of genome projects. For eukaryotic gene struc...Computational gene structure prediction, which is valuable for finding new genes and understanding the composition of genomes, plays a very important role in various kinds of genome projects. For eukaryotic gene structures, however, the prediction accuracy of existing methods is still limited. This paper presents a method of pre-dicting eukaryotic gene structures based on multilevel opti-mization. The complicated problem of predicting gene structure in eukaryotic DNA sequence containing multiple genes can be decomposed into a series of sub-problems at several levels with decreasing complexity, including the gene level (single-exon gene, multi-exon gene), the element level (exon, intron, etc.), and the feature level (functional site sig-nals, codon usage preference, etc.). On the basis of this de-composition, a multilevel model for the prediction of complex gene structures is created by a multilevel optimization proc-ess, in which the models dealing with sub-problems at low complexity level are first optimized respectively, and then optimally combined together to form models for those sub-problems at higher complexity level. Based on the multi-level model, a dynamic programming algorithm is designed to search for optimal gene structures from DNA sequences, and a new program GeneKey (1.0) for the prediction of eu-karyotic gene structures is developed. Testing results with widely used datasets demonstrate that the prediction accura-cies of GeneKey (1.0) at the nucleotide level, exon level and gene level are all higher than that of the well known program GENSCAN. A web server of GeneKey(1.0) is available at http://gffzze1e99242f9d74955hkw6wnnv0vkkv65oq.ffgz.tsg.suse.edu.cn.展开更多
PERM is the most efficient approach for solv- ing protein folding problem based on simple lattice model. In this article a personification explanation of PERM is pro- posed. A new version of PERM, population control a...PERM is the most efficient approach for solv- ing protein folding problem based on simple lattice model. In this article a personification explanation of PERM is pro- posed. A new version of PERM, population control algorithm with two main improvements is presented: one is that it is able to redefine the weight and its predicted value in PERM, and the other is that it is able to unify the calculation of weight when choosing possible branches. The improved PERM is more efficient than the previous version; specifi- cally it can find the known lowest energy states for the four well-known difficult instances and is generally several to hundreds times faster than PERM. It is noteworthy that with the improved PERM we found new lowest energy configura- tions of three of the four difficult problems missed in previ- ous papers.展开更多
Storage and retrieval of multimedia objects has become a requirement for many contemporary systems.For example,given an image database,one may want to retrieve all images that are similar to a query image.Asmany c...Storage and retrieval of multimedia objects has become a requirement for many contemporary systems.For example,given an image database,one may want to retrieve all images that are similar to a query image.Asmany content-based retrieval techniques for digital imagery use a feature vector approach to represent image contents,it is desirable to reduce the dimensionality of the data,whilst maintaining as much of its original structure.Several dimensionality reduction techniques are available.The most popular one is PCA,which works well for static databases.In this paper,we present a novel scheme for performing PCA-based dimensionality reduction in dynamic databases.Instead of using the entire dataset,we only recompute the PCA transform matrix on the updating dataset.Note that the size of the updating dataset is usually much smaller than that of the entire data,this technique may reduce the PCA computation time complexity without losing exactness.In addition,the updates to the database are based on the existing dimensionality-reduced data vectors rather than the original high-dimensional data vectors,which may relieve the system overhead for the management of the original high-dimensional data.展开更多
摘要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.
基金SupportedbyNational973ResearchProgramofChi na (G1 9990 330 0 6)
摘要Based on the two path metrics being equal at a merged node in the trellis employed to describe a Viterbi detector for the detection of data encoded with a rate 6:8 balanced binary code in page-oriented optical memories, the combined Viterbi detector scheme is proposed to improve raw biterror rate performance by mitigating the occurrence of a twobit reversing error event in an estimated codeword for the balanced code. The effectiveness of the detection scheme is verified for different data quantizations using Monte Carlo simulations. Key words holographic data storage - balanced code - modulation code - Viterbi algorithm - path metric CLC number TN 911. 21 Foundation item: Supported by National 973 Research Program of China (G1999033006)Biography: Chen Duan-rong (1960-), male, Lecturer, Ph. D candidate, research direction: coding and signal processing for the recording channel of holographic data storage.
摘要Digital broadcasting system has become a high-light of research on computer application. To respond to the changes of the playbill in the broadcasting system in real time, the response time of the system must be studied. There is scarcely the research on this area currently. The influence factors in the response time are analyzed; the model on the response time of the system service is built; how the influence factors affect the response time of the system service is validated; and four improvement measures are proposed to minimize the response time of system service.
摘要For a data cube there are always constraints between dimensions or among attributes in a dimension, such as functional dependencies. We introduce the problem that when there are functional dependencies, how to use them to speed up the computation of sparse data cubes. A new algorithm CFD (Computation by Functional Dependencies) is presented to satisfy this demand. CFD determines the order of dimensions by considering cardinalities of dimensions and functional dependencies between dimensions together, thus reduce the number of partitions for such dimensions. CFD also combines partitioning from bottom to up and aggregate computation from top to bottom to speed up the computation further. CFD can efficiently compute a data cube with hierarchies in a dimension from the smallest granularity to the coarsest one. Key words sparse data cube - functional dependency - dimension - partition - CFD CLC number TP 311 Foundation item: Supported by the E-Government Project of the Ministry of Science and Technology of China (2001BA110B01)Biography: Feng Yu-cai (1945-), male, Professor, research direction: database system.
摘要We cleveloped a high-speed information retrieval system. The system hased on the IXP 2800 is one of the dedicute device. The velocity of the information retrieval is 6.8 Gb/s. The protocol support Telnet, FTP, SMTP, POP3 etc. various networks protocols. The information retrieval supports the key word and the natural language process. This paper explains the hardware system, software system and the index of the performance. Key words network processor - IXP2800 - information retrieval - IXA CLC number TP 309 Foundation item: Supported by the National Natural Science Foundation of China (69873016 & 69972017) and the National High Technology Development Program of China (863-301-06-1)Biography: SHI Shu-dong (1963-), male, Ph. D. candidate, research direction: network & information security.
摘要To meet the authorization administration requirements in a distributedcomputer network environment, this paper extends the role-based access control model with multipleapplication dimensions and establishes a new access control model ED-RBAC(Extended Role Based AccessControl Model) for the distributed environment. We propose an extendable hierarchical authorizationassignment framework and design effective role-registeringi role-applying and role-assigningprotocol with symmetric and asymmetric cryptographic systems. The model can be used to simplifyauthorization administration in a distributed environment with multiple applications.
摘要We propose a new approach to store and query XML data in an RDBMS basing on the idea of the numbering scheme and inverted list. O ur approach allows us to quickly determine the precedence, sibling and ancestor/ descendant relationships between any pair of nodes in the hierarchy of XML, and utilize path index to speed up calculating of path expressions. Examples have de monstrated that our approach can effectively and efficiently support both XQuery queries and keyword searches. Our approach is also flexible enough to support X ML documents both with Schema and without Schema, and applications both retrieva l and update. We also present the architecture of middleware for application acc essing XML documents stored in relations, and an algorithm translating a given X ML document into relations effectively.
摘要In this paper, the job shop scheduling problem concerned with minimizing make\|span is discussed, and a new local search algorithm is proposed for it. This local search method is based on an improved shifting bottleneck procedure and Tabu Search technique. This new local search is different from the previous Tabu Search (TS) proposed by other authors, which is because the improved shifting bottleneck procedure is a new technology that is provided by us for the problem, and two remarkable strategies--intensification and diversification of TS are modified. To demonstrate the performance, our algorithm has been tested on many common problem instances (benchmarks) with various sizes and levels of hardness and compared with other algorithms, especially the latest TS in the literatures. Computational experiments show that this algorithm is effective and efficient.
摘要Computational gene structure prediction, which is valuable for finding new genes and understanding the composition of genomes, plays a very important role in various kinds of genome projects. For eukaryotic gene structures, however, the prediction accuracy of existing methods is still limited. This paper presents a method of pre-dicting eukaryotic gene structures based on multilevel opti-mization. The complicated problem of predicting gene structure in eukaryotic DNA sequence containing multiple genes can be decomposed into a series of sub-problems at several levels with decreasing complexity, including the gene level (single-exon gene, multi-exon gene), the element level (exon, intron, etc.), and the feature level (functional site sig-nals, codon usage preference, etc.). On the basis of this de-composition, a multilevel model for the prediction of complex gene structures is created by a multilevel optimization proc-ess, in which the models dealing with sub-problems at low complexity level are first optimized respectively, and then optimally combined together to form models for those sub-problems at higher complexity level. Based on the multi-level model, a dynamic programming algorithm is designed to search for optimal gene structures from DNA sequences, and a new program GeneKey (1.0) for the prediction of eu-karyotic gene structures is developed. Testing results with widely used datasets demonstrate that the prediction accura-cies of GeneKey (1.0) at the nucleotide level, exon level and gene level are all higher than that of the well known program GENSCAN. A web server of GeneKey(1.0) is available at http://gffzze1e99242f9d74955hkw6wnnv0vkkv65oq.ffgz.tsg.suse.edu.cn.
摘要PERM is the most efficient approach for solv- ing protein folding problem based on simple lattice model. In this article a personification explanation of PERM is pro- posed. A new version of PERM, population control algorithm with two main improvements is presented: one is that it is able to redefine the weight and its predicted value in PERM, and the other is that it is able to unify the calculation of weight when choosing possible branches. The improved PERM is more efficient than the previous version; specifi- cally it can find the known lowest energy states for the four well-known difficult instances and is generally several to hundreds times faster than PERM. It is noteworthy that with the improved PERM we found new lowest energy configura- tions of three of the four difficult problems missed in previ- ous papers.
摘要Storage and retrieval of multimedia objects has become a requirement for many contemporary systems.For example,given an image database,one may want to retrieve all images that are similar to a query image.Asmany content-based retrieval techniques for digital imagery use a feature vector approach to represent image contents,it is desirable to reduce the dimensionality of the data,whilst maintaining as much of its original structure.Several dimensionality reduction techniques are available.The most popular one is PCA,which works well for static databases.In this paper,we present a novel scheme for performing PCA-based dimensionality reduction in dynamic databases.Instead of using the entire dataset,we only recompute the PCA transform matrix on the updating dataset.Note that the size of the updating dataset is usually much smaller than that of the entire data,this technique may reduce the PCA computation time complexity without losing exactness.In addition,the updates to the database are based on the existing dimensionality-reduced data vectors rather than the original high-dimensional data vectors,which may relieve the system overhead for the management of the original high-dimensional data.