ISSN 1000-1239 CN 11-1777/TP

Table of Content

15 November 2007, Volume 44 Issue 11
A Survey of Classification of Data Streams
Wang Tao, Li Zhoujun, Yan Yuejin, and Chen Huowang
2007, 44(11):  1809-1815. 
Asbtract ( 643 )   HTML ( 3)   PDF (347KB) ( 1307 )  
Related Articles | Metrics
Data streams mining, the technology of getting valuable information from continuous data streams is a field that has recently gained increasingly attention all over the world. In the model of data streams, data does not take the form of persistent relations, but rather arrives in a multiple, continuous, rapid and time-varying way. Because of the rapid data arriving speed and huge size of data set in data streams, novel algorithms are devised to resolve these problems. Among these research topics, classifying methods is an important one. In this review paper, the state-of-the-art in this growing vital field is presented, and theses methods are introduced from two directions: stationary distribution data streams and data streams with concept drift. Finally, the challenges and future work in this field are explored.
Multi-Dimensional Concept Lattice and Incremental Discovery of Multi-Dimensional Sequential Patterns
Jin Yang and Zuo Wanli
2007, 44(11):  1816-1824. 
Asbtract ( 454 )   HTML ( 0)   PDF (545KB) ( 474 )  
Related Articles | Metrics
Multi-dimensional sequential pattern mining is the process of mining association rules from one or more dimensions of background information in which the order of the dimension values is not relevant, alongside mining sequential patterns from one or more dimensions of information in which the order is important. Multi-dimensional sequential patterns are much more informative frequent patterns which are suitable for immediate use. Although some work has been conducted for mining multi-dimensional sequential patterns, association patterns and sequential patterns are mined separately based on different data structures. In this paper, a novel data model called multi-dimensional concept lattice is proposed, which is the extension or generalization toward concept lattice. The intension of multi-dimensional concept lattice is more informative, which is constituted of one or more ordered task-relevant dimensions and one or more unordered background dimensions. Moreover, an incremental multi-dimensional sequential pattern mining algorithm is developed. The proposed algorithm integrates sequential pattern mining and association pattern mining with a uniform data structure and makes the mining process more efficient. The performance study on synthetic datasets shows the scalability and effectiveness of the proposed algorithm. At the same time, the application on the real-life financial datasets demonstrates the practicability of the approach.
A Two-Order Particle Swarm Optimization Model
Hu Jianxiu and Zeng Jianchao
2007, 44(11):  1825-1831. 
Asbtract ( 332 )   HTML ( 0)   PDF (373KB) ( 358 )  
Related Articles | Metrics
Particle swarm optimization (PSO) is an evolutionary computation technique developed by Kennedy and Eberhart in 1995. The underlying motivation for the development of PSO algorithm is social behavior of animals such as bird flocking, fish schooling, and swarm theory. Now PSO has been proved to be very effective for some problems. However, like other stochastic algorithms, PSO also suffers from the premature convergence problem, especially in the large scale and complex problems. In order to improve the global convergent ability of the standard particle swarm optimization (SPSO), a new version of particle swarm optimization named by a two-order PSO model is developed. Firstly, a two-order PSO model is introduced, its convergence analysis is given, and at the same time its parameter choices are studied. Secondly, a PSO model with the stochastic inertia weight is educed from the evolutionary equations of the two-order PSO. Thirdly, the two-order oscillating PSO with an oscillating factor is provided to adjust the influence of the acceleration on the velocity, which can guarantee the two-order PSO to converge to the global optimization validly. Finally, the above-proposed models are used to some benchmark optimizations. The experimental results show the proposed models can overcome the premature problem validly, and outperform the standard PSO in the global search ability and convergent speed.
Iterative sIB Algorithm Based on Mutation
Zhu Zhenfeng, Ye Yangdong, and Gang Li
2007, 44(11):  1832-1838. 
Asbtract ( 497 )   HTML ( 1)   PDF (426KB) ( 503 )  
Related Articles | Metrics
IB method employs the joint probability distribution between the source variable and the relevant variable to maximally compress the source variable, such that the middle compression variable can maximally save the information about the relevant variable. As a result, this method gives birth to several effective iterative algorithms, in which, the sequential IB algorithm (sIB) is one of the better and widely applied IB algorithms. But this algorithm also has some limits, such as, low efficiency and insufficient optimization, etc. For the sake of solving these problems of the sIB algorithm discovered in applications, an iterative sIB algorithm (isIB) based on mutation method is proposed here. Firstly, relevant experiments for selecting reasonable mutation rate are conducted. Based on this rate, the isIB algorithm chooses random proportional positions from the initial solution vector resulting from a seeding sIB algorithm, and randomly mutates the corresponding mapping relation from these chosen positions to the clustering labels. After getting the initial solution, the isIB algorithm optimizes it iteratively. The experimental results on the benchmark data sets indicate that the proposed isIB algorithm outperforms the sIB algorithm in both the accuracy and the efficiency.
Communication Protocol Entity Behavioral Specification and Description Language
Fan Hao, and Wu Zhehui
2007, 44(11):  1839-1848. 
Asbtract ( 649 )   HTML ( 1)   PDF (569KB) ( 528 )  
Related Articles | Metrics
A language named CPEBSDL (communication protocol entity behavioral specification and description language) is presented. The CPEBSDL language has a powerful ability on protocol description, it can describe protocol entity's states, behaviors and controlling and accessing to resources. The CPEBSDL regards the interaction between protocol entities as entities' control of the same resource. So the interactions between protocol entities can be denoted by the resources that entities mutually control. When a complicated protocol is required to describe by CPEBSDL, every single protocol entity's description can be established respectively, and then the whole description of protocols can be obtained by integrating every single protocol entity's description. In this point, the CPEBSDL make protocol analysis and testing easier. The CPEBSDL' regulation is proved to be equal to a context-free grammar G(CPEBSDL) and the G(CPEBSDL)is transformed to its Chomsky normal form. Based on those foundation, an algorithm that can validate whether a given protocol behavior sequence accords with CPEBSDL' regulation is proposed. Compared with traditional and classical protocol description languages, the CPEBSDL can decompose complicated protocol's behaviors to every single protocol entity's behaviors. Furthermore, the CPEBSDL can be easily translated into Petri nets, in which protocol's Petri nets can be modeled automatically if the protocol is described by the CPEBSDL. For example, the whole procedures of describing LAPD protocol using CPEBSDL are given and an example of validating the protocol behavior sequence is given too.
Self-Organization Resource Topology Revolution Based on Trust Mechanism
Wang Wei and Zeng Guosun
2007, 44(11):  1849-1856. 
Asbtract ( 493 )   HTML ( 0)   PDF (484KB) ( 380 )  
Related Articles | Metrics
Utilizing peer-to-peer (P2P) overlay networks to organize resources is a hot topic recently. How to assure the dependability of the resource selection in the overlay is a crucial problem. In overlay networks, self-organization is handled through protocols for node arrival and departure. Topology revolution based on physical location can improve the performance of P2P networks, but it ignores the problem of malicious nodes in the networks, which will greatly affect the resource providing ability of the whole P2P network; while topology revolution based on interest could improve the efficiency of resource sharing and searching in the networks, but it ignores the actual ability of resource providing and the reliability of nodes as well. In this paper a trust mechanism-based self-organization resource topology is developed and Bayesian method is used to evaluate the trust value of nodes based on their behavior. By updating the trust-based connection between each node, a novel self-organization topology is built on the top of the physical topology. Simulation experiments show that the proposed model not only increases the resource find ratio, but also improves the interaction performance of the entire network. In addition, this kind of model can cluster nodes near the trustworthy ones in the networks which have stronger ability of resource providing, and assure the reliability of resource sharing and selection.
Replacement Solutions for Streaming Cache on P2P Network
Chen Gang, Zhang Weiwen, and Wu Guoxin
2007, 44(11):  1857-1865. 
Asbtract ( 413 )   HTML ( 0)   PDF (564KB) ( 365 )  
Related Articles | Metrics
Peer-to-peer streaming cache is employed widely as it can reduce the bandwidth usage and improve the utilization of objects efficiently, in which FIFO and LRU algorithms are often used to replace objects. However, media streaming is different from Web objects and the P2P network is also different from the client/server model and has its own features so that the system performance may be restricted when these algorithms are applied in distributed environment. To solve this problem, FIFO and LRU are analyzed and then two algorithms are presented, evaluated and compared with FIFO, LRU and LSB (least sent bytes). The SD algorithm makes its decision based on supply-demand relationship of media segments, and the REP algorithm ejects objects according to replicas count of segments respectively. By simulation, it is found that both algorithms performed better than FIFO and LRU in terms of initial buffer delay, movie replicas number and dependency on the root with various peers' arrival interval. In some scenarios, initial buffer delay of LSB is reduced by about 40% compared with SD while the REP has an advantage over LSB in aspect of replicas number. It is proved that the system performance could be improved when SD and REP algorithms are exploited for cache replacement in streaming media service on P2P network.
A Self-Adaptive, Energy-Efficient Low Latency MAC Protocol for Wireless Sensor Network
Gong Haigang, Yu Changyuan, Liu Ming, Yi Fasheng, Wang Xiaomin and Chen Lijun
2007, 44(11):  1866-1872. 
Asbtract ( 408 )   HTML ( 0)   PDF (405KB) ( 421 )  
Related Articles | Metrics
Wireless sensor networks (WSNs) have been envisioned to have a wide range of applications. The main constraint of sensor nodes is their low finite battery energy, which limits the lifetime and the quality of the network, so that the protocols running on sensor networks must consume energy efficiently in order to achieve a longer network lifetime. One of the key problems for wireless sensor networks is the design of medium access control (MAC) protocol, in which medium access is the major consumer of sensor energy. And research on MAC protocols for WSNs has recently attracted significant attention to many applications. A self-adaptive, energy-efficient low latency (SEEL) medium access control protocol is presented for wireless sensor network. According to SEEL, each sensor node adjusts the initial contention window according to the current traffic load to reduce the collision probability while employing a fast backoff scheme to reduce the time for idle listening during backoff procedure, which reduces the energy consumption. In addition, an extended RTS/CTS scheme is employed in which the extended RTS scheme reduces active time of sensor nodes and the extended CTS scheme shortens the packet delay. Simulation results show that SEEL outperforms S-MAC and TEEM protocols.
A New Service Guaranteed Scheduling Policy for Buffered Crossbar Switches
Li Ji, Zeng Huaxin, and Xu Dengyuan
2007, 44(11):  1873-1880. 
Asbtract ( 414 )   HTML ( 0)   PDF (491KB) ( 386 )  
Related Articles | Metrics
Fast scheduler with service guarantee performance is preferred in high speed switching networks. Based on the features of EPFTS (Ethernet-oriented physical frame timeslot switching) and CICQ (combined input-crosspoint-queued), a new scheduling policy called timeslot reservation weighted fair scheduling (TRWFS) is introduced. In order to provide bandwidth guarantee service to guarantee-required (GR) traffic, TRWFS takes the total reserved timeslots of aggregated GR traffic on each I/O port pair as the basic scheduling weight and forwards traffic according to the following principles: 1) Giving dispatching priority to GR traffic and 2) Trying to balance the surplus timeslots (defined as service discrepancy between the actual packetized system and the idealized fluid system) for GR-traffic on each I/O port pair. In order to apply TRWFS and decrease the implementation complexity of TRWFS to constant time complexity O(1), two scheduling algorithms—TRWFS_I and TRWFS_II are further presented. Analysis and simulation results demonstrate that the two TRWFS algorithms both reach the design objective. Moreover, simulation results show that TRWFS/round-robin combined scheduling scheme in CICQ switches require fewer crosspoint buffer compared with other schemes.
A Security Domain Separation Z Model Based on DTE Policy
Qing Sihan, Li Liping, He Jianbo, and Shen Qingni
2007, 44(11):  1881-1888. 
Asbtract ( 469 )   HTML ( 1)   PDF (441KB) ( 368 )  
Related Articles | Metrics
High security level trusted information system need formal model of security policies to gain adequate assurance. Security domain separation based on DTE policy is one of the basic technologies to build trusted system. But the current DTE systems are difficult to assure their security, because they have no explicit security objective, their policy configuration is too complex, and there are no formal specification and formal verification of security properties on these systems or their policies. A security domain separation model based on DTE policy is formalized. It defines system state and adopted least privilege as domain separation principle. It extends original DTE policy, defines authorized information flow and pipeline information flow as two new invariants based on information flow analysis. Then system secure state is given and formal analysis by proven theorem is adopted to verify system security. The model is specified using the Z formal language and verified with the help of Z/EVES tool. The model has been implemented in the ANSHENG V4.0 security operation system and a Web server example is given. The work will also facilitate policy analysis and management of SELinux. This formal model resolves the formalization problem of DTE system and provids the foundation for security domain separation implementation and verification.
Transitive Trust and Performance Analysis in Windows Environment
Li Xiaoyong, Han Zhen, and Shen Changxiang
2007, 44(11):  1889-1895. 
Asbtract ( 526 )   HTML ( 1)   PDF (368KB) ( 368 )  
Related Articles | Metrics
Dynamic multi-path trust chain (DMPTC) is a software type and character based mechanism to assure system trustworthiness. DMPTC differentiates static system software and dynamic application software and takes different ways and policies to control the loading and running of various executable codes. The goal of DMPTC is to build a trusted computing platform by making computing platform only load and run trustworthy executables. DMPTC can be used to: 1) resist malicious codes (including known and unknown virus) which are the most serious threats to information systems, so as to improve system continuity of operation; and 2) help to manage and control what applications can be executed in business systems, improve their cost-effectiveness and productivity efficiency. DMPTC mainly uses the hash value of executables to verify their authenticity and integrity which is always a time-exhausted process; However, DMPTC gives great consideration to the impact it causes to system performance. Based on the attributes of various executables and by taking advantage of Windows interior security mechanisms, DMPTC reduces the time cost of the executables verification process greatly. The testing of DMPTC implemented on Windows platform shows that the performance loss caused by DMPTC is lower than 1%, and it is this optimization result that ultimately assures the flexibility and utility of DMPTC.
A Game-Based Axiomatization of μ-Calculus
Liu Wanwei, Wang Ji, and Chen Huowang
2007, 44(11):  1896-1902. 
Asbtract ( 442 )   HTML ( 0)   PDF (459KB) ( 323 )  
Related Articles | Metrics
With the never-ending growth of the complexity of modern hardware and software systems, more and more sophisticated methods of verification are required. Model checking has been proved to be an effective approach to guaranteeing the correctness of design and implementation of software and hardware system. Model and temporal logics are used as specification languages in software and hardware verification. Modal μ-calculus is an extremely popular and important one among these logics. It is succinct in syntax and powerful in expressiveness. Since Kozen's paper on modal μ-calculus, it has received ever growing interest in both theoretical and application aspects. Based on the focus game theory, Lange and Stirling proposed the axiom systems for LTL and CTL. This paper extends that idea to that for modal μ-calculus. A game-theoretic approach is presented to test the satisfiability of modal μ-calculus formulas. In addition, this approach converts the satisfiability problem for μ-calculus into a solving problem for focus games. Consequently, based on these game rules, an axiom system for μ-calculus is developed, and the completeness of this deductive system can be proved via the game based satisfiability testing procedure. By comparison, this axiom system is much more intuitive and succinct than the existing μ-calculus axiom systems.
A Game-Based Axiomatization of μ-Calculus
Liu Wanwei, Wang Ji, and Chen Huowang
2007, 44(11):  1896-1902. 
Asbtract ( 302 )   HTML ( 0)   PDF (459KB) ( 405 )  
Related Articles | Metrics
With the never-ending growth of the complexity of modern hardware and software systems, more and more sophisticated methods of verification are required. Model checking has been proved to be an effective approach to guaranteeing the correctness of design and implementation of software and hardware system. Model and temporal logics are used as specification languages in software and hardware verification. Modal μ-calculus is an extremely popular and important one among these logics. It is succinct in syntax and powerful in expressiveness. Since Kozen's paper on modal μ-calculus, it has received ever growing interest in both theoretical and application aspects. Based on the focus game theory, Lange and Stirling proposed the axiom systems for LTL and CTL. This paper extends that idea to that for modal μ-calculus. A game-theoretic approach is presented to test the satisfiability of modal μ-calculus formulas. In addition, this approach converts the satisfiability problem for μ-calculus into a solving problem for focus games. Consequently, based on these game rules, an axiom system for μ-calculus is developed, and the completeness of this deductive system can be proved via the game based satisfiability testing procedure. By comparison, this axiom system is much more intuitive and succinct than the existing μ-calculus axiom systems.
An Efficient Greedy Algorithm for Schema Matching
Zhang Zhi and Shi Pengfei
2007, 44(11):  1903-1911. 
Asbtract ( 570 )   HTML ( 2)   PDF (563KB) ( 465 )  
Related Articles | Metrics
Schema matching is the task of finding semantic correspondences between elements of two schemas, which plays a key role in many database applications, such as data integration, electronic commerce, data warehouse, semantic query processing, and XML message exchange, etc. Especially, it is a basic research issue in metadata management. Unfortunately, it still remains largely a manual, labor-intensive, and expensive process. In this paper, the schema matching problem is treated as a combinatorial problem. Firstly, schemas are transformed into multi-labeled graphs, which are the internal schema model for schema matching. Therefore, the schema matching problem is reduced to the labeled graph matching problem. Secondly, a generic graph similarity measure is discussed, which uses the labels of nodes and the edges to compute the similarity between the two schemas. Then, an objective function based on the multi-labeled graph similarity is proposed. Based on the objective function, a greedy matching algorithm is designed to find the desired matching state for schema matching. A prominent characteristic of this method is that the algorithm combines the feasible matching information to obtain optimal matching. Finally, some schema samples are used to test the greedy matching algorithm. The test results confirm that the algorithm is effective, which can obtain mapping results with high quality.
A Fault-Tolerant Priority Configuration Mixed Search Algorithm
Li Jun, Cao Wanhua, Yang Fumin, Tu Gang, Lu Yansheng, and Luo Wei
2007, 44(11):  1912-1919. 
Asbtract ( 379 )   HTML ( 0)   PDF (475KB) ( 311 )  
Related Articles | Metrics
Hard real-time systems are those that specified in terms of strong timing constraints. Fault tolerance in a real-time system implies that the system is able to deliver correct results in a timely manner even in the presence of faults. Techniques employing time redundancy are commonly used for tolerating a wide class of faults such as transient faults. In these systems, it is essential that the exploitation of time redundancy for correctness should not jeopardize the timeliness attribute. Hence scheduling aspects of fault tolerant hard real-time systems become all the more important. In this paper, a fault-tolerant priority-configuration-mixed search algorithm is proposed, that can be used, together with the schedulability analysis, to effectively increase the fault resilience of the fault-tolerant hard real-time systems. Schedulability analysis takes into account the fact that the recoveries of tasks are allowed to execute at some appropriate priority levels, either higher priority levels or lower priority levels. The performance of this mixed search algorithm is compared with that of other fault-tolerant priority configuration search algorithms by simulation. The results show that the average obtained increment on fault resilience when using the proposed algorithm is over 20%, which is higher than that of the three traditional algorithms.
Gaussian Mixture Modeling of Neighbor Characters for Multilingual Text Extraction in Images
Fu Hui, Liu Xiabi, and Jia Yunde
2007, 44(11):  1920-1926. 
Asbtract ( 393 )   HTML ( 4)   PDF (467KB) ( 337 )  
Related Articles | Metrics
A new method based on the Gaussian mixture modeling of neighbor characters is proposed to extract multilingual texts in images. In the training phase, the Gaussian mixture model of three neighbor characters is trained from the examples. Then the texts in an input image are extracted in the following steps. Firstly, the image is binarized using the edge-pixel clustering method and the morphological closing operation is performed on the binary image, in order that each character in it can be treated as a connected component. Secondly, the neighborhood of connected components is established according to the Voronoi partition of the image. Three connected components neighboring with each other constitute a neighbor set. For each neighbor set, a posteriori pseudo-probability is computed based on the Gaussian mixture model of three neighbor characters and used to classify the neighbor set as the case of three neighbor characters. Finally, the text extraction is completed by labeling the connected components as characters or non-characters with the following rule: if a connected component is included in at least one neighbor set classified as the case of three neighbor characters, then the connected component is labeled as a character, or else as a non-character. The proposed method are tested in the applications of Chinese and English text extraction. In the experiments, the expectation-maximization algorithm is employed to train the Gaussian mixture model of three neighbor characters. The experimental results of text extraction show the effectiveness of the method.
Kernel Methods for Radar Target Recognition Using Range Profiles
Yu Xuelian, Wang Xuegang, and Liu Benyong
2007, 44(11):  1927-1931. 
Asbtract ( 322 )   HTML ( 0)   PDF (304KB) ( 304 )  
Related Articles | Metrics
In a high resolution radar system, range profiles contain rather detailed structure information of a target and thus provide a more reliable tool for target recognition. However, the complexity of radar targets and their environments lead to nonlinear relationships between different targets. For this reason, it is necessary to adopt some nonlinear methods to obtain satisfactory recognition results. Currently, kernel-based method is a focus in the field of pattern recognition and shows many advantages as to solve nonlinear problems. In this paper, several kernel-based nonlinear methods are studied and applied to radar range profile recognition. As it is known to all, kernel Fisher discriminant analysis (KFDA) is one of the most effective techniques for nonlinear feature extraction. But it always suffers from the small sample size (SSS) problem. In order to deal with this problem, a method, called null-KFDA, is given and used to extract features from a range profile. Then, a novel kernel-based nonlinear classifier, called KNR (kernel-based nonlinear representor), is introduced and applied for classification. Experimental results on measured profiles from three aircrafts indicate that the null-KFDA is able to extract optimal discriminant vectors and does not suffer from the SSS problem, and that the performance of KNR is superior to those obtained by nonlinear support vector machine (SVM) and radial basis function neural network (RBFNN) in terms of both recognition rate and efficiency.
Planar Shape Blending Algorithm with Preserving Interior Similarity
Zhang Dongmei and Liu Ligang
2007, 44(11):  1932-1938. 
Asbtract ( 401 )   HTML ( 0)   PDF (446KB) ( 393 )  
Related Articles | Metrics
Planar shape blending or morphing, which involves the creation of a smooth transition from a source planar polygon to a target one, has gained widespread use in recent years. In order to obtain good effects in computer animation, a novel and efficient algorithm for planar shape blending is presented, which can preserve the similarity of the interiors of the polygons and avoid local expansion or shrinkage. First, the high quality compatible triangulations between the source and target polygons are constructed. Then, the geometric quantities including the angle and edge ratio at every interior angle of the intermediate triangulation are computed by interpolating the counterparts of the source and target triangulations. Finally, the intermediate triangulation is constructed by solving a linear sparse system, which can be efficiently solved by some solver library. The intermediate polygon is obtained by the boundaries of intermediate triangulation. Planar shape blending is formulated as solving a linear sparse system finally. The feature polygon is introduced to preserve the global visual features of the source and target polygons. This approach is simple and fast and can be used in practical applications in real-time. Many experimental results are presented to show that the approach is applicable and flexible and can obtain satisfactory results for complex polygons.
A Genetic Algorithm for Error-Bounded Polygonal Approximation of Curves
Wang Bin, Shu Huazhong, and Luo Limin
2007, 44(11):  1939-1945. 
Asbtract ( 350 )   HTML ( 0)   PDF (391KB) ( 343 )  
Related Articles | Metrics
Polygonal approximation of digital curve is a hot topic in image processing and pattern recognition and has found wide applications. Genetic algorithms (GA) have been used to solve polygonal approximation problems recently. However, the existing GA-based methods have the following disadvantages which limit their performance. Firstly, the length of chromosome is very long because of adopting fixed-length chromosome encoding; secondly, the local search ability of the traditional genetic operator is poor; finally, the penalty function method is adopted to cope with infeasible solution, and however, an appropriate penalty function is very difficult to determine. To overcome these problems, a novel GA-based method is proposed for error-bounded polygonal approximation. Its main ideas are: 1) a variable-length chromosome encoding scheme is adopted to reduce the memory storage and computational time; 2) a novel genetic operator named gene-removing crossover is developed for removing the redundant genes; 3) a chromosome-repairing scheme is proposed to cope with the infeasible solutions by iteratively adding the valuable candidate genes to the chromosome and an gene evaluating scheme is developed for this task. The experimental results demonstrate that the proposed method outperforms the existing GA-based method. The proposed method is also applied to the polygonal approximation of the satellite image of lake and obtains a better approximation result.
Disposing X86 FPU Stack in Binary Translation
Xie Haibin, Wu Chenggang, Cui Huimin, and Li Jing,
2007, 44(11):  1946-1954. 
Asbtract ( 492 )   HTML ( 1)   PDF (591KB) ( 324 )  
Related Articles | Metrics
Binary translation system is an across-architecture code migration system based on software, which translates binary codes of one architecture into those of another architecture. Binary translation is applied for not only the legacy code porting but also software being used in different hardware platform. The research on the binary translation has significance not only for legacy code migration but also for the program performance improvement and other aspects. How to dispose X86 FPU stack is one of the critical problems of research on binary translation whose source platform is X86, and it is also critical to the performance of binary translation whose source platform is X86. An extending virtual stack method has been presented. It makes sure that every floating register in every basic block which is referred by floating computing can directly be mapped to a target floating register using unifying method. It omits unnecessary judges in the entrance of every block using translation analysis, which ensures the effectiveness of translation. Besides, the necessary and sufficient conditions of floating register stack overflow and underflow have also been presented. It does goodness to generate more effective native code. It can dispose the problem of X86 float stack in binary translation successfully. The experiments show that this method can gain better performance without influencing the correctness of programs.
Compatibility and Substitutability Analysis of Web Services Composition
Shi Yuliang, Wang Haiyang, Zhang Liang, and Shi Baile
2007, 44(11):  1955-1961. 
Asbtract ( 472 )   HTML ( 0)   PDF (361KB) ( 421 )  
Related Articles | Metrics
It is evidenced that formal analyses are helpful for Web services composition. Current analytical methods put the emphasis on checking whether the generated global interactive process during Web services composition is consistent with the predefined composite model, ignoring whether the respective behaviors of Web services are compatible. Through formalizing description of Web services based on WSCI by using automata, the Client/Server model is proposed built on the model of Web services, the concept of compatibility is defined, and the corresponding algorithm is developed, which can ensure the correctness of Web services composition. Also, because of dynamic features of Web services, the concept of substitutability is defined based on the concept of compatibility, and a theorem to ensure the correctness of substitute Web services is proposed.
Error Propagation Analysis in Software
Li Aiguo, Hong Bingrong, Wang Si, and Piao Songhao
2007, 44(11):  1962-1970. 
Asbtract ( 544 )   HTML ( 1)   PDF (506KB) ( 333 )  
Related Articles | Metrics
Error propagation is a basic problem in analyzing uncertainty of reliable systems. During software development and dependability testing, it would be helpful to have a framework that clearly demonstrates the error propagation and containment capabilities of the different software components. However, in the former study, only the propagation characteristic of data errors in signals is considered, not including the error-generating properties of software itself induced by environment. In this paper, another error propagation frame is proposed, which not only includes the error propagation process, but also involves the error-generating ability of software itself. And this frame may be used in the later period of software development or in the process of software dependability testing. In this frame, the error propagation process in software is studied and characterized and a set of metrics that quantitatively represent the inter-modular software interactions are derived. Furthermore, a real embedded target system used in a navigation-pose control system of a satellite is used to perform fault-injection experiments to obtain experimental values for the metrics proposed. The result shows that the derived analytical framework establishes a very close correlation between the analytical and experimental values obtained. The intent is to use this framework to be able to systematically identify potential vulnerabilities in software.
Model and Algebra of Object-Relation Bitemporal Data Based on Temporal Variables
Ye Xiaoping
2007, 44(11):  1971-1979. 
Asbtract ( 419 )   HTML ( 0)   PDF (511KB) ( 329 )  
Related Articles | Metrics
The processing of temporal data is based on the platform of relational databases mostly, and temporal data model is an important part in the general temporal data model. It is difficult for relational data model to deal with the data which contains the complex type, and the object oriented data model is short of commercial applied basis. There are extensions to the function of objects in most relational databases, so it's not only very necessary but also rather feasible to extend the temporal relational data model to the one based on object-relation. Firstly, working on the data model of temporal-relation, a bitemporal data model on object-relation is proposed in this paper, which may be implemented in current object-relational databases. Secondly, the relationship and the transformation between temporal object-relation and the temporal relation are disussed in the model's framework, which is a fundamental requirement of extending temporal data schema to temporal object-relational data schema. Thirdly, the complex semantics of the temporal variables and the corresponding binding algorithm of the variables are discussed, which is one of the keys for the practical operation of temporal databases. Finally, the temporal algebra operations of the temporal object-relation data with the complex semantics in temporal variables are built, which is a significant for the study of the temporal query algorithm.
Indexing Bit-Code and Distance for Fast KNN Search in High-Dimensional Spaces
Liang Junjie, and Wang Changlei
2007, 44(11):  1980-1985. 
Asbtract ( 772 )   HTML ( 0)   PDF (333KB) ( 590 )  
Related Articles | Metrics
In the recent literature, a variety of index structures have been proposed to facilitate high-dimensional KNN queries, among which the techniques of approximate vector presentation and one dimensional transformation can efficiently break the curse of dimensionality. Based on the two techniques above, a novel high-dimensional index, called bit-code and distance based index (BD) is proposed. On the basis of the data distribution in high-dimensional spaces, the BD partitions the surface of dimensionality in a special way, such that all the data points are divided into lots of partitions according to some cluster centroids. By the definitions of bit code and transformation function, a high-dimensional vector can be first approximately represented and then transformed into a one-dimensional vector, the key managed by a special B\++-tree. During the process of KNN search, the BD enables two levels filtering: the transformation function prunes away points that do not share similar distance ranges, while the bit code component filters away points by the lower bounded distance. A fast algorithm is presented for KNN search, by which one can greatly reduce the number of distance computations and the cost of the tree search. By using both synthetic and real data, the results of extensive experiments demonstrate that the BD outperforms the existing index structures for KNN search in high-dimensional spaces.