Loading...
ISSN 1000-1239 CN 11-1777/TP

Table of Content

15 February 2013, Volume 50 Issue 2
Paper
Advances in Spatiotemporal Data Mining
Liu Dayou, Chen Huiling, Qi Hong, and Yang Bo
2013, 50(2):  225-239. 
Asbtract ( 1666 )   HTML ( 15)   PDF (1797KB) ( 2593 )  
Related Articles | Metrics
In recent years, the widespread use of the advanced technologies such as global positioning systems, sensor network and mobile devices, results in accumulation of a great amount of non-spatiotemporal data and spatiotemporal data. In addition, the processing of spatiotemporal data is more complex, which makes the increasing onerous situation of data processing tasks worse. To address these challenges, spatiotemporal data mining has emerged as an active research field, focusing on the development of theory, methodology, and practice for the extraction of useful information and knowledge from massive and complex spatiotemporal databases. Therefore, looking for effective spatiotemporal data mining methods is of great significance. This paper attempts to review the recent theoretical and applied research progress in spatiotemporal data mining and knowledge discovery. We mainly focus on spatiotemporal pattern discovery, spatiotemporal clustering, spatiotemporal anomaly detection, spatiotemporal prediction, spatiotemporal classification, and the combination of spatiotemporal data mining with reasoning. We have introduced the state-of-the-art research on spatiotemporal data mining in detail, and discussed the current major problems we are facing and its possible solutions.
A Multi-Motive Reinforcement Learning Framework
Zhao Fengfei and Qin Zheng
2013, 50(2):  240-247. 
Asbtract ( 624 )   HTML ( 1)   PDF (1880KB) ( 674 )  
Related Articles | Metrics
The traditional reinforcement learning methods such as Q-learning, maintain a table that maps the states to the actions. This simple dual-layer mapping structure has been widely used in many applied situations. However, dual-layer mapping structure of state-action lacks flexibility, while priori knowledge can not be effectively used to guide the learning process. To solve this problem, a new reinforcement learning framework is proposed, called multi-motive reinforcement learning (MMRL). Between state layer and action layer, MMRL framework introduces motive layer, in which multiple motives can be set based on experience. In this way, the original state-action dual-layer structure is extended to state-motive-action triple-layer structure. Under this framework, two new corresponding algorithms are presented, the first is MMQ-unique algorithm and the second is MMQ-voting algorithm. Moreover, it is stated that traditional reinforcement learning methods can be seen as a degenerate form of multi-motive reinforcement learning. That is to say, multi-motive reinforcement learning framework is a superset of traditional methods. This new framework and the corresponding algorithms improve the flexibility of reinforcement learning by adding the motive layer, and make use of priori knowledge to speed up the learning process. Experiments demonstrate that, multi-motive reinforcement learning can get better performance than the traditional reinforcement learning methods significantly by setting reasonable motives.
Theory and Algorithms of Attribute Decrement for Concept Lattice
Zhang Lei, Zhang Hongli, Yin Lihua, and Han Daojun
2013, 50(2):  248-259. 
Asbtract ( 465 )   HTML ( 1)   PDF (1935KB) ( 757 )  
Related Articles | Metrics
Incremental algorithms for the construction of concept lattices are of key importance. But most of them focus on the case of the addition of objects or attributes in formal context. When the attributes in formal context are deleted, reconstructing concept lattice by these algorithms is needed. It is very time consuming. The theory and algorithms of incrementally obtaining new concept lattice by updating the old one after attributes being deleted are investigated in this paper. At first, the mapping relation between concepts of the old and new concept-lattice is explained and the changes of edges from the old concept lattice to the new one are analyzed. Based on this, two decremental algorithms called top-down and bottom-up algorithms are proposed, by which the original concept lattice can be directly modified to obtain the new one, and reconstructing the whole structure from scratch is avoided. Relying on the structure of concept lattice, the algorithms only explore limited parts of the lattice for modifying. Thus, its time complexity is reduced to O(‖L‖·‖G‖·‖M‖). Experimental results show that the algorithms presented can save considerable time compared with the traditional algorithms.
Particle Swarm Optimization for Multiple Multicast Routing Problem
Ma Xuan and Liu Qing
2013, 50(2):  260-268. 
Asbtract ( 441 )   HTML ( 0)   PDF (1963KB) ( 644 )  
Related Articles | Metrics
The optimization problem of multiple multicast routing with both bandwidth and delay constraints is more complicated than the multicast routing problem. To get the optimal solution of the multiple multicast routing problem quickly, this paper proposes a particle swarm optimization algorithm based on evolution of tree structure. In the proposed algorithm a particle, as a feasible solution of the problem, is represented as a vector, and the components of the particle are represented by tree structure coding. The flight of particles in the search space is implemented through the evolution of trees. Visual radius of a particle is introduced in the orbicular social structure of particle population to enhance the ability of particle neighborhood learning. The tree structure mutation method is designed to increase the possibility of which the algorithm jumps out of local optima. To the infeasible solutions unsatisfied with constraints in the population, penalty strategy is adopted to penalize the particle and its components according to the situation unsatisfied with constraints. Simulation experiments have been carried out on different network topologies produced by random for networks consisting of 26, 50 and 100 nodes. The results of solving the routings of multiple multicast requests show that the proposed algorithm performs better in searching optimal solution and converging speed.
Heuristic Discrimination Cotton Ripeness Using Hybrid Filter and Wrapper
Wang Ling, Liu Shanjun, Chen Binglin, and Ji Changying*
2013, 50(2):  269-277. 
Asbtract ( 550 )   HTML ( 0)   PDF (2006KB) ( 574 )  
Related Articles | Metrics
Raw ripeness discrimination is a pivotal technology of machine vision system of cotton picking robot. The dimensionality curse exists in spatial and frequency feature sets describing morphology structure and boundary contour of raw cotton, and their feature selection problem is an NP hard problem. A solution algorithm is proposed using floating search by filter and stopping search by wrapper based on cross validation. The optimal l feature subset (l=1,2,3,…) is selected on training set using filter with an assessing function of class-separability measured value and heuristic criterion including optimal scalar feature combination and floating search. A model is established on training set using the optimal l feature subset by wrapper with an assessing function of the error rate of Bayes-classifier. The optimal feature subset is with a capacity of 6 at the minimum value of average error rate of the model on validation set, and the average classification rate of which on prediction sets is 87.61%. The algorithm has been validated on 40 databases involved in correlative research work, and experimental results show that the algorithm has good classification performance and higher execution efficiency on 29 datasets.
Survey of Security and Trust in Opportunistic Networks
Wu Yue, Li Jianhua, and Lin Chuang
2013, 50(2):  278-290. 
Asbtract ( 885 )   HTML ( 1)   PDF (1556KB) ( 1221 )  
Related Articles | Metrics
Opportunistic networks (OppNets) are one of the evolutionary mobile ad hoc networks whose communication links often suffer from disruption, while their totally different networking paradigm attracts extensive attentions from both researchers and developers. The message in OppNets is transferred only on the occasional encountering of pair-wise mobile wireless nodes, and the routing paradigm is referred to as “store-carry-and-forward” transmission characteristics to implement network communication. In such networks, continuous end-to-end connectivity may not be possible. Due to unique features of high mobility of nodes, frequent link variation and long communication delays, many opportunistic forwarding protocols present major security issues, the design of OppNets faces serious challenges such as how to effectively protect data confidentiality and integrity and how to ensure routing security, privacy and node authentication and incentive cooperation. In other words, systematic research on OppNets is still open and far from a widely-used practical system. In this paper, it first systematically describes the security threats and requirements in OppNets; then elaborates the popular research problems including secure routing, privacy protection, node authentication and incentive cooperation mechanisms in opportunistic networks; and then various security and trust schemes are comprehensively analyzed and compared. Finally it concludes and gives the future research directions.
An Online Mobile Payment Model with Simplified Terminal Authentication
Wang Hongxin, Yang Deli, Jiang Nan, and Ma Hui
2013, 50(2):  291-301. 
Asbtract ( 625 )   HTML ( 1)   PDF (2241KB) ( 526 )  
Related Articles | Metrics
Mobile payment is an important and core application of information safety technology in mobile Internet,and the mobile terminal authentication is the important issue needing to be solved first in mobile payment. In order to meet the special requirement of mobile payment, such as mobile terminal resource constraints from portable needs and mobile terminal update acceleration from more and more rich personalized needs, the steps of terminal authentication need to be as simple as possible, the dependence on equipment needs to be as little as possible, and the customer’s operation experience also need the authentication to be as simple as possible. So there should be a simplified and independent of equipment’s terminal authentication. Therefore, a mobile payment model with simplified terminal authentication is introduced. The model is designed based on the “pre-trust” hierarchical certification model and the payment system framework with a character of “public-service-domain”. To achieve the purpose of controlled system safety and simplified terminal authentication, a credit transfer chain starting from merchants is built, as well as an account addressing and management mechanism are designed. Meanwhile, related research review, system framework, authentication model and corresponding payment protocol are given. Furthermore, the security of the protocol is analyzed.
ID Based Signature Scheme from Strong RSA Assumption in the Standard Model
Wang Zhiwei and Zhang Wei
2013, 50(2):  302-306. 
Asbtract ( 804 )   HTML ( 0)   PDF (641KB) ( 613 )  
Related Articles | Metrics
ID based cryptography is always the interested field in the cryptography research, since it has the advantage of eliminating user’s certificates, and the cost of certificate management is saved. Although many ID based cryptographic primitives have been proposed, most of them are constructed from bilinear pairing, and based on the hardness assumptions in bilinear pairing. Since pairing usually involves heavy computational costs, how to construct ID based cryptographic primitives without pairing is still a valuable issue in the cryptography. A few ID based signature schemes have been presented, however, some of them have not provided the security proof, and others can only be proved secure in the random oracle. There is still no true ID based signature schemes in the standard model. In this paper, an ID based signature scheme from Hohenberger and Waters signature is proposed, which can be proved weakly secure under the strong RSA assumption. Furthermore, with the help of Chameleon Hash function, the proposed scheme can be transformed into a provably secure scheme in the standard model. In the proposed scheme, the signature involves 2 elements in N*N, and the signing algorithm only needs 2 modular exponentiations.
Steganalysis of Color Images Based on Noise Model and Channels Integration
Qi Ke, and Xie Dongqing
2013, 50(2):  307-318. 
Asbtract ( 479 )   HTML ( 7)   PDF (2845KB) ( 622 )  
Related Articles | Metrics
Steganalysis of color images weaken or ignore the correlation among different color channels by only using single signal channel. The noise model of stego color images is analyzed, and a general steganalysis algorithm based on noise model and color channels integration is proposed. Firstly, the wavelet decomposition of the image is made, and a filtering operation is applied to obtain the wavelet subbands of noise image. Secondly, noise gradient orientation sequences between any two noise channels and noise gradient sum sequence are extracted from the noise wavelet subbands. Thirdly, color gradient orientation sequences between any two channels and color gradient sum sequence are extracted from the color image. Finally, the HilbertHuang transform based vibration features of these sequences are integrated as eigenvectors, and SVM is used to detect images. The experimental results show that the proposed technique realizes the reliable steganalysis of color images with higher correct rate and lower false positive rate, compared with traditional color image steganalysis algorithms.
An Encryption Algorithm for Image Based on Affine and Composed Chaos
Wen Changci, Wang Qin, Liu Xianghong, Huang Fumin, and Yuan Zhishu
2013, 50(2):  319-324. 
Asbtract ( 612 )   HTML ( 0)   PDF (1167KB) ( 668 )  
Related Articles | Metrics
With the popular application of multimedia, the security of digital image becomes more and more important. According to the feature of digital image and on the basis of three-dimension affine transformation and chaos, a novel spatial domain encryption algorithm is proposed. Firstly, it scrambles pixel position and confuses pixel value according to the corresponding coordination. Secondly, it takes a series of nonlinear diffusion and substitution in turn for all lines. The algorithm proceeds with the above two steps for at least 3 times, and it can be conveniently converted to the frequency domain algorithm while replacing the processed data in the spatial domain with quantized coefficients in the frequency domain. In the process of substitution, pixel value is introduced to perturb multiple chaos systems that are coupled together for self-adaptive encryption. In the encryption process, the scrambling parameters are generated by chaos systems automatically, and the scrambling function is compatible with images at any ratio of length to width without any preprocessing. Theoretical analysis shows that the algorithm has huge key space to defend against violent attack, the mapping relation between the plaintext and the ciphertext is complex enough to resist chosen plaintext attack efficiently, and the algorithm using simple chaos systems is designed modularly in order to be realized parallelly conveniently. Experimental results show that the algorithm takes good encryption result, gets strong sensitivity, conforms to confusion and diffusion principles in cryptography, and achieves high security.
Formal Verification of TCG Remote Attestation Protocols Based on Process Algebra
Wang Yong, Fang Juan, Ren Xingtian, and Lin Li
2013, 50(2):  325-331. 
Asbtract ( 661 )   HTML ( 0)   PDF (885KB) ( 566 )  
Related Articles | Metrics
Remote attestation protocol of TCG (Trusted Computing Group) is the earliest remote attestation solution for trusted computing. Two forms of TCG remote attestation are analyzed: direct remote attestation protocol and remote attestation with trusted third party protocol. And the abstract models of the above two forms are presented in which interacting channels between the whole system and the outside environment are treated as exterior channels and interacting channels between parts of the system are treated as inner channels. Based on these abstract models, we provide the process algebra-based formal descriptions, in which every part involved in the protocols is described by a process term to capture the state transitions of the system part, and we put these process terms into parallel to get the whole formal systems. Then we conduct the related formal verifications of the parallel formal system based on the axioms of process algebra. The verification results show that the formal systems of two protocols exhibit desired external behaviors.
Call-Graph-Based Interclass MM Path Generation
He Wei, Zhao Ruilian, and Zhu Qunxiong
2013, 50(2):  332-343. 
Asbtract ( 1215 )   HTML ( 9)   PDF (2346KB) ( 507 )  
Related Articles | Metrics
Interclass integration testing of object-oriented software is particularly hard. Method/message path (MM path) is defined as an interleaved sequence of method executions linked by messages. It presents well the interactions between the methods of object-oriented software, and hence fits for object-oriented integration testing. In this paper, a call-graph-based approach to generate interclass MM paths automatically is proposed. This approach is evaluated by two typical call graph construction algorithms, class hierarchy analysis and Anderson’s points-to analysis, on twelve benchmark programs. The result shows that our approach is practicable, and based on Anderson’s points-to analysis, 13.11% more interclass MM paths can be generated with 27.78% less time consumption than based on the class hierarchy analysis. Moreover, the structural coverage is increased by 2% and 7% with the MM-path-oriented test suites which are generated based on Anderson’s points-to analysis than based on the class hierarchy analysis. Therefore, Anderson’s points-to analysis outperforms the class hierarchy analysis for call-graph-based interclass MM path generation.
The Property Inference of Aspect-Oriented Program
Ye Jun, Tan Qingping, and Li Tun
2013, 50(2):  344-351. 
Asbtract ( 593 )   HTML ( 1)   PDF (777KB) ( 585 )  
Related Articles | Metrics
To simplify the formal verification of programs developed with aspect-oriented programming (AOP) paradigm, Djoko et al. identified categories of aspects systematically and determined some class of properties that each aspect category can preserve. For example, one of the aspect categories named “observer ”are those aspects that wouldn’t modify the states and the control flow of their base program. The observer can preserve all safety and liveness properties that don’t include “Next” operator. Their work can avoid direct verifications of the woven programs which always have larger scale than their base program. Their work is of great importance. Based on their work, this paper proposes a new aspect category named “functor” and proposes the concept of “property inference” (PI). Functors are those aspects that add new functionalities to a base program under certain conditions. They have changed the property of a base program, but in an inferable way. PI infers the property of woven programs using the verified properties of a base program and special characterizes its aspects. PI also avoids direct verifications of the woven programs. Our work is an important supplement to Djoko’s work.
Formal Software Specification Generation Approach Based on Problem Patterns
Wang Changjing,,Luo Haimei, and Zuo Zhengkang,
2013, 50(2):  352-360. 
Asbtract ( 733 )   HTML ( 0)   PDF (1538KB) ( 661 )  
Related Articles | Metrics
Precise formal software specifications are foundation of software description、development and verification, while industrial community in general use non-(semi-) formal representation to define and describe user requirements. It is one of the difficulties of current requirement engineering that how non-(semi-) formal user requirements are generated into the formal software specifications. In this paper, problem pattern is defined by extending the concept of design pattern, then a generation approach of formal software specification is proposed based on problem patterns. From the high-level problem requirements described by structured natural language-SNL, they are refined step by step to get various new sub-problem formal specifications by selecting problem patterns from knowledge base. Afterwards the sub problems are composed and optimized to get the final formal specification. Furthermore we use the principle and concepts of model refinement calculus to provide theory basis of the generation method. We adopt algorithmic program domain as research object and use Radl as formal specification language. This approach is elaborated using a classic example about algorithmic program domain, and practical effects manifest that it can effective generate formal specification of high quality.
A Fitting Method of Paracatadioptric Line Images Based on Antipodal Image Points
Duan Huixian
2013, 50(2):  361-370. 
Asbtract ( 477 )   HTML ( 0)   PDF (5068KB) ( 653 )  
Related Articles | Metrics
Under central catadioptric camera, the image of a line is a conic curve. Due to the partial occlusion, it is very difficult to correctly estimate the catadioptric line image from its visible part, and the existing methods in the literatures cannot still solve this problem effectively. Except for the necessary and sufficient conditions that must be satisfied by a set of paracatadioptric line images, we find that if the antipodal points of image points on the visible arc are known, the fitting accuracy can be improved greatly. Thus, in this paper, based on this idea, a new method for fitting paracatadioptric line images is proposed. Firstly, a new relationship between a pair of antipodal image points and the camera principal point are derived. Next, using this relationship, a new method is proposed to estimate the paracatadioptric line images. Finally, the camera intrinsic parameters are calibrated using the estimated conics. Experimental results on both simulated and real image data have demonstrated theeffectiveness of the method.
A Novel Approach for Abstractive Video Visualization
Peng Dichao, Liu Lin, Chen Guangyu, Chen Haidong, Zuo Wuheng, and Chen Wei
2013, 50(2):  371-378. 
Asbtract ( 1121 )   HTML ( 1)   PDF (2761KB) ( 587 )  
Related Articles | Metrics
We present a novel approach for abstractive video visualization, which can help users understand the semantic information from the video in a fast and effective manner. We use the scale-invariant feature transform(SIFT) algorithm to detect features of each frame, together with a modified bag of words algorithm to construct a feature vocabulary in order to compute the feature frequencies. By mapping the video sequence onto a 3D curve in a high dimensional vocabulary space with the use of the multi-dimensional scaling (MDS) algorithm, the video is abstracted and embedded into a visually recognizable curve in 3D space. This generated visualization result can vividly illustrate the evolvement of the video contents, while well protecting and preserving the semantic meaning that are encoded within the video. Experimental results indicate that this curve-based visualization technique can uncover the semantic relationship between the frames, characterize the transition of video contents, and help the users understand the semantic structure of the underlying video sequence with a quick glance.
Action Recognition Based on Sine Series Fitting
Zhao Xuan, and Peng Qimin
2013, 50(2):  379-386. 
Asbtract ( 733 )   HTML ( 1)   PDF (3622KB) ( 509 )  
Related Articles | Metrics
This paper presents a sine series-based method for action recognition. The proposed method can be divided into three stages: feature extraction, series fitting and feature matching. In the stage of feature extraction, the method gets binary human silhouette through background difference and Gaussian background modeling at first, then uses the binary silhouette to represent the given image sequence and calculates the distance from the silhouette centroid to the boundary points according to a clockwise movement, thus changing the human silhouette into distance curve. In the stage of series fitting, the method fits the curve with the sine series and changes the distance curve into sine parameters with different amplitude, frequency and offset, which reduces the computational cost greatly and changes the process of action recognition into the matching of curve parameter features. Finally, in the stage of feature matching, the method classifies each frame in the given image sequence through calculating the minimum distance between it and the known action categories at first, and then gets the category of the given image sequence by voting. We adopt a leave-one-out scheme for experiment evaluation. The experiment results on a database of 90 short video sequences show that the promising performance is both effective and efficient.
Expression Detail Synthesis Based on Wavelet-Based Image Fusion
Wang Xiaohui, Jia Jia, and Cai Lianhong
2013, 50(2):  387-393. 
Asbtract ( 681 )   HTML ( 0)   PDF (1660KB) ( 617 )  
Related Articles | Metrics
Expression details are texture changes caused by facial expression, such as wrinkles in the corner of the mouth when smiling and wrinkles on the forehead when surprising. Expression details can help to enhance the realistic experience of synthesized face image. In this paper, we propose to synthesize expression details by using the method of wavelet-based image fusion. We try to mine the texture feature of expression details for natural expression generation. In order to meet the requirements of individual expression detail synthesis, we use different wavelet transforms, such as the traditional wavelet transform and dual-tree complex wavelet transform, and kinds of fusion operators to get rich results. To seamlessly integrate the synthesized image of expression details to the output expressive face image, we select the optimal replacement for both images by clustering and graph cut method. Our proposed approach is applied to not only grayscale images, but also color images by the color space conversion. The experimental results show that the proposed method is effective on the expression detail synthesis, which can enhance the realistic experience of synthesized face image.
Construction of Symmetrical Filled-in Julia Sets on Spherical Surfaces
Chen Ning and Lin Qiufang
2013, 50(2):  394-400. 
Asbtract ( 383 )   HTML ( 0)   PDF (2833KB) ( 468 )  
Related Articles | Metrics
To continuously generate the images of filled-in Julia sets with attracting orbits of multi-periodicity on a spherical surface, a method of constructing a half spherical surface image on a discretional projective plane is presented. Firstly, the parameters are automatically selected to construct a spherical surface dynamic system whose Lyapunov exponent (L) is less than 0. Then, the iterating orbits of the points on the upper half spherical surface on a discretional projective plane are tracked with the mapping founded in the coordinates system whose origin is the spherical center by the coordinates transform. All the different attracting orbits are built in a link list. Finally, every point on the spherical surface is pointed a color according to the iterating number by which its iterating orbit goes to an attracting orbit in the list, and the filled-in Julia set image on the upper half spherical surface is constructed. The result shows that the method can be used to generate a great number of symmetric filled-in Julia set images on the sphere surface.
Parallel Acceleration and Performance Optimization for GRAPES Model Based on GPU
Wang Zhuowei, Xu Xianbin, Zhao Wuqing, He Shuibing,, and Zhang Yuping
2013, 50(2):  401-411. 
Asbtract ( 630 )   HTML ( 0)   PDF (2379KB) ( 568 )  
Related Articles | Metrics
GRAPES(globalregional assimilation and prediction system) is a typical non-linear discrete system of the Earth’s atmosphere developed for numerical weather prediction. There are heavy computations involved in GRAPES. Researchers have recently paid a lot of attentions to the parallel acceleration of the GRAPES model by low-cost, low-power, and high-performance GPUs. In this paper, we implement the parallel acceleration for the GRAPES model in GPUs. But the experimental results show that its performance is not efficient as supposed. Therefore, based on this, we further propose some strategies for optimizing the system performance, including reducing the data transmission time, decreasing the amount of device memory loaded and stored equipment, and avoiding the branches of thread control flows. The experimental results show that the performance optimizations on GPUs improve GRAPES system performance effectively.
Parallel Computing of Central Difference Explicit Finite Element Based on GPU General Computing Platform
Cai Yong, Li Guangyao, and Wang Hu
2013, 50(2):  412-419. 
Asbtract ( 729 )   HTML ( 0)   PDF (2324KB) ( 698 )  
Related Articles | Metrics
Explicit finite element method has been widely used for the plane nonlinear dynamic problems. Because of the limitation of time step due to the conditional stability, the analysis of large-scale problem always requires long computing time. Graphics processing unit (GPU) is a parallel device with single instruction, multiple data classification. GPU offers high computation power and increases memory bandwidth at a relatively low cost, and it is well suited for problems that can be expressed as data-parallel computations with high arithmetic intensity. Nowadays, it has gained more and more attention as a kind of general parallel processor, followed by various general purpose GPU computing technologies represented by NVIDIA CUDA. In this paper, a method of explicit finite element parallel computing based on central difference method and GPU general computing platform for plane nonlinear dynamic problems is developed. The original serial algorithm is adjusted and optimized for GPU computing based on the characteristics of GPU. Finally, GPU is used for the whole explicit iterative process by mapping one element or one node to one CUDA thread, and the iterative process can be solved parallelly in any order. The numerical examples indicate that this method can greatly improve the computational efficiency with the same computing precision on the NVIDIA GTX 460, and it provides an efficient and simple method for the plane nonlinear dynamic problem.
Duplication Based Energy-Efficient Scheduling for Dependent Tasks in Grid Environment
Ma Yan, Gong Bin, and Zou Lida
2013, 50(2):  420-429. 
Asbtract ( 489 )   HTML ( 0)   PDF (2974KB) ( 484 )  
Related Articles | Metrics
As efficient energy management emerges as an important issue for reliable and green computing, energy-aware scheduling approach is regarded as a promising way since it is practical and low-cost. At present, there exist large challenges in the area of energy-aware scheduling for dependent tasks in grid computing system, because the precedence constraints of applications, massive data transmission, system heterogeneity and the conflict of multiple scheduling indicators should be balanced. In this paper, taking into account all the above factors, we propose ESGDT (energy-efficient scheduling of grid dependent task) algorithm, which aims to reduce energy consumption while optimizing execution time for applications. ESGDT algorithm reduces data transfer time and communication energy consumption through task duplication and progressive ratio metric, and considers complex data dependent relationship between tasks. It also considers the static power of processing element through dynamic power management technique following the trends of chip miniaturization and multi-core technology. Moreover, the condition of task duplication, the computation method of progressive ratio metric, and the rule of task adjustment all properly consider two conflicting scheduling indicators——time and energy. ESGDT algorithm also focuses on dynamic and adaptive scheduling issues in total heterogeneous system. Simulation experiments demonstrate that ESGDT algorithm could reduce more energy consumption while not influencing scheduling performance than HEFT, EETDS and HEADUS algorithms.
Pornography Web Site Identification Based on User Behavior Analysis
Cao Jianxun, Liu Yiqun, Cen Rongwei, Ma Shaoping, and Ru Liyun
2013, 50(2):  430-436. 
Asbtract ( 974 )   HTML ( 7)   PDF (1445KB) ( 1468 )  
Related Articles | Metrics
The problem of illegal Web resources, especially pornography sites, poses a major challenge for Webrelated applications. Due to the significant differences in page content, site structure and visitors, user behavior patterns on pornography Web sites and ordinary Web sites can be separated from each other. With the help of a popular commercial search engine in China, large scale user behavior data is collected and it is found that when users surf in porn sites, their behaviors are significantly different from that when they are visiting ordinary Web sites. These differences in user behavior patterns can help us separate porn sites from other ones. A number of behavior features are proposed and combined with machine learning algorithms to develop a porn site identification method. Experimental results show effectiveness of the proposed method.
WSD Method Based on Heterogeneous Relation Graph
Yang Zhizhuo and Huang Heyan
2013, 50(2):  437-444. 
Asbtract ( 632 )   HTML ( 3)   PDF (1071KB) ( 647 )  
Related Articles | Metrics
As one of the most important problems in natural language processing, word sense disambiguation (WSD) aims to identify the intended meaning (sense) of words in context. Traditional knowledge-based WSD methods usually leverage only one sort of knowledge (semantic or co-occurrence relationships) but ignore the complementarity between different types for disambiguation. To deal with this problem, this paper proposes a novel WSD model using heterogeneous relation graph. Based on the reconstruction of traditional graph-based WSD model, different kinds of knowledge are naturally incorporated. Furthermore, since not all types of knowledge play an equally important role in WSD, an automatic parameter estimation method is designed and implemented to optimize the disambiguation effect by estimating the weight of various kinds of relations. The parameter estimation algorithm is adapted based on simulated annealing algorithm. The proposed WSD model is unsupervised. It can make full use of multi-source knowledge and alleviate the data sparseness and knowledge acquisition problems. The model is evaluated on a standard multilingual Chinese English lexical task (SemEval-2007), and the results indicate that the proposed method could significantly outperform the baseline method. Moreover, the proposed model also performs better than the best participating system in the evaluation.
Similarity Analysis of RNA Secondary Structure with Symbolic Dynamics
Tian Fengchun, Wang Shiyuan, Wang Jia, and Liu Xiao
2013, 50(2):  445-452. 
Asbtract ( 669 )   HTML ( 3)   PDF (1693KB) ( 594 )  
Related Articles | Metrics
Based on the principle of symbolic dynamics, a novel graphical representation of RNA secondary structures is proposed. The free bases and paired bases in RNA secondary structures are mapped into two kinds of discrete time sequences by considering the biological information in free bases and free energy in paired bases, respectively. With no loss of information in the transfer of data from RNA secondary structures to their mathematical representation, the proposed graphical representation can also identify the paired regions of RNA in 2D graph, clearly. Based on this graphical representation, the characteristic matrices are constructed, and a vector consisting of the leading eigenvalues of these matrices are then designed for comparison of RNA secondary structures. In time and frequency domains, quantitative and qualitative analysis are performed to distinguish a set of RNA secondary structures at the 3′-terminus of different viruses, and similar results are acquired in the two domains. The examination of similaritiesdissimilarities illustrates the utility of the proposed graphical representation. Compared with other methods for similarity analysis, this proposed method can obtain the larger numerical difference between the dissimilar species and the similar ones, which will help to discriminate different species more easily.