Computer Science

State-of-the-art and Development Trend of Artificial Intelligence Combined with Law

HUANG Qiao-juan, LUO Xu-dong

Computer Science. 2018, 45 (12): 1-11. doi:10.11896／j.issn.1002-137X.2018.12.001

Abstract

PDF(1447KB) ( 4009 )

References | Related Articles | Metrics

There is no unified definition of artificial intelligence,but generally speaking,if a computer system can do whatever a person needs intelligence to do,the computer system has artificial intelligence.Therefore,artificial intelligence has been widely used in various fields needing human intelligence,such as law,medicine,finance,e-commerce,and so on,among which law is one of the most important applications currently.Therefore,this paper surveyed the research state-of-art and development trend of the combination of artificial intelligence and law,and aimed to help more resear-chers enter the field.Specifically,the survey mainly covers aspects from legislation (artificial intelligence system assisted legislation and legislative supervision of artificial intelligence systems,especially autonomous driving vehicles),grasping law (retrieving legal information,generating and reviewing legal documents),and enforcement of law (evidence collection,legal reasoning and online dispute resolution).

Survey of Data Storage and Query Techniques in Blockchain Systems

WANG Qian-ge, HE Pu, NIE Tie-zheng, SHEN De-rong, YU Ge

Computer Science. 2018, 45 (12): 12-18. doi:10.11896／j.issn.1002-137X.2018.12.002

Abstract

PDF(1924KB) ( 3095 )

References | Related Articles | Metrics

At present,blockchain systems,represented by Bitcoin and Ethereum,are becoming more and more mature,and blockchain technology has become a hot topic in academic and industrial circles.However,in practical applications,these systems are generally faced with tough problems such as simple query function and low query performance due to the limitation of data storage scheme.This paper presented the survey and prospect of the research progress on data storage and query technology of blockchain systems.First,the data storage mechanism and query processing strategy used in current popular blockchain systems were introduced .Then,two methods of extending query processing functions on the existing system were introduced in details.The features of their query efficiency,write performance optimization,storage space occupancy,data security and availability were compared and analyzed in detail.Finally,the trend of the query technology development in the future block chain system was analyzed,and the main research direction was discussed and explored.

Survey of DTN Architecture and Key Technologies

HUANG Xing-he, LI Ai-jing, WANG Hai

Computer Science. 2018, 45 (12): 19-23. doi:10.11896／j.issn.1002-137X.2018.12.003

Abstract

PDF(2073KB) ( 1262 )

References | Related Articles | Metrics

Disruption / Delay tolerant network (DTN) is a totally new network model abstracted from MANET(Mobile Ad-hoc network).Different from traditional wireless mobile Ad-hoc networks,DTN is mainly used in high-delay and instable environment.As an emerging study area for restricted network environment,DTN uses a special mode “store-carry-forward” for data transfer,so as to combat the effects of higher latency and disruption in restricted networks.The development of DTN will provide a more reliable communication for scenarios such as future military wars,space communications,disaster relief and so on.In this paper,firstly,the architecture and characteristics of DTN were analyzed.Then the DTN routing protocol was studied from the aspects of the calculated amount,reliability and dependence on other node’s state information.Finally,some difficult problems on DTN were presented,and some research topics that might bring great progress to DTN systems were emphasized.

Research on Network Asset Detection Technology

WANG Chen-dong, GUO Yuan-bo, ZHEN Shuai-hui, YANG Wei-chao

Computer Science. 2018, 45 (12): 24-31. doi:10.11896／j.issn.1002-137X.2018.12.004

Abstract

PDF(1620KB) ( 3995 )

References | Related Articles | Metrics

With the rapid spread of network technology,large numbers of diversified network assets bring great conve-nience to people’s daily life,but challenges are also posed to their own safety management at the same time.Accurate and comprehensive network asset detection is the prerequisite for the effective management of network assets and the basis for threat analysis.First,this paper reviewed the origin and development process of network asset detection.Next,this paper comprehensively analyzed three common novel methods of network asset detection (active,passive and search engine based)and each key technologies,and summarized the characteristics of these methods respectively.Finally,this paper discussed the development trends and further research directions of this technology.

Security for Communication Protocols in Internet of Things:A Survey

YANG Wei, HE Jie, WAN Ya-dong, WANG Qin

Computer Science. 2018, 45 (12): 32-41. doi:10.11896／j.issn.1002-137X.2018.12.005

Abstract

PDF(2149KB) ( 1174 )

References | Related Articles | Metrics

The IEEE and IETF standardization bodies are working together to develop a framework for the communication protocols of the Internet of Things (IoT).The communication protocols can meet the important criteria of reliability,power-efficiency and Internet connectivity.The IEEE defines the physical layer and medium access control (MAC)layer standard such as IEEE802.15.4-2006,and IEEE802.15.4e is the latest MAC layer standards for the IoT.The IETF defines the network layer and above standards,such as 6LoWPAN,RPL and CoAP,which can connect the resource constrained sensor nodes to the Internet.Network security is the fundamental of large-scale development of IoT,so it is necessary to design some secure and efficient mechanisms to protect the communication protocols.This paper reviewed the communication protocols in the IoT,then analyzed and discussed the latest research progress of secure technologies for them.Finally,it summerized and looked ahead some important directions of secure communication protocols for IoT.

Review of Dynamic Gesture Recognition Based on Depth Information

CHEN Tian-tian, YAO Huang, ZUO Ming-zhang, TIAN Yuan, YANG Meng-ting

Computer Science. 2018, 45 (12): 42-51. doi:10.11896／j.issn.1002-137X.2018.12.006

Abstract

PDF(2291KB) ( 1435 )

References | Related Articles | Metrics

With the rapid development of computer technology,natural,simple and non-contact gesture recognition is favored in human-computer interaction.Dynamic gesture recognition has always been a hot and difficult issue in the field of human-computer interaction.In order to understand the development status of dynamic gestures,this paper described the dynamic gestures based on depth information from four aspects of gesture segmentation,gesture modeling,feature extraction and gesture recognition based on the extensive investigation of the existing literature and the latest achievements,introduced the applications of dynamic gesture recognition,and discussed the existing difficulties and problems.

Survey of Tire Pattern Image Retrieval Techniques

LIU Ying, ZHANG Shuai, GE Yu-xiang, WANG Fu-ping, LI Da-xiang

Computer Science. 2018, 45 (12): 52-60. doi:10.11896／j.issn.1002-137X.2018.12.007

Abstract

PDF(4181KB) ( 1326 )

References | Related Articles | Metrics

Tire pattern image retrieval (TPIR) plays an important role in traffic accident management and criminal case solving.Although content-based image retrieval (CBIR) has been studied for decades,and few literatures has been done in TPIR due to the lack of tire pattern data source and its special application scenario.Based on the review of the research papers in the field of TPIR in recent years,this paper provided a comprehensive survey of the state-of-the-art techniques in this area.First,this paper described the research status of TPIR by summarizing the existing techniques in low-level texture feature extraction and high-level semantic learning for tire pattern images.Then,this paper introduced tire pattern image databases appeared in literature and the performance evaluation parameters used by researchers.In addition,this paper presented experimental results testing on low-level and high-level features of tire pattern images,with results analysis provided.Lastly,considering existing techniques and practical applications,this paper discussed the research challenges in this filed and pointed out a few potential future research directions.

Opportunistic Network Forwarding Algorithm Based on Node Cosine Similarity

ZHU Kun, LIU Lin-feng, WU Jia-gao

Computer Science. 2018, 45 (12): 61-65. doi:10.11896／j.issn.1002-137X.2018.12.008

Abstract

PDF(3211KB) ( 537 )

References | Related Articles | Metrics

Aiming at the problem of low data delivery ratio in opportunistic networks,this paper defined and computed the node forwarding utility according to the historical contacts between nodes,e.g.,the number of nodes contacts,the length of contacts and the stability of nodes relations.First,the node with the largest utility value falling into the communication range is selected as the initial forwarding node.Then,other forwarding nodes are selected by their cosine similarities,such that the forwarding nodes can be evenly distributed approximately.On this basis,an opportunistic network forwarding algorithm based on node cosine similarity (ONNCS) was proposed.ONNCS enables the selected forwarding nodes to be evenly distributed and improves the data delivery ratio.The simulation results show that ONNCS has a hig-her forwarding success rate and lower forwarding energy consumption,and the success rate of the algorithm is 5% to 8% higher than other algorithms in this paper.

Virtual Network Mapping Algorithm Based on Cellular Genetic Mechanism

WANG Ming, ZHUANG Lei, WANG Guo-qing, ZHANG Kun-li

Computer Science. 2018, 45 (12): 66-70. doi:10.11896／j.issn.1002-137X.2018.12.009

Abstract

PDF(3319KB) ( 449 )

References | Related Articles | Metrics

The optimal mapping problem of virtual network requests which satisfies the constraints of nodes and links is an NP-hard problem.Heuristic algorithms,such as particle swarm algorithm and genetic algorithm,can solve those problems.They solve the problem from the perspective of mathematical model optimization,but fail to consider the influence of the change of virtual network mapping node itself on the optimal solution,and they also have the problems of slow convergence speed and being easy to fall into local optimal solution.This paper introduced the cellular genetic mechanism into the problem of virtual network mapping,and proposed the virtual network mapping algorithm (VNE-CGA).This algorithm uses the cellular automata to model the nodes,and replaces the cross operator in the traditional genetic algorithm with the “B4567 / S1234” rule.Besides,the individual’s optimization process is guided through lear-ning from neighbors,making up for the inherent defects of traditional genetic algorithms.Finally it improves the request acceptance rate of virtual network and the operating income of underlying physical network.

Study on Local World Evolution Model of Weighted Complex Supply Chain NetworkBased on Location Attraction

ZHAO Zhi-gang, ZHOU Gen-gui, PAN Rui-fang

Computer Science. 2018, 45 (12): 71-76. doi:10.11896／j.issn.1002-137X.2018.12.010

Abstract

PDF(2082KB) ( 527 )

References | Related Articles | Metrics

The initial position values of enterprise nodes are presented as power-law distribution to reflect different roles of node enterprises on the basis of common local-world evolving network models.Inspired by the law of universal gravitation,this paper utilized the size of position and distance values to define the concept of position attraction of node enterprises,and determined the local world of every newly added node by using attraction rules.The compound priority connection mode of node degree and node strength is adopted among new nodes and the old nodes in the local world,making up for the defect that priority connection only relies on node degrees.In this sense,the weighted complex supply chain network-world evolving model was established based on position attraction.The experiments were conducted to simulate the dynamic evolution process such as complex network growth,edge exit and node exit etc.Through the calculation and statistic analysis of important parameters in complex supply chain networks such as network integrity degree distribution,average path length and average gather coefficient,it is found that the degree distribution of the complex supply chain network shows power-law distribution.It can guarantee the heavy tailed characteristics with the majority of the nodes possessing low degree and few nodes possessing high degree.At the same time,the complex supply chain network possesses small world characteristics with larger clustering coefficient and smaller average path length.This research provides theoretical foundation for supply chain enterprises to establish supply chain networks in practice,and it is conducive to analyze characteristics related to real supply chain networks better and identify important nodes for further protection.

Study on Monte Carlo Location Algorithm in Wireless Sensor Networks

ZHANG Qi-man, ZHANG Ying

Computer Science. 2018, 45 (12): 77-80. doi:10.11896／j.issn.1002-137X.2018.12.011

Abstract

PDF(2430KB) ( 648 )

References | Related Articles | Metrics

In the field of node location of wireless sensor network,there exist problems of high location error and low sampling efficiency of the commonly used Monte Carlo-based location algorithm.In order to improve the sampling efficiency and location accuracy of mobile node in wireless sensor networks,this paper made use of Markov chain to sample,and proposed an improved location algorithm based on Monte Carlo.The new algorithm combines the Markov chain to complete the collection of node samples based on Monte Carlo algorithm,then filters them,and finally obtains the exact position of the node by weighting the obtained node position values.Simulation results indicate that the proposed algorithm has lower location error than other algorithms,and improves the sampling efficiency and location accuracy for moving nodes.

Prefix-based Anycast Routing Protocol for Wireless Sensor Networks

GU Yun-li, XU Xin, DU Jie

Computer Science. 2018, 45 (12): 81-85. doi:10.11896／j.issn.1002-137X.2018.12.012

Abstract

PDF(1725KB) ( 464 )

References | Related Articles | Metrics

In wireless sensor networks,nodes and links often suffer temporary failures,and this needs to consume a lot of resources for re-building communication tree.For this problem,a prefix-based anycast routing protocol for wireless sensor networks was proposed.The protocol applies a lightweight routing discovery process to build new anycast paths,and applies unicast method based on prefixlabels.Compared with broadcast,unicast method can avoid flooding a large number of routing packets in the network.Prefix routing can help to find new anycast paths with fewer path length quickly.Compared with the traditional label methods,the cost (label size) of prefix label increases,but the increasing amount is very small (not more than log₂3 times).In comparison with traditional tree-based anycast routing protocol,simulation experiments results show that the performance of the proposed algorithm is better in terms of routing query overhead (information packets number),routing query capability and end-to-end transmission delay while searching for a new alternative anycast path.

Swarm Intelligence Algorithm for Prolonging Target Coverage Network Lifetime

FAN Xing-gang, LIU Tao, HU Feng-dan, HAO Xiang

Computer Science. 2018, 45 (12): 86-91. doi:10.11896／j.issn.1002-137X.2018.12.013

Abstract

PDF(2290KB) ( 469 )

References | Related Articles | Metrics

In wireless sensor networks,target coverage is a hot research topic recently.This paper rescheduled nodes based on swarm intelligence to enhance network lifetime under target coverage location.This paper defined network lifetime when Q-coverage of many targets are required.Using this lifetime model as fitness function of artificial colony algorithm,it redeploys nodes to meet the coverage demand of target using two-dimensional and three-dimensional perception model,so as to maximize network lifetime.Simulation results show that the deployment optimization based on artificial colony algorithm can prolong the network lifetime effectively.

Integrity-verifying Single Keyword Search Method in Clouds

DAI Hua, BAO Jing-jing, ZHU Xiang-yang, YI Xun, YANG Geng

Computer Science. 2018, 45 (12): 92-97. doi:10.11896／j.issn.1002-137X.2018.12.014

Abstract

PDF(2799KB) ( 481 )

References | Related Articles | Metrics

The service of outsourcing resources in clouds makes the data out of control from its owner and generates many security issues.It has become a serious threat to data users to verify the integrity of search results received from clouds.In the area of secure keyword search for cloud computing,current works mainly focus on the privacy-preserving issues which adopts the honest-but-curious threat model,but they are not able to solve the problem ofintegrity verification of the search result while the malicious attack threat model is adopted.This paper proposed a method of verifiable single keyword searching based on the partially ordered constraint chain,called IVSKS.According to the partial order relation of the relevance between keywords and files,data owner constructs the partial ordered constraint chains as verification objects of files,which are generated by hash functions.The verification objects and the corresponding files are subsequently outsourced together to clouds.When data users search the top-k relevance files by an interested keyword,the clouds will return the qualified files along with the corresponding verification objects.Data users can reconstruct the verification objects by these files and make a comparison to determine whether the result files are complete or correct.The experimental results indicate that IVSKS performs better on search result redundancy and completeness verification efficiency compared with the existing methods.

Self-adaption Adjustment Method for Experts in Risk Assessment

LENG Qiang, YANG Ying-jie, HU Hao

Computer Science. 2018, 45 (12): 98-103. doi:10.11896／j.issn.1002-137X.2018.12.015

Abstract

PDF(1445KB) ( 698 )

References | Related Articles | Metrics

Information asset assessment is a part of the important research content of information security risk assessment technology.At present,it mainly uses quantitative evaluation methods based on expert assessment and expert weighting.However,in the implementation of this method,how to scientifically determine the expert weight to reduce the impact of the assessment opinion with larger deviation on the overall evaluation results is a question.Considering this problem,this paper proposed a weight self-adaption adjustment evaluation method based on the deviation degree of experts,which can effectively reduce the impact of abnormal value on evaluation by expert.At the end of this paper,the algorithm was implemented and the algorithm validity experiment was carried out.The results show that this method can effectively reduce the impact of the abnormal evaluation value on the assessment.

Link Correlation Spoofing Attack and Detection Mechanism

XU Jia-jia, BAI Guang-wei, SHEN Hang

Computer Science. 2018, 45 (12): 104-110. doi:10.11896／j.issn.1002-137X.2018.12.016

Abstract

PDF(1707KB) ( 496 )

References | Related Articles | Metrics

Recent studies highlight the existence of link correlation of adjacent wireless links,and this phenomenon has shown significant impact on the performance of various network protocols.The efficiency of these existing link-correlated protocols heavily relies on the accuracy of link correlation measurement.However,analysis shows that due to its features of mobility and RF communication,wireless networks is vulnerable to various threats and attacks.This paper first proposed a spoofing attack mechanism about link correlation aware protocols.When the source node broadcasts packets,some or even all of the corresponding receivers maliciously revise their packet reception bitmaps to tamper link correlation metric,thus degrading protocol performance.Against the attack,a Watchdog-based detection mechanism was proposed to capture a node’s behavior with objective of inferring the real packet reception bitmaps.The simulation results show that this spoofing attack increases the retransmission counts,and degrades the performance of communication protocol,while the propoced detection mechanism can defend the spoofing attack effectively.

Microblogging Malicious User Identification Based on Behavior Characteristic Analysis

XIA Chong-huan, LI Hua-kang, SUN Guo-zi

Computer Science. 2018, 45 (12): 111-116. doi:10.11896／j.issn.1002-137X.2018.12.017

Abstract

PDF(1679KB) ( 1059 )

References | Related Articles | Metrics

In recent years,as a hotspot in data mining of physical network,social network data mining has made grati-fying achievements in the current user behavior analysis,interest recognition and product recommendation.With the advent of social networking business opportunities,many malicious users and malicious behaviors have also emerged,which have a great impact on the effectiveness of data mining.A malicious user identification method based on user behavior feature analysis was proposed.This method uses the principal component analysis(PCA) to mine the user behavior data in microblogging network,and ranks the weight of each feature.It can effectively identify malicious users with first six-dimensional principal component features.The new features fitted by the principal component features are used to improve the recognition performance of the system.The experimental results show that the proposed method can effectively sort the microblogging user features and identify the malicious users in the microblogging social network,which provides a good data cleaning technique for social network data mining in other directions.

Semantic Roles Mining Algorithms Based on Formal Concept Analysis

ZHOU Chao, REN Zhi-yu, WU Wen-chao

Computer Science. 2018, 45 (12): 117-122. doi:10.11896／j.issn.1002-137X.2018.12.018

Abstract

PDF(2667KB) ( 488 )

References | Related Articles | Metrics

Role-based access control (RBAC) with the advantages of management and security has been widely used in various fields after more than 20 years of development.How to migrate a non-RBAC system with a variety of data into an RBAC system has become a significant problem.Role is a basic feature of RBAC,therefore,role mining is an important part of the implementation of RBAC system.In this paper,the user-permission concept lattice and user-attribute concept lattice were generated based on formal concept analysis.After the user-permission concept lattice was reversed,it was mapped to initial candidate role state,and the final role state was mined by reduction and pruning operations.And then,the most approximate expressions were defined to give semantic meanings to roles by analyzing the similarity between user-permission concept lattice and user-attribute concept lattice.The generated roles have two advantages,one is structural hierarchy,which effectively reduces the authorization burden of administrator,and the other one is semantic meanings,which can be associated with the concepts in real life,enhancing the interpretability of role.Finally,the expe-rimental results verify the correctness and effectiveness of the proposed algorithm.

DDoS Attack Detection System Based on Intelligent Bee Colony Algorithm

YU Xue-shan, HAN De-zhi, DU Zheng-xin

Computer Science. 2018, 45 (12): 123-129. doi:10.11896／j.issn.1002-137X.2018.12.019

Abstract

PDF(1971KB) ( 796 )

References | Related Articles | Metrics

With the popularity of the applications of big data,DDoS attacks become increasingly serious and have been the main network security issues.This paper designed a DDoS attack intrusion detection system based on clustering and intelligent bee colony algorithm (DFSABC_elite) for DDoS attack detection in environment of big data.The system combines the clustering algorithm and the intelligent bee colony algorithm to classify DDoS attack data flow,and uses the traffic feature distribution entropy and the generalized likelihood comparison distinguishing factor together to detect the characteristics of DDoS attack data stream,thus achieving the efficient detection of DDoS attack data flow.Experimental results show that this system is obviously superior to the ordinary bee colony algorithm based on parallelization K-means and the DDOS detection algorithm based on parallelization K-means in terms of intra-class compactness,inter-class separation,clustering accuracy,consumed time and DDoS detection accuracy.

Selective Expression Approach Based on Event Trigger for Event Coreference Resolution on Twitter

WEI Ping, CHAO Wen-han, LUO Zhun-chen, LI Zhou-jun

Computer Science. 2018, 45 (12): 130-136. doi:10.11896／j.issn.1002-137X.2018.12.020

Abstract

PDF(2482KB) ( 892 )

References | Related Articles | Metrics

With the development and popularization of social media,how to recognize the coreference relation between two event mention in short texts is an urgent issue.In traditional researches about event coreference resolution,a rich set of linguistic features derived from pre-existing NLP tools and various knowledge bases is required,which restricts domain scalability and leads to the propagation of errors.To overcome these limitations,this paper proposed a novel selective expression approach based on event trigger to explore the coreference relationship on Twitter.Firstly,a bi-direction long short term memory (Bi-LSTM) is exploited to extract the features at sentence level and at mention level.Then,the latent features are generated by applying a gate on sentence level features to make it selectively express.Next,two auxiliary features named the overlapped words of trigger and time interval are designed.Finally,all these features are concatenated and fed into a simple classifier to predict the coreference relationship.In order to evaluate this method,this paper annotated a new dataset EventCoreOnTweet (ECT).The experimental results demonstrate that the selective expression approach significantly improves the performance of coreference resolution of short texts.

Learnt Clause Evaluation Algorithm of SAT Problem Based on Trend Strength

CHEN Qing-shan, XU Yang, WU Guan-feng

Computer Science. 2018, 45 (12): 137-141. doi:10.11896／j.issn.1002-137X.2018.12.021

Abstract

PDF(1682KB) ( 547 )

References | Related Articles | Metrics

For the problem that it is difficult to effectively evaluate whether the learnt clause is beneficial to the follo-wing search in the solving process of propositional logic equation,a clause evaluation algorithm was proposed based on the trend strength.First of all,the distribution characteristic of time involved in conflict analysis for the learnt clauses during the lifecycle is analyzed,and the random,discrete time distribution is transformed into the continuous cumulative trend strength.Then,when the deletion period arrives,the clauses with little possibility of being used in the subsequent search process will be deleted by setting the threshold of trend strength,while the clauses of high probability will be kept.Lastly,by using SAT international testing examples in 2015 and 2016,two state-of-the-art algorithms (i.e.,activi-ty evaluation algorithm and literal block distance (LBD) algorithm) are adopted for comparison purpose.The experimental results show that the proposed evaluation algorithm with trend strength can significantly outperform the activity evaluation algorithm in efficiency and can obtain more solving instances,and has the comparable performance with the LBD algorithm.

Study on Recursive Auto-encoding Sentiment Classification Based on Topic Enhancement

ZHU Yin, HUANG Hai-yan

Computer Science. 2018, 45 (12): 142-147. doi:10.11896／j.issn.1002-137X.2018.12.022

Abstract

PDF(1511KB) ( 601 )

References | Related Articles | Metrics

The emotional analysis of Chinese text aims to discover the emotional tendencies of users to things and events,however,the existing studies often neglect the interrelationships between texts.In light of this,this paper proposed a recursive auto-encoding classification model based on topic enhancement.By incorporating the subject information of the text into the recursive auto-encoding model,this model can further consider the content information of the text and improve the capability to understand the text emotion and generaliza ability.The experimental results on the COAE2014 dataset show that the proposed classification model can achieve better classification performance when used for tasks of sentiment classification,thus verifying its applicability and feasibility in practical problems.

Parallel Text Categorization of Random Forest

PENG Zheng, WANG Ling-jiao, GUO Hua

Computer Science. 2018, 45 (12): 148-152. doi:10.11896／j.issn.1002-137X.2018.12.023

Abstract

PDF(1504KB) ( 732 )

References | Related Articles | Metrics

Text categorization is one of the core technologies of information retrieval.Because of the limited computing performance and storage capacity in a computer,the traditional text categorization method can’t be suitable for big data era nowadays.It is realistic and urgent to execute algorithms for classifying the text in parallel to improve the efficiency of algorithm by the parallelization operation of data and tasks on the big data platform of Spark.This paper proposed an improved random fo-rest algorithm for the imbalanced data.It can reduce the impact of imbalanced data on random fo-rests by under-sampling the majority class samples and back-sampling the minority class samples to make up new trai-ning samples.The experimental results show that the new algorithm improves the categorization accuracy of the minority classes when handling imbalanced data sets.

Multi-granularity Sentiment Classification Method Based on Sequential Three-way Decisions

ZHANG Gang-qiang, LIU Qun, JI Liang-hao

Computer Science. 2018, 45 (12): 153-159. doi:10.11896／j.issn.1002-137X.2018.12.024

Abstract

PDF(1957KB) ( 807 )

References | Related Articles | Metrics

How to classify the review data correctly is important research content in sentiment analysis.From the perspective of granular computing and cognitive science,this paper proposed a multi-granularity sentiment classification method for Chinese reviews based on sequential three-way decisions.Firstly,based on the characteristics of review data,a coarse-to-fine multi-granularity sentiment information representation method is put forward according to the amounts of sentiment information existing in the review.Then,by combining the principle of sequential three-way decisions,the calculation is gradually executed in different sentiment information granularity and the sequenced three-way decision is carried out for the boundary reviews.Lastly,according to the decision thresholds and costs in different granularities,the final sentiment classification is provided for the review data.The experimental results show that the proposed method achieves better performance,and performes higher classification accuracy and stronger robustness on three classic datasets.

Dynamic Reliability Evaluation Method of Evidence Based on Intuitionistic Fuzzy Sets and Its Applications

WU Wen-hua, SONG Ya-fei, LIU Jing

Computer Science. 2018, 45 (12): 160-165. doi:10.11896／j.issn.1002-137X.2018.12.025

Abstract

PDF(2056KB) ( 455 )

References | Related Articles | Metrics

This paper presented a new evidence reliability evaluation method based on evidence theory and intuitionistic fuzzy sets,which can conduct reliability evaluation for different evidence sources when the prior knowledge is lacked.Firstly,the basic probability assignment (BPA) is transformed to intuitionistic fuzzy sets.Then,the similarity among BPAs is calculated through the similarity measure of intuitionistic fuzzy sets.On this basis,the concept of evidence support degree is proposed,and the relative reliability and absolute reliability of evidence can be obtained by analyzing the relationship between supporting degree and reliability of evidence.Lastly,the original evidence is corrected based on evidence discounting operation,and the corrected evidences are combined by Dempster rule.Besides,this paper proposed a multi-sensor fusion method based on the evidence reliability evaluation considering intuitionistic fuzzy sets.Numerical experiment was conducted to analyze its performance.The results show that this method can effectively evaluate the unreliable evidences.

Decision Making Approach Based on Evidential Reasoning Considering SemanticRelationship among Assessment Grades

ZHANG Mei-jing, WANG Ying-ming

Computer Science. 2018, 45 (12): 166-169. doi:10.11896／j.issn.1002-137X.2018.12.026

Abstract

PDF(2432KB) ( 549 )

References | Related Articles | Metrics

In the framework of evidential reasoning,assessment information is aggregated by Dempster-Shafter Theory,which will bring the disadvantage of information leak in the process of aggregation using orthogonal summationmode without considering the semantic relationship among assessment grades.From the viewpoint of semantics and degree of assessment grades,a new algorithm for separately aggregating information was proposed based on the relationship among assessment grades.An improved framework for evidential reasoning was established based on the new fusion algorithm,and relevant decision-making model and decision-making process were provided.At last,a complete numerical example was utilized to demonstrate the application of this approach.Compared with the application of new and old methods in the example,the feature of the new method was investigated.

Physical Quantity Regression Method Based on Optimized BP Neural Network

PAN Jun-hong, WANG Yi-huai, WU Wei

Computer Science. 2018, 45 (12): 170-176. doi:10.11896／j.issn.1002-137X.2018.12.027

Abstract

PDF(1931KB) ( 549 )

References | Related Articles | Metrics

In the development of practical application system of Internet of Things(IoT),traditional regression methods have the problems of non-uniform expression,poor non-linear correction ability and dynamic adaptability for physical quantity regression of A/D conversion.Based on the analysis of the physical quantity regression elements of A/D conversion,and according to the non-linear mapping ability in BP artificial neural network,this paper proposed a BP neural network optimized by cuckoo search algorithm,and utilized it to realize physical quantity regression method of A/D conversion with unified mathematical expression.Practice shows that this method has the characteristics of uniform mathematical formula,strong nonlinear correction ability and dynamic adaptability.This method is not only suitable for IoT system using communication methods to send A/D acquisition data to PC directly,but also suitable for the environment in which PC is used to learn.The neural network structure parameters are stored in the Flash of MCU,and the A/D value is directly converted to the actual physical quantity at the terminal IoT.

Deep Learning Model for Typhon Grade Classification Based on Improved Activation Function

ZHENG Zong-sheng, LIU Zhao-rong, HUANG Dong-mei, SONG Wei, ZOU Guo-liang, HOU Qian, HAO Jian-bo

Computer Science. 2018, 45 (12): 177-181. doi:10.11896／j.issn.1002-137X.2018.12.028

Abstract

PDF(2721KB) ( 592 )

References | Related Articles | Metrics

Aiming at the issue that it is difficult to select the activation function in deep learning model for specific task,on the basis of analyzing the advantages and disadvantages of traditional activation function and the popular activation function at the present stage,this paper constructed an activation function T-ReLU which can make up for the shortcomings of Tanh function and ReLU function by combining the Tanh activation function with the widely used ReLU function.By constructing the deep learning model Typ-CNNs for typhoon grade classification,using the Typhoon satellite image published by the Japan Meteorological Agency as the self-built sample data,this paper made use of several different activation functions to conduct comparison experiments.The results show that the test accuracy of typhoon grade classification using the T-ReLU function is 1.124% higher than that of using ReLU activation function,which is 2.102% higher than that of using Tanh function.In order to further verify the reliability of the results,the MNIST general data set was utilized to carry out the comparison experiment of activation function.The final results show that 99.855% training accuracy and 98.620% test accuracy can be obtained by using T-ReLU function,and it performs better than other activation functions.

Weighted Support Vector Machine Algorithm Based on Inner-correlations and Mutual Information of Features

PENG Xiao-bing, ZHU Yu-quan

Computer Science. 2018, 45 (12): 182-186. doi:10.11896／j.issn.1002-137X.2018.12.029

Abstract

PDF(1612KB) ( 928 )

References | Related Articles | Metrics

The feature-weighted support vector machine (FWSVM) does not take into account the correlation among the features,thus the redundancy and the interference caused by it will have a negative impact on the final classification result.A feature weighting algorithm based on inner-feature correlation and mutual information was proposed and applied in support vector machines.The algorithm introduces the inter-feature coefficient as an index to measure the redundancy,and then calculates the penalty factor to deal with the weight on the basis of the feature weighting vector machine.Thus it realizes the contribution of the feature to the classification as much as possible.The comparison of experiments on multiple data sets with several different algorithms shows that the proposed new algorithm has better robustness and generalization ability.

Simulation and Optimization of Crowd Movement Behavior Based on Repast Simphony Platform

LIU Wen-long, ZHANG Jing, ZHOU Sui-ping, LI Yue-long

Computer Science. 2018, 45 (12): 187-191. doi:10.11896／j.issn.1002-137X.2018.12.030

Abstract

PDF(2335KB) ( 443 )

References | Related Articles | Metrics

Aiming at the movement behaviors of subway passengers,based on the Agent model and the particle swarm algorithm,through utilizing the simulation platform of Repast Simphony,this paper built a simulation model of crowd movement behavior.The model simulates the process of passengers entering the waiting room of subway station,then looking for subway’s door for queuing,and entering the subway when subway arrives at station.On this basis,this paper proposed an improved routing algorithm based on Markov decision model.Experimental results show that this algorithm can effectively solve the problem that traditional particle swarm algorithm is easy to trap in local solution,and significantly reduce the number of collisions.In addition,this paper proposed a method to avoid congestion in some compartments through employing passenger number indicator of subway compartment.Experimental results show that this method is effective and can improve the efficiency of passengers entering the compartment by 9%.

Correlation-Hierarchy Based Virtual Maintenance Modeling Method for ComplexElectromechanical Components of Aircraft

DONG Jian-kang, TANG Chao, GENG Hong

Computer Science. 2018, 45 (12): 192-195. doi:10.11896／j.issn.1002-137X.2018.12.031

Abstract

PDF(2629KB) ( 478 )

References | Related Articles | Metrics

Aiming at the problems that the traditional maintenance simulation modelsdon’t meet the requirement of virtual maintenance environment and lack generality,this paper proposed a virtual maintenance modeling method of aircraft complex electromechanical components based on association-hierarchy.In this method,the model is divided into the top-level correlation model,the middle-level hierarchy model and the bottom-level geometric model.The correlation model reflects the relationship between complex electromechanical components and other components,the hierarchy model integrates the constraints,functions,faults and structures of itself,and the geometric model is used for real-time display and collision detection in the virtual maintenance environment.The established model information is complete and universal,which can meet the requirements of virtual environment for the model and be applied to the maintenance training of machine.Finally,the effectiveness of this modeling method is verified by the example.

Application of Improved UCT Algorithm in EinStein Würfelt Nicht! Computer Game

ZHANG Xiao-chuan, LI Qin, NAN Hai, PENG Li-rong

Computer Science. 2018, 45 (12): 196-200. doi:10.11896／j.issn.1002-137X.2018.12.032

Abstract

PDF(1773KB) ( 959 )

References | Related Articles | Metrics

UCT (Upper Confidence Bound Apply to Tree) algorithm,as the extension of Monte Carlo search algorithm,is widely concerned and applied to computer game system because of its strong robustness.EinStein würfelt nicht! game is a new kind of game introduced in the domestic game competition in recent years,and the randomness and entertainment of throwing the dice in the competition attracts the participation of the majority of scholars.From the perspective of global optimization method,UCT algorithm was introduced to apply in EinStein würfelt nicht! game system.Firstly,the UCT algorithm is further optimized by using the parallel computing method based on the current state of multi-core computer.Secondly,the current winning factor (WINK) and the optimal node selection factor (UCTK) are introduced to optimize the optimal relationship between the decision winning percentage and the move.Finally,a complete EinStein würfelt nicht! game system is constructed.The winning percentage is improved by 25% by computer-computer game with the game system based on the Minimax algorithm,α-β algorithm and Monte Carlo algorithm,and it has won the champion in the National Computer Game Contest,which further validates the effectiveness of the algorithm.

Repeatable Motion Planning of Redundant Manipulators Based on Terminal Neural Networks

KONG Ying, SUN Ming-xuan

Computer Science. 2018, 45 (12): 201-205. doi:10.11896／j.issn.1002-137X.2018.12.033

Abstract

PDF(1732KB) ( 565 )

References | Related Articles | Metrics

To solve the joint-angle drift problems in cyclic motion of redundant robot manipulators,a kind of quadratic optimization models for redundant manipulators’ trajectory planning based on terminal optimality criterion was proposed and analyzed.The terminal neural network models with limited value activation functions are applied to redundant manipulators to demonstrate the effectiveness of the proposed computing models in performing the repeatable motion planning tasks under the condition that the initial position deviates from the target position.New types of terminal neural network (TNN) and its accelerated form (ATNN) were proposed,which are of terminal attractor characteristics and can get effective solution for time-varying matrix in finite time.Compared with the asymptotic neural network (ANN),terminal neural network method not only accelerate the convergent rate,but also improve convergent precision.The si-mulation results on the model of PUMA560 show that the proposed method is effective and real-time.

Classification Algorithm for Texture Image Based on Local Characteristics of N-FoldRotation Invariant Feature

HUANG Qing-yu, ZHANG Deng-yi

Computer Science. 2018, 45 (12): 206-209. doi:10.11896／j.issn.1002-137X.2018.12.034

Abstract

PDF(3131KB) ( 584 )

References | Related Articles | Metrics

This paper adopted a non-quantifiable local feature to design a robust texture descriptor,so as to enhance the robustness of the texture classification in the rotation and scale changes.First of all,the concept of local feature with rotational symmetry is introduced.It is found that many rotation invariant local features are rotational symmetric to a certain degree.Therefore,this paper proposed a novel local feature to describe the rotation invariant properties of the texture.In order to deal with the change of rotation and scale in texture image,Fisher vector encoding method is used to manage multiscale analysis for the texture feature,which can combine with the scale information without increasing the dimension of the local feature.The resulting local features have strong robustness to rotation and gray intensity variation.Experimental results show that the proposed method outperforms the existing algorithms on many data sets,greatly improving the texture classification accuracy.

Improved Image Reconstruction Algorithm Based on L1-Norm and TV Regularization

XU Min-da, LI Zhi-hua

Computer Science. 2018, 45 (12): 210-216. doi:10.11896／j.issn.1002-137X.2018.12.035

Abstract

PDF(2169KB) ( 1616 )

References | Related Articles | Metrics

Concerning the streak artifacts and noise in the image reconstruction for incomplete projection data,this paper presented a image reconstruction model integrating L1 and TV regularization.Based on this model,this paper proposed a new image reconstruction method combining Bregman iteration and TV soft-thresholding filter.In the proposed method,the projection data are first applied to carry out preliminary reconstruction through Bregman iteration,and then the iterative results are used to minimize the TV model.At last,by repeating the above two steps,the reconstructed ima-ge can be obtained.To demonstrate its effectiveness,the Shepp-Logan model without noise and the Abdomen model with noise were employed to take experiments.The proposed algorithm not only has better visual effects,but also has more excellent performance compared with the existing algorithms such as ART,LSQR,L1 and BTV etc.Experimental results show that the proposed algorithm can well preserve image details and edges,and possesses good anti-noise capability,while eliminating streak artifacts effectively.

Multi-focus Image Fusion Method Based on NSST and Adaptive PCNN

YANG Li-su, WANG Lei, GUO Quan

Computer Science. 2018, 45 (12): 217-222. doi:10.11896／j.issn.1002-137X.2018.12.036

Abstract

PDF(5334KB) ( 874 )

References | Related Articles | Metrics

In order to overcome the disadvantages of low fusion quality in traditional image fusion methods,this paper proposed an image fusion method based on the nonsubsampled shearlet transform (NSST) and adaptive pulse coupled neural network (PCNN).Firstly,the source image is decomposed by nonsubsampled shearlet transform.Then,the low frequency fusion of the obtained low frequency components is performed by using the fusion rule based on the guided image filter.After that,the improved spatial frequency is used as the PCNN input for the high frequency component,and the improved Laplace energy summation is used as the PCNN link strength of PCNN.Finally,the fused image is obtained by inversion of NSST.The experimental results show that this algorithm can preserve the details well and prevent product artifacts and distortions from the perspective of subjective effects,and it possesses more superior perfor-mance in terms of objective indicator,such as standard deviation,Q^AB/F,entropy and mutual information.

Hyperspectral Image Classification Based on Adaptive Active Learning and Joint Bilateral Filtering

LI Chang-li, ZHANG Lin, FAN Tang-huai

Computer Science. 2018, 45 (12): 223-228. doi:10.11896／j.issn.1002-137X.2018.12.037

Abstract

PDF(3038KB) ( 530 )

References | Related Articles | Metrics

It is very important to select appropriate samples as training samples to train the classifier in hyperspectral image classification (HIC).In this paper,the uncertainty and representativeness of the sample are combined,and the sample selection is completed by the adaptive active learning method.The Kernel-K clustering means is used to obtain representative samples,while the uncertainty is determined by the weighted sum of the probability difference between the optimal label and the suboptimal label and their ratio.In addition,in order to improve the accuracy of classification,the joint bilateral filtering is used to obtain the spatial information of hyperspectral image,and it is incorporated into the classification process.Finally,a spatial-spectral HIC approach is proposed,which combines adaptive active learning and joint bilateral filtering.The experimental results show the superiority of the proposed method.

Image Inpainting Based on Generative Adversarial Networks

SUN Quan, ZENG Xiao-qin

Computer Science. 2018, 45 (12): 229-234. doi:10.11896／j.issn.1002-137X.2018.12.038

Abstract

PDF(4025KB) ( 1158 )

References | Related Articles | Metrics

Aiming at the problems of the restricted shape and size of the damaged area,the obvious inpainting tracks and the discontinuous inpainting edge in the existing image impainting algorithms,this paper proposed an image inpainting method based on generative adversarial networks.In this method,a new generative model named generative adversarial networks(GAN) is used as the basic framework with combining Wasserstein distance and the idea of conditional genera-tive adversarial networks(CGAN).The network receives the damaged image as additional conditional information and combines adversarial loss with content loss to train the network model for restoring pixels of missing areas.This method can be used to repair most of the damages in images.The experimental results on two datasets of CelebA and LFW suggest the capability of this method to obtain good performance.

Surface Labeling Method Based on Feed-forward Context and Shape Priors

GUO Yan-fei, LIU Hong-zhe, YUAN Jia-zheng, WANG Xue-jiao

Computer Science. 2018, 45 (12): 235-242. doi:10.11896／j.issn.1002-137X.2018.12.039

Abstract

PDF(6328KB) ( 524 )

References | Related Articles | Metrics

Aiming at the problem that the scene semantics cannot be understood caused by mutual occlusion,this paper proposed a method based on feed-forward context and shape priors to semantically label the foreground region and the occluded background area.Firstly,the original image is divided into super pixels,and the feature of pixel is extracted.The accelerated decision tree method is used to mark the foreground and the target model is detected by the improved multi-scale deformable component model method.Then,the visible object information is combined with the feed-forward context prediction to infer the occluded portions of background region.Next,the prior knowledge of shape for each label is provided based on polygons which match the current label confidence.Finally,the pixel prediction is combined with the visual plane prediction and the polygon knowledge to form a complete scene labeling image.Compared with the exis-ting method,this method can get more consistent results with the street scene,and can perform better labeling effect when the sidewalk is close to the road.

Hyperspectral Image Classification Based on Multi-scale Discriminative Spatial-spectral Features

REN Shou-gang, WAN Sheng, GU Xing-jian, WANG Hao-yun, YUAN Pei-sen, XU Huan-liang

Computer Science. 2018, 45 (12): 243-250. doi:10.11896／j.issn.1002-137X.2018.12.040

Abstract

PDF(3752KB) ( 540 )

References | Related Articles | Metrics

In order to cope with the unevenness of homogenous regions’ area in hyperspectral images,an algorithm based on multi-scale discriminative spatial-spectral features was proposed.First,the image is processed with multi-scale filters.Then discriminative spatial-spectral information is extracted from the filtered images before put into SVM classifiers.At last,classification results of the filtered image are combined with decision fusion strategy.The experimental results on Indian Pines,Kennedy Space Center and University of Pavia indicate the effectiveness of the extracted spatial information.The overall accuracy of this algorithm can reach up to 96% when 10 percent of samples are randomly selected for training.What’s more,the classification accuracy and Kappa coefficient are higher than the comparative algorithms.

Hyperspectral Unmixing Algorithm Based on Dual Graph-regularized Semi-supervised NMF

ZOU Li, CAI Xi-biao, SUN Jing, SUN Fu-ming

Computer Science. 2018, 45 (12): 251-254. doi:10.11896／j.issn.1002-137X.2018.12.041

Abstract

PDF(3127KB) ( 469 )

References | Related Articles | Metrics

In hyperspectral images,the existence of mixed pixels greatly impedes the development of hyperspectral remote sensing technology.Therefore,how to carry out unmixing accurately and efficiently in the process of using spectral images is a key problem.For hyperspectral unmixing,using original non-negative matrix factorization (NMF) algorithm faces some difficulties,for example,the objective function is non-convex function,so it is difficult to solve the global optimal solution.Besides,the pure pixel like element doesn’t exist in mixed pixel.In order to solve these problems,this paper proposed a mixed pixel unmixing algorithm namely dual graph-regularized constrained semi-supervised NMF (DCNMF) .This algorithm adopts gradient descent algorithm and iterative updating rule,considers the geometric structures of hyperspectral data manifold and the spectral feature manifold,and can jump out of the local extremum,thus solving the global optimal solution.Real hyperspectral image data simulation experiments show that DCNMF algorithm can be used to decompose the mixed pixel accurately and efficiently,enhancing the effect of unmixing,improving the accuracy of mixing,saving the computing time and speeding up convergence.

Classification of Tongue Image Based on Multi-task Deep Convolutional Neural Network

TANG Yi-ping, WANG Li-ran, HE Xia, CHEN Peng, YUAN Gong-ping

Computer Science. 2018, 45 (12): 255-261. doi:10.11896／j.issn.1002-137X.2018.12.042

Abstract

PDF(1784KB) ( 1425 )

References | Related Articles | Metrics

It is difficult to exploit the existing methods to achieve efficient classification and identification of tongue ima-ge’ labels in parallel,and it is also difficult to utilize the correlation between labels for comprehensive analysis.Aiming at the problems above,this paper proposed a classification method of tongue image based on multi-task deep convolutional neural network and constructed a multi-task joint learning model based on deep convolutional neural network to realize the simultaneous identification of tongue color,moss color,tongue crack and tooth marks in tongue diagnosis of Chinese medicine.First,the shared network layer is used to learn all labels,and the correlation between the tags is extracted and utilized automatically from the perspective of feature extraction.Then,the learning tasks of specific labels are completed in different sub-network layers to eliminate the ambiguity in the multi-label classification problem.Finally,multiple Softmax classifiers are trained to achieve parallel prediction of all labels.Experimental results suggest that the proposed method can simultaneous extract multiple features of tongue image and implement classification by means of end to end.The lowest value is about 0.96 in several evaluation indexes and the multi-task recognition rate is about 34ms.Therefore,this algorithm has obvious advantages in accuracy and speed.

Visual Analysis Method of Garbage Disposal Modes Based on Self-organizing Maps Clustering

QIN Xu-jia, SHAN Yang-yang, XU Fei, ZHENG Hong-bo, ZHANG Mei-yu

Computer Science. 2018, 45 (12): 262-267. doi:10.11896／j.issn.1002-137X.2018.12.043

Abstract

PDF(6020KB) ( 596 )

References | Related Articles | Metrics

A hybrid visual analysis method was proposed for the data of garbage disposal modes in various provinces of China.In order to analyze the data from multiple views,this paper combined three visualization techniques including unified distance matrix,parallel coordinate and Small-Multiple,designed and realized the interactions among the three views.Firstly,the data are processed by clustering so that the garbage disposal modes of different provinces in recent years can be divided into different categories.The clustering used in this paper is based on self-organizing maps (SOM) neural network clustering algorithm.Secondly,according to the results of SOM clustering,the unified distance matrix is used for visualization,and the parallel coordinate is used to describe the attributes of each clustering result.In order to analyze the geographical and sequential attributes of data,the Small-Multiple visualization technology is used.Thirdly,interactions such as multi-view linkage and refreshing are implemented to help users explore the data on their own and achieve interactive display and analysis of multiple views.The experimental results show that the hybrid visualization method can achieve a good visualization effect of multi-attributes interaction and can help users to understand the distribution and trend analysis of garbage disposal modes in China.

City Functional Region Discovery Algorithm Based on Travel Pattern Subgraph

XIAO Fei, WANG Yue, MEI Yi-nan, BAI Lu, CUI Li-xin

Computer Science. 2018, 45 (12): 268-278. doi:10.11896／j.issn.1002-137X.2018.12.044

Abstract

PDF(3699KB) ( 735 )

References | Related Articles | Metrics

City’s functional regions refer to the geographical regions with relatively fixed functions(such as industry,commerce,housing,education,etc.) in the development of city.The position structure of these functional regionsaffect people’s travel patterns,and these travel patterns also objectively reflect the real function of regions.This paper focused on the travel patterns of urban residents by using the taxicabs’ trajectory data,and obtained functional regions accor-ding to these travel models.The main contributions of this paper are as follows.Firstly,this paper constructed the region pattern graph by using the taxicabs’ trajectories and the road network structures,and then connected different geographical regions via the graph structure created by region graph pattern construcing algorithm.Secondly,this paper proposed the framework and basic implementation idea of bottom-up functional region discovering algorithm,including mining the frequent travel pattern subgraphs and discovering frequent travel pattern from these subgraphs.Thirdly,this paper proposed a functional region cluster algorithm to cluster the obtained travel pattern graph set,thus discovering the functional regions according to the clustering results.The experimental results show that this method is effective and achieves higher purity of the function compared with traditional methods,and the entropy is decreased by 10%.

Location Prediction Method Based on Similarity of Users Moving Behavior

LI Sheng-zhi, QIAO Jian-zhong, LIN Shu-kuan

Computer Science. 2018, 45 (12): 288-292. doi:10.11896／j.issn.1002-137X.2018.12.046

Abstract

PDF(2231KB) ( 591 )

References | Related Articles | Metrics

With the development and widespread use of mobile communication technology and global positioning system,location-based service (LBS) receives extensive attention.Location prediction technology is an important part of LBS,and has wide application.In practical application,GPS trajectories are often sparse due to the sampling points lost or a new user appearing,which makes the accuracy of location prediction based on data of a single user low.To solve this problem,this paper proposed a novel Markov location prediction approach based on similarity of moving behavior and clustering of users.Firstly,in order to endow the locations with physical meaning,this paper proposed a region partitioning method based on Voronoi diagram.Then,the paper transformed the GPS trajectories into region trajectories and predicted the locations over region trajectories.Secondly,this paper put forward a new approach to measure the simi-larity of users’ moving behavior by considering users’ transfer features and regional features.Thirdly,based on the similarity of moving behavior,this paper divided users into various groups and applied the first-order Markov model on the groups for location prediction,which improves the accuracy of location prediction.The experiments over real GPS trajectory dataset indicate that the proposed method is effective for location prediction.

Cloud Storage System Based on Network Coding

LIU Yan-tao, LIU Heng

Computer Science. 2018, 45 (12): 293-298. doi:10.11896／j.issn.1002-137X.2018.12.047

Abstract

PDF(2248KB) ( 713 )

References | Related Articles | Metrics

Storage,repair bandwidth and update bandwidth are three performance metrics for a cloud storage system.System design needs to make trade-off among them.To decrease the consumption on storage,repair bandwidth update bandwidth and system complexity,this paper proposed a network coding based cloud storage system.This system is in the form of an m*n data array.The n columns stand for n storage nodes,which are comprised of two parts,one is systematic part which stores source symbols,and the other is nonsystematic part which stores parity symbols.The m rows of the data array stand for the number of m(n,k) systematic Maximum Distance Separable (MDS) code.Any source symbol is only involved into encoding within the unique row in which it locates and is not used by other rows.Such a structure significantly decreases the complexity of encoding and decoding.The functionality of the system is still available even in front of the failures of less than (n－k) nodes.Moreover,by using interference alignment,systematic MDS code is beneficial to further reduce repair bandwidth in case of single node failures.Compared to some existing cloud storage schemes,the system greatly reduces the resource consumption on storage space,update bandwidth and repair bandwidth,so its performance is improved significantly.

Method of Similarity Join on Uncertain Graphs Using MapReduce

MIAO Feng-yu, WANG Hong-zhi, RUAN Qun-sheng

Computer Science. 2018, 45 (12): 299-307. doi:10.11896／j.issn.1002-137X.2018.12.048

Abstract

PDF(1584KB) ( 548 )

References | Related Articles | Metrics

Compared to the similarity join on the deterministic graph,the similarity join on the uncertain graph usually has greater practical application value and higher computational complexity.This paper studied the similarity join on uncertain graph databases based on MapReduce distributed programming framework,and proposed two pruning strategies using the existence probability,namely Map Side Pruning and Reduce Side Pruning.The Map Side Pruning can filter out the uncertain graphs at the Map side which have no chance to be similar with any other uncertain graph at the Map side.The Reduce Side Pruning can reduce the candidate pairs at Reduce side in the process of reduction.Based on the above pruning approaches,this paper proposed a similarity join algorithm MUGSJoin on uncertain graph databases based on MapReduce.The experiment results show that the proposed approach has much better performance and scala-bility than the similar algorithms.

De Novo Transcriptome Assembly Algorithm Based on RNA-Seq Datasets

WU Si-wen, LI Jing, ZHANG Shao-qiang

Computer Science. 2018, 45 (12): 308-312. doi:10.11896／j.issn.1002-137X.2018.12.049

Abstract

PDF(1623KB) ( 553 )

References | Related Articles | Metrics

Transcriptome assembly is an important part of genome sequencing and function annotations.To improve the precision and efficiency of transcriptome assembly,this paper presented a new de novo transcriptome assembly algorithm called StepLink.The main innovations of this algorithm are presenting two concepts,namely leftmost k-mer (short sequence of length k) and right k-mer,and using the hash of hashes table to store the k-mer pairs,which makes the assembly more quickly and accurately.This algorithm was used to assemble the datasets of human,dog and mouse in the SRA databases respectively.The experimental results suggest that the proposed algorithm has higher efficiency than other existing algorithms.