ISSN 1000-1239 CN 11-1777/TP

Table of Content

15 August 2012, Volume 49 Issue 8
A Constraint Optimization Based Mapping Method for Virtual Network
Li Xiaoling, Guo Changguo, Li Xiaoyong, and Wang Huaimin
2012, 49(8):  1601-1610. 
Asbtract ( 618 )   HTML ( 0)   PDF (2155KB) ( 556 )  
Related Articles | Metrics
Virtual network mapping problem, which attempts to map different virtual networks on the same substrate network, is an extremely challenging problem. A constraint optimization based mapping method is proposed to solve the problem. In this method, the process of solving the problem is divided into two phases, node mapping phase and link mapping phase, which are all NP-hard. The former phase maps the virtual nodes to the substrate nodes, and the latter phase maps the virtual links to the substrate paths. Node-mapping algorithm and link-mapping algorithm are proposed to solve the node mapping phase and the link mapping phase, respectively. Node-mapping algorithm adopts the thinking of greedy algorithm, mainly considering the available resources which are supplied by substrate nodes and distances among the nodes, in order to maintain load balancing. Meanwhile, an access control mechanism is also proposed to filter the unmoral virtual networks for the purpose of increasing the resource utilization. Link-mapping algorithm is based on the result of node mapping phase, and it adopts the thinking of distributed constraint optimization problem in artificial intelligence. The algorithm can guarantee the optimal solution, namely the minimum cost of mapping the virtual links. Finally, simulation experiments are conducted and the results show that the method performs very well.
A Multi-Source ALM Congestion Control Method Based on Bi-Directional Pressure
Gao Jianmin, Lu Huimei, Liu Jing, and Cao Yuanda
2012, 49(8):  1611-1617. 
Asbtract ( 499 )   HTML ( 0)   PDF (1849KB) ( 519 )  
Related Articles | Metrics
The multi-source ALM(application layer multicast) can achieve multi-party interaction applications with less resources compared with the traditional multicast method. But the multicast characters, the application layer environment and the properties of the multi-source will make the congestion control of ALM worse. So a multi-source ALM congestion control method based on bi-directional pressure is proposed in this paper. By calculating the forward pressure and the backward pressure for every flow on local node, all the flows according to its weight share the local buffers so as to improve utilization. The forward pressure accelerates the data transmission speed and the backward pressure decreases the data volume produced by the source. To release the congestion on the local node and achieve the control target, the method limits the data volume of different flows in the local buffer. The ring congestion problem, which is critical for the multi-source ALM, has also been discussed in this paper, and a simple method has been proposed. PlanetLab experiment is given to demonstrate that the proposed method can be used to control the congestion effectively, balance flows and buffers of all the sources and achieve fairness and scalability.
Design and Performance Analysis of A MAC Protocol for Wireless Public Bus Networks
Kuang Luobei, Xu Ming, Yu Wei, and Chen Yingwen
2012, 49(8):  1618-1631. 
Asbtract ( 438 )   HTML ( 0)   PDF (4683KB) ( 396 )  
Related Articles | Metrics
Providing high quality Internet service in public buses allows bus passengers to entertain themselves and even to work remotely during their travel time, thus significantly improving their quality of life. In this paper, a MAC protocol for public bus networks, called BusMAC, is proposed to provide high quality Internet service for bus passengers. The proposed protocol decreases collisions caused by multiple access from multiple passengers based on the improved bus network architecture. The MAC protocol based on super-frame structure decreases greatly the communication bottleneck in the bus network, combined with dynamical contention and piggyback mechanisms. The performance analysis of BusMAC is carried out based on request contention model and data scheduling model. Each model is expressed as a two-layer structure which catches up two access phases in the proposed MAC protocol. Extensive simulations are conducted to evaluate the BusMAC protocol. With simulations, the performance analytical models are verified to be accurate. Also, the results show that BusMAC can achieve much better performance than the traditional ones, and is more adaptive to bus communication. Specially, the deployment feasibility in the realistic system for the protocol can be accounted for through the experiments conducted under realistic mobility trace scenarios.
An Algorithm for the Cover Problem Based on Cellular Structure in Wireless Sensor Networks
Lu Kezhong, Jiang Zhao, Mao Rui, Liu Gang, and Ming Zhong
2012, 49(8):  1632-1640. 
Asbtract ( 694 )   HTML ( 0)   PDF (2679KB) ( 788 )  
Related Articles | Metrics
In wireless sensor networks, network lifetime can be effectively extended by scheduling some sensor nodes into sleep mode while keeping the target region fully covered by other active nodes. Finding a minimum cover set that can completely cover the target region is an NP-hard problem. When the number of sensor nodes is large, the cover problem can be only solved by approximation algorithm now. Cellular structure is the optimal topologic structure to cover a two-dimensional plane. But it cant be directly applied to the cover problem in wireless sensor networks. An algorithm for the cover problem based on cellular structure is proposed. In each stage of the iterative construction process of this algorithm, a node is selected into a set which is initially empty while keeping the topologic structure of this set close to the cellular structure. This process is repeated until this node set becomes a cover set. The worst-case time complexity of this algorithm is O(n\+3), where n is the total number of sensor nodes in the network. Simulation results show that this algorithm can obtain a cover set in very short time, and outperforms existing algorithms for the cover problem with respect to the size of the obtained cover set.
Algorithm-Level Low-Power Technology for the Channel Decoding Coprocessor of the Network Processor
Song Lihua, Guo Yanfei, and Wang Qin
2012, 49(8):  1641-1648. 
Asbtract ( 512 )   HTML ( 0)   PDF (1643KB) ( 560 )  
Related Articles | Metrics
In this paper, a new low power reed-solomon decoding algorithm (LP-RSA) is proposed, with the scenario that the RS decoder is integrated as a coprocessor of network processor. The proposed LP-RSA could dynamically judge the number of error symbols in advance and then close the unnecessary polynomial operations as soon as possible. By inserting the dynamic error pre-judgment circuit, the implemented coprocessor of RS decoder, which complies with the proposed LP-RSA, could turn the unnecessary processing circuits into sleep status to prevent the unavailable toggling of them and reduce the power of the coprocessor of RS decoder as well as the power of network processor. Under the same testing environment, the proposed LP-RSA allows the RS coprocessor achieving about 66.1% gain in power saving. At the same time, the proposed algorithm will help to extend the application range of network processor in the communication system with low power characteristic.
Immune-Computing-Based Location Planning of Base Station and Relay Station in IEEE 802.16j Network
Zhu Sifeng, Liu Fang, Chai Zhengyi, and Qi Yutao,
2012, 49(8):  1649-1654. 
Asbtract ( 524 )   HTML ( 0)   PDF (1097KB) ( 524 )  
Related Articles | Metrics
The IEEE 802.16j standard can provide coverage and capacity improvements through the introduction of new nodes called relay stations (RS). IEEE 802.16j network has the potential to deliver higher capacity networks at lower cost than more conventional single hop wireless access network. The joint optimization of relay stations and base stations is one of the network planning content for mobile network operators. Because the relay stations can be developed at significantly lower cost than base stations, given a set of candidate sites and network coverage demand, the number of base stations which need deploying can decrease through the joint optimization of relay stations and base stations, and the total cost of the network construction can be reduced. To solve the problem of location planning of base station and relay station in IEEE 802.16j relay network, a solution of location planning based on immune algorithm is proposed. The mathematical model of location planning is expounded, the framework of immune optimization algorithm is given, and simulation experiments are conducted to validate the algorithm. Experimental result shows that the proposed solution of location planning can obtain good network capacity with low cost of network construction, and has the advantages of good application value.
A Kind of More Secure Orthomorphism Generator
Tong Yan, Zhang Huanguo, and Deng Xiaotie
2012, 49(8):  1655-1661. 
Asbtract ( 470 )   HTML ( 0)   PDF (703KB) ( 490 )  
Related Articles | Metrics
Orthomorphism is a kind of important elementary permutation in symmetric cryptography, which is also a kind of complete mapping. Orthomorphism has been proved to have the perfectly balanced property. Construction and counting of orthomorphism has become one of the focal issues to Chinese and foreign scholars from 1995, however current researches on orthomorphisms pay little attention on their cryptographic properties, such as difference uniformity, nonlinearity and so on. Orthomorphisms with good cryptographic properties can be directly used to construct the cryptographic units in symmetric cryptographic algorithms. In this paper, firstly a problem in a conclusion about nonlinearity of composite functions is pointed out and corrected. Then several cryptographic properties against differential attack and linear attack of normal BDLL orthomorphism generator are analyzed, such as nonlinearity, algebraic degree and difference uniformity. Next, a modified orthomorphism generator based on composite functions is proposed. With the corrected conclusion of composite functions, the modified orthomorphism generator is proved to be able to construct nonlinear orthomorphisms with higher nonlinearity and algebraic degree than previous normal BDLL orthomorphism generators. And the numbers of orthomorphisms which can be derived from the modified orthomorphism generator is also proved to be bigger than that of previous normal BDLL orthomorphism generators.
An Improved VCA Interaction Model for Virtual Enterprises Based on Threshold RSA Signature
Zhang Wenfang, Wang Xiaomin, and He Dake,
2012, 49(8):  1662-1667. 
Asbtract ( 522 )   HTML ( 0)   PDF (818KB) ( 482 )  
Related Articles | Metrics
In this paper, the VCA interaction scheme for VE presented by Liu and Pan (for short, L-P scheme) is firstly analyzed, and it is found that a plain secret sharing method was directly used to construct the threshold RSA signature and the key distribution algorithms in the ring Z\-φ(N), which inevitably causes some algebraic construction flaws, i.e. incalculableness of elements’ inverses, unexpected decomposition of the module N, and the leakage of system secrets. In order to remedy L-P scheme’s drawbacks, a new improved scheme is then presented, in which a new parameter π is introduced to avoid computing of some particular elements’ inverses in the ring Z\-φ(N) since it is the multiple of these elements. And consequently the important parameter exp can be computed in the integer ring Z other than the residue ring Z\-φ(N) since it is the exponential component in the function of SIG which is in Z\-N. Analysis shows that the new scheme can effectively avoid any inverse’s computing in any ring, and can furthermore avoid the unexpected decomposition of the module N and the leakage of secret parameters. In addition, the proposed scheme is more efficient than the L-P scheme in the VCA sub-keys redistribution stage. Therefore, the new improved scheme provides a correct and feasible VCA interaction model for VE based on RSA threshold signature mechanism.
A Self-Adaptive Image Steganography Algorithm Based on Cover-Coding and Markov Model
Zhang Zhan, Liu Guangjie, Dai Yuewei, and Wang Zhiquan
2012, 49(8):  1668-1675. 
Asbtract ( 586 )   HTML ( 2)   PDF (2960KB) ( 412 )  
Related Articles | Metrics
It is a difficulty and hotspot how to desigh steganography algorithms with large-capacity, low-distortion and high statistical security. A self-adaptive image steganography algorithm which takes account of the perceptual distortion and second-order statistical security is proposed. It introduces the smoothness of the various parts of the cover-object to the encoding generation process of cover codes, and reduces the distortion by the reasonable use of a cluster of cover codes in each part of cover-object. In the embedding aspect, in order to improve the statistic security, the algorithm uses a dynamic compensate method based on the image Markov chain model, and it embeds secret information into the least two significant bit (LTSB) planes in order to ensure the capacity. Experiment results show the proposed algorithm has lower distortion and smaller changes of cover statistical distribution than the stochastic LTSB match steganography algorithm and the algorithm which only uses one cover code under the same embedded payload. And the proposed algorithm has larger payloads than one cover code embedding when the distortion and statistical distribution changes are close.
Program Behavior Monitoring Based on System Call Attributes
Li Zhen, Tian Junfeng, and Yang Xiaohui
2012, 49(8):  1676-1684. 
Asbtract ( 702 )   HTML ( 0)   PDF (1632KB) ( 564 )  
Related Articles | Metrics
The automaton of program behavior based on system call is often used to model program behavior. The automaton of program behavior based on system call attributes is proposed, which overcomes some drawbacks of traditional automaton of program behavior, such as low accuracy of program behavior trace modeled by control flow and data flow of system calls, high time overhead of capturing the system call context, and inability to monitor the program behavior between adjacent system calls. First of all, several system call attributes are introduced and the program behavior trace modeled by system call sequence can be monitored more accurately by considering the deviation degrees of system call attributes comprehensively. Secondly, system call arguments policies based on context are proposed to monitor the program behavior aiming at control flow or data flow. Thirdly, the time interval attribute of system call is presented and the program behavior trace between adjacent system calls, which cannot be monitored by system call and its arguments policies, can be monitored to some extent. The experimental results show that the automaton of program behavior based on system call attributes can model the program behavior more accurately and has better deviation detection ability of program behavior than traditional models of program behavior.
Provable Secure ID-Based Authenticated Key Agreement Protocol
Gao Haiying
2012, 49(8):  1685-1689. 
Asbtract ( 607 )   HTML ( 1)   PDF (587KB) ( 607 )  
Related Articles | Metrics
Key agreement protocols are fundamental to establish communications between two or more parties over an insecure network. Authenticated key agreement protocols not only allow parties to compute the session key but also ensure the authenticity of the involved parties. The design of ID-based authenticated key agreement protocols, which are secure and efficient, remains an open question in the field of ID-based cryptography. In recent years, several ID-based two-party authenticated key agreement protocols have been proposed. However, we discover that these protocols are in fact insecure if the attacker has stronger ability of revealing the ephemeral private keys of parties. In this paper, a new ID-based two-party authenticated key agreement protocol is presented which possesses attribute of PKG forward security. In this protocol, the session key is calculated by the long-term private keys and ephemeral private keys of parties. It is provable secure under q-augmented bilinear Diffie-Hellman exponent (q-ABDHE) assumption in standard model. Analysis shows that the session key is also secure even if the attacker gets the long-term private keys or ephemeral private keys of parties. Compared with other protocols from security and performance, our protocol has a good balance between computational cost and security.
Perceptual Robust Image Hashing Scheme Based on Secret Sharing
Qin Chuan, Chang Chin Chen, and Guo Cheng
2012, 49(8):  1690-1698. 
Asbtract ( 716 )   HTML ( 1)   PDF (2032KB) ( 530 )  
Related Articles | Metrics
Since the cryptographic Hash function is sensitive, any slight change of the input message will influence the result of the Hash value significantly. But for the scenario of image hashing, the traditional cryptographic Hash functions will not be suitable. This is due to the fact that the images usually must undergo various manipulations and many of the manipulations are content-preserving, even though the digital representations of the images will be changed. This paper proposes a perceptual robust image hashing scheme, which can be applied in the fields such as image retrieval and authentication. Image resizing and total-variation-based filtering are firstly used to pre-process the input image for regularization. The sign relationship matrix of DCT low frequency coefficients for each image block and and corresponding neighborhood are then extracted, which can effectively reflect the distribution feature of local image content. The extracted feature matrix is finally compressed using the secret sharing mechanism to produce the final binary Hash after scrambling. The security of the scheme completely depends on the secret keys. Experiments are conducted to show the presented scheme has satisfactory robustness performance against perceptually content-preserving manipulations, e.g., JPEG compression, Gaussian low-pass filtering, and resizing, and simultaneously has very low anti-collision probability for the hashes of distinct images.
Local Progressive Interpolation for Subdivision Surface Fitting
Zhao Yu, Lin Hongwei, and Bao Hujun
2012, 49(8):  1699-1707. 
Asbtract ( 678 )   HTML ( 0)   PDF (2157KB) ( 664 )  
Related Articles | Metrics
The quality of subdivision surface generated by the approximating scheme is usually better than that by the interpolating scheme, while the approximating subdivision surface is unable to interpolate the vertices of the initial control mesh. Traditional methods that make the approximating subdivision surface interpolate the initial mesh need to solve a global linear system. It is computation-intensive, and hard to deal with dense meshes. Without solving a linear system, the progressive interpolation calculates the approximating subdivision surface that interpolates the initial mesh by adjusting the vertices of the control mesh iteratively. It can handle control meshes of any size and any topology while generating smooth subdivision surfaces that faithfully resemble the shape of the initial meshes. In this paper, we show the local property of the progressive interpolation for approximating subdivision schemes. That is, if only a subset of the vertices of the control mesh are adjusted, and others remain unchanged, the limit of the subdivision surface generated in the progressive interpolation procedure still interpolates the corresponding subset of the vertices in the initial mesh. The local property of the progressive interpolation brings more flexibility for shape controlling, and makes the adaptive fitting possible. Lots of experimental examples illustrate the shape controlling and adaptive fitting capabilities of the local progressive interpolation.ss
Adaptive Multi-Resolutional Image Tracking Algorithm
Lü Na and Feng Zuren
2012, 49(8):  1708-1714. 
Asbtract ( 590 )   HTML ( 0)   PDF (2450KB) ( 379 )  
Related Articles | Metrics
In order to solve the target scaling problem in visual tracking, a new adaptive multi-resolutional image tracking algorithm employing posteriori probability similarity measure is developed. The pixel-wise computational property of the posteriori probability measure is proved firstly, based on which, a maximum posteriori probability tracking algorithm is developed. The posteriori probability measure can be computed both by feature and by pixel, which enables the convenient computation of each pixel’s contribution to the similarity value. Based on this property, a new adaptive scaling method is developed. On the other hand, when the size of the tracked target becomes large, multi-resolutional skill can be employed to reduce the computation burden, which is also derived from the computation property of the employed measure. Finally, a new adaptive multi-resolutional image tracking algorithm based on posteriori probability similarity measure is constructed. Experimental results demonstrate the effectiveness of the new algorithm.
Detail Extraction from Three-Dimensional Relief Surface
Zheng Hanlin and Liu Ligang
2012, 49(8):  1715-1720. 
Asbtract ( 663 )   HTML ( 0)   PDF (1604KB) ( 513 )  
Related Articles | Metrics
Reliefs are sculptures that are carved on a surface of bump ups and downs. In recent years, they have received a lot of attention. It is hoped that the three-dimensional reliefs will be presented on the screen, so that we could easily edit them and carry out its re-creation. Before the analysis of reliefs, an important task is to extract the details from the background surface. This can be seen as a segmentation problem. However, current algorithms have some restrictions on the input and output results, for example, the output relief are connected with no holes, or it needs some careful interactions. In this paper, we provide a more accurate method for estimating the background surface, called base surface. With the iterative means, we can then extract the relief details automatically. Various experiments show that our method can obtain good extraction results for base region dominated reliefs.
A New Unsupervised Foreground Object Detection Method
Liang Peng, Li Shaofa, and Wang Cheng
2012, 49(8):  1721-1729. 
Asbtract ( 914 )   HTML ( 0)   PDF (3343KB) ( 473 )  
Related Articles | Metrics
Aiming at the low accuracy of object detection methods based on unsupervised object detection, this paper proposes a foreground object detection method in unlabeled dataset. The basic idea is that correct feature clustering results can guide future object feature extraction, while the accurate foreground object features can improve the accuracy of feature clustering. The proposed method extracts local features from unlabeled images and then clusters features based on minimum feature distances. By matching pairwise images in the same cluster, feature weights are computed through feature correspondence. Finally, the updated feature weights are used to guide feature clustering in the next iteration. We simultaneously group similar images and detect foreground objects after iterations. The experimental results on Caltech256 and Google car side images demonstrate the effectiveness of our method. Furthermore, due to the present unsupervised object detection methods lacking of incremental learning ability, we propose an incremental implementation of our method. The experimental results show the incremental learning method can improve the computation speed greatly.
Supervised Laplacian Discriminant Analysis for Small Sample Size Problem with Its Application to Face Recognition
Lou Songjiang, Zhang Guoyin, Pan Haiwei, and Wang Qingjun
2012, 49(8):  1730-1737. 
Asbtract ( 604 )   HTML ( 0)   PDF (1148KB) ( 508 )  
Related Articles | Metrics
For high-dimensional data, extraction of effective features is important for pattern recognition. Unsupervised discriminant projection shows desirable performance by maximizing the ratio of non-local scatter to the local scatter, but it is an unsupervised method and suffers from the singularity problem, which is also called the small sample size (SSS) problem. To solve these problems, supervised Laplacian discriminant analysis (SLDA) is proposed, which takes the class information into account while calculating the local and non-local scatter matrix. The null space of total Laplacian scatter matrix is discarded firstly, then the intra-class Laplacian scatter matrix is projected onto the range space of the total Laplacian scatter matrix, and the solution is reduced to the eigen-problem in that space, thus the SSS is artfully avoided. Theoretical analysis shows that no discriminative information is lost and it is also computational efficient. Experiments on face recognition confirm the correctness and effectiveness of the proposed algorithm.
Cost-Sensitive Listwise Ranking Approach
Lu Min, Huang Yalou, Xie Maoqiang, Wang Yang, Liu Jie, and Liao Zhen
2012, 49(8):  1738-1746. 
Asbtract ( 762 )   HTML ( 1)   PDF (1644KB) ( 568 )  
Related Articles | Metrics
Learning to rank is a popular research area in machine learning and information retrieval (IR). In IR, the ranking order on the top of the ranked list is very important. However, listwise approach, a kind of classical approach in learning to rank, cannot emphasize the ranking order on the top of the ranked list. To solve the problem, the idea of cost-sensitive learning is brought into the listwise approach, and a framework for cost-sensitive listwise approach is established. The framework imposes weights for the documents in the listwise loss functions. The weights are computed based on evaluation measure: Normalized Discounted Cumulative Gain (NDCG). It is proven that the losses of cost-sensitive listwise approaches are the upper bound of the NDCG loss. As an example, a cost-sensitive ListMLE method is proposed. Moreover, the theoretical analysis is conducted on the order preservation and generalization of cost-sensitive ListMLE. It is proven that the loss function of cost-sensitive ListMLE is order preserved. Experimental results on the benchmark datasets indicate that the cost-sensitive ListMLE achieves higher ranking performance than the baselines on the top of the ranked list.
Multiple Attractor Cellular Automata Classification Method and Over-Fitting Problem with CART
Fang Min, Niu Wenke, and Zhang Xiaosong
2012, 49(8):  1747-1752. 
Asbtract ( 597 )   HTML ( 0)   PDF (1063KB) ( 467 )  
Related Articles | Metrics
The classification methods based on multiple attractor cellular automata can process the classification of two classes, and they are difficult to overcome overfitting problem. There are not yet effective methods for constructing a multiple attractor cellular automata which can process multi-classification and overfitting problem. The pattern space partition in the view of cell space is a kind of uniform partition which is difficult to adapt to the needs of spatial non-uniform partition. By combining the CART algorithm with the multiple attractor cellular automata, a kind of classifier with tree structure is constructed to solve the non-uniform partition problem and overfitting problem. The multiple attractor cellular automata characteristic matrix is defined, and the learning method of classifiers as a node in a tree is studied based on particle swarm optimization algorithm. The multiple attractor cellular automata classifiers built on this approach are able to obtain good classification performance by using less number of bits of pseudo-exhaustive field. The classifier with tree frame of multiple attractor cellular automata reduces the number of empty basin and restrains overfitting problem without lost accurate rate, and shorts the classification time. The feasibility and the effectiveness of the proposed method have been verified by experiments.
A Hybrid Evolutionary Algorithm Based on Clustering Good-Point Set Crossover for Constrained Optimization
Long Wen, Liang Ximing, Xu Songjin, and Chen Fu
2012, 49(8):  1753-1761. 
Asbtract ( 534 )   HTML ( 1)   PDF (1458KB) ( 464 )  
Related Articles | Metrics
A hybrid evolutionary algorithm based on multi-parent crossover of clustering good-point set and adaptive constraint-handling technique is proposed in this paper for solving constrained optimization problems. As for search mechanism, it utilizes good-point set to construct the initialization population that is scattered uniformly over the entire search space in order to maintain the diversity. The individuals of population are divided into several sub-populations according to the similarity of the two parents. The parents are selected randomly from the several sub-populations to arrange the crossover operation. The crossover operator can effectively make use of the information carried by the parents and generate representation offspring in order to maintain and increase the diversity of population. In addition, a local search scheme is introduced to enhance the local search ability and speed up the convergence of the proposed algorithm. As for constraint-handling technique, a new individual comparison criterion is proposed, which can adaptively select different individual comparison criterion according to the proportion of feasible solution in current population. The proposed algorithm is tested on 15 well-known benchmark functions, and the empirical evidence shows its effectivity.
Distributed Affinity Propagation Clustering Based on MapReduce
Lu Weiming, Du Chenyang, Wei Baogang, Shen Chunhui, and Ye Zhenchao
2012, 49(8):  1762-1772. 
Asbtract ( 1135 )   HTML ( 4)   PDF (4011KB) ( 698 )  
Related Articles | Metrics
With the rapid development of computer technology, data grows explosively. There are challenges for the traditional machine learning algorithms to deal with the large scale data. Many parallel algorithms have been proposed to address the scalability problem, such as MapReduce-based K-means algorithm and parallel spectral clustering algorithm. Affinity propagation (AP) clustering algorithm is introduced to address some drawbacks of the traditional clustering methods such as K-means algorithm. However, its scalability and performance still need improving when dealing with large scale data. In this paper, we propose a distributed AP clustering algorithm based on MapReduce, named DisAP. At first, large scale data are partitioned into several smaller subsets randomly. Then each subset is sparsified in parallel by using AP clustering algorithm. The results are fused and then clustered again, which forms a set of high-quality exemplars. Finally, all data are assigned to exemplars in parallel. DisAP is implemented on a Hadoop cluster, and the experiments on synthetic datasets,human face image datasets, and IRIS dataset demonstrate that DisAP can achieve high performance on both scalability and accuracy.
Bialgebraic Semantics of the Typed π-Calculus
Li Yongji, Li Shixian, and Zhou Xiaocong
2012, 49(8):  1773-1780. 
Asbtract ( 517 )   HTML ( 0)   PDF (864KB) ( 424 )  
Related Articles | Metrics
Proofs of bisimilarity being congruence in process calculi are lengthy and error-prone. The bialgebraic semantic provides a uniform framework to solve this problem. If the behavior functor over the semantic category preserves weak pullbacks and the forgetful functor from the category of coalgebras to the underlying semantic category has right adjoint, then the greatest coalgebraic bisimulation is congruence. When applying the bialgebraic framework to model the typed π-calculus, two problems arise: the behavior functors do not preserve weak pullbacks, and process bisimulations do not coincide with coalgebraic bisimulations. Solutions to the above two problems are proposed. For the first problem, the dense topology over the category of closed contexts is used to derive a boolean sheaf subcategory of the semantic category, so that the behavior functors, resulting from being restricted into such Boolean subcategory, preserve weak pullbacks. For the second problem, a specific class of functors over the Boolean sheaf subcategory, which includes the behavior functors for earlylate semantics, is defined. That process bisimilarity induced by these functors is the greatest coalgebraic bisimulation is proved. The existing bialgebraic framework is improved by using the above two techniques, and an appropriate bialgebraic model for the typed π-calculus is given. The corresponding bialgebraic semantic is fully abstract, and process bisimilarity is congruence. The methods described have paved the way for modelling more complex calculi in the bialgebraic framework.
Bialgebraic Structures for Abstract Data Types and Their Computations
Su Jindian and Yu Shanshan
2012, 49(8):  1787-1803. 
Asbtract ( 569 )   HTML ( 0)   PDF (3105KB) ( 501 )  
Related Articles | Metrics
Most of abstract data types in programming languages include both syntactive constructions and dynamic behaviors features which can be defined recursively or corecursively respectively, so simply using algebras or coalgebras can not offer a comprehensive description. As a pair of algebras and coalgebras with the same carrier set, bialgebras provide a feasible way to discuss the relations and properties between syntactic constructions and dynamic behaviors of abstract data types from the perspective of categorical theory. Bialgebraic structures for abstract data types are proposed in this paper and distributive laws of algebraic functors over coalgebraic functors are used to analyze the natural transformations between syntactic constructions and dynamic behaviors. Then, distributive laws are used to functorially lift coalgebraic and algebraic functors, which entail a way to build coalgebraic (or algebraic) structures on initial algebras (or final coalgebras) and lift them into initial (or final) λ-bialgebras. Finally, the applications of functorial lifting in the definitions and computations of various recursions (including iterations and primitive recursion) and corecursions (including coiterations and primitive corecursion) are discussed, as well as their corresponding computation laws.
An Approach for Migrating Data Adaptively in Hierarchical Storage Systems
Zhang Guangyan, amd Qiu Jianping
2012, 49(8):  1804-1810. 
Asbtract ( 670 )   HTML ( 4)   PDF (1764KB) ( 499 )  
Related Articles | Metrics
Hierarchical storage management (HSM) constructs a storage system with different types of devices, e.g., SCSI disks, SATA disks, FC disks and even SSD disks. The goal is to obtain large capacity with low cost. In order to achieve high performance, hierarchical storage management systems classify data dynamically and move them between fast devices and slow devices efficiently. However, almost all existing HSM systems have some limitations. Especially, without taking full advantage of the information from workloads, they make data migration affect application performance noticeably. AutoMig, an approach to automatically migrate data in a HSM system is proposed to enhance I/O performance of foreground applications. Firstly, AutoMig dynamically classifies files according to file access history, file size and storage utilization. Furthermore, an LRU queue is used to maintain the files in the fast devices. Secondly, it finds correlated files for automatic prefetching with data mining technology. Thirdly, AutoMig applies different policies to files migrating actions. It adaptively adjusts the migration rate according to varying workloads for migrating out actions while uses the asfastaspossible policy for migrating back actions. The application in a hierarchical storage system showes that AutoMig can effectively shorten foreground I/O response time compared with existing approaches.
Deriving Markov Chain Usage Model from UML Model
Wu Caihua, Liu Juntao, Peng Shirui, and Li Haihong
2012, 49(8):  1811-1819. 
Asbtract ( 684 )   HTML ( 1)   PDF (1403KB) ( 449 )  
Related Articles | Metrics
Constructing software usage model is basic for software reliability testing and software reliability evaluation. In recent years, how to derive Markov chain usage model from UML model has gained much attention. For large software system, the state space of Markov chain usage model using the existing methods is too large to describe, which is bad for generating test cases automatically and evaluating software reliability. For the above problems, a new method deriving a Markov chain usage model from UML model is proposed. The preconditions and postconditions of scenario are taken as the states of Markov chain usage model, and the performance and the performance probability of scenario are taken as the transition driver and transition probability. Compared with other methods, the state space of gained Markov chain usage model by proposed method is smaller and the constructing process is direct and automatic. Furthermore, the test cases can be generated easily by using the above method. In order to validate the validity of the UML model, the validity algorithm from UML model, which is extended by reliability evaluation to Markov chain model, is proposed too. Finally, the performance of the proposed method is verified by an example.
Kernelization for Weighted 3-Set Packing Problem
Li Shaohua, Feng Qilong, Wang Jianxin, and Chen Jianer
2012, 49(8):  17811-786. 
Asbtract ( 732 )   HTML ( 1)   PDF (603KB) ( 469 )  
Related Articles | Metrics
Packing and Matching problems form an important class of NP-hard problems, which have attracted lots of attention in the study of parameterized algorithms and kernelization of the problems. In this paper, we mainly study the kernelization algorithm for weighted 3-Set Packing problem. By further analyzing the problem structure, this paper proposes and proves two reduction rules for the weighted 3-Set Packing problem. Firstly, the numbers of sets in given instance of weighted 3-Set Packing problem containing two fixed elements and containing only one element are bounded. Based on the two bounded numbers, the total number of sets in the instance is bounded. Moreover, the processes of getting the two bounded numbers bring two efficient reduction rules for the weighted 3-Set Packing problem. Applying the two reduction rules, a kernel of size 27k\+3-36k\+2+12k can be obtained, which is the first kernel result for weighted 3-Set Packing problem. The kernelization process for weighted 3-Set Packing problem can also be applied to the weighted 3D-Matching problem, which results in the same kernel size as that of the weighted 3-Set Packing problem.