2010 Vol. 47 No. 7
2010, 47(7): 1145-1155.
Abstract：
Source-to-source translation is an important way to make analysis and optimization in a compiler retargetable. It is widely used to support various parallel programming language extensions and platform independent optimizations, and it can help programmers to validate the program correctness and to tune the performance. In the multi-core and many-core times, users are more eagerly demanded to get involved in program analysis and optimization. Source-to-source code generation, which is platform independent and user friendly, is increasingly welcomed. Source-to-source is easy to implement in a simple compiler, but difficult to implement in a compiler with complex program analysis and aggressive optimizations. Therefore few production quality compilers provided robust source-to-source translation. It is found that transformation produced by optimization is the leading cause of the difficulty. The problems are analyzed in the source-to-source translation based on a lot of error cases, and a translation technique with type restoration is provided to solve the problem. Then the authors implement the technique in the Open64 compiler, evaluate it via supertest and spec2000 benchmarks and prove that it greatly improves the robustness of the source-to-source translation. The method in the paper is integrated in the source-to-source translator module and separated from various optimizations, so it is easy to be used in other compilers.
Source-to-source translation is an important way to make analysis and optimization in a compiler retargetable. It is widely used to support various parallel programming language extensions and platform independent optimizations, and it can help programmers to validate the program correctness and to tune the performance. In the multi-core and many-core times, users are more eagerly demanded to get involved in program analysis and optimization. Source-to-source code generation, which is platform independent and user friendly, is increasingly welcomed. Source-to-source is easy to implement in a simple compiler, but difficult to implement in a compiler with complex program analysis and aggressive optimizations. Therefore few production quality compilers provided robust source-to-source translation. It is found that transformation produced by optimization is the leading cause of the difficulty. The problems are analyzed in the source-to-source translation based on a lot of error cases, and a translation technique with type restoration is provided to solve the problem. Then the authors implement the technique in the Open64 compiler, evaluate it via supertest and spec2000 benchmarks and prove that it greatly improves the robustness of the source-to-source translation. The method in the paper is integrated in the source-to-source translator module and separated from various optimizations, so it is easy to be used in other compilers.
2010, 47(7): 1156-1164.
Abstract：
The approach based on model-driven software architecture is one of the most important approaches for software adaptation. Especially in the analysis and planning stages, many model-based methods and tools are used to support designers in decision making. But most of these approaches and their supporting tools are provided only for specific architectural description languages or modeling tools. It is hard to reuse or integrate them with other approaches. On the other hand, recent research in the field of model driven architecture (MDA) provides standards to enhance the interoperability of the methods and tools. These standards include MOF for meta modeling, QVT for model query, view and transformation, and so on. For these concerns, the authors summarize the models and model operations needed in the analysis and planning stages to see how to apply standard model technologies to support these stages. They then extend the ABC-ADL, and use the standard model technologies including model transformation and model query in its implementation to support analysis and planning. The adaptation of an anti-pattern in ECPerf system is used as a case study to show the usability of our ADL. In addition, two analysis approaches used in the case study show how to use their ADL to reuse and integrate other approaches.
The approach based on model-driven software architecture is one of the most important approaches for software adaptation. Especially in the analysis and planning stages, many model-based methods and tools are used to support designers in decision making. But most of these approaches and their supporting tools are provided only for specific architectural description languages or modeling tools. It is hard to reuse or integrate them with other approaches. On the other hand, recent research in the field of model driven architecture (MDA) provides standards to enhance the interoperability of the methods and tools. These standards include MOF for meta modeling, QVT for model query, view and transformation, and so on. For these concerns, the authors summarize the models and model operations needed in the analysis and planning stages to see how to apply standard model technologies to support these stages. They then extend the ABC-ADL, and use the standard model technologies including model transformation and model query in its implementation to support analysis and planning. The adaptation of an anti-pattern in ECPerf system is used as a case study to show the usability of our ADL. In addition, two analysis approaches used in the case study show how to use their ADL to reuse and integrate other approaches.
2010, 47(7): 1165-1174.
Abstract：
With the increasing size and complexity of software systems, the focus of software development has been shifting from algorithms and data structures to software architectures. Graphical and integrated software architecture development environments are becoming more and more important for the research and practice of software architectures-centric system development. Proposed in this paper is a generative framework for graph grammar-based visual development environment. Given a description of a certain software architecture style in graph grammar, the framework can automatically generate a corresponding graph grammar-directed environment. Compared with existing work of meta-model-based tools, this graph grammar-directed approach is more intuitive as it uses graphic notations, while it is still equipped with a rich set of formal semantics and reasoning theories. It encodes more style-specific semantics and dynamic evolution of software architectures is also depicted with graph transformations. It makes better use of the implicit semantics of software architecture style, and hence makes the generated environment easier to use and more reliable. A prototype system Artemis-GADE has been designed and implemented. Besides graph grammar-directed visual editing of software architecture specifications, Artemis-GADE provides feasible supports for the activities in the whole lifecycle of software architecture-centric system construction and evolution, including online system adaption based on dynamic architecture reconfigurations.
With the increasing size and complexity of software systems, the focus of software development has been shifting from algorithms and data structures to software architectures. Graphical and integrated software architecture development environments are becoming more and more important for the research and practice of software architectures-centric system development. Proposed in this paper is a generative framework for graph grammar-based visual development environment. Given a description of a certain software architecture style in graph grammar, the framework can automatically generate a corresponding graph grammar-directed environment. Compared with existing work of meta-model-based tools, this graph grammar-directed approach is more intuitive as it uses graphic notations, while it is still equipped with a rich set of formal semantics and reasoning theories. It encodes more style-specific semantics and dynamic evolution of software architectures is also depicted with graph transformations. It makes better use of the implicit semantics of software architecture style, and hence makes the generated environment easier to use and more reliable. A prototype system Artemis-GADE has been designed and implemented. Besides graph grammar-directed visual editing of software architecture specifications, Artemis-GADE provides feasible supports for the activities in the whole lifecycle of software architecture-centric system construction and evolution, including online system adaption based on dynamic architecture reconfigurations.
2010, 47(7): 1175-1183.
Abstract：
The degree to which internal states and behavior of software systems conform to their requirement is a key issue to evaluate whether a software system can provide services of high quality consistently. Software monitoring is an effective approach to help ensure such integrity of large-scale software systems. But it is usually time-consuming and error-prone to code and deploy the monitors manually. Proposed in this paper is an approach which utilizes model-based software monitoring techniques to ensure the high quality of software. The basic idea is to capture concerned events from runtime software and discover errors that occur during its execution, in order to rapidly adjust the system and guarantee the quality of software services. In this paper a monitoring model is proposed to present the monitoring requirements. By adopting the monitoring model, this approach facilitates the process of equipping a software system with monitoring capability. Based on the included constraint descriptions and a series of transformation rules, the monitoring model is transformed into corresponding bunch of monitoring code semi-automatically or automatically. In addition, these codes will be deployed to the monitored system in an appropriate mechanism, either in the way of bytecode instrumentation or by adding interceptors. Experimental results show that both the performance of these two methods is affordable.
The degree to which internal states and behavior of software systems conform to their requirement is a key issue to evaluate whether a software system can provide services of high quality consistently. Software monitoring is an effective approach to help ensure such integrity of large-scale software systems. But it is usually time-consuming and error-prone to code and deploy the monitors manually. Proposed in this paper is an approach which utilizes model-based software monitoring techniques to ensure the high quality of software. The basic idea is to capture concerned events from runtime software and discover errors that occur during its execution, in order to rapidly adjust the system and guarantee the quality of software services. In this paper a monitoring model is proposed to present the monitoring requirements. By adopting the monitoring model, this approach facilitates the process of equipping a software system with monitoring capability. Based on the included constraint descriptions and a series of transformation rules, the monitoring model is transformed into corresponding bunch of monitoring code semi-automatically or automatically. In addition, these codes will be deployed to the monitored system in an appropriate mechanism, either in the way of bytecode instrumentation or by adding interceptors. Experimental results show that both the performance of these two methods is affordable.
2010, 47(7): 1184-1191.
Abstract：
Traditional workflow technology can't meet the requirements of real-time system because of the particularity of business with temporal factor. Thence the real-time workflow is defined for real-time system in this paper, and the metamodel of real-time workflow is established, expending the metamodel of traditional workflow to support the time constraint and exception in real-time workflow. The extended attributes include the start time and duration in activity model, the duration in workflow process, the concurrent constraint in concurrent activities etc. Besides, the timeout exception of execution of activities is considered, and the relationships between the application programs and activities executed by them are established in the metamodel. Based on the metamodel, a UML based real-time workflow description language is defined by using profile mechanism, which is extended from UML2.0. The modeling principles are discussed to describe a real-time workflow by using this language firstly; and then the UML based extension technology and the profiles of the language are introduced; finally, a specific example of shipborne combat system is given to explain the modeling approach. This work provides a language which is easy to learn, use and understand for workflow designers, and basis for the execution and time analysis of real-time workflow.
Traditional workflow technology can't meet the requirements of real-time system because of the particularity of business with temporal factor. Thence the real-time workflow is defined for real-time system in this paper, and the metamodel of real-time workflow is established, expending the metamodel of traditional workflow to support the time constraint and exception in real-time workflow. The extended attributes include the start time and duration in activity model, the duration in workflow process, the concurrent constraint in concurrent activities etc. Besides, the timeout exception of execution of activities is considered, and the relationships between the application programs and activities executed by them are established in the metamodel. Based on the metamodel, a UML based real-time workflow description language is defined by using profile mechanism, which is extended from UML2.0. The modeling principles are discussed to describe a real-time workflow by using this language firstly; and then the UML based extension technology and the profiles of the language are introduced; finally, a specific example of shipborne combat system is given to explain the modeling approach. This work provides a language which is easy to learn, use and understand for workflow designers, and basis for the execution and time analysis of real-time workflow.
2010, 47(7): 1192-1200.
Abstract：
Methods of pure performance testing or single analytical modeling, such as queueing network model, etc, have their limitation on the accuracy of performance indexes measurement, the validity of performance forecasting, and the controlling of testing iteration due to the complexity of Web systems. A Web performance modeling framework supporting mixed performance modeling is proposed. It uses different performance modeling methods for different kinds of performance indexes to derive closed form functions and their hypothesis of measurement. The regression analysis and testing are used on the training data to estimate the parameters of the closed form functions. To demonstrate the feasibility and validity of this framework, a real-world Web community system (igroot.com) is studied under the framework. For the indexes of system response time and scalability, a mixed modeling method is proposed by combining queueing network reduction and extended universal scalability model US-γ. Compared with other practical system performance testing methods, such as universal scalability model US, the model accuracy of performance forecasting is greatly improved and the cost of software and hardware used in the process is greatly reduced. The error rate of estimated response time is within 4 percent, the error rate of estimated throughout saturation point is within 1 percent, and the error rate of estimated infimum of buckle point is within 5 percent. Correlating the scalability model and threads data of the Web server, an HTTP processing bottleneck at the architecture level is identified.
Methods of pure performance testing or single analytical modeling, such as queueing network model, etc, have their limitation on the accuracy of performance indexes measurement, the validity of performance forecasting, and the controlling of testing iteration due to the complexity of Web systems. A Web performance modeling framework supporting mixed performance modeling is proposed. It uses different performance modeling methods for different kinds of performance indexes to derive closed form functions and their hypothesis of measurement. The regression analysis and testing are used on the training data to estimate the parameters of the closed form functions. To demonstrate the feasibility and validity of this framework, a real-world Web community system (igroot.com) is studied under the framework. For the indexes of system response time and scalability, a mixed modeling method is proposed by combining queueing network reduction and extended universal scalability model US-γ. Compared with other practical system performance testing methods, such as universal scalability model US, the model accuracy of performance forecasting is greatly improved and the cost of software and hardware used in the process is greatly reduced. The error rate of estimated response time is within 4 percent, the error rate of estimated throughout saturation point is within 1 percent, and the error rate of estimated infimum of buckle point is within 5 percent. Correlating the scalability model and threads data of the Web server, an HTTP processing bottleneck at the architecture level is identified.
2010, 47(7): 1201-1210.
Abstract：
In real-time embedded systems, due to race conditions, synchronization order of operations to the shared variables or shared resource during the multiple tasks may be different from one execution to another. This may cause abnormal behaviors of systems. In order to detect the possible race conditions and analyze the impacts of race conditions effectively in real-time embedded systems, a formal model of execution sequences and operation events are presented according to the timing behaviors and execution characteristics of real-time embedded systems. Their characteristics are also discussed. Based on the execution sequence model, race conditions including message races and semaphore races in real-time embedded systems are described formally and precisely. And then, a new race set is presented to describe and store race conditions in systems. It includes the information of happened-before relations and race synchronization relations among the operation events which have races. With the race set generated, a race condition graph is constructed to visualize the race conditions. It is also used to predict the potential race synchronization relations of systems. The case study shows that the approach proposed can be used to analyze and predict efficiently the potential race synchronization relations as well as the different execution situations and results of real-time embedded systems.
In real-time embedded systems, due to race conditions, synchronization order of operations to the shared variables or shared resource during the multiple tasks may be different from one execution to another. This may cause abnormal behaviors of systems. In order to detect the possible race conditions and analyze the impacts of race conditions effectively in real-time embedded systems, a formal model of execution sequences and operation events are presented according to the timing behaviors and execution characteristics of real-time embedded systems. Their characteristics are also discussed. Based on the execution sequence model, race conditions including message races and semaphore races in real-time embedded systems are described formally and precisely. And then, a new race set is presented to describe and store race conditions in systems. It includes the information of happened-before relations and race synchronization relations among the operation events which have races. With the race set generated, a race condition graph is constructed to visualize the race conditions. It is also used to predict the potential race synchronization relations of systems. The case study shows that the approach proposed can be used to analyze and predict efficiently the potential race synchronization relations as well as the different execution situations and results of real-time embedded systems.
2010, 47(7): 1211-1218.
Abstract：
SIP-based VoIP systems use C/S architecture, which brings two intrinsic issues when the user number grows to a large scale, namely single point of failure and performance bottleneck problems. The systems based on P2P-SIP are scalable and fault-tolerant. However, existing systems cannot meet the administrable and maintainable requirements from the service providers. The authors propose an administrable and manageable VoIP system based on P2P-SIP, called AMAP. In an AMAP system, a number of servers, deployed by service providers, form a DHT-based service overlay network, which provides services for the user agents, such as registration, session initialization, etc. The AMAP system leverages extended SIP messages for the overlay maintenance and, thus, is compatible with traditional SIP-based VoIP systems. To further improve the fault tolerance and relieve the hot spot problem, the AMAP system replicates and caches the user information on the service overlay. A distributed meta-data aggregation and dissemination algorithm is proposed to support the management. This algorithm leverages the tree structures which are implicitly defined on the service overlay based on DHT nodes' finger table. The analysis results show that, compared with existing VoIP systems based on P2P-SIP, the AMAP system reduces the maintenance overhead by 80%. A prototype has been implemented and some functional tests have been performed.
SIP-based VoIP systems use C/S architecture, which brings two intrinsic issues when the user number grows to a large scale, namely single point of failure and performance bottleneck problems. The systems based on P2P-SIP are scalable and fault-tolerant. However, existing systems cannot meet the administrable and maintainable requirements from the service providers. The authors propose an administrable and manageable VoIP system based on P2P-SIP, called AMAP. In an AMAP system, a number of servers, deployed by service providers, form a DHT-based service overlay network, which provides services for the user agents, such as registration, session initialization, etc. The AMAP system leverages extended SIP messages for the overlay maintenance and, thus, is compatible with traditional SIP-based VoIP systems. To further improve the fault tolerance and relieve the hot spot problem, the AMAP system replicates and caches the user information on the service overlay. A distributed meta-data aggregation and dissemination algorithm is proposed to support the management. This algorithm leverages the tree structures which are implicitly defined on the service overlay based on DHT nodes' finger table. The analysis results show that, compared with existing VoIP systems based on P2P-SIP, the AMAP system reduces the maintenance overhead by 80%. A prototype has been implemented and some functional tests have been performed.
2010, 47(7): 1219-1224.
Abstract：
In P2P streaming systems, content servers which supply the source data and drive the data to spread in the whole system, are important components. The deployment of the servers obviously affects the network traffic which is related with the benefits of both P2P application providers and Internet service providers. But little research work focuses on the server deployment areas. The authors discuss the problem on server deployment from three optimization directions: load balance, minimum traffic in core network and minimum allocation costs. The adaptive algorithms, including load-balance-based greedy algorithms and the 0-1 linear-programming-based branch and bound algorithm, are presented. Some experiments are conducted to prove the effects of server deployments on the system, and it can be seen that different optimizations can achieve the different objectives.
In P2P streaming systems, content servers which supply the source data and drive the data to spread in the whole system, are important components. The deployment of the servers obviously affects the network traffic which is related with the benefits of both P2P application providers and Internet service providers. But little research work focuses on the server deployment areas. The authors discuss the problem on server deployment from three optimization directions: load balance, minimum traffic in core network and minimum allocation costs. The adaptive algorithms, including load-balance-based greedy algorithms and the 0-1 linear-programming-based branch and bound algorithm, are presented. Some experiments are conducted to prove the effects of server deployments on the system, and it can be seen that different optimizations can achieve the different objectives.
2010, 47(7): 1225-1233.
Abstract：
It is important in large networks to use routes that are as short as possible while keeping routing tables small. Generic shortest-path routing does extremely well in optimizing routes, but each node has to maintain state for all nodes. Thus generic shortest-path routing does not scale well as routing table size grows linearly with network size. The authors study scalable routing via graph embedding, i.e. embedding networks into specific coordinate spaces such that packets can be delivered with greedy forwarding. However, generic embedding usually can not guarantee packet delivery. To obtain guaranteed delivery and high routing efficiency, the idea of embedding graph spanners is presented in this paper. Based on the fact that most real-world networks have small-world and scale-free topologies, a embedding & routing scheme is proposed, namely GEROUTE, which uses the shortest-path trees rooted at high-degree nodes as spanners, and assigns to each node a set of short labels such that the distance between any two nodes in the spanners can be inferred from their labels. Over the metric space defined by labels, each node only stores the labels of its neighbors and always picks the neighbor closest to the destination as next hop when routing packets. Analysis and simulations show that the scheme can perform particularly well on Internet-like graphs, outperforming prior related routing schemes.
It is important in large networks to use routes that are as short as possible while keeping routing tables small. Generic shortest-path routing does extremely well in optimizing routes, but each node has to maintain state for all nodes. Thus generic shortest-path routing does not scale well as routing table size grows linearly with network size. The authors study scalable routing via graph embedding, i.e. embedding networks into specific coordinate spaces such that packets can be delivered with greedy forwarding. However, generic embedding usually can not guarantee packet delivery. To obtain guaranteed delivery and high routing efficiency, the idea of embedding graph spanners is presented in this paper. Based on the fact that most real-world networks have small-world and scale-free topologies, a embedding & routing scheme is proposed, namely GEROUTE, which uses the shortest-path trees rooted at high-degree nodes as spanners, and assigns to each node a set of short labels such that the distance between any two nodes in the spanners can be inferred from their labels. Over the metric space defined by labels, each node only stores the labels of its neighbors and always picks the neighbor closest to the destination as next hop when routing packets. Analysis and simulations show that the scheme can perform particularly well on Internet-like graphs, outperforming prior related routing schemes.
2010, 47(7): 1234-1343.
Abstract：
KNN-Join is an important database primitive, which has been successfully applied to speed up applications such as similarity search, data analysis and data mining.Up to now, the KNN-Join has been studied in the context of disk-based systems where it is assumed that the databases are too large to fit into the main memory.This assumption is increasingly being challenged as RAM gets cheaper and larger.Therefore, it is necessary to study the problem of KNN-Join in the main memory. Δ-tree is a novel multi-level index structure that can speed up the high-dimensional query in the main memory environment. In this paper, a new KNN-Join approach is proposed, which uses Δ-tree as the underlying index structure, exploits coding and decoding, bottom up, depth first search and pruning technique.The problem that it is hard to identify the distance from each point in R to its K nearest neighbors in S is solved and the Join efficiency is improved.The correctness verification and cost analysis of the above mentioned algorithm are presented.Extensive experiments on both real datasets and synthetic clustered datasets are conducted, and the results illustrate that Δ-tree-KNN-Join is an efficient KNN-Join method in main memory.
KNN-Join is an important database primitive, which has been successfully applied to speed up applications such as similarity search, data analysis and data mining.Up to now, the KNN-Join has been studied in the context of disk-based systems where it is assumed that the databases are too large to fit into the main memory.This assumption is increasingly being challenged as RAM gets cheaper and larger.Therefore, it is necessary to study the problem of KNN-Join in the main memory. Δ-tree is a novel multi-level index structure that can speed up the high-dimensional query in the main memory environment. In this paper, a new KNN-Join approach is proposed, which uses Δ-tree as the underlying index structure, exploits coding and decoding, bottom up, depth first search and pruning technique.The problem that it is hard to identify the distance from each point in R to its K nearest neighbors in S is solved and the Join efficiency is improved.The correctness verification and cost analysis of the above mentioned algorithm are presented.Extensive experiments on both real datasets and synthetic clustered datasets are conducted, and the results illustrate that Δ-tree-KNN-Join is an efficient KNN-Join method in main memory.
2010, 47(7): 1244-1251.
Abstract：
Group nearest neighbor query is more complex than the traditional nearest neighbor query because it contains one more query points. Its objective is to find a data point that has the smallest sum of distances to all query points. The conditions that group nearest neighbor should be satisfied and the theories that valuate the group nearest neighbor are put forward, which are obtained by considering the distribution characteristics of query points and the qualities of geometric figures that they form. The VGNN algorithm is presented to deal with group nearest neighbor query based on Voronoi diagrams. It can get the query points' nearest neighbor exactly by using the VGNN algorithm. When the query points are non-collinear, the query way of the VGNN algorithm is firstly to estimate one data point that is the query points' nearest neighbor possible, and then to outspread around the data point to find the final result. And it also concludes the search region when the query points are collinear to limit the quantity of data points which are included in the computation. The VTree index grounded on Voronoi diagrams is brought forward. Experimental results show that the VGNN algorithm based on the VTree index has better performance, and it is more stable when the query points are non-collinear.
Group nearest neighbor query is more complex than the traditional nearest neighbor query because it contains one more query points. Its objective is to find a data point that has the smallest sum of distances to all query points. The conditions that group nearest neighbor should be satisfied and the theories that valuate the group nearest neighbor are put forward, which are obtained by considering the distribution characteristics of query points and the qualities of geometric figures that they form. The VGNN algorithm is presented to deal with group nearest neighbor query based on Voronoi diagrams. It can get the query points' nearest neighbor exactly by using the VGNN algorithm. When the query points are non-collinear, the query way of the VGNN algorithm is firstly to estimate one data point that is the query points' nearest neighbor possible, and then to outspread around the data point to find the final result. And it also concludes the search region when the query points are collinear to limit the quantity of data points which are included in the computation. The VTree index grounded on Voronoi diagrams is brought forward. Experimental results show that the VGNN algorithm based on the VTree index has better performance, and it is more stable when the query points are non-collinear.
2010, 47(7): 1252-1260.
Abstract：
With the development of space technology, people pay more and more attention to the use of space data. Space data cannot be accessed without any restriction. So the access control models of space data are becoming more and more important. This is also a hot spot in current research in the world. Presented in this paper is an STS-RBAC model, which is an improvement of traditional RBAC model. STS-RBAC model is based on the spatial database operations and it includes the attributes of space, time and scale. It can also be used in vector data and raster data. This model can manage the problems of multi-scale spatial objects as well. Scale, as is all known, is a basic element in the security of spatial data such as time and space. STS-RBAC model focuses on the special character of spatial data, and introduces role hierarchies based on the constraints of position and time, which guarantees the reliability in spatial database access. STS-RBAC model also defines the transmissibility and partial order in permissions, which makes it possible that authorizations can be inferred from others. This decreases the time and space when spatial database is accessed. With the help of STS-RBAC model, it is possible to access spatial data more efficiently and securely.
With the development of space technology, people pay more and more attention to the use of space data. Space data cannot be accessed without any restriction. So the access control models of space data are becoming more and more important. This is also a hot spot in current research in the world. Presented in this paper is an STS-RBAC model, which is an improvement of traditional RBAC model. STS-RBAC model is based on the spatial database operations and it includes the attributes of space, time and scale. It can also be used in vector data and raster data. This model can manage the problems of multi-scale spatial objects as well. Scale, as is all known, is a basic element in the security of spatial data such as time and space. STS-RBAC model focuses on the special character of spatial data, and introduces role hierarchies based on the constraints of position and time, which guarantees the reliability in spatial database access. STS-RBAC model also defines the transmissibility and partial order in permissions, which makes it possible that authorizations can be inferred from others. This decreases the time and space when spatial database is accessed. With the help of STS-RBAC model, it is possible to access spatial data more efficiently and securely.
2010, 47(7): 1261-1267.
Abstract：
Feature selection, also called attribute selection, is the process of selecting a subset of features from a relatively large dataset. Feature selection is efficient in removing redundant and noisy features and the selected features are effective to describe the whole dataset. Since there are many features in intrusion detection data, which is large in quantity, feature selection plays an important role in intrusion detection. Within these features, many are numerical features. The traditional feature selection methods, such as the correlation analysis, information gain (IG), support vector machine (SVM) and rough set, must discretize numerical features when dealing with mixed features. The discretization process usually consumes much time and sometimes will even result in the loss of important information, decreasing the classification accuracy. Aiming at solving these problems, the neighborhood rough set reduction model is employed in this paper, which can process the numerical features directly without discretization. Then the particle fitness function in particle swarm optimization (PSO) algorithm is built based on that model. Finally, a novel feature selection algorithm based on particle swarm optimization and neighborhood rough set reduction model is proposed. Experimental results prove that the new algorithm improves classification ability with fewer features selected.
Feature selection, also called attribute selection, is the process of selecting a subset of features from a relatively large dataset. Feature selection is efficient in removing redundant and noisy features and the selected features are effective to describe the whole dataset. Since there are many features in intrusion detection data, which is large in quantity, feature selection plays an important role in intrusion detection. Within these features, many are numerical features. The traditional feature selection methods, such as the correlation analysis, information gain (IG), support vector machine (SVM) and rough set, must discretize numerical features when dealing with mixed features. The discretization process usually consumes much time and sometimes will even result in the loss of important information, decreasing the classification accuracy. Aiming at solving these problems, the neighborhood rough set reduction model is employed in this paper, which can process the numerical features directly without discretization. Then the particle fitness function in particle swarm optimization (PSO) algorithm is built based on that model. Finally, a novel feature selection algorithm based on particle swarm optimization and neighborhood rough set reduction model is proposed. Experimental results prove that the new algorithm improves classification ability with fewer features selected.
2010, 47(7): 1268-1275.
Abstract：
Spatial concepts conversion in text-to-scene conversion systems (TTS) is one of the basic tasks. Spatial concepts conversion is to transfer the object locations specified with natural language into the objects display in the virtual scene. In the present, there are some methods including image schemes, expert knowledge base and graphic annotation to resolve the spatial concepts conversion in TTS. The problems of these methods are human labor consumed and skilled art training needed. In this paper, an architecture of spatial ontology for domain of text-to-scene conversion is provided, which makes up the gap between natural language system and graphic system from spatial concept point of view and improves the acceptability of the output scene. The architecture of domain spatial ontology is designed on the domain spatial ontology modol in the framework of SUMO top level. The architecture has two levels, one is the top derived from SUMO top level and has 8 nodes, and the other is the low defined on the features of TTS domain and composed of subclasses of nodes of SelfConnectedObject, Relation and Attribute from the top level. The spatial ontology is tested in the experiment of objects displayed on Chinese text in the text-to-scene system and a good result is gotton.
Spatial concepts conversion in text-to-scene conversion systems (TTS) is one of the basic tasks. Spatial concepts conversion is to transfer the object locations specified with natural language into the objects display in the virtual scene. In the present, there are some methods including image schemes, expert knowledge base and graphic annotation to resolve the spatial concepts conversion in TTS. The problems of these methods are human labor consumed and skilled art training needed. In this paper, an architecture of spatial ontology for domain of text-to-scene conversion is provided, which makes up the gap between natural language system and graphic system from spatial concept point of view and improves the acceptability of the output scene. The architecture of domain spatial ontology is designed on the domain spatial ontology modol in the framework of SUMO top level. The architecture has two levels, one is the top derived from SUMO top level and has 8 nodes, and the other is the low defined on the features of TTS domain and composed of subclasses of nodes of SelfConnectedObject, Relation and Attribute from the top level. The spatial ontology is tested in the experiment of objects displayed on Chinese text in the text-to-scene system and a good result is gotton.
2010, 47(7): 1276-1285.
Abstract：
Reuse of design knowledge has become an urgent problem for computer-aided fixture design (CAFD). Ontology is widely used to describe the concept model of information systems at the semantic knowledge level and makes the model reusable. Therefore an ontology based representation approach on fixture design is proposed. Following the structural method of CommonKADS methodology, the fixture design knowledge ontology is established, and represented by the ontology modeling language OWL. The ontology is corresponding to the domain knowledge model of CommonKADS and comprises a detailed specification of the types and relations of the data involved in fixture design process. Assisted by the Protégé system, the basic concepts such as fixturing feature, fixture component, relation and constraint, are defined, amongst which the layered conceptual structure are constructed. Based on the ontology, the concept of rule-type is defined and the rules of CAFD are expressed in semantic Web rule language (SWRL), which improves the interoperability between the rules and the ontology. The facts and rules are captured into the knowledge base with explicit semantic, based on which a prototype system is implemented to infer fixture configuration. Finally examples are presented to demonstrate the application of the ontology. The results show that the ontology is easy for extension and sharing, and it can support logic inference effectively.
Reuse of design knowledge has become an urgent problem for computer-aided fixture design (CAFD). Ontology is widely used to describe the concept model of information systems at the semantic knowledge level and makes the model reusable. Therefore an ontology based representation approach on fixture design is proposed. Following the structural method of CommonKADS methodology, the fixture design knowledge ontology is established, and represented by the ontology modeling language OWL. The ontology is corresponding to the domain knowledge model of CommonKADS and comprises a detailed specification of the types and relations of the data involved in fixture design process. Assisted by the Protégé system, the basic concepts such as fixturing feature, fixture component, relation and constraint, are defined, amongst which the layered conceptual structure are constructed. Based on the ontology, the concept of rule-type is defined and the rules of CAFD are expressed in semantic Web rule language (SWRL), which improves the interoperability between the rules and the ontology. The facts and rules are captured into the knowledge base with explicit semantic, based on which a prototype system is implemented to infer fixture configuration. Finally examples are presented to demonstrate the application of the ontology. The results show that the ontology is easy for extension and sharing, and it can support logic inference effectively.
Abstract：
A new interesting algorithm, iso-neighborhood projection (ISONP), is proposed for finding succinct representations in a supervised manner. Motivated by the fact that each class has its unique property and is independent from other classes, the recognition problem is cast as finding highly symmetric iso-neighborhood for all classes respectively, which is highly different from the traditional linear methods such as principal component analysis (PCA), linear discriminant analysis (LDA), and locality preserving projection (LPP). The traditional linear methods, like PCA, LDA and LPP, find a certain optimal projection and then map the training data into a lower space in a batch. Given labeled input data, ISONP discovers basis functions which can map each data into its corresponding neighborhood while keeping the intrinsic structure of each class at the same time. The basis functions span the lower subspace, and can be computed by a convex optimization problem: an L\-2-constrained least square problem. When recognizing a test sample, the authors map the new data into the spanned lower subspace and just compare the distance to the center of iso-neighborhoods instead of all training samples, which can enhance the recognizing speed. Experiments are conducted on several data sets and the results demonstrate the competence of the proposed algorithm.
A new interesting algorithm, iso-neighborhood projection (ISONP), is proposed for finding succinct representations in a supervised manner. Motivated by the fact that each class has its unique property and is independent from other classes, the recognition problem is cast as finding highly symmetric iso-neighborhood for all classes respectively, which is highly different from the traditional linear methods such as principal component analysis (PCA), linear discriminant analysis (LDA), and locality preserving projection (LPP). The traditional linear methods, like PCA, LDA and LPP, find a certain optimal projection and then map the training data into a lower space in a batch. Given labeled input data, ISONP discovers basis functions which can map each data into its corresponding neighborhood while keeping the intrinsic structure of each class at the same time. The basis functions span the lower subspace, and can be computed by a convex optimization problem: an L\-2-constrained least square problem. When recognizing a test sample, the authors map the new data into the spanned lower subspace and just compare the distance to the center of iso-neighborhoods instead of all training samples, which can enhance the recognizing speed. Experiments are conducted on several data sets and the results demonstrate the competence of the proposed algorithm.
2010, 47(7): 1294-1303.
Abstract：
Medical image segmentation plays a very important role in medical image processing, particularly in the clinical analysis of magnetic resonance (MR) brain images. Intensity inhomogeneity in MR images, which can change the local statistical characteristics of the images, becomes a major obstacle to any automatic method for MR images. In order to reduce the influences of intensity inhomogeneity during segmentation, a secondary segmentation algorithm is presented for MR brain images based on local entropy minimization. By making use of the tissue-based method and local entropy minimization, the clustering blocks of brain image segmentation are gotton, and then the dynamic search is implemented by taking each clustering block as central region. For each dynamic searching-window, the fuzzy C-means algorithm is used to segment the images. Comparing all the segmentation results with them of original clustering block, secondary segmentation is made for the pixels which hold the conditions of secondary segmentation. The segmentation results by using both simulated and real MR images show that the proposed secondary segmentation algorithm is accurate and reliable.
Medical image segmentation plays a very important role in medical image processing, particularly in the clinical analysis of magnetic resonance (MR) brain images. Intensity inhomogeneity in MR images, which can change the local statistical characteristics of the images, becomes a major obstacle to any automatic method for MR images. In order to reduce the influences of intensity inhomogeneity during segmentation, a secondary segmentation algorithm is presented for MR brain images based on local entropy minimization. By making use of the tissue-based method and local entropy minimization, the clustering blocks of brain image segmentation are gotton, and then the dynamic search is implemented by taking each clustering block as central region. For each dynamic searching-window, the fuzzy C-means algorithm is used to segment the images. Comparing all the segmentation results with them of original clustering block, secondary segmentation is made for the pixels which hold the conditions of secondary segmentation. The segmentation results by using both simulated and real MR images show that the proposed secondary segmentation algorithm is accurate and reliable.
2010, 47(7): 1304-1312.
Abstract：
Invertible watermarking is a type of schemes which has the capability that recovers the host media without any loss after embedded data is extracted, and plays key roles in scenarios where exact host media are crucial. In practical applications, compressed images are widely used for easy storage and transfer. Proposed in this paper is a novel invertible watermarking method with high capacity and low distortion for compressed images, in which original compressed images can be exactly retrieved on the extracting side. A sequence of coefficients in the medium and high frequencies of a quantized DCT block is defined as the candidate position for embedding. As long as the maximum index of zero coefficients in this sequence is not smaller than the integer value of watermark bits, the proposed method can embed these bits by modifying only one zero coefficient. Since the ratio between the number of modified coefficients and the number of watermark bits is low, a large amount of watermark can be embedded with low distortion. Experimental results demonstrate that the capacity and quality of watermarked images of the proposed scheme are better than those of the schemes as reported in other state-of-the-art literature. In addition, the proposed scheme is also well adaptable and configurable.
Invertible watermarking is a type of schemes which has the capability that recovers the host media without any loss after embedded data is extracted, and plays key roles in scenarios where exact host media are crucial. In practical applications, compressed images are widely used for easy storage and transfer. Proposed in this paper is a novel invertible watermarking method with high capacity and low distortion for compressed images, in which original compressed images can be exactly retrieved on the extracting side. A sequence of coefficients in the medium and high frequencies of a quantized DCT block is defined as the candidate position for embedding. As long as the maximum index of zero coefficients in this sequence is not smaller than the integer value of watermark bits, the proposed method can embed these bits by modifying only one zero coefficient. Since the ratio between the number of modified coefficients and the number of watermark bits is low, a large amount of watermark can be embedded with low distortion. Experimental results demonstrate that the capacity and quality of watermarked images of the proposed scheme are better than those of the schemes as reported in other state-of-the-art literature. In addition, the proposed scheme is also well adaptable and configurable.
2010, 47(7): 1313-1320.
Abstract：
Recently the LDPC decoder that could support multi-standard has become a major topic in the research of wireless communication system. Compared with traditional LDPC decoders, the proposed design in this paper has several merits as follows: 1.the novel decoder achieves a reconfigurable architecture for multiple code rates and data lengths, which consequently could support multi-standard schemes; 2.using a modified TPMP algorithm, the decoder largely reduces the memory size and avoids the data collision as a result of unstructured block-LDPC codes; 3.an architecture based on SIMD processor structure has been adopted to implement a high regular architecture which is convenient for chip layout; 4.enhancing the hardware resources utilization and gaining a higher system throughput by designing a dynamically reconfigurable 6-stage pipelined processing unit that can be configured into CNUs or VNUs by time-division multiplexing. A multi-standard LDPC decoder which supports both CMMB and DTMB standards has been synthesized on SMIC 0.13μm 1.2V 8-metal layer CMOS technology, the area of the decoder is about 0.75 million equivalent gates and the maximum operating clock frequency is 220MHz resulting in a decoding throughput of 300Mbps. The proposed architecture can be applied to other multi-standard LDPC decoder schemes, such as an integration of IEEE 802.16e (WiMAX) and IEEE 802.11n (WLAN), etc.
Recently the LDPC decoder that could support multi-standard has become a major topic in the research of wireless communication system. Compared with traditional LDPC decoders, the proposed design in this paper has several merits as follows: 1.the novel decoder achieves a reconfigurable architecture for multiple code rates and data lengths, which consequently could support multi-standard schemes; 2.using a modified TPMP algorithm, the decoder largely reduces the memory size and avoids the data collision as a result of unstructured block-LDPC codes; 3.an architecture based on SIMD processor structure has been adopted to implement a high regular architecture which is convenient for chip layout; 4.enhancing the hardware resources utilization and gaining a higher system throughput by designing a dynamically reconfigurable 6-stage pipelined processing unit that can be configured into CNUs or VNUs by time-division multiplexing. A multi-standard LDPC decoder which supports both CMMB and DTMB standards has been synthesized on SMIC 0.13μm 1.2V 8-metal layer CMOS technology, the area of the decoder is about 0.75 million equivalent gates and the maximum operating clock frequency is 220MHz resulting in a decoding throughput of 300Mbps. The proposed architecture can be applied to other multi-standard LDPC decoder schemes, such as an integration of IEEE 802.16e (WiMAX) and IEEE 802.11n (WLAN), etc.
