Table of Content

10 July 2016, Volume 36 Issue 7

Previous Issue    Next Issue

Admission control of media delivery network based on software defined network

CAO Hao, YIN Baoqun, CAO Jie, LU Xiaonong

2016, 36(7):  1767-1771.  DOI: 10.11772/j.issn.1001-9081.2016.07.1767

Asbtract ( )   PDF (957KB) ( )  

References | Related Articles | Metrics

Focusing on the admission control problems of media delivery network in Software Defined Network (SDN), an admission control scheme of comprehensively optimizing the service performance of service nodes and transmission links was proposed. The proposed scheme used SDN controller's abilities of directly controlling routers and perception of entire network, to jointly optimize the service performance of the service nodes on the application layer and the transmission links between the service nodes and the users on the network layer, and the influences of link congestion to data transmission and quality of service were reduced. Firstly, the admission control process of the SDN service system was modeled as a Partially Observable Markov Decision Process (POMDP). Secondly, the observation-based randomized policy was used as the admission control policy of the system. Finally, the policy-gradient algorithm was used to optimize the admission control policy, and the optimal policy of the model was obtained. The simulation results show that, compared with the best effort service policy, the POMDP-based optimal admission control policy improves system performance by 10%, which illustrates the effectiveness of the proposed approach.

Intelligent update method for flow table in switch through analyzing data flow characteristics

JIANG Lili, ZENG Guosun, DING Chunling

2016, 36(7):  1772-1778.  DOI: 10.11772/j.issn.1001-9081.2016.07.1772

Asbtract ( )   PDF (1117KB) ( )  

References | Related Articles | Metrics

To address the low matching rate of flow table, an intelligent update method for flow table in Software Defined Network (SDN) switch was proposed. First, the impact of timeout value on the packet matching was described, besides, the shortcomings of First In First Out (FIFO), Least Recently Used (LRU) and other common methods were analyzed and compared. Secondly, based on the reality of survival time of the flow entry related closely to the characteristics of data flow, the Hidden Markov Model (HMM)-based Deep Flow Inspection (DFI) technology was used to classify the data flow. Finally, according to the condition of the flow table resources and controller's computing resources, the intelligent update of the flow entry of different type of data flow was realized. The simulation experiments conducted on data center behavior data of real campus indicate that the proposed method can improve more than 5% of the matching rate compared with the common methods, and it has a practical significance to the management of the SDN switch.

M/G/1 queuing model under nonpreemptive limited-priority

HUANG Yewen, KUANG Shenfen, YANG Rongling, YANG Chunxia

2016, 36(7):  1779-1783.  DOI: 10.11772/j.issn.1001-9081.2016.07.1779

Asbtract ( )   PDF (847KB) ( )  

References | Related Articles | Metrics

Concerning the network congestion risk of computer network service system for some data frames having a full priority of transmission, a method about nonpreemptive limited-priority M/G/1 queuing system model was proposed. Firstly, as the parameter n of limited-priority was introduced into the model, the data frame with full priority was converted to the one with limited priority. Secondly, in order to lower the risk of computer network service system and stabilize the network system further, the fairness among different priorities was studied in the model. Moreover, by making use of total probability theorem, three results of the models, the average waiting time, the average dwelling time and the average queue length were obtained. Simulation under Matlab 2010a showed that, the mean absolute error between average waiting time and theoretical formula results at all levels of queue, was just 0.951%. In the experiment, the average waiting time ratio with limited-priority was significantly smaller than the average waiting time ratio with full priority at all levels of queue. The experimental results show that the theoretical results, which use the nonpreemptive limited-priority M/G/1 queuing system model, are correct; besides, the model is more stable than the others.

Flow scheduling cost based congestion control routing algorithm for data center network on software defined network architecture

SUN Sanshan, WANG Shuai, FAN Zifu

2016, 36(7):  1784-1788.  DOI: 10.11772/j.issn.1001-9081.2016.07.1784

Asbtract ( )   PDF (797KB) ( )  

References | Related Articles | Metrics

To alleviate the congestion of traditional data center network, the flow scheduling cost based congestion control routing algorithm on Software Defined Network (SDN) architecture was proposed. Firstly, the maximum flows and minimum flows on congestion links were differentiated. Secondly, the cost of each equivalent route for maximum flows was calculated, and the routes with minimum cost were selected as available scheduling routes for maximum flows. Then, the flow scheduling cost of each available scheduling route was defined by considering the cost change of rerouting operation and the occupancy ratio of bandwidth together. Finally, the maximum flows with minimum scheduling cost were scheduled to related available scheduling routes. The experimental results show that, the proposed algorithm is qualified to reduce the load of congestion links when network congestion occurs. Moreover, compared with the previous congestion control algorithm which taking into account the flow route selection only, the proposed algorithm improves the link utilization and reduces the transmission time of flow, which make the network link resources to be better used.

Invulnerability analysis of vehicular Ad Hoc network based on complex network

FENG Huifang, LI Caihong

2016, 36(7):  1789-1792.  DOI: 10.11772/j.issn.1001-9081.2016.07.1789

Asbtract ( )   PDF (791KB) ( )  

References | Related Articles | Metrics

Concerning the problem of invulnerability in Vehicular Ad Hoc NETwork (VANET), the invulnerability characteristics for VANET under random attacks and intentional attacks were analyzed. Firstly, the largest connected component, average size of components, critical point removal ratio as well as network efficiency were proposed to be used for the invulnerability evaluation metrics for VANET. Then, based on intelligent driver model with lane changes, the VANET was established through VanetMobisim software. Finally, the influence of the number of nodes, transmission ranges and patterns of attack on VANET invulnerability were given. The experimental results show that the VANET has a strong invulnerability faced with random attacks while its invulnerability to intentional attacks is fairly low as a result of the uneven degree distribution of vehicles; the intentional attacks based on node betweenness destroy the networks more quickly and strongly. The derived rules can provide the optimization of VANET topology control, protocol development and network management with new guidance.

Parallel algorithm for massive point cloud simplification based on slicing principle

GUAN Yaqin, ZHAO Xuesheng, WANG Pengfei, LI Dapeng

2016, 36(7):  1793-1796.  DOI: 10.11772/j.issn.1001-9081.2016.07.1793

Asbtract ( )   PDF (595KB) ( )  

References | Related Articles | Metrics

Concerning the problems of low efficiency and less processing points of the traditional algorithm for point cloud simplification, according to the slicing principle in the rapid prototyping with feature-preserving and low computational complexity, a parallel slicing algorithm was designed and implemented for more than ten millions point cloud of Light Detection And Ranging (LiDAR) data. The point cloud model was layed with the slicing principle and every layer was sorted according to the angle. Incorporating the parallel computation framework of Compute Unified Device Architecture (CUDA) proposed by NVIDA and taking the highly parallel performance advantages of the programmable Graphics Processing Unit (GPU), and parallel execution of the single slice point cloud simplification with the multi-thread of GPU was done, which improved the algorithm efficiency. Finally, a comparing experiment was done with three groups of point cloud data in different order of magnitudes. The experimental results show that the efficiency of the proposed algorithm has 1-2 order of magnitude higher than that of traditional algorithm under the condition of keeping the model characteristics and not changing the compression ratio.

Fast deduplication for massive images

HAN Fengqing, SONG Zhijian, YU Rui

2016, 36(7):  1797-1800.  DOI: 10.11772/j.issn.1001-9081.2016.07.1797

Asbtract ( )   PDF (568KB) ( )  

References | Related Articles | Metrics

To solve the problem of low efficiency for fast deduplicating the same image in massive images, a parallel deduplication technology for massive images based on image features was proposed. Firstly, the image color, texture, shape and other features were extracted to fully represent images. Secondly, the metric was used to calculate the distance between images. Finally, according to these distances, the same image could be fast located and deduplicated by the thought that the two points might be the same point if they had same distance to any other point. It has been analyzed and verified in combination with the experimental data that this technology is accurate in deduplicating images, besides, it just needs 10 minutes to deal with 5 million images by one computer with i5 processor. Compared with one by one calculation, the technology improves the efficiency of massive image deduplication and can shorten the calculation time.

Parallel design and implementation of scale invariant feature transform algorithm based on OpenCL

XU Chuanpei, WANG Guang

2016, 36(7):  1801-1806.  DOI: 10.11772/j.issn.1001-9081.2016.07.1801

Asbtract ( )   PDF (966KB) ( )  

References | Related Articles | Metrics

The real-time performance of Scale Invariant Feature Transform (SIFT) algorithm is excessively bad. To solve the problem, a parallel optimized SIFT algorithm using the Open Computing Language (OpenCL) was proposed. Firstly, all steps of the original algorithm were split and combined; in addition, the indexing method of feature points in memory was restructured. Thus the middle calculation results could be made completely to finish interaction in the memory. Then, each step of the original algorithm was designed in parallel to improve the efficiency of data reading and reduce the transmission delay by multiplexing global memory object, sharing local memory and optimizing memory access. Finally, a fine-grained parallel accelerated SIFT algorithm was completed on Graphics Processing Unit (GPU) platform using OpenCL and the transplant was completed on the Central Processing Unit (CPU) platform. The parallel algorithm speeded up 10.51-19.33 and 2.34-4.74 times in feature extraction on GPU and CPU platform when the registration result was close to the original algorithm. The experimental results show that the parallel accelerated SIFT algorithm using OpenCL can improve the real-time performance of image registration and overcome the disadvantages of that Compute Unified Device Architecture (CUDA) is difficult to be transplanted so that it can not make full use of the multiple computing cores in heterogeneous systems.

Improved method of transcendental function piecewise linear approximation

TIAN Zheng, DU Huimin, HUANG Xiaokang

2016, 36(7):  1807-1810.  DOI: 10.11772/j.issn.1001-9081.2016.07.1807

Asbtract ( )   PDF (568KB) ( )  

References | Related Articles | Metrics

When the transcendental function is used in the calculation of the piece-wise linear approximation algorithm, the accuracy can not be determined in advance and part of interval resources are wasted. In order to solve the problems, an improved piece-wise linear approximation algorithm of transcendental function was proposed. The proposed algorithm calculated a linear approximation function with predefined interval endpoints and adjusted the function by the concave of the function to be approximated and then calculated the maximum error between the function adjusted and the function to be approximated. The approximation intervals would be adjusted automatically based on the precision requirement and a fewer number of segments would be obtained by such iterative process. The proposed algorithm was simulated in Matlab. The simulation results show that the number of segments of the proposed algorithm is reduced by 60% compared with the equal division method. Thus, the proposed algorithm can reduce the resource consumption of the Look Up Table (LUT) greatly on the premise of guaranteeing accuracy.

Diversified malware detection framework toward cloud platform

GAO Chao, ZHENG Xiaomei, JIA Xiaoqi

2016, 36(7):  1811-1815.  DOI: 10.11772/j.issn.1001-9081.2016.07.1811

Asbtract ( )   PDF (949KB) ( )  

References | Related Articles | Metrics

In recent years, physical and virtual machines are heavily threatened by malwares. Deploying traditional detection tools such as anti-virus softwares and firewalls on Infrastructure as a Service (IaaS) cloud faces the following problems:1) detection tools may be damaged or shut down by malwares; 2) the detection rate of a single tool is insufficient; 3) detection tools are easily bypassed; 4) it's difficult to deploy additional softwares in each virtual machine. A diversified malware detection framework was proposed to overcome these shortcomings. The framework leveraged virtualization technology to intercept some specific behavior of virtual machines at first. Then codes from virtual machines' memory were extracted dynamically. Finally, several anti-virus softwares were used to codetermine whether the extracted codes were malicious or not. The extraction and judgment processes were totally transparent to virtual machines. A prototype was implemented based on the Xen hypervisor and some experiments were done. The prototype has a malware detection rate of 85.7%, which is 14.3 percentage points higher than static anti-virus softwares. The experimental results show that the diversified malware detection framework on cloud platform can provide more effective protection to the security of virtual machines.

Efficient public auditing scheme for cloud storage supporting user revocability with proxy re-signature scheme

ZHANG Xinpeng, XU Chunxiang, ZHANG Xinyan, SAI Wei, HAN Xingyang, LIU Guoping

2016, 36(7):  1816-1821.  DOI: 10.11772/j.issn.1001-9081.2016.07.1816

Asbtract ( )   PDF (927KB) ( )  

References | Related Articles | Metrics

Due to user revocability, the new data manager needs to verify the integrity of the former data manager's management data stored in the cloud server, which is obviously inevitable in reality. In order to solve this issue, an efficient privacy-preserving public auditing scheme for cloud storage scheme was proposed. Firstly, in the proposed scheme based on unidirectional proxy re-signature, the proxy re-signature key was generated by the current data manager's private key and the former public key, which did not leak any information, to realize transferring of ownership data caused by the users revocability securely. Secondly, it was proved that the proposed scheme could protect any malicious cloud server from generating the forged response proof which could pass the verification to cheat the Third Party Auditor (TPA). Moreover, the random masking technique was employed to prevent the curious TPA from revealing the primitive data blocks. Compared with the Padna scheme, even though the proposed scheme adds the new functions but its communication overhead in the process of auditing and computational cost are also lower than Panda's.

Ciphertext-policy attribute-based encryption scheme in hybrid clouds

CHEN Liang, YANG Geng, TU Yuanfei

2016, 36(7):  1822-1827.  DOI: 10.11772/j.issn.1001-9081.2016.07.1822

Asbtract ( )   PDF (901KB) ( )  

References | Related Articles | Metrics

Focusing on inefficient data security and access control in the existed cloud storage, which results in sensitive information to be stolen, combined with the existed Ciphertext-Policy Attribute-Based Encryption (CP-ABE) and data partition,an efficient data privacy protection model based on the hybrid cloud was proposed. First of all, according to the data sensitive degree, the data were divided into data blocks based on different sensitivity levels, and then data blocks were stored on different cloud platforms. According to the security level of the data, data were encrypted by using the different intensity encryption technologies. At the same time, the scheme of "first match after decryption" was adopted in the decryption stage and the algorithm was optimized. Finally, user decrypted ciphertext by the multiplication. Compared with the single node algorithm, for encrypting 1 Gb data, the efficiency of symmetric encryption algorithm more than doubled in the public clouds. The experimental results show that the proposed scheme can protect the privacy data of cloud storage user, reduces the system cost and improves the system flexibility.

Mobile cloud storage-oriented attribute based decryption service middleware

CAI Mengfei, HE Qian, CHEN Dongsheng, WANG Shicheng

2016, 36(7):  1828-1833.  DOI: 10.11772/j.issn.1001-9081.2016.07.1828

Asbtract ( )   PDF (896KB) ( )  

References | Related Articles | Metrics

The Attribute Based Encryption (ABE) algorithm can support fine grained access control for cloud data. Concerning the problems that the ABE decryption has huge complexity and is difficult to realize on resource constrained mobile device, a mobile cloud storage-oriented attribute based decryption service middleware was proposed and realized. Without getting the information about the encrypted data, the middleware could delegate the ABE decryption service, a tree-based Linear Secret Sharing Scheme (LSSS) matrix solution was realized, and so the computation and communication cost of the mobile terminal were decreased. Accordingly, the decryption speed was improved. The attribute authority could revoke the user attributes through this middleware instantly with fine-grained control without involving any users. All the services were defined as Restful interface and then the generality of the middleware was ensured. The experimental results show that the middleware improves attribute based decryption performance nearly 30 times, and it has good parallel performance and practical attribute revoking capability.

Specification and verification method for security policy in multi-domain cloud systems

CAI Ting, CAI Yu, OUYANG Kai

2016, 36(7):  1834-1840.  DOI: 10.11772/j.issn.1001-9081.2016.07.1834

Asbtract ( )   PDF (1108KB) ( )  

References | Related Articles | Metrics

To effectively manage the enforcement of secure policies during the cross-domain interoperation among cloud systems, a management technique applied for the verification of multi-domain cloud policies was proposed. First, both the access control policies and security properties under secure inter-operation environments were studied, the intra-domain administration was distinguished from inter-domain administration according to role hierarchies, and a multi-domain Role Based Access Control (domRBAC) model and specifications for the security properties based on Computation Tree Logic (CTL) were formally defined. Next, a role-to-role mapping algorithm derived from the graph theory was proposed, to depict the reasoning for domRBAC hierarchies, and a verification algorithm of security policies for cloud systems was further constructed. The simulation results show that, the time cost of security policy verification for multi-domains increases with the expansion of the size of the system. Multi-process parallel detection mode can reduce the time of policy verification from 70.1% to 88.5%, and compared to the normal mode, the model optimized detection mode fluctuates smaller in time lines, and the time overhead is significantly lower for large-scale systems. Therefore, the proposed technique has stable performance and high efficiency to be used in secure interoperation of large-scale cloud systems.

Auto-download behavior detection

HUANG Jikun, GONG Weigang, YOU Wei, QIN Bo, SHI Wenchang, LIANG Bin

2016, 36(7):  1841-1846.  DOI: 10.11772/j.issn.1001-9081.2016.07.1841

Asbtract ( )   PDF (903KB) ( )  

References | Related Articles | Metrics

Nowadays, many malicious Web pages can launch the downloading of malware without any user interaction only by leveraging normal Web programming techniques and deceive victims into executing the downloaded malware. This type of attack is called auto-download. The existing defense mechanisms equipped with browsers can not effectively identify the attack. In order to solve the problem, an approach was presented to mitigate the attack. The downloading operations were monitored. When a download was performing, it would be checked to see whether it was triggered by the user interaction or not. Consequently, potential auto-download behaviors would be detected and terminated. The approach had been implemented in two browsers WebKitGtk+2.8.0 and Chromium 38.0.2113.1. Both of the two detection and defense systems were evaluated. The false negatives and false positives were 0, and performance overload was 1.26% and 7.79%. The experimental results show that the proposed approach can effectively detect and terminate the auto-download attack with less performance overload.

Audit log association rule mining based on improved Apriori algorithm

XU Kaiyong, GONG Xuerong, CHENG Maocai

2016, 36(7):  1847-1851.  DOI: 10.11772/j.issn.1001-9081.2016.07.1847

Asbtract ( )   PDF (771KB) ( )  

References | Related Articles | Metrics

Aiming at the problem of low-level intelligence and low utilization of audit logs of the security audit system, a secure audit system based on association rule mining was proposed. The proposed system was able to take full advantage of the existing audit logs and establish the behavior pattern database of users and the system with data mining technique. The abnormal situation was discovered in a timely manner and the security of computer system was improved. An improved E-Apriori algorithm was proposed which could narrow the scanning range of the set of transactions, lower the time complexity, and refine the operating efficiency. The experimental results indicate that the lift of recognition capability to identify the type of attack can reach 10% in the secure audit system based on association rule mining, the proposed E-Apriori algorithm clearly outperforms the traditional Apriori algorithm and FP-GROWTH algorithm, and the maximum increase can reach 51% especially in the large sparse datasets.

Protection method for global offset table based on address randomization and segment isolation

LIN Jian, GUO Yudong, ZHOU Shaohuang

2016, 36(7):  1852-1855.  DOI: 10.11772/j.issn.1001-9081.2016.07.1852

Asbtract ( )   PDF (771KB) ( )  

References | Related Articles | Metrics

In an Executable and Linkable Format (ELF) executable program, Global Offset Table (GOT) was used to store the absolute addresses of library functions. But in Linux operation system, GOT dereference and GOT overwrite are two common vulnerability exploit methods. Through analyzing the GOT feature, a protection method for GOT based on address randomization and segment isolation was proposed and implemented. With modifying the ELF loader program, all sections which pointed to the GOT were loaded into random memory addresses. Using segment isolation technology, all instructions with reference to GOT used a new segment register. The experimental results prove that the proposed method can not only defense against the exploit method of GOT effectively, but also has a very low cost of average 2.9 milliseconds.

GSW-type hierarchical identity-based fully homomorphic encryption scheme from learning with errors

DAI Xiaoming, ZHANG Wei, ZHENG Zhiheng, LI Zhenlin

2016, 36(7):  1856-1860.  DOI: 10.11772/j.issn.1001-9081.2016.07.1856

Asbtract ( )   PDF (779KB) ( )  

References | Related Articles | Metrics

Focusing on the function defect of the traditional Identity-Based Encryption (IBE) scheme that the ciphertexts can not be calculated directly, a new IBE scheme was proposed. The homomorphism transformation mechanism proposed by Gentry was used to transform the hierarchical IBE scheme proposed by Agrawal into a homomorphic hierarchical IBE scheme. Compared with the GSW (Gentry, Sahai, Waters) scheme (GENTRY C, SAHAI A, WATERS B. Homomorphic encryption from learning with errors:conceptually-simpler, asymptotically-faster, attribute-based. CRYPTO 2013:Proceedings of the 33rd Annual Cryptology Conference on Advances in Cryptology. Berlin:Springer, 2013:75-92) and CM (Clear, Mcgoldrick) scheme (CLEAR M, MCGOLDRICK C. Bootstrappable identity-based fully homomorphic encryption. CANS 2014:Proceedings of 13th International Conference on Cryptology and Network Security. Berlin:Springer, 2014:1-19), the construction method of the proposed scheme was more natural, the level of space complexity was reduced from cubic to square with higher efficiency. In the current environment of cloud computing, the proposed scheme can contribute to the transformation from theory to practice of fully homomorphic encryption scheme based on Learning With Errors (LWE) problem. The performance analysis and the verification results under the random oracle model prove the security for Indistinguishability of the Identity-Based Encryption Scheme under Chosen-Plaintext Attack (IND-ID-CPA) of the proposed scheme.

Identity based ring signature scheme in ideal lattice

SUN Yiru, LIANG Xiangqian, SHANG Yufang

2016, 36(7):  1861-1865.  DOI: 10.11772/j.issn.1001-9081.2016.07.1861

Asbtract ( )   PDF (889KB) ( )  

References | Related Articles | Metrics

The existing signature schemes based on bi-linear pairings were proved to be insecure in quantum computing environment. A lattice has the features of simple computational operations and difficult problems on which are hard to solve. In order to resist the quantum attack, an identity based ring signature scheme was presented based on the assumption of the hardness of lattice problem-Small Integer Solution (SIS), and it was provably secure in the standard model by using the Ducas' ideal lattice technology (DUCAS L, MICCIANCIO D. Improved short lattice signatures in the standard model. Proceedings of the 34th Annual Cryptology Conference on Advances in Cryptology. Berlin:Springer, 2014:335-352). The scheme was mainly divided in to four steps:master key generation algorithm, the signature private key generation algorithm, signature algorithm and validation algorithm. The signature was output as a single vector. Compared to the same type signature schemes, to some extent, the proposed scheme shortens the length of private key, public key and the signature, improves the operation efficiency, in addition, it is also suitable for lightweight authentication, and the security of electronic commerce and cloud computing are indirectly ensured by the security of the signature algorithm.

Secure outsourcing algorithm of bilinear pairings with single server

JIANG Tiejin, REN Yanli

2016, 36(7):  1866-1869.  DOI: 10.11772/j.issn.1001-9081.2016.07.1866

Asbtract ( )   PDF (546KB) ( )  

References | Related Articles | Metrics

Bilinear pairings computation is one of the basic operations of public key cryptography algorithm, which is widely used in the identity-based encryption and attributed-based encryption schemes. However, all of the efficient outsourcing algorithms of bilinear pairings are based on two untrusted servers, which is difficult to be realized in practical applications. In order to solve the problem, a secure outsourcing algorithm of bilinear pairings with single server was proposed. The input of users' device was took for blind treatment, which could protect the input and output confidentiality and verify the correctness of the server output by a small amount of pre-computations. The experimental results show that the proposed algorithm reduces the computation of the users' device just by several point additions and multiplications, and its verifiability probability is 2/5. Compared with the previous schemes, the proposed scheme is based on one single untrusted server and easier to be realized in reality.

Mutation fruit fly optimization algorithm based on adaptive dynamic step size

WANG Xingfu, CHEN Jing, WANG Lin

2016, 36(7):  1870-1874.  DOI: 10.11772/j.issn.1001-9081.2016.07.1870

Asbtract ( )   PDF (768KB) ( )  

References | Related Articles | Metrics

The basic Fruit Fly Optimization Algorithm (FOA) has the shortcomings of being easy to fall into local optimal value, slow convergence and low convergence accuracy. Aiming at the problems, a Mutation Fruit Fly Optimization Algorithm Based on Adaptive Dynamic Step Size (MFOAADS) was proposed. Firstly, the selection of the initial position of the population was improved using the optimal point set method, which reduced the randomness of initial point selection and the probability of getting trapped in local optimal value. Secondly, the adaptive dynamic step size optimization strategy was adopted to improve the convergence rate and the accuracy of the solution. Finally, if the algorithm fell into premature convergence, the Cauchy mutation perturbation would be utilized in a certain probability for the sake of making them jump out of local optimum. The test results of the five classical functions showed that convergence accuracy and convergence speed of MFOAADS were obviously superior to the FOA when the number of iterations was fixed. And in the comparison experiments with FOA, the average number of iterations of MFOAADS decreased significantly with a success rate of more than 97% when target accuracy was fixed. The experimental results show that, compared with the basic FOA, the proposed algorithm significantly improves the accuracy, efficiency and reliability.

Info-association topology based social relationship mining on Internet

LIU Jinwen, XING Kai, RUI Weikang, ZHANG Liping, ZHOU Hui

2016, 36(7):  1875-1880.  DOI: 10.11772/j.issn.1001-9081.2016.07.1875

Asbtract ( )   PDF (1000KB) ( )  

References | Related Articles | Metrics

To solve the problems of needing labeling a great number of training data and pre-defining relation types in relation extraction methods based on supervised learning, a method for personal relation extraction by constructing the correlation network based on word co-occurrence information and performing graph clustering analysis on the correlation network was proposed. Firstly, 500 highly related person pairs for the research of relation extraction were gotten from the news title data. Secondly, the news data which contained related person pairs were crawled and performed pre-processing, and the keywords in the sentences which contained person pairs were gotten by the Term Frequency-Inverse Document Frequency (TF-IDF). Thirdly, the correlation between the words was acquired by the words co-occurrence information, and the key-words correlation network was constructed. Finally, the personal relations were acquired by the graph clustering analysis on the correlation network. In the relation extraction experiments, compared with the traditional algorithm of Chinese relation extraction based on word co-occurrence and pattern matching technology, the precision, recall and F-score of the proposed method were improved by 5.5, 3.7 and 4.4 percentage points respectively. The experimental results show that the proposed algorithm can effectively extract abundant and high-quality personal relation data from news data without labeling training data.

Entity alignment of Chinese heterogeneous encyclopedia knowledge base

HUANG Junfu, LI Tianrui, JIA Zhen, JING Yunge, ZHANG Tao

2016, 36(7):  1881-1886.  DOI: 10.11772/j.issn.1001-9081.2016.07.1881

Asbtract ( )   PDF (1027KB) ( )  

References | Related Articles | Metrics

Aiming at the problem that the traditional entity alignment algorithm may lead to bad performance in entity alignment task of Chinese heterogeneous encyclopedia knowledge base, an entity alignment method based on entity attributes and the features of context topics was proposed. First, a Chinese heterogeneous encyclopedia knowledge base was constructed based on Baidu encyclopedia and Hudong encyclopedia data. Next, the Resource Description Framework Schema (RDFS) vocabulary list was made to normalize the entity attributes. Then the entity context information was extracted and the Chinese word segmentation was used on the contexts. The contexts were modelled by using the topic model and the parameters were computed by Gibbs sampling method. After that the topic-word probability matrix, the characteristic word collection and the corresponding feature matrix were calculated. Last, the Longest Common Subsequence (LCS) algorithm was used to compute the entity attribute similarity. When the similarity was between the lower and the upper bounds, the topic features of the entities' context were combined to resolve the entity alignment problem. Finally, according to the standard method, an entity alignment data set of Chinese heterogeneous encyclopedia was constructed for simulation experiments. In comparison with the traditional property similarity algorithm, weighted-property algorithm, context term frequency feature model and topic model algorithm, the experimental results show that the proposed method achieves 97.8% accuracy, 88.0% recall, 92.6% F-score in people class and 98.6% accuracy, 73.0% recall, 83.9% F-score in movie class. It outperformed the other entity alignment algorithms. The experimental results also indicate that the proposed method can improve the entity alignment results in constructing the Chinese heterogeneous encyclopedia knowledge base, and it can be applied to the entity alignment tasks with context information.

Twitter text normalization based on unsupervised learning algorithm

DENG Jiayuan, JI Donghong, FEI Chaoqun, REN Yafeng

2016, 36(7):  1887-1892.  DOI: 10.11772/j.issn.1001-9081.2016.07.1887

Asbtract ( )   PDF (945KB) ( )  

References | Related Articles | Metrics

Twitter messages contain a large number of nonstandard tokens, created unintentionally or intentionally by people. It is crucial to normalize the nonstandard tokens for various natural language processing applications. In terms of the existing normalization systems which perform poorly, a novel unsupervised normalization system was proposed. First, a standard dictionary was used to determine whether a tweet needs to be normalized or not. Second, a nonstandard token was considered to take 1-to-1 or 1-to-N recovering based on its characteristics. For 1-to-N recovering, the nonstandard token would be divided into multiple possible words using forward and backward search. Third, some normalization candidates were generated for nonstandard tokens among multiple possible words by integrating random walk and spelling checker. Finally, the best normalized twitter could be obtained by taking all the candidates into consideration of n-gram language model. The experimental results on the manual dataset show that the proposed approach obtains F-score of 86.4%, which is 10 percentage points higher than that of current best graph-based random walk algorithm.

Distributed Rete algorithm in smart environment

WANG Chengliang, WEN Xin

2016, 36(7):  1893-1898.  DOI: 10.11772/j.issn.1001-9081.2016.07.1893

Asbtract ( )   PDF (942KB) ( )  

References | Related Articles | Metrics

Concerning the problem that rule-based inference engine in smart environment needs to centralize data to sink node resulting in excessive data transmission in sensor network, a Minimum Transmission Cost of Rete Distribution Scheme algorithm (MCoRDS) based on Rete network cost model was proposed. Through the dependence statistics of sub-rule patterns in Rete Network on fact data, it was found that many sub-rule patterns could be reasoned nearby the source data collected sensor. Data transmission to sink node could be cut down and the data transmission of whole sensor network was decreased by distributing sub-rule patterns of Rete network into the sensor which firstly collected all the source data for it. Compared to centralized inference which places the Rete network in the sink node, 4 experiments were conducted. In the 4th experiment, total sensor network hops was reduced from 85000 to 8036, about 90.5% reduction, the other experiments had some reduction too. The experimental results show that MCoRDS has lower data transmission, especially in the case of large-scale rules and low frequency rule trigger.

Web spam detection based on immune clonal feature selection and under-sampling ensemble

LU Xiaoyong, CHEN Musheng, WU Jhenglong, CHANG Peichan

2016, 36(7):  1899-1903.  DOI: 10.11772/j.issn.1001-9081.2016.07.1899

Asbtract ( )   PDF (808KB) ( )  

References | Related Articles | Metrics

To solve the problem of "curse of dimensionality" and imbalance classification, a binary classifier algorithm based on immune clonal feature selection and Under-Sampling (US) ensemble was proposed to detect Web spam. Firstly, major samples in training dataset were sampled into several sample subsets, which were combined with minor samples to generate several balanced training sample subsets. Then an immune clonal algorithm was proposed to select several optimal feature subsets. The balanced training subsets were projected to multiple views based on the optimal feature subsets. Finally, several Random Forest (RF) classifiers were trained by these views of the training sample subsets to classify the testing samples. The testing samples' classifications were determined by voting. The experimental results on the WEBSPAM UK-2006 dataset show that the ensemble classifier algorithm outperforms these algorithms like RF, Bagging with RF and AdaBoost with RF, and its accuracy, F1-Measure, AUC (Area Under ROC Curve) are increased by more than 11% respectively. Compared with several state-of-the-art baseline classification models, the F1-Measure is increased by 2% and the AUC reaches the optimum result using the ensemble classifier.

Customer behavior prediction for card consumption based on two-step clustering and hidden Markov chain

SONG Tao, WANG Xing

2016, 36(7):  1904-1908.  DOI: 10.11772/j.issn.1001-9081.2016.07.1904

Asbtract ( )   PDF (786KB) ( )  

References | Related Articles | Metrics

Bank card payments account for a large proportion in the social consumption, which plays a major role in the promotion of economic growth. So, predicting consumer behavior is important. However, the traditional methods are difficult to effectively deal with complex data and dynamic changes. Based on this, a customer behavior prediction method for card consumption based on two-step clustering and Hidden Markov Chain (HMC) was presented. Firstly, consumer behaviors were conduced by pattern clustering based on sequence; then the secondary clustering was conducted by introducing penalty clustering, which carried out the equilibrium division of the hierarchical states in the sequential pattern. Secondly, HMC was used to estimate the state transition of consumption levels in the sequence and predict the future consumer behavior of the users. Finally, the experimental comparison and analysis results on the traditional clustering, clustering without penalty and clustering with penalty show that the proposed method based on two-step clustering and HMC is more suitable to the consumer behavior prediction model.

Modeling and simulating thermotaxis behavior of Caenorhabditis elegans based on artificial neural network

LI Mingxu, DENG Xin, WANG Jin, WANG Xiao, ZHANG Xiaomou

2016, 36(7):  1909-1913.  DOI: 10.11772/j.issn.1001-9081.2016.07.1909

Asbtract ( )   PDF (771KB) ( )  

References | Related Articles | Metrics

To research the thermal behavior of Caenorhabditis elegans (C.elegans), a new method was proposed to model and simulate the thermal behavior of C.elegans based on the artificial neural network. Firstly, the motion model of the nematode was established. Then, a nonlinear function was designed to approximate the movement logic of the thermotaxis of the nematode. Thirdly, the speed and the orientation change capabilities were implemented, and these capabilities had been realized by the artificial neural network. Finally, the experimental simulation was carried out in the Matlab environment, and the thermal behavior of the nematode was simulated. The experimental results show that Back Propagation (BP) neural network can simulate the thermal behavior of C.elegans better than Radical Basis Function (RBF) neural network. The experimental results also demonstrate that the proposed method can successfully model the thermal behavior of C.elegans, and reveal the essence of the thermotaxis of C.elegans to some extent, which theoretically supports the research on the thermotaxis of the crawling robot.

3D model retrieval algorithm based on curvedness feature

ZHOU Jilai, ZHOU Mingquan, GENG Guohua, WANG Xiaofeng

2016, 36(7):  1914-1917.  DOI: 10.11772/j.issn.1001-9081.2016.07.1914

Asbtract ( )   PDF (732KB) ( )  

References | Related Articles | Metrics

To improve the retrieval precision of 3D model with the complex surface, a new method based on curvedness feature was proposed. First, the sample points were obtained on the 3D model surface. The curvedness of these points was obtained by computing Gauss curvature and Mean curvature. The curvedness values showed properties of 3D model surface. Secondly, the centroid of the model was set as the center. The coordinate system in which two coordinate axes were the curvedness value and the Euclid distance between the random point and the center was constructed. The distribution matrix of curvedness feature was obtained by computing the statistical number of the sample points in the different Euclid distance. This distribution matrix was the feature descriptor of the 3D model. This descriptor had the property of rotation invariance and translation invariance, which could well reflect the geometric characteristics of complex surfaces. Finally, the similarity between different models was given by comparing the curvedness distribution matrix. The experimental results show that the proposed method can effectively improve the accuracy of the 3D model retrieval, especially suitable for those models with complex surfaces.

Image retrieval method based on new space relationship feature

GUO Qian, YANG Hongju, LIANG Xinyan

2016, 36(7):  1918-1922.  DOI: 10.11772/j.issn.1001-9081.2016.07.1918

Asbtract ( )   PDF (794KB) ( )  

References | Related Articles | Metrics

There is no clear space structure among images, so correlation information of images' space structure could not be utilized effectively. To tackle this problem, a new space relationship feature based image retrieval method was proposed. Firstly, feature vectors were extracted from all images which contain the queried image. And then, all of the every two feature vectors' similarities were calculated to form a similarity matrix. The set of similarity matrix's columns was taken as the new feature vector, namely the new space relationship feature vector, so the former feature vectors could be mapped into a Euclidean space. Finally, similarities were calculated on the new feature space. In this way, the problem of feature vectors' similarity was turned into the new space relationship feature vectors' similarity. The space structure among images was clearer than before on the new feature space, so the accuracy of image retrieval was improved. The experimental results on the Corel database show that the average retrieval precision, recall-precision and visual evaluation metric of the proposed method have advantage over the color histogram in the image retrieval task. The proposed image retrieval method based on the new space relationship feature sufficiently utilizes correlation information of images' space structure and it has better retrieval effect.

Improved feature points matching algorithm based on speed-up robust feature and oriented fast and rotated brief

BAI Xuebing, CHE Jin, MU Xiaokai, ZHANG Ying

2016, 36(7):  1923-1926.  DOI: 10.11772/j.issn.1001-9081.2016.07.1923

Asbtract ( )   PDF (626KB) ( )  

References | Related Articles | Metrics

Focusing on the issue that the Oriented fast and Rotated Brief (ORB) algorithm does not have scale invariance, an improved algorithm based on Speed-Up Robust Feature (SURF) and ORB was proposed. First, the feature points were detected by Hessian matrix, which made the extracted feature points have scale invariance. Second, the feature descriptors were generated by the ORB. Then the K-nearest neighbor algorithm was used for rough matching. Finally, the ratio test, symmetry test, the Least Median Squares (LMedS) theorem was used for purification. When the scale changed, the proposed algorithm's matching precision was improved by 74.3 percentage points than the ORB and matching precision was improved by 4.8 percentage points than the SURF. When the rotation changed, the proposed algorithm's matching precision was improved by 6.6 percentage points than the ORB. The proposed algorithm's matching time was above the SURF, below the ORB. The experimental results show that the improved algorithm not only keeps the rotation invariance of ORB, but also has the scale invariance, and the matching accuracy is improved greatly without decreasing the speed.

Quaternion wavelet transform for evaluation of image sharpness

WANG Zhiwen, LUO Xiaoqing, ZHANG Zhancheng

2016, 36(7):  1927-1932.  DOI: 10.11772/j.issn.1001-9081.2016.07.1927

Asbtract ( )   PDF (1213KB) ( )  

References | Related Articles | Metrics

The current image sharpness evaluation methods suffer from insufficient discrimination and monotonicity as well as the narrow applicable scope in the process of measurement. In order to solve the problems, an image sharpness evaluation method based on amplitude and phase of Quaternion Wavelet Transform (QWT) was proposed. The image was transformed into frequency domain from spatial domain by QWT, the amplitude and phase information of low frequency subband and high frequency subbands were got by further calculation of the QWT coefficients. After multiplication of the gradient of amplitude and corresponding directional phase, the proposed sharpness metrics were obtained by adding each direction's value together. The proposed sharpness metrics were conducted on the images with different content, degree of blur and degree of noise. Compared with the existing algorithms, the proposed algorithm has a fine monotonicity and discrimination for all kinds of images. The experimental results show that the proposed sharpness metrics not only overcome the shortcomings of the existing algorithms in the monotonicity and discrimination, but also can be applied to image processing.

Boundary points extraction method of planar point cloud based on multi-threshold

LIAO Zhongping, LIU Ke, XIANG Yu, CAI Chenguang

2016, 36(7):  1933-1937.  DOI: 10.11772/j.issn.1001-9081.2016.07.1933

Asbtract ( )   PDF (751KB) ( )  

References | Related Articles | Metrics

The method of point cloud reconstruction based on slicing technology needs to extract boundary points from slicing planar points. In order to solve the problem of extracting boundary points and overcome the drawback of low efficiency and bad result of current algorithms, a boundary points extraction method of planar point cloud based on multi-threshold was proposed. In the algorithm, k adjacent points were selected from the judged points, then the angle between the nearest points were calculated and the maximum angle was limited because there existed the biggest angle, thus the boundary points could be rapidly extracted. By analyzing the value of multi-threshold, testing the method to extract boundary points of different point cloud and comparing the proposed method with other three methods, the method accurately and better extracted boundary points regardless of the shapes. The experimental results show that the proposed method can well extract the boundary points on the condition of guaranteeing the original characteristic information and improves the speed and efficiency of point cloud reconstruction.

Intra mini-block copy algorithm for screen content coding

ZHAO Liping, LIN Tao, GONG Xunwei, ZHU Rong

2016, 36(7):  1938-1943.  DOI: 10.11772/j.issn.1001-9081.2016.07.1938

Asbtract ( )   PDF (985KB) ( )  

References | Related Articles | Metrics

Concerning the problem that existing Intra Bock Copy (IBC) algorithm is not well suitable to the screen content with a variety of different sizes and shapes of patterns, an Intra Mini-Block Copy (IMBC) algorithm was proposed to further improve coding efficiency of the screen content. Firstly, the Coding Unit (CU) was divided into a set of L mini-blocks. Secondly, each mini-block was taken as the smallest matching and replication unit, the reference mini-block which matched the mini-block best was found in the reference set R by a mini-block matching optimal selection strategy. And the location of the reference mini-block and its location in the current CU were specified by L Displacement Vectors (DVs). Finally, a prediction algorithm was firstly applied to the L DVs for eliminating the correlation between DVs before entropy encoding. Compared with the IBC algorithm, for the High Efficiency Video Coding (HEVC), Screen Content Coding (SCC) test sequences, IMBC achieved the BD-rate reduction up to 3.4%, 2.9%, 2.6% for All Intra (AI), Random Access (RA) and Low-delay B (LB) configurations in lossy coding respectively, and the Bit-rate saving up to 9.5%, 5.2%, 5.1% for AI, RA, LB configurations in lossless coding respectively. The experimental results show that IMBC algorithm can effectively improve the coding efficiency of screen image at very low additional encoding and decoding complexity.

Video super resolution method based on structure tensor

YAN Honghai, PU Fangling, XU Xin

2016, 36(7):  1944-1948.  DOI: 10.11772/j.issn.1001-9081.2016.07.1944

Asbtract ( )   PDF (996KB) ( )  

References | Related Articles | Metrics

The parameter of traditional regularized Super Resolution (SR) reconstruction model is difficult to choose:the higher parameter value results in blurred reconstruction and the fading of edge and detail, while the lower parameter value weakens the denosing ability. A double regularization parameters super resolution reconstruction method based on structure tensor was proposed. Firstly, smooth region and edge was detected by using local structure tensor. Secondly, the Total Variation (TV) was weighted with the priori information of difference curvature. Finally, two different parameters toward smooth region and edge were used to reconstruct super resolution image. The experimental data show that the proposed algorithm can improve the Peak Signal-to-Noise Ratio (PSNR) of 0.033-0.11 dB, and get better reconstruction results. The proposed algorithm can effectively improve the reconstruction effect of Low Resolution (LR) video frames, and can be applied to LR video enhancement, license plate recognition and the interest target enhancement in video surveillance, etc.

Multi-focus image fusion method based on image matting technique

ZHANG Shenglin, YI Benshun, LI Weizhong, LIU Hongyu

2016, 36(7):  1949-1953.  DOI: 10.11772/j.issn.1001-9081.2016.07.1949

Asbtract ( )   PDF (880KB) ( )  

References | Related Articles | Metrics

To solve the problem of information loss and obvious block effect in multi-focus image fusion, a novel multi-focus image fusion method based on image matting technique was proposed. Firstly, the rough focus information of each source image was obtained by focusing measure, all of which was used to generate the trimap of the fusion image, namely, foreground, background and unknown region. Secondly, according to the trimap, the precise focus region of each source image could be gotten by using the image matting. Finally, the obtained focus regions were combined to consist of new foreground and background. And the optimal fusion of the unknown region was conducted on the basis of the foreground and background, which enhanced the correlations between the nearby pixels of the three focusing regions. The experimental results show that compared with the traditional algorithms, the proposed algorithm can acquire higher Mutual Information (MI) and edge preservation on the objective evaluation. For the subjective evaluation, it can be seen that the block effect is obviously suppressed and the visual effect is more excellent. The proposed algorithm can be applied to the object identification and computer vision to obtain optimal fusion result.

Mesh layout algorithm based on greedy optimization strategy

LOU Ziting, ZHANG Yaping

2016, 36(7):  1954-1958.  DOI: 10.11772/j.issn.1001-9081.2016.07.1954

Asbtract ( )   PDF (959KB) ( )  

References | Related Articles | Metrics

Concerning low rendering performance of complex data sets which is caused by the limited memory bandwidth and data access speed, a triangle mesh layout algorithm based on greedy optimization strategy was proposed, by rearranging the triangle sequences to improve spatial locality and temporal locality of data. Firstly, the vertices were divided into three categories, according to the improved cost function, the vertex with the minimum cost was chosen as currently active vertex. Then, all adjacent triangles which were not rendered were output, and the neighbors were pushed into buffer. The above steps were executed iteratively until adjacent triangles of all vertices were rendered. Finally, the rearranged triangle sequence was got. The experimental results show that the proposed algorithm can provide a higher vertex cache hit ratio, improve the rendering speed, and reduce the execution time of the sorting, which can effectively solve the problem of data access speed lagging behind the processing speed of Graphics Processing Unit (GPU) seriously.

Static gesture recognition method based on locking mechanism

WANG Hongxia, WANG kun

2016, 36(7):  1959-1964.  DOI: 10.11772/j.issn.1001-9081.2016.07.1959

Asbtract ( )   PDF (981KB) ( )  

References | Related Articles | Metrics

The static gesture recognition speed is higher than that of dynamic gesture recognition for RGB-D (RGB-Depth) data, but redundancy gestures and repeated gestures lead to low recognition accuracy. In order to solve the problem, a static gesture recognition method based on locking mechanism was proposed. First, RGB data flow and the Depth data stream were obtained through Kinect equipment, then two kinds of data flow were integrated into human body skeleton data flow. Second, the locking mechanism was used to identify static gestures, and comparison and calculation were done with the established bone point feature model gesture library before. Finally, an "advanced programmers road" brain-training Web game was designed for application and experiment. In the experiments of six different movement gestures, compared with the static gesture recognition method, the average recognition accuracy of the proposed method was increased by 14.4%; compared with the dynamic gesture recognition method, the gesture recognition speed of the proposed method was improved by 14%. The experimental results show that the proposed method keeps the high speed of static recognition method, realizes the real-time recognition; and also improves the identification accuracy through eliminating redundant repeated gestures.

General method for gesture recognition in complex environment

DU Kun, TAN Taizhe

2016, 36(7):  1965-1970.  DOI: 10.11772/j.issn.1001-9081.2016.07.1965

Asbtract ( )   PDF (948KB) ( )  

References | Related Articles | Metrics

The methods for dealing with influence of light and complex background often consume large calculation and long time. To solve this problem, a general method of gesture recognition in complex environment was proposed. The proposed method was based on the binary Support Vector Machine (SVM) and bitwise operation instead of sliding window to achieve the goal of rapid screening, and then Compute Unified Device Architecture (CUDA) was used to build a convolutional neural network to re-judge the initial screen area. The proposed method does not rely on dynamic gesture recognition techniques, and can be used for both dynamic and static gesture recognition. The method can deal with the problem of illumination change and background interference. The experimental results show that compared with the methods based on sliding window, the computational efficiency is improved by 100 to 1000 times. It takes less than 0.01 s to process a picture. The experimental results on the modified Marcel data set show that its precision achieves 96.1% and recall achieves 100%. The proposed algorithm can be used for real-time hand gesture recognition under complex environment for its high performance.

Face recognition method based on uncertainty measurement combined with 3D features extraction using active appearance model

BU Yu, REN Xiaofang, TANG Xuejun, SUN Ting

2016, 36(7):  1971-1975.  DOI: 10.11772/j.issn.1001-9081.2016.07.1971

Asbtract ( )   PDF (750KB) ( )  

References | Related Articles | Metrics

Concerning the credibility problem of the classification results in face recognition, a face recognition method based on the theory of uncertainty was proposed. Firstly, in order to estimate 3D features, Active Appearance Model (AAM) and triangulation were used to process two 2D images of unknown object. Then, the score of each object in the database was estimated, and two images were further processed through uncertainty. Finally, the decision was made based on the estimated scores and the estimated uncertainty classification list. All identified objects and their corresponding credibilities were stored in the classification list. Stereo vision system with two cameras captures face images of various postures in the experiment. Compared with a similar probability forecasting measurement method, the correct detection rate of the proposed method was increased by 10%, and the false detection rate was reduced by at least 9%. The experimental results show that the classification accuracy is improved by constructing the uncertainty information of 3D image feature and adopting appropriate statistical method.

Pencil drawing rendering based on textures and sketches

SUN Yuhong, ZHANG Yuanke, MENG Jing, HAN Lijuan

2016, 36(7):  1976-1980.  DOI: 10.11772/j.issn.1001-9081.2016.07.1976

Asbtract ( )   PDF (853KB) ( )  

References | Related Articles | Metrics

Concerning the problem in pencil drawing generation that the pencil lines lack flexibility and textures lack directions, a method of combining directional textures and pencil sketches was proposed to produce pencil drawing from natural images. First, histogram matching was employed to obtain the tone map of the image, and an image was segmented into several regions according to color. For each region, tone and direction were computed by its color and its shape, to decide the final tone and direction of the pencil drawing. Then, an adjusted linear convolution was used to get the pencil sketches with certain randomness. Finally, the directional textures and sketches were combined to get the pencil drawing style. Different kinds of natural images could be converted to pencil drawings by the proposed method, and the renderings were compared with those of existing methods including line integral convolution and tone based method. The experimental results demonstrate that the directional texture can stimulate the manual pencil texture better and the adjusted sketches can mimic the randomness and flexibility of manual pencil drawings.

Clustering algorithm with maximum distance between clusters based on improved kernel fuzzy C-means

LI Bin, DI Lan, WANG Shaohua, YU Xiaotong

2016, 36(7):  1981-1987.  DOI: 10.11772/j.issn.1001-9081.2016.07.1981

Asbtract ( )   PDF (886KB) ( )  

References | Related Articles | Metrics

General kernel clustering only concern relationship within clusters while ignoring the issue between clusters. Misclassification easily occurs when clustering data sets with fuzzy and noisy boundaries. To solve this problem, a new clustering algorithm was proposed based on Kernel Fuzzy C-Means (KFCM) clustering algorithm, which was called Kernel Fuzzy C-Means with Maximum distance between clusters (MKFCM). Considering the relationship between within-cluster elements and between-cluster elements, a penalty term representing the distance between centers in feature space and a control parameter were introduced. In this way, the distance between clustering centers was broadened and the samples near boundaries were better classified. Compared with traditional clustering algorithms, the experiments results on simulated data sets show that the proposed algorithm reduces the offset distance of clustering centers obviously. On man-made Gaussian data sets, the ACCuracy (ACC), Normalized Mutual Information (NMI) and Rand Index (RI) of the proposed algorithm were improved to 0.9132, 0.7575 and 0.9138. The proposed algorithm shows its theoretical research significance on data sets with fuzzy and noisy boundaries.

Improved algorithm for mining collaborative frequent itemsets in multiple data streams

WANG Xin, LIU Fang'ai

2016, 36(7):  1988-1992.  DOI: 10.11772/j.issn.1001-9081.2016.07.1988

Asbtract ( )   PDF (769KB) ( )  

References | Related Articles | Metrics

In view of low memory usage rate and inefficient discovery for mining frequent itemsets in multiple data streams, an improved Mining Collaborative frequent itemsets in Multiple Data Stream (MCMD-Stream) algorithm was proposed. Firstly, the window sliding based on bit-sequence technique was utilized, which was a single-pass algorithm to find the potential and frequent itemsets. Secondly, Compressed frequent Pattern Tree (CP-Tree), which is similar to Frequent Pattern Tree (FP-Tree), was constructed to store the potential and frequent itemsets. And each node in the CP-Tree could generate the logarithmic tilted window to save the counts of frequent itemsets. Finally, the valuable frequent itemsets that appeared repeatedly in multiple data streams, namely collaborative frequent itemsets, were got. Compared to A-Stream and H-Stream algorithms, MCMD-Stream algorithm can improve the mining efficiency of collaborative frequent itemsets in multiple data streams, and also reduce the usage of the memory space. The experimental results show that MCMD-Stream algorithm can efficiently be applied to mine the collaborative frequent itemsets in multiple data streams.

Chi-square distribution based similarity join query algorithm on high-dimensional data

MA Youzhong, JIA Shijie, ZHANG Yongxin

2016, 36(7):  1993-1997.  DOI: 10.11772/j.issn.1001-9081.2016.07.1993

Asbtract ( )   PDF (829KB) ( )  

References | Related Articles | Metrics

To deal with the curse of dimensionality and costly computation problems existed in high-dimensional similarity join query, the high-dimensional data were mapped to low-dimensional space based on p-stable distribution. According the definition of chi-square distribution, a theorem was proved:if the distance of two points in low-dimensional space is greater than kε, the probability that the distance of two points in original space is greater than ε has a lower bound. So the effective filtering can be performed at relative low cost in the mapped space. A novel chi-square distribution-based similarity join query algorithm on high-dimensional data was proposed. In order to further improve the query efficiency, another similarity join query algorithm based on double filtering was also proposed. Comprehensive experiments were performed. The experimental results show that the proposed approaches have good performance. The recall of the chi-square distribution-based similarity join query algorithm is larger than 90%. The double filtering based similarity join query algorithm can further improve the efficiency, but it will lose some recall rate. Chi-square distribution based similarity join query algorithm is suitable for the query tasks which are critical of the query performance but not critical of the recall; otherwise, the similarity join query algorithm based on double filtering is favorable.

Graph reachability query based on reference node embedding

WEN Juping, HU Xiaosheng, LIN Dongmei, ZENG Yaguang

2016, 36(7):  1998-2005.  DOI: 10.11772/j.issn.1001-9081.2016.07.1998

Asbtract ( )   PDF (1390KB) ( )  

References | Related Articles | Metrics

Focusing on the issue that the problem of graph reachability query with distance constraint can not be solved by k-step reachability algorithm, a method of graph reachability query based on reference node embedding was proposed. Firstly, a very small part of representative global reference nodes were selected from all nodes, the shortest path distance between all nodes and these global reference nodes were previously calculated. Then the local reference nodes were obtained through the technology of the shortest path tree and range minimum query. Next, distance range was obtained based on the triangle inequality relation. Lastly, according to the relationship between the distance in query condition and the distance range, a conclusion of reachability could be drawn quickly. Comparative tests were done on data of social network and road network, the proposed algorithm was compared with Dijkstra algorithm and K-Reach algorithm. Compared with K-Reach algorithm, the indexing time of the proposed algorithm was four orders of magnitude shorter, and the index size was two orders of magnitude smaller. Compared with Dijkstra algorithm, the proportion of drawing a reachability conclusion directly by the proposed algorithm was 92% in the New York Road network, while 78.6% in the Digital Bibliography & Library Project (DBLP) network, moreover, the running time was shortened greatly, which was reduced by 95.5% and 92% respectively. The experimental results demonstrate that the computational complexity of online queries is reduced with a small index cost through the method proposed in this paper, which is a good solution to graph reachability query with distance constraint, and suitable for weighted graph as well as unweighted graph.

Collaborative filtering algorithm based on Bhattacharyya coefficient and Jaccard coefficient

YANG Jiahui, LIU Fangai

2016, 36(7):  2006-2010.  DOI: 10.11772/j.issn.1001-9081.2016.07.2006

Asbtract ( )   PDF (729KB) ( )  

References | Related Articles | Metrics

The traditional collaborative filtering recommendation algorithm based on neighborhood has problems of data sparsity and similarity measures only utilizing ratings of co-rated items, so a Collaborative Filtering algorithm based on Bhattacharyya coefficient and Jaccard coefficient (CFBJ) was proposed. The similarity was measured by introducing Bhattacharyya coefficient and Jaccard coefficient. Bhattacharyya coefficient could utilize all ratings made by a pair of users to get rid of common rating restrictions. Jaccard coefficient could increase the proportion of common items in similarity measurement. The nearest neighborhood was selected by improving the accuracy of item similarity and the preference prediction and personalized recommendation of the active users were optimized. The experimental results show that the proposed algorithm has smaller error and higher classification accuracy than algorithms of Mean Jaccard Difference (MJD), Pearson Correlation (PC), Jaccard and Mean Squared Different (JMSD) and PIP (Proximity-Impact-Popularity). It effectively alleviates the data sparsity problem and enhances the accuracy of recommendation system.

Preference prediction method based on time attenuation and preference fluctuation

YANG Li, HU Yunhong, SHAO Guirong

2016, 36(7):  2011-2015.  DOI: 10.11772/j.issn.1001-9081.2016.07.2011

Asbtract ( )   PDF (709KB) ( )  

References | Related Articles | Metrics

The existing recommender systems often use the nearest neighbors' preference behavior to predict current users' preference, and their recommendation accuracy are influenced by the lack of consideration that users' preference would change over time. To solve this problem, a cooperative preference prediction method based on time attenuation and preference fluctuation was proposed. First, attenuation increment and attenuation speed were obtained based on time and historical preference, and the attenuation function was generated by attenuation increment and attenuation speed to modify users' historical preference behavior. Then the distribution of historical preference was used to compute the preference fluctuation range. Finally, the recommender list was generated for user by applying the attenuation function and preference fluctuation range into the acquisition of nearest neighbors and the preference acquisition process. The experimental results on real data set show that, compared with the Collaborative Filtering based on Rating Distribution (RDCF) and Optimizing Top-N Collaborative Filtering (OTCF), the average Mean Absolute Error (MAE) of the proposed method is decreased by about 6.42% and 7.73% respectively. It also shows that the proposed method can achieve higher recommendation accuracy and better recommendation quality.

Port automata based behavioral expression method for nested system structure

XUE Gang, ZHANG Yunchun, LIU Di, YAO Shaowen

2016, 36(7):  2016-2020.  DOI: 10.11772/j.issn.1001-9081.2016.07.2016

Asbtract ( )   PDF (847KB) ( )  

References | Related Articles | Metrics

Concerning the problem of describing and analyzing dynamic behavior of the categorical model of nested-style structure, a Port Automata based behavioral expression Method (PAM) was proposed. The method was based on system states, input and output ports to define computations on object and structure. And it has been proved that PAM is a functor, which means that PAM is a structure preserved computation. Under the help of PAM, typical composite behaviors (including parallel, serial, and feedback) and application issues were discussed. The relevant results show that PAM can be applied in describing and analyzing dynamic behavior of systems with nested structure.

Evolution pattern recognition and genealogy construction based on clone mapping of versions

ZHANG Jiujie, ZHAI Ye, WANG Chunhui, ZHANG Liping, LIU Dongsheng

2016, 36(7):  2021-2030.  DOI: 10.11772/j.issn.1001-9081.2016.07.2021

Asbtract ( )   PDF (1721KB) ( )  

References | Related Articles | Metrics

To solve the problems that the method of building clone genealogy is complicated, as well as evolution patterns need urgently expanding, new clone evolution patterns were proposed, and clone genealogy was built automatically based on the mapping relationships of code clones between versions. First, topics of code clones were extracted using Latent Dirichlet Allocation (LDA) from clone detection results in each released software version. Second, mapping relationships of code clones between of versions were confirmed by similarities of the topics. Third, evolution patterns were appended to code clones according to the existing mapping relationships, and evolution features were analyzed. Finally, clone genealogy was built by integrating mapping relationships and evolution patterns together. Experiments of building clone genealogy was conducted on four open source systems. The experimental results show that the proposed approach is feasible, and the proposed evolution patterns really exist in the procedure of software evolution. Further more, it is found that about 90% of code clones in the software systems are stable during evolution, and approximately 67% of clone groups live through less than half of the release versions. The experimental conclusions and relevant analysis provide strongly support for the future research as well as maintenance and management of code clones.

Clone group mapping method based on improved vector space model

CHEN Zhuo, ZHANG Liping, WANG Huan, ZHANG Jiujie, WANG Chunhui

2016, 36(7):  2031-2037.  DOI: 10.11772/j.issn.1001-9081.2016.07.2031

Asbtract ( )   PDF (1026KB) ( )  

References | Related Articles | Metrics

Focusing on the less quantity and low efficiency problem of Type-3 clone code mapping method, a mapping method based on improved Vector Space Model (VSM) was proposed. Improved VSM was introduced into the clone code analysis to get an effective clone group mapping method for Type-1, Type-2 and Type-3. Firstly, clone group document was pretreated to get the code document with removing useless word, and the file name, function name and other features of clone group document were extracted at the same time. Secondly, word frequency vector space of clone group was extracted and built; the similarity of clone group was calculated by using cosine algorithm. Then mapping of clone group was constructed by clone group similarity and feature matching, and the result of cloning group mapping was obtained finally. Five pieces of open source software was tested and verified by experiments. The proposed method can guarantee the recall and the precision of not less than 96.1% and 97.1% at low time consumption. The experimental results show that the proposed method is feasible, which provides data support for the analysis of software evolution.

Crowdsourcing incentive method based on reverse auction model in crowd sensing

ZHU Xuan, YANG Maishun, AN Jian, XIANG Lele, YANG Qiangwei

2016, 36(7):  2038-2045.  DOI: 10.11772/j.issn.1001-9081.2016.07.2038

Asbtract ( )   PDF (1176KB) ( )  

References | Related Articles | Metrics

Intention is the main method of crowdsourcing service in Crowd Sensing (CS), in view of the existing methods in the process of service without fully considering the effects on CS which are from the number of participants and malicious competition, a kind of Incentive Mechanism based on Reverse Vickrey Auction model (RVA-IM) method was proposed. Firstly, incentive mechanisms of crowdsourcing were studied in this paper, in combination with reverse auction and Vickrey auction, a reverse auction model oriented to task covering was built. Secondly, the in-depth analysis and research on the key technical problems involved in the model were conducted, such as task covering, reverse auction selection and reward implementation. Finally, the effectiveness of RVA-IM method was analyzed in five ways:computational efficiency, individual rationality, budget-balance, truthfulness and honesty. The simulation results show that, compared with IMC-SS (Incentive Mechanism for Crowdsourcing in the Single-requester Single-bid (SS)-model) and MSensing (Myerson Sensing) method, RVA-IM method is more effective and feasible. It can solve the problem of malicious competition in the existing methods, and improves the average rate of service completion by 21%.

Urban functional area identification based on call detail record data

JIANG Guilin, HU Fangyu, SHI Lixing

2016, 36(7):  2046-2050.  DOI: 10.11772/j.issn.1001-9081.2016.07.2046

Asbtract ( )   PDF (782KB) ( )  

References | Related Articles | Metrics

Urban function areas can be differentiated either by their external physical characteristics or by inherent social functions. And, they have been keeping in dynamic process over time. Remote sensing, as a typical traditional method in urban function area classification, has its critical defects such as high time cost and helpless in their social functions. In order to solve the problem, a new urban functional area identification method based on Call Detail Record (CDR) data was proposed. The application of this new data source in urban land use classification was verified as follow steps. First, communication station cells were labeled with five categories (residence area, office area, commercial area, college area, scenic-spot area). Second, call duration distribution features and move-frequency features, extracted from these five urban function areas were compared and analyzed. Finally, a weighted decision algorithm based on the Gaussian Mixture Model (GMM) was designed, and the simulation on the training set was conducted. The experimental results prove that the CDR data is capable of delivering useful information between different urban function areas. There are corresponding relationships between the nature of urban functional areas and the behavior characteristics of mobile phone users. When decision weight is 0.6, the weighted decision algorithm achieves 51.08% recall rate in current datasets. Combined with the error analysis, this work indicates the feasibility of CDR data in solving the problem of urban functional area identification.

Design and implementation of cloud resource monitoring system based on bionics

SUN Peng, XU Han, CHEN Jingjing, CAO Xudong

2016, 36(7):  2051-2055.  DOI: 10.11772/j.issn.1001-9081.2016.07.2051

Asbtract ( )   PDF (811KB) ( )  

References | Related Articles | Metrics

Concerning the problems of heavy network traffic, which is caused by the excessive load of master node, bad expansibility and poor ability to handle node failure in existing monitoring system, a novel Cloud Monitoring System based on Bionic autonomic nervous system (B-CMS) was proposed. Firstly, B-CMS imported hierarchical storage and batch-wise report mechanism to upload the monitoring information, which can decrease the network traffic at any moment to ensure monitor system's stability. In addition, the use of similar Dynamic Host Configuration Protocol (DHCP) and polling-driven heartbeat checking mechanism enabled the monitor system to get the self-organizing and self-repairing ability which is similar to Bionic Autonomic Nervous System (BANS) when adding new node and handling node failure in autonomic way. The experimental results show that B-CMS achieves self-organizing and self-repairing, and effectively decreases network traffic. In some special moment, the network traffic is only one-third of the original system.

3-D visualization and information management system design based on open scene graph

ZHANG Wenying, HE Kunjin, ZHANG Rongli, LIU Yuxing

2016, 36(7):  2056-2060.  DOI: 10.11772/j.issn.1001-9081.2016.07.2056

Asbtract ( )   PDF (830KB) ( )  

References | Related Articles | Metrics

Concerning the problem of managing components information in the process of three-dimensional presentation of virtual assembly, a design of integrating 3-D visualization and information management technology combined with electric vehicles assembling and disassembling was proposed. Firstly, 3D model and information library were established according to the topology and supporting information of electric vehicles such as material and type. Secondly, a directory tree was created based on the parent-child relationship between the parts and sub-assemblies from information library, and three-dimensional presentation of the sub-assembly was achieved according to the principle that sub-assembly and scene tree have the same structure of "multi-tree", each node of the sub-assembly was animated before disassembly presentation. Finally, pickup interactive query and retrieving location query were achieved by combining the information management and visualization of electric vehicle. The constructed system was verified by century bird electric bicycle models, the integration of 3-D visualization and virtual assembly was realized, which could provide technical support for 3-D presentation and virtual assembly effectively. The experimental results show that the constructed system can effectively integrate the 3-D visualization and information management of components in virtual assembly.