Supervised and Sponsored by Chongqing Southwest Information Co., Ltd.
CODEN JKIEBK
Featured ArticlesMore...


Development of Parallel Computing Subject
陈国良, 张玉杰. 并行计算学科发展历程[J]. 计算机科学, 2020, 47(8): 14.
CHEN Guoliang, ZHANG Yujie, . Development of Parallel Computing Subject[J]. Computer Science, 2020, 47(8): 14.  CHEN Guoliang, ZHANG Yujie,
 Computer Science. 2020, 47 (8): 14. doi:10.11896/jsjkx.200600027
 Abstract ( 11 ) PDF(1062KB) ( 14 )
 References  Related Articles  Metrics

Computational science has become the third science in parallel with traditional theoretical science and experimentalscience.They complement each other and promote the development of human science and technology and the progress of social civilization.The research frontiers of key scientific and economic problems in the 21st century may be solved by computing techniques and computing science.Highperformance computing is a manifestation of a country’s comprehensive national strength, and it is one of the key technologies supporting the continuous development of national strength.It has an important strategic position in national defense security, hightech development and national economic construction.Through more than 40 years of development, we have focused on parallel computers, parallel algorithms and parallel programming, integrating parallel computer architecture, numerical and nonnumerical parallel algorithm design and parallel program design, forming parallel computing “architecturealgorithmprogrammingapplication” disciplinary system and system curriculum framework.This article reviews the work we have done in the development of parallel computing, and introduces the calculation methods in nonnumerical computing and the research of new nonvon Neumann structured computer architecture.

Survey of Heterogeneous Hybrid Parallel Computing
阳王东, 王昊天, 张宇峰, 林圣乐, 蔡沁耘. 异构混合并行计算综述[J]. 计算机科学, 2020, 47(8): 516.
YANG Wangdong, WANG Haotian, ZHANG Yufeng, LIN Shengle, CAI Qinyun. Survey of Heterogeneous Hybrid Parallel Computing[J]. Computer Science, 2020, 47(8): 516.  YANG Wangdong, WANG Haotian, ZHANG Yufeng, LIN Shengle, CAI Qinyun
 Computer Science. 2020, 47 (8): 516. doi:10.11896/jsjkx.200600045
 Abstract ( 5 ) PDF(3592KB) ( 8 )
 References  Related Articles  Metrics

With the rapid increase in computing power demand of computer applications such as artificial intelligence and big data and the diversification of application scenarios, the research of heterogeneous hybrid parallel computing has become the focus of research.This paper introduces the current main heterogeneous computer architecture, including CPU/coprocessor, CPU/manycore processor, CPU/ASCI and CPU/FPGA heterogeneous architectures.The changes made by the heterogeneous hybrid parallel programming model with the development of various heterogeneous hybrid structures are briefly described, which is a transformation and reimplementation of an existing language, or an extension of an existing heterogeneous programming language, or heterogeneous programming using instructional statements, or container pattern collaborative programming.The analysis shows that the heterogeneous hybrid parallel computing architecture will further strengthen the support for AI, and will also enhance the versatility of the software.This paper reviewes the key technologies in heterogeneous hybrid parallel computing, including parallel task partitioning, task mapping, data communication, data access between heterogeneous processors, parallel synchronization of heterogeneous collaboration, and pipeline parallelism of heterogeneous resources.Based on these key technologies, this paper points out the challenges faced by heterogeneous hybrid parallel computing, such as programming difficulties, portability difficulties, large data communication overhead, complex data access, complex parallel control, and uneven resource load.The challenges faced by heterogeneous hybrid parallel computing are analyzed, and this paper concludes that the current key core technologies need to be integrated from generalpurpose and AIspecific heterogeneous computing, seamless migration of heterogeneous architectures, unified programming model, integration of storage and computing, and intelligence breakthroughs in task division and allocation

Communication Optimization Method of Heterogeneous Cluster Application Based on New Language Mechanism
崔翔, 李晓雯, 陈一峯. 基于新型语言机制的异构集群应用通信优化方法[J]. 计算机科学, 2020, 47(8): 1715.
CUI Xiang, LI Xiaowen, CHEN Yifeng. Communication Optimization Method of Heterogeneous Cluster Application Based on New Language Mechanism[J]. Computer Science, 2020, 47(8): 1715.  CUI Xiang, LI Xiaowen, CHEN Yifeng
 Computer Science. 2020, 47 (8): 1715. doi:10.11896/jsjkx.200100124
 Abstract ( 8 ) PDF(1901KB) ( 12 )
 References  Related Articles  Metrics

Compared with traditional cluster, heterogeneous cluster has obvious advantage in cost performance.However, compared with the rapidly developing hardware technology, the current software technology is still backward and cannot adapt to the constantly updated heterogeneous hardware and the superlarge scale parallel computing environment.Currently, the common solution is to directly use parallel programming tools for different hardware.The disadvantages of this combination solution are that the programming level is low and it is difficult to develop, modify and debug.This paper introduces a new language mechanism to describe the multidimensional rule structure, arrangement and communication mode of data and threads.A new method of software migration and optimization between heterogeneous systems based on new language mechanism is proposed.Taking the direct normal turbulence simulation as an example, the communication optimization and fast migration for different heterogeneous systems are realized.

Joint Optimization Algorithm for PartitionScheduling of Dynamic Partial Reconfigurable Systems Based on Simulated Annealing
王喆, 唐麒, 王玲, 魏急波. 一种基于模拟退火的动态部分可重构系统划分调度联合优化算法[J]. 计算机科学, 2020, 47(8): 2631.
WANG Zhe, TANG Qi, WANG Ling, WEI Jibo. Joint Optimization Algorithm for PartitionScheduling of Dynamic Partial Reconfigurable Systems Based on Simulated Annealing[J]. Computer Science, 2020, 47(8): 2631.  WANG Zhe, TANG Qi, WANG Ling, WEI Jibo
 Computer Science. 2020, 47 (8): 2631. doi:10.11896/jsjkx.200500110
 Abstract ( 2 ) PDF(1476KB) ( 3 )
 References  Related Articles  Metrics

Dynamically partially reconfigurable (DPR) technology based on FPGA has many applications in the field of highperformance computing because of its advantages in processing efficiency and power consumption.In the DPR system, the partition of the reconfigurable region and task scheduling determine the performance of the entire system.Therefore, how to model the logic resource partition and scheduling of the DPR system and devising an efficient solution algorithm are the keys to ensure the performance of the system.Based on the establishment of the partition and scheduling model, a joint optimization algorithm of DPR system partitionscheduling based on simulated annealing (SA) is designed to optimize the reconfigurable region partitioning and task scheduling.A new method is proposed for skip infeasible solutions and poor solutions effectively which accelerates the search of solution space and increases the convergence speed of the SA algorithm.Experimental results show that, compared with mixed integer linear programming (MILP) and ISk, the proposed algorithm based on SA has lower time complexity, and for the largescale applications, it can solve better partition and scheduling results in a short time.

Parallelizing Multigrid Application Using Datadriven Programming Model
郭杰, 高希然, 陈莉, 傅游, 刘颖. 用数据驱动的编程模型并行多重网格应用[J]. 计算机科学, 2020, 47(8): 3240.
GUO Jie, GAO Xiran, CHEN Li, FU You, LIU Ying. Parallelizing Multigrid Application Using Datadriven Programming Model[J]. Computer Science, 2020, 47(8): 3240.  GUO Jie, GAO Xiran, CHEN Li, FU You, LIU Ying
 Computer Science. 2020, 47 (8): 3240. doi:10.11896/jsjkx.200500093
 Abstract ( 2 ) PDF(3157KB) ( 1 )
 References  Related Articles  Metrics

Multigrid is an important family of algorithms to accelerate the convergence of iterative solvers for linear systems, and it plays an important role in largescale scientific computing.At present, distributedmemory systems have evolved to large scale systems based on multicore nodes or heterogeneous nodes with accelerators.Legacy applications face the urgent need to be ported to modern supercomputers with diverse nodelevel architectures.In this paper, a datadriven programming language, AceMesh is introduced, and using this directive language, NAS MG is ported to two homemade supercomputers which are Tianhe2 and Sunway TaihuLight supercomputer.This paper shows how to taskify computation loops and communicationrelated codes in AceMesh, and analyzes the characteristics on its task graph and on its computationcommunication overlapping.Experimental results show that compared with traditional programming models, the AceMesh versions achieve relative speedup up to 1.19X and 1.85X on Sunway TaihuLight and Tianhe2 respectively.Analyses show that performance improvements come from two main reasons, memoryrelated optimization and communication overlapping optimization.At last, future directions are put forward to further optimize interprocess communications for the AceMesh version.

Computing Resources Allocation with Load Balance in Modern Processor
王国澎, 杨剑新, 尹飞, 蒋生健. 负载均衡的处理器运算资源分配方法[J]. 计算机科学, 2020, 47(8): 4148.
WANG Guopeng, YANG Jianxin, YIN Fei, JIANG Shengjian. Computing Resources Allocation with Load Balance in Modern Processor[J]. Computer Science, 2020, 47(8): 4148.  WANG Guopeng, YANG Jianxin, YIN Fei, JIANG Shengjian
 Computer Science. 2020, 47 (8): 4148. doi:10.11896/jsjkx.191000148
 Abstract ( 2 ) PDF(1828KB) ( 2 )
 References  Related Articles  Metrics

To improve the efficiency of program, it is used to arrange multiple function units in modern superscalar processor, supporting to execute instructions in parallel.The allocation policy of computing resources plays an important role in taking full advantage of multiple function units.Although the policy of how to allocate computing resources and schedule instruction has been well studied in literature, the proposed solutions almost concentrate on optimization methods at compile time, which is mostlystatic, inflexible and inefficient because of lack of computing pipeline information at run time.To mitigate the negative impacts of improper computing resource allocation and maximize the power of multiple function units, this paper abstracts the mathematical model of resource allocation problem at run time and makes a study of hardware finegrained automatic method based on symmetric and asymmetric configuration of function units, in order to make dynamic and wise computing resource allocating decision when instructions are issued in general situation.As a result, a loadbalanced greedy resource allocation strategy is proposed and evaluated.The experimental results show that our policy is efficient to minimize blocking time caused by unfair allocation of computing resources.Furthermore, the more computing resources are provided, the better performance our policy can yield.

Parallel Algorithm of Deep Transductive Nonnegative Matrix Factorization for Speech Separation
李雨蓉, 刘杰, 刘亚林, 龚春叶, 王勇. 面向语音分离的深层转导式非负矩阵分解并行算法[J]. 计算机科学, 2020, 47(8): 4955.
LI Yurong, LIU Jie, LIU Yalin, GONG Chunye, WANG Yong. Parallel Algorithm of Deep Transductive Nonnegative Matrix Factorization for Speech Separation[J]. Computer Science, 2020, 47(8): 4955.  LI Yurong, LIU Jie, LIU Yalin, GONG Chunye, WANG Yong
 Computer Science. 2020, 47 (8): 4955. doi:10.11896/jsjkx.190900202
 Abstract ( 2 ) PDF(2394KB) ( 5 )
 References  Related Articles  Metrics

Nonnegative matrix factorization can preserve the nonnegative features of the speech signal.It is an important method for speech separation.However, this method has the problems of complicated data operation and computation, it is necessary to propose a parallel method to reduce computation time.Aiming at the calculation problem of speech separation pretraining and separation process, this paper proposes a deep transductive nonnegative matrix factorization multilevel parallel algorithm, which considers the data correlation of the iterative update process, and designs a multilevel parallel algorithm between tasks and within tasks.The parallel algorithm at the task level decomposes the training speech to obtain the corresponding base matrix as two independent tasks in parallel calculation.The matrix is divided into rows and columns at the internal process level of the task.The master process distributes the matrix blocks to the slave process, and the slave process receives the current submatrix, then the matrix block calculates the result matrix subblock, and then sends the current process matrix block to the next process to achieve the traversal of each matrix block of the second matrix in all processes, calculating the product of the corresponding subblock of the result matrix, and finally the subblock is collected by the main process from the slave process.During the threadlevel submatrix multiplication operation, an acceleration strategy of generating multiple threads and exchanging data through shared memory for submatrix block calculation is adopted.This algorithm is the first one to implement deep transduction nonnegative matrix factorization algorithm.The experimentis performed on the Tianhe II platform.The test results show that when separating multispeaker mixed speech signals without changing the separation effect, in the pretraining process, the proposed parallel algorithm performs well using 64 processes at a speed ratio of 18, and in the separation process, the corresponding speedup is 24.Compared to serial and MPI model separation, hybrid model separation time is greatly shortened, which proves that for the speech separation process, the parallel algorithm proposed in this paper can effectively improve the separation efficiency.

Design and Optimization of Twolevel Particlemesh Algorithm Based on Fixedpoint Compression
程盛淦, 于浩然, 韦建文, 林新华. 基于定点压缩技术的双层粒子网格算法的设计与优化[J]. 计算机科学, 2020, 47(8): 5661.
CHENG Shenggan, YU Haoran, WEI Jianwen, James LIN. Design and Optimization of Twolevel Particlemesh Algorithm Based on Fixedpoint Compression[J]. Computer Science, 2020, 47(8): 5661.  CHENG Shenggan, YU Haoran, WEI Jianwen, James LIN
 Computer Science. 2020, 47 (8): 5661. doi:10.11896/jsjkx.200200112
 Abstract ( 1 ) PDF(1841KB) ( 1 )
 References  Related Articles  Metrics

Largescale Nbody simulation is of great significance for the study of modern physical cosmology.One of the most popular Nbody simulation algorithms is particlemesh(PM).However, the PMbased algorithms cost considerable amounts of memory, which becomes the bottleneck to scale the Nbody simulations in the modern supercomputer.Therefore, this paper proposes to use fixedpoint compression to reduce memory footprints per Nbody particle to only 6 bytes, nearly an order of magnitude lower than the traditional PMbased algorithms.This paper implements the twolevel particlemesh algorithm with fixedpoint compression and optimizes it with mixedprecision computation and communication optimizations.These optimizations significantly reduce the performance loss caused by fixedpoint compression.The proportion of compression and decompression in the total time of the program reduces from 21% to 8% and achieves up to 2.3 times speedup on computing hotspots which make the algorithm maintain high efficiency and scalability with low memory consumption.

Prediction of Loop Tiling Size Based on Neural Network
池昊宇, 陈长波. 基于神经网络的循环分块大小预测[J]. 计算机科学, 2020, 47(8): 6270.
CHI Haoyu, CHEN Changbo. Prediction of Loop Tiling Size Based on Neural Network[J]. Computer Science, 2020, 47(8): 6270.  CHI Haoyu, CHEN Changbo
 Computer Science. 2020, 47 (8): 6270. doi:10.11896/jsjkx.191200180
 Abstract ( 1 ) PDF(2981KB) ( 2 )
 References  Related Articles  Metrics

Optimization of loop programs is an important topic in program optimization.As a typical technique of loop optimization, loop tiling has been widely studied and applied.The selection of tile size, which is complex and highly dependent on program and hardware, has a great impact on the performance of loops.Traditional approaches based on static analysis and heuristic experience search have high cost of labor and time, and lack generality and portability.Therefore, the neural network method, which is good at representing highdimensional information, is considered to learn the hidden correlation between tiling size and program performance, which is a result of complex interaction between program and hardware.A new group of features with 29 dimensions are extracted based on size of the problem, structure of the loop, locality of the operations within the loop.The experiments are carried out on hundreds of thousands of lines of six kinds of kernel programs (3D loop, 2D data) with random sizes in the range of 1024 to 2048.The sequential model (TSST6) achieves an average speedup of 6.64 compared with GCCO2, 98.5% of the average maximum available performancecompared with the exhaustive search, and an average 9.9% performance improvement compared with Pluto.The parallel model (TSSPT6Search) achieves an average speedup of 2.41 compared with the OpenMP default optimization, 91.7% of the average maximum available performance compared with the exhaustive search, and an average 9% performance improvement compared with Pluto default parallel tiling optimization.

Algorithm Design of Variable Precision Transcendental Functions
郝江伟, 郭绍忠, 夏媛媛, 许瑾晨. 可变精度超越函数算法设计[J]. 计算机科学, 2020, 47(8): 7179.
HAO Jiangwei, GUO Shaozhong, XIA Yuanyuan, XU Jinchen. Algorithm Design of Variable Precision Transcendental Functions[J]. Computer Science, 2020, 47(8): 7179.  HAO Jiangwei, GUO Shaozhong, XIA Yuanyuan, XU Jinchen
 Computer Science. 2020, 47 (8): 7179. doi:10.11896/jsjkx.200200013
 Abstract ( 2 ) PDF(3052KB) ( 1 )
 References  Related Articles  Metrics

Transcendental functions are the main part of fundamental mathematical software library.Their accuracy and performance greatly determine those of the upperlayer applications.Aiming at the problems of tedious and errorprone implementation of transcendental functions as well as accuracy requirements of different applications, a variable precision transcendental function algorithm is proposed, which considers both generality and mathematical characteristics of functions.Based on the similarity of transcendental functions, a transformationreductionapproximationreconstruction algorithm template is constructed to unify common transcendental function algorithm implementations, and the algorithm template parameters are adjusted to handle errors to generate different precision versions of function codes.Experiment results show that the algorithm is able to generate function codes of different precision versions of common transcendental functions and has performance advantages over the corresponding functions in the standard mathematical software library.

Cuckoo Hash Table Based on Smart Placement Strategy
金琪, 王俊昌, 付雄. 基于智能放置策略的Cuckoo哈希表[J]. 计算机科学, 2020, 47(8): 8086.
JIN Qi, WANG Junchang, FU Xiong. Cuckoo Hash Table Based on Smart Placement Strategy[J]. Computer Science, 2020, 47(8): 8086.  JIN Qi, WANG Junchang, FU Xiong
 Computer Science. 2020, 47 (8): 8086. doi:10.11896/jsjkx.191200109
 Abstract ( 0 ) PDF(2074KB) ( 0 )
 References  Related Articles  Metrics

Because time overhead of query is O (1), Cuckoo hash table has been widely used in big data, cloud computing and other fields.However, insertion of the existing Cuckoo hash tables generally uses random replacement strategy to replace existing entries when encountering conflicts.On the one hand, writers are prone to highlatency insertion and infinite loops, especially when the load rate of hash table is relatively high, and even have the risk of reconstructing entire hash table;on the other hand, due to existing random replacement strategies, entries are scattered as much as possible in the buckets of hash table.The lack of good spatial locality among entries reduces the efficiency of positive query.To solve the above problems, this paper proposes a Cuckoo hash table based on smart placement strategy.Specifically, in order to improve efficiency of insertion, a loadbalance Cuckoo hash table (LBCHT) is proposed, which limits the load of each bucket in real time, using breadthfirst search to find the best Cuckoo path to ensures load balancing among buckets.Experimental results show that LBCHT can effectively reduce long tail effect of insertion under high load rate.And in order to improve efficiency of lookup, a Cuckoo hash table that makes full use of the locality principle is proposed (LPCHT).By fully exploring the spatial Locality among entries, CPU cache miss rate caused by lookup is reduced and efficiency of positive query is improved.Experiments show that in a high load rate stress test environment, compared with libcuckoo, LBCHT throughput of insertion can be increased by 50%, and LPCHT improves positive query efficiency by 7%.

Large Scalability Method of 2D Computation on Shenwei Manycore
庄园, 郭强, 张洁, 曾云辉. 大规模申威众核环境下二维数据计算的可扩展方法[J]. 计算机科学, 2020, 47(8): 8792.
ZHUANG Yuan, GUO Qiang, ZHANG Jie, ZENG Yunhui. Large Scalability Method of 2D Computation on Shenwei Manycore[J]. Computer Science, 2020, 47(8): 8792.  ZHUANG Yuan, GUO Qiang, ZHANG Jie, ZENG Yunhui
 Computer Science. 2020, 47 (8): 8792. doi:10.11896/jsjkx.191000011
 Abstract ( 0 ) PDF(1963KB) ( 1 )
 References  Related Articles  Metrics

With the development of supercomputer and its programming environment, multilevel parallelism under heterogeneous system infrastructure is a promising trend.Applications ported to Sunway TaihuLight are typical.Since the Sunway TaihuLight was open to public in 2016, many scholars focus on the method study and application verification, so much experience on Shenwei manycore programming method is accumulated.However, when the CESM model is ported to Shenwei manycore infrastructure, some two dimensional computations in the ported POP model show quite good results under 1024 processes.On the contrary, they perform much worse than the original version, and false acceleration ratios appeared under 16800 processes.Upon this problem, a new parallel method based on slavecore partitions was proposed.Under the new parallel method, the 64 slavecores in a coregroup are divided into some disjoint small partitions, which make that different and independent computing kernels can run at different slavecore partitions simultaneously.In the method, the computing kernels can be loaded to different slavecore partitions with the suitable data size and computational load, where the amount and number of the slavecores in each partition can be properly set according to the computing scale, so the slavecore’s calculation ability can be fully utilized.Based on the new parallel method, also with the loops combination and function expansion, the slavecores are fully applied and some computing time among several parallel running codes is hidden.Furthermore, it is effective to extend the parallel granularity of the kernels to be athreaded.Applied the above methods, the simulation speed of POP model in highresolution CESM Gcompset is improved by 0.8 simulation year per day under 1.1 million cores.

Largescale Quantum Fourier Transform Simulation Based on SW26010
刘晓楠, 荆丽娜, 王立新, 王美玲. 基于申威26010处理器的大规模量子傅里叶变换模拟[J]. 计算机科学, 2020, 47(8): 9397.
LIU Xiaonan, JING Lina, WANG Lixin, WANG Meiling. Largescale Quantum Fourier Transform Simulation Based on SW26010[J]. Computer Science, 2020, 47(8): 9397.  LIU Xiaonan, JING Lina, WANG Lixin, WANG Meiling
 Computer Science. 2020, 47 (8): 9397. doi:10.11896/jsjkx.200300015
 Abstract ( 0 ) PDF(2381KB) ( 1 )
 References  Related Articles  Metrics

Quantum computing has a natural parallel advantage due to its entanglement and superposition.However, current quantum computing equipment is limited to the technological level of physical realization.It takes a certain amount of time to accumulate and break through to achieve huge computing power and solve practical problems with practical significance.Therefore, using classical computers to simulate quantum computing has become an effective way to verify quantum algorithms.Quantum Fourier Transform is a key part of many quantum algorithms.It involves phase estimation, order finding, factors, etc.Research on Quantum Fourier Transform and largescale simulation implementation can effectively promote the research, verification and optimization of related quantum algorithms.In this paper, a largescale Quantum Fourier Transform is simulated using the supercomputer, “Sunway TaihuLight”, independently developed by our country.According to the heterogeneous parallel characteristics of SW26010 processor, MPI, accelerated thread library, and communication and computing hiding technology are adopted to optimize the system.The correctness of the Quantum Fourier Transform simulation is verified by seeking the period in the Shor algorithm, and the simulation and optimization of the Quantum Fourier Transform of 46Qubits are realized, which provides reference for the verification and optimization of other quantum algorithms on the supercomputing platform and the proposal of new quantum algorithms.

Optimization of BFS on Domestic Heterogeneous Manycore Processor SW26010
袁欣辉, 林蓉芬, 魏迪, 尹万旺, 徐金秀. 面向国产异构众核处理器SW26010的BFS优化方法[J]. 计算机科学, 2020, 47(8): 98104.
YUAN Xinhui, LIN Rongfen, WEI Di, YIN Wanwang, XU Jinxiu. Optimization of BFS on Domestic Heterogeneous Manycore Processor SW26010[J]. Computer Science, 2020, 47(8): 98104.  YUAN Xinhui, LIN Rongfen, WEI Di, YIN Wanwang, XU Jinxiu
 Computer Science. 2020, 47 (8): 98104. doi:10.11896/jsjkx.191000013
 Abstract ( 0 ) PDF(3058KB) ( 2 )
 References  Related Articles  Metrics

In recent years, there is growing concern for the processing capabilities of dataintensive task.Breadthfirst search(BFS) is a typical dataintensive problem, which is widely used in a variety of graph algorithms.Graph 500 Benchmark, taking BFS algorithm as the core, has become the benchmark for the evaluation of processing capabilities of dataintensive tasks.Sunway TaihuLight supercomputer topped the Top 500 list for four consecutive times from June 2016 to November 2017, the processor of which, named SW26010, is the first Chinese homegrown heterogeneous manycore processor.This paper studies how to use the architecture characteristics of SW26010 to accelerate BFS algorithm.A directionoptimizing hybrid BFS algorithm based on a single core group(CG) is implemented on SW26010, using bytemap to release the data dependencies in inner loops, hiding overhead of calculation and SPM access by using asynchronous DMA, taking advantage of heterogeneous architecture to compute collaboratively and carrying out graph preprocessing.Eventually, with Graph 500 as the benchmark processing a scale 22 graph, a single CG of SW26010 processor achieves a performance of 457.54MTEPS.

Realtime SIFT Algorithm Based on GPU
汪亮, 周新志, 严华. 基于GPU的实时SIFT算法[J]. 计算机科学, 2020, 47(8): 105111.
WANG Liang, ZHOU Xinzhi, YNA Hua. Realtime SIFT Algorithm Based on GPU[J]. Computer Science, 2020, 47(8): 105111.  WANG Liang, ZHOU Xinzhi, YNA Hua
 Computer Science. 2020, 47 (8): 105111. doi:10.11896/jsjkx.190700036
 Abstract ( 1 ) PDF(4602KB) ( 3 )
 References  Related Articles  Metrics

Aiming at the complex and low realtime defects of the SIFT feature extraction algorithm, a realtime SIFT algorithm based on GPU is proposed, called CoSift (CUDA Optimized SIFT).Firstly, the algorithm uses the CUDA stream concurrency mechanism to construct the SIFT scale space.In this process, the highspeed memory in the CUDA memory model is fully utilized to improve data access speed, and the twodimensional Gaussian convolution kernel is optimized to reduce the amount of computation.Then, the warpbased histogram policy is designed to rebalance the workload during the characterization process.Compared with the traditional algorithm of the CPU version and the improved algorithm of the GPU version, the proposed algorithm greatly improves the realtime performance of the SIFT algorithm without reducing the accuracy of feature extraction, and has a relatively higher optimization effect on largesize images.CoSift can extract features within 7.7~8.8ms (116.28~129.87fps) on the GTX1080Ti.The algorithm effectively reduces the complexity of the traditional SIFT algorithm process, improves the realtime performance, and is convenient to be applied in scenarios where the realtime requirement of SIFT algorithm is higher.

Energy Efficient Scheduling Algorithm of Workflows with Cost Constraint in Heterogeneous Cloud Computing Systems
张龙信, 周立前, 文鸿, 肖满生, 邓晓军. 基于异构云计算的成本约束下的工作流能量高效调度算法[J]. 计算机科学, 2020, 47(8): 112118.
ZHANG Longxin, ZHOU Liqian, WEN Hong, XIAO Mansheng, DENG Xiaojun. Energy Efficient Scheduling Algorithm of Workflows with Cost Constraint in Heterogeneous Cloud Computing Systems[J]. Computer Science, 2020, 47(8): 112118.  ZHANG Longxin, ZHOU Liqian, WEN Hong, XIAO Mansheng, DENG Xiaojun
 Computer Science. 2020, 47 (8): 112118. doi:10.11896/jsjkx.200300038
 Abstract ( 0 ) PDF(1843KB) ( 1 )
 References  Related Articles  Metrics

Cloud computing has become a very important computing service mode in various industries.Traditional studies on cloud computing mainly focus on the research of service quality such as the pricing mode, profit maximization and execution efficiency of cloud services.Green computing is the development trend of distributed computing.Aiming at the scheduling problem of workflow task set that meets the computing cost constraint of cloud users in heterogeneous cloud environment, an energyaware based on budget level scheduling algorithm(EABL) with low time complexity is proposed.The EABL algorithm consists of three main stages:task priority establishment, task budget cost allocation, optimal execution virtual machine and energy efficiency frequency selection of the parallel task set, so as to minimize the energy consumption during task set execution under the constraint of budget cost.A largescale workflow task sets in the real world are used to conduct a large number of tests on the algorithm for the experiment in this paper.Compared with famous algorithms EA_HBCS and MECABP, EABL algorithm can effectively reduce the energy consumption in the computing process of cloud data centers by making full use of the budget cost.

ENLHS:Sampling Approach to Auto Tuning Kafka Configurations
谢文康, 樊卫北, 张玉杰, 徐鹤, 李鹏. ENLHS:一种基于抽样的Kafka自适应调优方法[J]. 计算机科学, 2020, 47(8): 119126.
XIE Wenkang, FAN Weibei, ZHANG Yujie, XU He, LI Peng. ENLHS:Sampling Approach to Auto Tuning Kafka Configurations[J]. Computer Science, 2020, 47(8): 119126.  XIE Wenkang, FAN Weibei, ZHANG Yujie, XU He, LI Peng
 Computer Science. 2020, 47 (8): 119126. doi:10.11896/jsjkx.200300010
 Abstract ( 0 ) PDF(2357KB) ( 1 )
 References  Related Articles  Metrics

When Kafka is applied in a production environment, its performance is not only limited by the machine’s hardware environment and system platform.Its own configuration items are the key element to judge whether it can achieve the desired performance under the condition of limited hardware resources, but it is manually configured.The efficiency of item modification and tuning is extremely poor.If the actual resource environment is not optimized, Kafka cannot guarantee its performance in each production environment using default configuration parameters.Because Kafka’s configuration bound is extremely large, the performance of traditional adaptive algorithms in largescale production systems is poor.Therefore, in order to improve Kafka’s adaptive ability, eliminate complexity in the system, and obtain better operating performance, an adaptive performance tuning method for Kafka is proposed, which fully considers the influence weights of Kafka’s characteristic parameters and performance.It uses the principle of sampling to improve the efficiency of data sets generation and optimize the range of data selection, improve the efficiency of modeling and reduce the complexity of optimization methods.Experiments show that the algorithm optimizes the throughput rate and latency of the open source version Kafka, improves Kafka’s throughputs under a given system resource, and reduces latency.

Highperformance FPGA Implementation of Elliptic Curve ECC on Binary Domain
尤文珠, 葛海波. 二进制域上椭圆曲线密码ECC的高性能FPGA实现[J]. 计算机科学, 2020, 47(8): 127131.
YOU Wenzhu, GE Haibo. Highperformance FPGA Implementation of Elliptic Curve ECC on Binary Domain[J]. Computer Science, 2020, 47(8): 127131.  YOU Wenzhu, GE Haibo
 Computer Science. 2020, 47 (8): 127131. doi:10.11896/jsjkx.200600112
 Abstract ( 1 ) PDF(2308KB) ( 3 )
 References  Related Articles  Metrics

In recent years, the communications field has achieved tremendous development.Applications such as online banking and mobile communications have increased the security requirements in resourceconstrained environments.Compared with traditional cryptographic algorithms, elliptic curve cryptosystem(ECC) provides better security standards and more space for optimizing performance parameters.Therefore, an efficient elliptic curve cipher hardware design scheme is proposed.Based on the existing research, the proposed scheme uses the projected coordinate system LD Montgomery ladder algorithm to study the core scalar multiplication operation in ECC, and uses parallel scheduling to reduce delay in the group operation layer.For finite field operations, the bitparallel multiplication algorithm and improved Euclidean inverse algorithm are adopted.Based on Xilinx Virtex5 and Virtex7 FPGA device, the architecture is implemented on the binary domains with lengths of 163, 233 and 283 respectively.The experimental results show that the proposed scheme requires less FPGA resource consumption and faster calculation speed.Compared with other methods, the hardware resource consumption is reduced by 52.9% and the scalar multiplication operation speed is increased by 3.7times, so it is better suitable for the application of resourceconstrained devices.

Label Distribution Learning Based on Natural Neighbors
姚成亮, 朱庆生. 基于自然邻居的标记分布学习[J]. 计算机科学, 2020, 47(8): 132136.
YAO Chengliang, ZHU Qingsheng. Label Distribution Learning Based on Natural Neighbors[J]. Computer Science, 2020, 47(8): 132136.  YAO Chengliang, ZHU Qingsheng
 Computer Science. 2020, 47 (8): 132136. doi:10.11896/jsjkx.190700012
 Abstract ( 0 ) PDF(2100KB) ( 1 )
 References  Related Articles  Metrics

Label distribution is a new machine learning paradigm which can solve some markup ambiguity problems well.Label distribution can be seen as the generalization of multilabel.Traditional singlelabel learning and multilabel learning can be seen as special cases of label distribution learning.AAKNN based on algorithm adaptive is an effective algorithm, but it is diffcult to choose an appropriate parameter K which affects the perfomence when KNN is used.So, Natural neighbors is introduced into LDL and a new label distribution learning algorithm is proposed.It finds natural neighbors of each object by searching algorithm, and then gets the average of labels of these neighbours as the predicted result.The natural neighbours searching algorithm does not need any parameter and is passive so that neighbors of each object is decided automatically.Experiments was conducted on 6 data sets and 6 evaluation indexes.The experiments show that the proposed algorithm not only solves the problem of choosing parameter K, but also improves the performance compared with AAKNN.

Incremental Attribute Reduction Algorithm in Dominancebased Rough Set
桑彬彬, 杨留中, 陈红梅, 王生武. 优势关系粗糙集增量属性约简算法[J]. 计算机科学, 2020, 47(8): 137143.
SANG Binbin, YANG Liuzhong, CHEN Hongmei, WANG Shengwu. Incremental Attribute Reduction Algorithm in Dominancebased Rough Set[J]. Computer Science, 2020, 47(8): 137143.  SANG Binbin, YANG Liuzhong, CHEN Hongmei, WANG Shengwu
 Computer Science. 2020, 47 (8): 137143. doi:10.11896/jsjkx.190700188
 Abstract ( 0 ) PDF(2637KB) ( null )
 References  Related Articles  Metrics

In real life, as the data increase continuously, the relation between the original criteria and the decision making changes dynamically.How to effectively calculate the attribute reduction becomes an urgent problem to be solved in the dynamic decision making.Incremental updating method can effectively complete the dynamic learning task, because it can acquire new knowledge based on previous knowledge.This paper exploited the dominancebased rough set approach to study the incremental attribute reduction method when adding a single object to the data with dominant relation.Firstly, the dominant set matrix is defined as the target of the update to calculate the new dominant conditional entropy.Then, an incremental learning mechanism of the dominant conditional entropy is proposed by analyzing the three different situations of the adding object.After that, an incremental attribute reduction algorithm is designed based on the dominant set matrix.Finally, experiments on six different UCI data set are conducted to compare the effectiveness and efficiency of the incremental and nonincremental algorithms.The experimental results show that the incremental attribute reduction algorithm proposed in this paper is not only consistent with the nonincremental attribute reduction algorithm in term of effectiveness, but also far superior to the nonincremental attribute reduction algorithm in term of efficiency.Therefore, the proposed incremental algorithm can effectively and efficiently accomplish the task of attribute reduction in dynamical data with dominant relation.

Threeway Decision Models Based on Intuitionistic Hesitant Fuzzy Sets and Its Applications
陈玉金, 徐吉辉, 史佳辉, 刘宇. 基于直觉犹豫模糊集的三支决策模型及其应用[J]. 计算机科学, 2020, 47(8): 144150.
CHEN Yujin, XU Jihui, SHI Jiahui, LIU Yu. Threeway Decision Models Based on Intuitionistic Hesitant Fuzzy Sets and Its Applications[J]. Computer Science, 2020, 47(8): 144150.  CHEN Yujin, XU Jihui, SHI Jiahui, LIU Yu
 Computer Science. 2020, 47 (8): 144150. doi:10.11896/jsjkx.190800041
 Abstract ( 0 ) PDF(1504KB) ( 1 )
 References  Related Articles  Metrics

Due to the ability limitations of decision makers and the uncertainty of the objects being evaluated, the threeway decision models have insufficient expressive power in dealing with hesitant and fuzzy decision problems caused by fuzzy information and subjective cognitive concepts.In order to solve the above shortcomings, the intuitionistic fuzzy set is introduced to establish the corresponding threeway decision models.Firstly, considering that intuitionistic hesitant fuzzy set contains the characteristics of multiple membership degrees, the threeway decision method based on single intuitionistic fuzzy number is established in the case of determining the risk cost matrix.On this basis, threeway decision models based on intuitionistic hesitation fuzzy sets are established by using intuitionistic hesitation fuzzy sets as the domain.Then, taking into account the semantic interpretation of particular environment, decisionmaking rules based on optimism, pessimism, and minority obedience are formed.Finally, combining with the safety risk assessment methods in the aviation field, threeway decision methods of aviation safety risk based on double evaluation function are presented, and the concrete application process of the model is illustrated by an example.

Deep Domain Adaptation Algorithm Based on PE Divergence Instance Filtering
袁晨晖, 程春玲. 基于PE散度实例过滤的深度域适应方法[J]. 计算机科学, 2020, 47(8): 151156.
YUAN Chenhui, CHENG Chunling. Deep Domain Adaptation Algorithm Based on PE Divergence Instance Filtering[J]. Computer Science, 2020, 47(8): 151156.  YUAN Chenhui, CHENG Chunling
 Computer Science. 2020, 47 (8): 151156. doi:10.11896/jsjkx.190600175
 Abstract ( 1 ) PDF(1555KB) ( 2 )
 References  Related Articles  Metrics

Deep domain adaptation, one of the most common problems in transfer learning, has achieved excellent performance in many machine learning applications.However, the existing deep domain adaptation just adapts the fully connected layer while reduce domain shift, which ignores the spatial information and semantic context information of the convolutional layer, resulting in the loss of important information during the process of knowledge transfer.To this end, this paper combines instancebased domain adaptation with featurebased domain adaptation and proposes a deep domain adaptation algorithm based on PE divergence instance filtering (DAPEIF).Firstly, the relative importance weight of the source samples is calculated by PE divergence, and the source samples that are likely to cause negative transfer are deleted.Then the maximum mean discrepancy metric is included as a regularization term in the training of the neural network based on AlexNet, and the marginal probability distribution of the convolutional layer and the fully connected layer are jointly adapted to reduce the difference between the new source domain and the target domain.At the same time, the weight regularization term is introduced, and the network parameters are learned by the gradient descent to further improve the generalization performance of the model in the process of domain adaptation.The proposed algorithm can simultaneously assign domain adaptative ability to the parameters of the convolutional layer and the fully connected layer of the neural network.The experimental results on the public dataset OfficeCaltech in domain adaptation demonstrate that compared with the state of the art domain adaptation algorithms, the proposed algorithm has better performance in accuracy and the average accuracy reaches 84.46%.

Algorithm for Detecting Overlapping Communities Based on Centered Cliques
薛磊, 唐旭清. 基于中心团的重叠社区检测算法[J]. 计算机科学, 2020, 47(8): 157163.
XUE Lei, TANG Xuqing. Algorithm for Detecting Overlapping Communities Based on Centered Cliques[J]. Computer Science, 2020, 47(8): 157163.  XUE Lei, TANG Xuqing
 Computer Science. 2020, 47 (8): 157163. doi:10.11896/jsjkx.200300034
 Abstract ( 1 ) PDF(1985KB) ( 4 )
 References  Related Articles  Metrics

Community detection in complex network has become a vital way to understand its structure and dynamic characteristics.However, there are two inherent shortcomings that the parameter dependency and instability of using the traditional node clustering and link clustering to detect overlapping communities.This paper proposes an improving algorithm, that is, the local expansion method based on the centered clique(CLEM), for detecting overlapping communities.Firstly, in CLEM algorithm, the centered cliques is selected as the core seed and the nodes deleted by multiple times in the process of seed expansion are punished, so its stability of results is improved.Then, by selecting the fitness function with parameterindependent and improving its iterative calculation process, the parameter limitation of the fitness function is avoided and the computational complexity is quickly reduced.Finally, the test results on synthetic networks and realworld networks show that CLEM is good both in computing time and accuracy compared with some existing algorithms.

Opinion Wordpairs Collaborative Extraction Based on Dependency Relation Analysis
赵威, 林煜明, 王超强, 蔡国永. 基于依赖联系分析的观点词对协同抽取[J]. 计算机科学, 2020, 47(8): 164170.
ZHAO Wei, LIN Yuming, WANG Chaoqiang, CAI Guoyong. Opinion Wordpairs Collaborative Extraction Based on Dependency Relation Analysis[J]. Computer Science, 2020, 47(8): 164170.  ZHAO Wei, LIN Yuming, WANG Chaoqiang, CAI Guoyong
 Computer Science. 2020, 47 (8): 164170. doi:10.11896/jsjkx.190600153
 Abstract ( 2 ) PDF(1695KB) ( 5 )
 References  Related Articles  Metrics

In the same category of commodities, opinion wordpairs usually have strong opinion dependence relation to the opinion targets and the opinion words contained in them.Therefore, in the extraction process of opinion wordpairs, they can be extracted by analyzing the opinion dependence relations among the words in the review sentences.Firstly, a dependency relation analysis model is constructed to obtain the dependency relation information of each word in a review sentence, and the basic model is defined as LSTM neural network.Secondly, it is assumed that one of the item that opinion wordpairs contained in review sentence is known, and the known item is used as the model’s attention information, so that the model can focus on extracting the words of phrases associated with the known item with strong opinion dependence from the review sentence as another unknown item in the opinion wordpairs.Finally, the wordpairs with the highest score of the opinion dependence relation are output as the opinion wordpairs.Then a compound model is designed to realize the mining of opinion word pairs without knowing the known items in advance by combining the two models which contain the information of different known items in the opinion wordpairs.

Incremental Classification Model Based on Qlearning Algorithm
刘凌云, 钱辉, 邢红杰, 董春茹, 张峰. 一种基于Q学习算法的增量分类模型[J]. 计算机科学, 2020, 47(8): 171177.
LIU Lingyun, QIAN Hui, XING Hongjie, DONG Chunru, ZHANG Feng. Incremental Classification Model Based on Qlearning Algorithm[J]. Computer Science, 2020, 47(8): 171177.  LIU Lingyun, QIAN Hui, XING Hongjie, DONG Chunru, ZHANG Feng
 Computer Science. 2020, 47 (8): 171177. doi:10.11896/jsjkx.190600150
 Abstract ( 1 ) PDF(1369KB) ( 1 )
 References  Related Articles  Metrics

The traditional classification models are insufficient to take full advantage of the sequential data with their continuous and explosive growth due to the imprecision of the data.Therefore, the incremental learning is provided to handle this problem.However, the difference sequence of the training samples may have strong impact on performance of a classifier.Especially when the classifier is undertrained, traditional incremental learning method takes the risk of utilizing the noise samples with wrong labels to train the classifier.To overcome this problem, this paper proposes an incremental classification model based on Qlearning algorithm.The model employs the classical Qlearning algorithm in reinforcement learning to select the sequence samples incrementally, which is capable of softening the negative impact of the noise data and labels samples automatically as well.To overcome the problem of computational complexity along with the increasing of state space and action space of Qlearning, an improved batch incremental classification model based on Qlearning algorithm is proposed.Compared with the traditionally trained classifiers, the proposed model combines the ideas of online incremental learning and reinforcement learning, which is able to achieve high accuracy and can be updated online.Finally, the validity of the model is verified on three UCI datasets.The experimental results show that choosing training sets incrementally is helpful to improve the performance of the classifier and the precision of the classifier trained by different incremental training sequences varies greatly as well.The proposed incremental classification model based on Qlearning algorithm can make use of the limited available dataset for supervised initial training, and then construct newadded selfsupervised training set based on the Q value of each unlabeled sample to improve the accuracy of the classifier.Therefore, the incremental classification model based on Qlearning algorithm can be used to solve the problem of lack of supervisory information, and has a potential application.

KNearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection
董明刚, 黄宇扬, 敬超. 基于遗传实例和特征选择的K近邻训练集优化方法[J]. 计算机科学, 2020, 47(8): 178184.
DONG Minggang, HUANG Yuyang, JING Chao. KNearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection[J]. Computer Science, 2020, 47(8): 178184.  DONG Minggang, HUANG Yuyang, JING Chao
 Computer Science. 2020, 47 (8): 178184. doi:10.11896/jsjkx.190700089
 Abstract ( 0 ) PDF(2327KB) ( null )
 References  Related Articles  Metrics

The classification performance of KNearest Neighbor depends on the quality of training set.It is significant to design an efficient training set optimization algorithm.Two major drawbacks of traditional evolutionary training set optimization algorithm are low efficiency and removing the nonnoise samples and features by mistake.To address these issues, this paper proposes a genetic training set optimization algorithm.The algorithm uses the efficient genetic algorithm based on the maximum Hamming distance.Each cross preserves the parent and generates two new children with the largest Hamming distance, which not only improves the efficiency but also ensures the population diversity.In the proposed algorithm, the local noise sample deletion strategy is combined with the feature selection strategy.Firstly, the decision tree is used to determine the range of noise samples.Then the genetic algorithm is used to remove the noise samples in this range and select the features simultaneously.It reduces the risk of mistaken and improves the efficiency.At last, the 1NNbased selection strategy of validation set is used to improve the instance and feature selection accuracy of the genetic algorithm.Compared with coevolutionary instance feature selection algorithm ( IFSCoCo), weighted coevolutionary instance feature selection algorithm (CIWNN), evolutionary feature selection algorithm (EISRFS, evolutionary instance selection algorithm (PSNN) and traditional KNN, the average improvement of the proposed algorithm in classification accuracy is 2.18％ , 2.06％, 5.61％, 4.06％, 4.00％, respectively.The experiments results suggest that the proposed method has higher classification accuracy and optimization efficiency.

FSCRF:Outlier Detection Model Based on Feature Segmentation and Cascaded Random Forest
刘振鹏, 苏楠, 秦益文, 卢家欢, 李小菲. FSCRF:基于特征切分与级联随机森林的异常点检测模型[J]. 计算机科学, 2020, 47(8): 185188.
LIU Zhenpeng, SU Nan, QIN Yiwen, LU Jiahuan, LI Xiaofei. FSCRF:Outlier Detection Model Based on Feature Segmentation and Cascaded Random Forest[J]. Computer Science, 2020, 47(8): 185188.  LIU Zhenpeng, SU Nan, QIN Yiwen, LU Jiahuan, LI Xiaofei
 Computer Science. 2020, 47 (8): 185188. doi:10.11896/jsjkx.190600162
 Abstract ( 0 ) PDF(1697KB) ( 1 )
 References  Related Articles  Metrics

In the era of big data, there are many abnormal values hidden in massive data due to attack tampering, equipment failure, artificial fraud and other reasons.Accurately detect outliers in data is critical to data cleaning.Therefore, an outlier detection model combining feature segmentation and multilevel cascaded random forest (FSCRF) is proposed.Using the sliding window and the random forest to segment the original features, the generated class probability vector is used to train the multilevel cascaded random forest.Finally, the category of the sample is determined by the vote of the last layer.Simulation experiment results show that the new method can effectively detect outlier in classification tasks on UCI data sets, with high F1measure scores obtained on both high and low dimensional data sets.The cascade structure further improves the generalization ability of the model compared to the classical random forest.Compared with the GBDT and XGBoost, the proposed method has performance advantages on highdimensional data sets, and has fewer hyperparameters that easy to tune and has better comprehensive performance.

Analysis of China’s Patent Application Concern Based on Visibility Graph Network
张梦月, 胡军, 严冠, 李慧嘉. 基于可见性图网络的中国专利申请关注度分析[J]. 计算机科学, 2020, 47(8): 189194.
ZHANG Mengyue, HU Jun, YAN Guan, LI Huijia. Analysis of China’s Patent Application Concern Based on Visibility Graph Network[J]. Computer Science, 2020, 47(8): 189194.  ZHANG Mengyue, HU Jun, YAN Guan, LI Huijia
 Computer Science. 2020, 47 (8): 189194. doi:10.11896/jsjkx.200300001
 Abstract ( 0 ) PDF(2149KB) ( 2 )
 References  Related Articles  Metrics

Patent is an important embodiment of innovation.Many people will inquire about the process of patent application on the Internet and learn the application steps before patent application.In fact, the online searching is also a way to know whether innovative enterprises or individuals attach importance to innovation.This paper analyzes the dynamic characteristics of Baidu search index time series with the keywords of “patent application” from the perspective of a new time series analysis, namely from the perspective of network.The time series of Baidu search index is transformed into a complex network by using the principle of visibility graph algorithm, and its parameters are calculated to analyze the topological structure of the network.Firstly, by calculating the complex network, it can be found that the patent attention of each province has certain differences.Secondly, the study shows that most of the networks are scalefree networks and the original time series have fractal characteristics.Finally, by clustering, 31 provinces can be divided into 3 categories according to the characteristics of complex networks.This paper analyzes the data of Baidu search index from 2011 to 2018.By dividing the community structure, the time series period and the central node’s influence on the search index can be found.

Video Saliency Detection Based on 3D Full ConvLSTM Neural Network
王教金, 蹇木伟, 刘翔宇, 林培光, 耿蕾蕾, 崔超然, 尹义龙. 基于3D全时序卷积神经网络的视频显著性检测[J]. 计算机科学, 2020, 47(8): 195201.
WANG Jiaojin, JIAN Muwei, LIU Xiangyu, LIN Peiguang, GEN Leilei, CUI Chaoran, YIN Yilong. Video Saliency Detection Based on 3D Full ConvLSTM Neural Network[J]. Computer Science, 2020, 47(8): 195201.  WANG Jiaojin, JIAN Muwei, LIU Xiangyu, LIN Peiguang, GEN Leilei, CUI Chaoran, YIN Yilong
 Computer Science. 2020, 47 (8): 195201. doi:10.11896/jsjkx.190600148
 Abstract ( 1 ) PDF(3008KB) ( null )
 References  Related Articles  Metrics

Video saliency detection aims to mimic human’s visual attention mechanism of perceiving the world via extracting the most attractive regions or objects in the input video.At present, it is still a challenge for video saliency detection.Traditional video saliencydetection models have reached a certain level, but exploiting the consistency of spatiotemporal information is unsatisfactory.In order to solve this issue, this paper proposes a video saliencydetection model based on 3D full ConvLSTM neural network.Firstly, the fulltime convolution is utilized to extract spatiotemporal features from the input video, and then the 3D pooling layer is explored for dimensionality reduction.Secondly, the extracted features are decoded by 3D deconvolution in the decoding layer, and the interpolation algorithm is applied to restore the saliency map to the original size of the original image.The proposed method extracts the time and space information jointly so as to effectively enhance the completeness of the saliency map.Experimental results show that the performance of the proposed algorithm is superior to stateoftheart video saliency detection methods based on three widely used data sets (DAVIS, FBMS, SegTrack) for video saliency detection.

Dense Convolution Generative Adversarial Networks Based Image Inpainting
孟丽莎, 任坤, 范春奇, 黄泷. 基于密集卷积生成对抗网络的图像修复[J]. 计算机科学, 2020, 47(8): 202207.
MENG Lisha, REN Kun, FAN Chunqi, HUANG Long. Dense Convolution Generative Adversarial Networks Based Image Inpainting[J]. Computer Science, 2020, 47(8): 202207.  MENG Lisha, REN Kun, FAN Chunqi, HUANG Long
 Computer Science. 2020, 47 (8): 202207. doi:10.11896/jsjkx.190700017
 Abstract ( 0 ) PDF(3379KB) ( 1 )
 References  Related Articles  Metrics

Image inpainting is one technique of reconstruction defect areas by inferring information from the known context of defect images.For semantic image inpainting of large areas, there are still many problems in inpainting algorithms based on generation models, such as blur, artifacts, and poor visual similarity, especially for the complex background images and small datasets.To solve this problem, an image inpainting algorithm based on dense convolution generative adversarial networks is proposed.The generated adversarial network is the basic framework.Firstly, dense convolutional blocks are used to enhance image feature extraction, improve image repair capability, and avoid the problem of gradient disappearance caused by the network depth increasing in the generator network.Secondly, skip connection between the encoding and decoding structures is involved to avoid information transmission lost problems between network layers.After that, a total loss function, composed of the reconstruction loss, adversarial loss and TV loss, is used to optimize the network and enhance network stability.Finally, the proposed algorithm is validated on the CelebA dataset and Car dataset respectively, compared with three typical image inpainting algorithms.The effectiveness of the algorithm is proved in visual perception, peak signaltonoise ratio (PSNR) and structural similarity (SSIM).

Highway Abnormal Event Detection Algorithm Based on Video Analysis
姚兰, 赵永恒, 施雨晴, 于明鹤. 一种基于视频分析的高速公路交通异常事件检测算法[J]. 计算机科学, 2020, 47(8): 208212.
YAO Lan, ZHAO Yongheng, SHI Yuqing, YU Minghe. Highway Abnormal Event Detection Algorithm Based on Video Analysis[J]. Computer Science, 2020, 47(8): 208212.  YAO Lan, ZHAO Yongheng, SHI Yuqing, YU Minghe
 Computer Science. 2020, 47 (8): 208212. doi:10.11896/jsjkx.191000165
 Abstract ( 1 ) PDF(1787KB) ( 1 )
 References  Related Articles  Metrics

Abnormal event detection in a traffic scenario is significant for accident prevention, oncall solution and other applications.While currently, the detection approaches are neither labor efficient, nor realtiming.A multitarget tracking algorithm combining motion characteristics and apparent characteristic for vehicle trace in highway traffic scenario is derived by introducing target detection in deep learning and extracting targets in a video.An abnormal event detection method which is based on vehicle trajectory feature is proposed.The proposed tracking algorithm declines the dependent on background during the procedure of trajectory extraction.The abnormal event detection algorithm is designated adequately for highway scenario with an additional strategy of sliding window to improve the performance on abnormal detection for remote and complex scenes.Through the experiments on practical video repository, the proposed method is compared with existing methods and shows a highlighted performance in the terms of Precision, Recall rate and Fvalue index.This method turns out to be solid and efficient in abnormal event detection in highway traffic scenario.

GNNI Unet:Precise Segmentation Neural Network of Left Ventricular Contours for MRI Images Based on Group Normalization and Nearest Interpolation
高强, 高敬阳, 赵地. GNNI Unet：基于组归一化与最近邻插值的MRI左心室轮廓精准分割网络[J]. 计算机科学, 2020, 47(8): 213220.
GAO Qiang, GAO Jingyang, ZHAO Di. GNNI Unet:Precise Segmentation Neural Network of Left Ventricular Contours for MRI Images Based on Group Normalization and Nearest Interpolation[J]. Computer Science, 2020, 47(8): 213220.  GAO Qiang, GAO Jingyang, ZHAO Di
 Computer Science. 2020, 47 (8): 213220. doi:10.11896/jsjkx.190600026
 Abstract ( 0 ) PDF(3633KB) ( 2 )
 References  Related Articles  Metrics

Cardiovascular disease has become the No.1 killer of human health.At present, doctors manually label the left ventricle contour by left ventricular MRI imaging technology to calculate various functional parameters of the heart to prevent cardiovascular disease, which is not difficult but time consuming and cumbersome.Deep learning has achieved remarkable success in many areas of medical image segmentation, but there is still room for improvement in the field of left ventricular contour segmentation.We proposes a convolutional neural network based on group normalization and nearest interpolation upsampling which is called GNNI Unet (Unet with Group normalization and Nearest interpolation) for MRI left ventricular contour precise segmentation.We constructe a convolution module with group normalization operation based on group normalization method for fast and accurately feature extraction.Based on nearest neighbor interpolation method, we constructe an upsampling module for feature restoring.We conducte a preprocessing method for Center cropping ROI extraction and a detailed controlled experiment of GNNI Unet on the Sunnybrook left ventricular segmentation dataset and the LVSC left ventricular segmentation dataset.The experimental results show that the GNNI Unet obtains the accuracy of Dice coefficient of 0.937 and the accuracy of Jaccard coefficient of 0.893 on the Sunnybrook dataset, and it obtains the accuracy of the Dice coefficient of 0.957 and the accuracy of the Jaccard coefficient of 0.921 on the LVSC dataset.The GNNI Unet network achieves higher Dice coefficient accuracy than other convolutional network segmentation methods in the field of left ventricular contour segmentation.Finally, according to the experimental results, we discusse and verifie that the convolutional module of the normalization operation can accelerate the convergence of the network and improve the accuracy, and the upsampling module using the nearest neighbor interpolation method is more friendly to the smaller target segmentation such as the left ventricle contour, and our model can accelerate network convergence to a certain extent.

Endtoend Network Structure Optimization of Scene Text Recognition Based on Residual Connection
黄金星, 潘翔, 郑河荣. 基于残差连接的场景文本识别端到端网络结构优化[J]. 计算机科学, 2020, 47(8): 221226.
HUANG Jinxing, PAN Xiang, ZHENG Herong. Endtoend Network Structure Optimization of Scene Text Recognition Based on Residual Connection[J]. Computer Science, 2020, 47(8): 221226.  HUANG Jinxing, PAN Xiang, ZHENG Herong
 Computer Science. 2020, 47 (8): 221226. doi:10.11896/jsjkx.190500017
 Abstract ( 0 ) PDF(1897KB) ( null )
 References  Related Articles  Metrics

The existing text recognition methods will cause decreased recognition accuracy due to not enough network depth.The paper addresses this issue and proposes an improved endtoend text recognition network structure.Firstly, the algorithm takes the text as a sequence, and uses the residual module to divide the text into columns for the recurrent layer.This residual structureincreases network depth, to maintain the network’s best representation of the text image.It can capture the best feature representation of text images.Meanwhile, the residual module uses the stacked layer to learn the residual mapping to improve the convergence of the network though the number of layers is obviously increased.Secondly, we use the recurrent layer to model the context of these text features, and the modeling results will be taken into the softmax layer to predict corresponding labels, which achieve the recognition of arbitrary length of texts.The recurrent layer uses the Long ShortTerm Memory to learn the dependencies between texts and solve the gradient vanishing problem in long sequence training.Finally, text label transcription and decoding are performed by the optimal path method.The method finds a path to maximize its probability, and outputs the sequence corresponding to the path as the optimal sequence.The improved text recognition network structure increases network depth, improves the feature description of text images and the stability under noises.In the experimental part, this paper compares with existing typical algorithms over the multiple test datasets (ICDAR2003, ICDAR2013, SVT and IIIT5K).The experiments show that the network structure can obtain better text recognition accuracy and verify the effectiveness of the proposed network structure.

Threedimensional Convolutional Neural Network Evolution Method for Facial Microexpression Autorecognition
梁正友, 何景琳, 孙宇. 一种用于微表情自动识别的三维卷积神经网络进化方法[J]. 计算机科学, 2020, 47(8): 227232.
LIANG Zhengyou, HE Jinglin, SUN Yu. Threedimensional Convolutional Neural Network Evolution Method for Facial Microexpression Autorecognition[J]. Computer Science, 2020, 47(8): 227232.  LIANG Zhengyou, HE Jinglin, SUN Yu
 Computer Science. 2020, 47 (8): 227232. doi:10.11896/jsjkx.190700009
 Abstract ( 3 ) PDF(1955KB) ( 1 )
 References  Related Articles  Metrics

Due to the short duration of microexpressions and the small amplitude of motion, the automatic recognition of microexpressions is still a challenging problem.Aiming at the problems, this paper proposes a ThreeDimensional Convolutional Neural Network Evolution (C3DEvol) method for microexpression recognition.In the C3DEvol, threedimensional Convolutional Neural Network (C3D) which can extract dynamic information effectively is used to extract microexpression features in time domain and space domain.At the same time, the genetic algorithm with the capabilities of global search and optimization is used to optimize the network structure of C3D in order to obtain the optimal network structure and avoid local optimization.Experiments are performed on a workstation with two NVIDIA Titan X GPUs using the CASME2 dataset.Experiments show that the accuracy of C3DEvol microexpression automatic recognition reaches 63.71%, which is better than the existing microexpression automatic recognition method.

Image Caption of Safety Helmets Wearing in Construction Scene Based on YOLOv3
徐守坤, 倪楚涵, 吉晨晨, 李宁. 基于YOLOv3的施工场景安全帽佩戴的图像描述[J]. 计算机科学, 2020, 47(8): 233240.
XU Shoukun, NI Chuhan, JI Chenchen, LI Ning. Image Caption of Safety Helmets Wearing in Construction Scene Based on YOLOv3[J]. Computer Science, 2020, 47(8): 233240.  XU Shoukun, NI Chuhan, JI Chenchen, LI Ning
 Computer Science. 2020, 47 (8): 233240. doi:10.11896/jsjkx.190600109
 Abstract ( 3 ) PDF(4631KB) ( 3 )
 References  Related Articles  Metrics

In recent years, construction accidents caused by workers not wearing safety helmets occur frequently.In order to reduce the accident rate, this paper studies the image caption of workers wearing safety helmets.Existing image caption methods based on neural network are short of explanatory and detailed descriptions, and the research on the image caption of construction scene is relatively scarce.To solve this problem, this paper proposes YOLOv3 algorithm with the method based on the combination of semantic rules and sentence templates to gradually generate the description of wearing safety helmets.Firstly, images are collected, and the safety helmets wearing detection dataset and the image caption dataset are made.Secondly, the Kmeans algorithm is used to determine anchor boxes parameters, which are applicable to the dataset for the training and detection of YOLOv3 network.Thirdly, a semantic rule is predefined to combine the target detection results to extract visual concepts.Finally, the extracted visual concepts are filled into the sentence template generated by the image caption annotation, which is used to generate the image description statement about the workers wearing safety helmets or not in the construction scene.The Ubuntu16.04 system and the Keras deep learning framework are used to build the experimental environment, and different algorithmsare compared on the selfmade datasets of helmet wearing.The experimental results show that the proposed method can not only effectively define the number of safety helmet wearers and nonwearers, but also achieve 0.722 and 0.957 respectively on BLEU1 and CIDEr evaluation metrics, which are 6.9% and 14.8% higher than other methods, demonstrating the effectiveness and superiority of the proposed method.

Single Image Defogging Method Based on Weighted NearInFrared Image Fusion
朱珍, 黄锐, 臧铁钢, 卢世军. 基于加权近红外图像融合的单幅图像除雾方法[J]. 计算机科学, 2020, 47(8): 241244.
ZHU Zhen, HUANG Rui, ZANG Tiegang, LU Shijun. Single Image Defogging Method Based on Weighted NearInFrared Image Fusion[J]. Computer Science, 2020, 47(8): 241244.  ZHU Zhen, HUANG Rui, ZANG Tiegang, LU Shijun
 Computer Science. 2020, 47 (8): 241244. doi:10.11896/jsjkx.200300068
 Abstract ( 0 ) PDF(1702KB) ( 1 )
 References  Related Articles  Metrics

The traditional image defogging method has the problem that the image contrast in the fogfree area is too high, which causes the generated image visual effect is unnatural in some cases.In order to obtain natural and clear defogging images, a new single image defogging method based on weighted nearinfrared(NIR) image fusion is proposed.Image contrast is restored by fusing the detail components of NIR images into visible images of the same scene.The NIR image is weighted using the transmission map to prevent excessive enhancement in the fogfree region.The experimental results show that compared with the traditional single image defogging methods, the proposed method can effectively restore the image contrast, does not excessively strengthen the fogfree area, and has higher PSNR and SSIM values.

Research Status and Development Trend of Vehicle Following Control System
章军辉, 陈大鹏, 李庆. 车辆跟随控制系统研究现状及发展趋势[J]. 计算机科学, 2020, 47(8): 245254.
ZHANG Junhui, CHEN Dapeng, LI Qing. Research Status and Development Trend of Vehicle Following Control System[J]. Computer Science, 2020, 47(8): 245254.  ZHANG Junhui, CHEN Dapeng, LI Qing
 Computer Science. 2020, 47 (8): 245254. doi:10.11896/jsjkx.190700058
 Abstract ( 2 ) PDF(2670KB) ( 3 )
 References  Related Articles  Metrics

It has strongly been showed that intelligent vehicle following and vehicle platooning will be an effective way to deal with daily road traffic problems such as traffic congestion, traffic safety and environmental pollution.In this article, the development stages of vehicle following control system are explicated, and the latest research achievements of vehicle following control system in recent years are objectively and comprehensively discussed from the aspects of environmental perception technology, desired intervehicle clearance strategy, longitudinal and lateral vehicle dynamic modeling, as well as cooperative decision and control algorithms.Furthermore, the common problems of vehicle following control system are summarized, and some viewpoints concerning the future trend of such research are also suggested.

Word Embedding Optimization for Lowfrequency Words with Applications in Shorttext Classification
程婧, 刘娜娜, 闵可锐, 康昱, 王新, 周扬帆. 一种低频词词向量优化方法及其在短文本分类中的应用[J]. 计算机科学, 2020, 47(8): 255260.
CHENG Jing, LIU Nana, MIN Kerui, KANG Yu, WANG Xin, ZHOU Yangfan. Word Embedding Optimization for Lowfrequency Words with Applications in Shorttext Classification[J]. Computer Science, 2020, 47(8): 255260.  CHENG Jing, LIU Nana, MIN Kerui, KANG Yu, WANG Xin, ZHOU Yangfan
 Computer Science. 2020, 47 (8): 255260. doi:10.11896/jsjkx.191000163
 Abstract ( 2 ) PDF(2059KB) ( 1 )
 References  Related Articles  Metrics

Many Natural Language Processing (NLP) tasks have benefitted from the public availability of generalpurpose vector representations of words trained with largescale datasets.Since pretrained word embeddings only have general semantic features from large corpus, it is often necessary to finetune these embeddings to make them more suitable for target tasks when it is applied to certain downstream tasks.But, the words with low occurrence frequencies can hardly receive stable gradient information when finetuning.However, lowfrequency terms are likely to convey important classspecific information in tasks for short text classification.Therefore, it is necessary to obtain a better lowfrequency word embedding on the specific task.To address the problem, this paper proposes a modelagnostic algorithm, which optimizes the vector representations of these words according to the task specifics.This approach leverages the update information from common words to guide the embedding updating on rare words.It helps achieve more effective embeddings for the lowfrequency words.Our evaluation on three public shorttext classification tasks shows that the proposed algorithm produces better taskspecific embeddings for rarely occurring words, as a result, the model performance is improved from 0.4% to 1.4% on these tasks.It proves the positive influence of low frequency words on shorttext classification tasks, which can shed light on short text classification tasks.

Convolutional Neural Networks Compression Based on Pruning and Quantization
孙彦丽, 叶炯耀. 基于剪枝与量化的卷积神经网络压缩方法[J]. 计算机科学, 2020, 47(8): 261266.
SUN Yanli, YE Jiongyao. Convolutional Neural Networks Compression Based on Pruning and Quantization[J]. Computer Science, 2020, 47(8): 261266.  SUN Yanli, YE Jiongyao
 Computer Science. 2020, 47 (8): 261266. doi:10.11896/jsjkx.190700062
 Abstract ( 1 ) PDF(2523KB) ( null )
 References  Related Articles  Metrics

With the development of deep learning, Convolutional Neural Networks(CNN), as one of its important algorithms, is widely applied in a variety of fields such as target detection, natural language processing, speech recognition and image identification, and achieves better results than the traditional algorithm.The number of parameters and calculation are increasing with the depth of network structure, resulting in many algorithms must be implemented on GPU.So it is difficult to apply the CNN model to mobile terminals which has limited resources and high realtime request.To solve this problem, this paper presents a method of optimizing network structure and parameters simultaneously.Firstly, the algorithms prunes weight according to its influence on the results of network, and ensure that the redundant information is removed while retaining the important connection of the model.Then, this paper quantizes the floatpoint weight and activation of CNN.This changes floatpoint operation to fixedpoint operation.It not only reduces the computational complexity of the network model, but also reduces the size of the network model.To verify the algorithm, deep learning framework tensorflow is selected, and Spyder compiler is used in Ubuntu 16.04 operating system.The experimental results show that this method reduces size of LeNet model with simple structure from 1.64M to 0.36M.Compression ratio reaches 78%, but the accuracy drops only 0.016.And it also reduces the size of MobileNet with Lightweight network from 16.9M to 3.1M.Compression ratio reaches 81% with the accuracy dropping only 0.03.The data show that combining the weight pruning and parameter quantification of convolution neural network can effectively compress the convolution neural network within the acceptable range of accuracy loss.So, this method solve the difficulty of deploying the convolution neural network to the mobile terminal.

Intelligent 3D Printing Path Planning Algorithm
杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊. 智能3D打印路径规划算法[J]. 计算机科学, 2020, 47(8): 267271.
YANG Decheng, LI Fengqi, WANG Yi, WANG Shengfa, YIN Huishu. Intelligent 3D Printing Path Planning Algorithm[J]. Computer Science, 2020, 47(8): 267271.  YANG Decheng, LI Fengqi, WANG Yi, WANG Shengfa, YIN Huishu
 Computer Science. 2020, 47 (8): 267271. doi:10.11896/jsjkx.190700184
 Abstract ( 1 ) PDF(2628KB) ( 1 )
 References  Related Articles  Metrics

The path planning of large industrial parts in additive manufacturing directly affects manufacturing quality and efficiency.At present, the commonly used traditional path planning methods have many problems, such as turning and stacking of print head and the number of rise and fall of print head, so they are not suitable for large industrial parts.Therefore, an intelligent path planning algorithm is proposed.Firstly, the twodimensional plane obtained after slicing is concavely convexly decomposed into printing subareas, and then the internal longaxis scanning along the partition is performed on each subarea to reduce the number and length of printing paths.Then, the subpartition connection is treated as a traveling salesman problem (TSP) using genetic algorithms to complete the path planning between the subareas.Meanwhile, an intelligent 3D printing path planning system is designed and developed with C# language, which has the functions of slice input and display, print width setting, intelligent path planning and Gcode code output.By comparing with the two traditional path planning algorithms, the proposed method significantly reduces the number of paths, the idle travel distance, and the number of print head lifts.The subpartitionbased intelligent path planning method provides a new idea for the additive manufacturing process of large industrial parts.

Collisionfree Path Planning of AGVs Based on Improved Dijkstra Algorithm
姜辰凯, 李智, 盘书宝, 王勇军. 基于改进Dijkstra算法的AGVs无碰撞路径规划[J]. 计算机科学, 2020, 47(8): 272277.
JIANG Chenkai, LI Zhi, PAN Shubao, WANG Yongjun. Collisionfree Path Planning of AGVs Based on Improved Dijkstra Algorithm[J]. Computer Science, 2020, 47(8): 272277.  JIANG Chenkai, LI Zhi, PAN Shubao, WANG Yongjun
 Computer Science. 2020, 47 (8): 272277. doi:10.11896/jsjkx.190700138
 Abstract ( 2 ) PDF(2282KB) ( 6 )
 References  Related Articles  Metrics

Aiming at the path planning and conflict problems of automatic guided vehicle (AGV) in flexible manufacturing systems, an improved Dijkstra algorithm based on time window is proposed to realize dynamic path planning of multiple AGVs.Firstly, the traditional Dijkstra algorithm is used to calculate the path of the multiAGV for the scheduled task, and the degree of use of the planned path is calculated and the weighting coefficient is calculated, and then the weighted path length is updated to the database.Secondly, calculate the time for the AGV to pass through each station node, and avoid collision conflicts through the arrangement of time windows.In the end, when the conflict occurs, the path of the lower priority AGV is replanned by calculating and setting the priority of the AGV.The simulation results show that the proposed algorithm can effectively avoid conflicts and deadlocks under the optimal path, which not only improves the system efficiency, but also makes the system more robust.

Study on Optimal Scheduling of Gate Based on Mixed Integer Programming
张红颖, 申荣苗, 罗谦. 基于混合整数规划的停机位优化调度研究[J]. 计算机科学, 2020, 47(8): 278283.
ZHANG Hongying, SHEN Rongmiao, LUO Qian. Study on Optimal Scheduling of Gate Based on Mixed Integer Programming[J]. Computer Science, 2020, 47(8): 278283.  ZHANG Hongying, SHEN Rongmiao, LUO Qian
 Computer Science. 2020, 47 (8): 278283. doi:10.11896/jsjkx.190400154
 Abstract ( 1 ) PDF(1792KB) ( 1 )
 References  Related Articles  Metrics

In order to alleviate effectively the current situation of airport aircraft delay, the optimal scheduling of airport gate is studied.By deeply analyzing the characteristics of airport ground operation, considering the constraint restrictions such as aircraft model matching, buffer time and aircraft conflict, scientifically and reasonably weighing the various interest needs of the airport, this paper proposes a mixed integer programming model to optimize the gate scheduling problem, the main goal is to ensure the safe operation of the aircraft under the premise, so that the total flight delay time is the shortest.The probability distribution function is introduced to avoid the occurrence of aircraft conflict.Combining with the basic theory of multiobjective optimization and branching definition algorithm, the optimal assignment schemeis sought.The simulation results show that the model optimizes the timing of the expected inbound aircraft in the airport, adjusts the position allocation conflict by optimizing the scheduling scheme, and gets the optimal allocation scheme.The algorithm can reduce the search space, improve the efficiency of the solution, significantly reduce the total delay time, and improve the utilization rate of airport gate resources.Compared with heuristic algorithm, the aircraft delay is reduced by 2.4%, and the proposed method caneffectively reduce the delay rate of airport ground flight.

Multiobjective Fiveelements Cycle Optimization Algorithm for Complex Network Community Discovery
张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法[J]. 计算机科学, 2020, 47(8): 284290.
ZHANG Qingqi, LIU Mandan. Multiobjective Fiveelements Cycle Optimization Algorithm for Complex Network Community Discovery[J]. Computer Science, 2020, 47(8): 284290.  ZHANG Qingqi, LIU Mandan
 Computer Science. 2020, 47 (8): 284290. doi:10.11896/jsjkx.190700082
 Abstract ( 1 ) PDF(2556KB) ( null )
 References  Related Articles  Metrics

As an important property of complex networks, community structure is of great significance for understanding the function and organization of networks.In order to solve the community discovery problem of complex networks, a multiobjective fiveelements cycle optimization algorithm (MOFECO) is proposed.Firstly, the task of the community discovery is modelled as a multiobjective optimization problem, and two opposite targets, inverse ratio vssociation (IRA) and ratio cut (RC) are selected as the objective function.Then, based on fiveelements cycle model (FECM), individual updating is implemented through local optimal individuals and global optimal individuals, and crossover and mutation operators are introduced to improve the update strategy.Finally, the fast nondominated sorting method is used to obtain the Pareto optimal community partitioning set, which is helpful to reveal the hierarchical structure of complex networks.Experiments are conducted on LFR benchmark networks and real social networks, compared with singleobjective algorithms(GANet, MemeNet) and multiobjective algorithms, such as MOGANet, MOCD, MOEA/DNet, DMOPSO, DIMMOEA/D and MOCDACO, MOFECO overcomes the shortcomings of traditional singleobjective optimization of community structure division, and improves the accuracy of community discovery.

Grey Wolf Algorithm Based on Levy Flight and Random Walk Strategy
李阳, 李维刚, 赵云涛, 刘翱. 基于莱维飞行和随机游动策略的灰狼算法[J]. 计算机科学, 2020, 47(8): 291296.
LI Yang, LI Weigang, ZHAO Yuntao, LIU Ao. Grey Wolf Algorithm Based on Levy Flight and Random Walk Strategy[J]. Computer Science, 2020, 47(8): 291296.  LI Yang, LI Weigang, ZHAO Yuntao, LIU Ao
 Computer Science. 2020, 47 (8): 291296. doi:10.11896/jsjkx.190600107
 Abstract ( 4 ) PDF(2443KB) ( 1 )
 References  Related Articles  Metrics

The individuals in the grey wolf group tend to approach to the area where the leadership grey wolf is located because of the reduction of attenuation factor in the middle and late stage of the optimization process for the standard grey wolf optimization algorithm, which results in poor global optimization ability and reduces the optimization accuracy of the algorithm.Aiming at this problem, an improved grey wolf optimization algorithm (IGWO) is proposed.Firstly, by analyzing the influence of the decay factor, an adjustable segmentation decay factor is presented to focus on proper balance between exploration ability and exploitation ability.The appropriate parameter is searched to achieve more precise optimization.And it ensures that the algorithm has a certain global search ability in the middle and later stages of the optimization process.The numerical simulation experiments show that increasing the exploration ratio is beneficial to improve the convergence accuracy of the algorithm.Meanwhile, leadership wolves are selected by probability to carry out levy flight operation or random walk operation respectively in the process of optimization.The global optimization ability of the algorithm is improved by the levy flight with the feature of shortrange flight search and occasional longdistance walk.While the local optimization ability is improved by random walk with relatively centralized search range.Simulation experiments are conducted on optimization problems.The results show that compared with other algorithms, the improved algorithm has great performance in optimization precision, algorithm stability and convergence speed.

Salp Swarm Algorithm with Random Inertia Weight and Differential Mutation Operator
张志强, 鲁晓锋, 隋连升, 李军怀. 集成随机惯性权重和差分变异操作的樽海鞘群算法[J]. 计算机科学, 2020, 47(8): 297301.
ZHANG Zhiqiang, LU Xiaofeng, SUI Liansheng, LI Junhuai. Salp Swarm Algorithm with Random Inertia Weight and Differential Mutation Operator[J]. Computer Science, 2020, 47(8): 297301.  ZHANG Zhiqiang, LU Xiaofeng, SUI Liansheng, LI Junhuai
 Computer Science. 2020, 47 (8): 297301. doi:10.11896/jsjkx.190700063
 Abstract ( 11 ) PDF(1316KB) ( 1 )
 References  Related Articles  Metrics

After analyzing and summarizing the related research achievements of particle swarm optimization (PSO) and differential evolution (DE) algorithms, this paper proposes an improved salp swarm algorithm (iSSA) with random inertia weight and differential mutation operator for enhancing the convergence rate, computational accuracy and global optimization of SSA algorithm.Firstly, the random inertia weight of particle swarm optimization is introduced in the followers’ position update equation of SSA algorithm in order to enhance and balance the exploration and exploitation ability of SSA algorithm.Secondly, the leader position update of SSA algorithm is replaced with the mutation operator of differential evolution algorithm DE, which is used to improve the convergence rate and computational accuracy of SSA algorithm.For the purpose of checking the improvement effect on SSA algorithm by the random inertia weight and differential mutation operator, simulation experiments on some highdimension benchmark functions are performed and comparisons between the proposed iSSA and two typical improved SSA algorithms named by enhanced salp swarm algorithm (ESSA) and crazy and adaptive salp swarm algorithm (CASSA) are performed.The experimental results and analysis show that, the proposed iSSA with random inertia weight and differential mutation operator obviously improves the convergence rate, computational accuracy and global optimization when compared with two typical improved ESSA and CASSA algorithms in the case of no any increase in the time complexity of SSA algorithm.

Review of Link Prediction Methods Based on Feature Classification
王慧, 乐孜纯, 龚轩, 武玉坤, 左浩. 基于特征分类的链路预测方法综述[J]. 计算机科学, 2020, 47(8): 302312.
WANG Hui, LE Zichun, GONG Xuan, WU Yukun, ZUO Hao. Review of Link Prediction Methods Based on Feature Classification[J]. Computer Science, 2020, 47(8): 302312.  WANG Hui, LE Zichun, GONG Xuan, WU Yukun, ZUO Hao
 Computer Science. 2020, 47 (8): 302312. doi:10.11896/jsjkx.190700136
 Abstract ( 0 ) PDF(2715KB) ( 1 )
 References  Related Articles  Metrics

As an important research direction of network science research, link prediction of complex network has been more and more attention from experts from various disciplines, and it can make use of existing network information, such as the features of the nodes and edges, to predict possible future relationships, missing information in the network, and new or disappearing information, identify the false interactions, evaluate network evolution mechanism and conduct network reconfiguration, etc.Current articles on link prediction mainly come from the expert in engineering, computer science and physics.They are independent and lack cooperation, and there are few review articles combining multidisciplinary link prediction.The goal of this article is from the perspective of computer science and physics comprehensive to review, analyze, and discusse the research progress of link prediction algorithm based on feature classification, introduces a variety of feature extraction techniques in this field.This paper firstly introduces the idea of layering into the classification of link prediction algorithm, which divides the classification model into three layers, the metadata layer, features classification layer and feature extraction layer.The classification model includes two parts and seven aspects, that is, the prediction algorithm is divided into two parts, features extraction method and features learning method.The seven aspects are the similarity based methods, probabilistic methods, likelihood based methods, matrix factorization based method, random walk based method, neural network based method and custom loss function based method.This classification method covers many classical and latest link prediction techniques in various disciplines, including GNN, GCN, RNN and RL, which are the most popular link prediction techniques in graph neural networks.The differences of these algorithms in model complexity and prediction performance are studied, and the challenges of current link prediction technology in the future are discussed.

Unknown Binary Protocol Format Inference Method Based on Longest Continuous Interval
陈庆超, 王韬, 冯文博, 尹世庄, 刘丽君. 基于最长连续间隔的未知二进制协议格式推断[J]. 计算机科学, 2020, 47(8): 313318.
CHEN Qingchao, WANG Tao, FENG Wenbo, YIN Shizhuang, LIU Lijun. Unknown Binary Protocol Format Inference Method Based on Longest Continuous Interval[J]. Computer Science, 2020, 47(8): 313318.  CHEN Qingchao, WANG Tao, FENG Wenbo, YIN Shizhuang, LIU Lijun
 Computer Science. 2020, 47 (8): 313318. doi:10.11896/jsjkx.190700031
 Abstract ( 0 ) PDF(2057KB) ( null )
 References  Related Articles  Metrics

In the process of format inference of unknown binary protocols, a large amount of prior knowledge is often introduced, the experimental operation is complex and the accuracy of the results is low.For this reason, a method that requires less artificial setting of parameters, simple operation and higher accuracy is proposed to infer the unknown binary protocol format.The preprocessed protocol data is clustered hierarchically, and the optimal clustering is obtained by using CH (CalinskiHarabasz) coefficient as the evaluation criteria.Through the improved sequence comparison of the clustering results, the protocol data sequence with interval is obtained, continuous intervals are counted and merged to analyze protocol formats.The experimental results show that the binary protocol format inference method proposed in this paper can infer more than 80% of the field intervals in the unknown binary protocol.Compared with the format inference method in AutoReEngine algorithm, the F1Measure value of the proposed method is improved by about 30% as a whole.

Prediction of Wireless Network Traffic Based on Clustering Analysis and Optimized Support Vector Machine
曹素娥, 杨泽民. 基于聚类分析算法和优化支持向量机的无线网络流量预测[J]. 计算机科学, 2020, 47(8): 319322.
CAO Sue, YANG Zemin. Prediction of Wireless Network Traffic Based on Clustering Analysis and Optimized Support Vector Machine[J]. Computer Science, 2020, 47(8): 319322.  CAO Sue, YANG Zemin
 Computer Science. 2020, 47 (8): 319322. doi:10.11896/jsjkx.190800075
 Abstract ( 1 ) PDF(1748KB) ( 2 )
 References  Related Articles  Metrics

In order to solve the problems existing in the current wireless network traffic prediction process and improve the accuracy of wireless network traffic prediction, a wireless network traffic prediction model based on clustering analysis algorithm and optimized support vector machine is proposed.Firstly, data sets of wireless network traffic are collected and clustering analysis algorithm is used to construct the training sample set.And then, support vector machine is used to learn the training samples of wireless network traffic, and cuckoo search algorithms is introduced to optimize the parameters of support vector.Thus, the prediction model of wireless network traffic is established.Finally, the effectiveness of the model is analyzed through a specific example of wireless network traffic prediction.The results show that the proposed model has high prediction accuracy, improves the efficiency of wireless network traffic modeling, and the prediction effect of wireless network traffic is better than the current classical wireless network traffic prediction models, which has more significant advantages.

Multisource Sensor Body Area Network Data Fusion Model Based on Manifold Learning
张俊, 王杨, 李坤豪, 李昌, 赵传信. 基于流形学习的多源传感器体域网数据融合模型[J]. 计算机科学, 2020, 47(8): 323328.
ZHANG Jun, WANG Yang, LI Kunhao, LI Chang, ZHAO Chuanxin. Multisource Sensor Body Area Network Data Fusion Model Based on Manifold Learning[J]. Computer Science, 2020, 47(8): 323328.  ZHANG Jun, WANG Yang, LI Kunhao, LI Chang, ZHAO Chuanxin
 Computer Science. 2020, 47 (8): 323328. doi:10.11896/jsjkx.191000012
 Abstract ( 0 ) PDF(2573KB) ( 3 )
 References  Related Articles  Metrics

Due to the problem of large amount of data collected by multisensors in wireless body area networks and redundant data types, it is difficult to effectively perform multidimensional data fusion.Although traditional manifold and decomposition data fusion methods (Isomap, MDS, PCA, etc.) have the ability to generate a reasonable rejection gradient at a small distance and are less affected by anomalies, the data dimension reduction effect for wireless multisensor volume domain networks is notideal.Therefore, this paper proposed the TSNE algorithm based on manifold learning to fuse multisensor body area network data.The TSNE algorithm first converts the Euclidean distance between a highdimensional data point and its corresponding lowdimensional data point into a conditional probability matrix, then iterates the processed lowdimensional probability set a finite number of times, and finally updates the lowdimensional probability matrix to make the distance more reasonable exclusion gradient be generated between the small points, and a multidimensional body area network data fusion model is constructed.Experimental results show that compared with the traditional manifold reduction algorithm and traditional decomposition dimensionality reduction algorithm under a specific body area network data set, the TSNE algorithm has a precision of 1.11 times that of Isomap, 1.33 times that of MDS, and 1.21 times that of PCA, achieves a better data dimensionality reduction effect.

Development of Parallel Computing Subject

Computer Science  [an error occurred while processing this directive]
More>> 
Polynomial Time Algorithm for Hamilton Circuit Problem (4182)
JIANG Xinwen
Computer Science. 2020, No.7:820Abstract (4182) PDF (1760KB) (6828) Detecting Community from Bipartite Network Based on Spectral Clustering (208)
ZHANG Xiaoqin, AN Xiaodan, CAO Fuyuan
Computer Science. 2019, No.4:216221Abstract (208) PDF (1772KB) (2493) Review of Time Series Prediction Methods (414)
YANG Haimin, PAN Zhisong, BAI Wei
Computer Science. 2019, No.1:2128Abstract (414) PDF (1294KB) (2316) Survey of Distributed Machine Learning Platforms and Algorithms (656)
SHU Na,LIU Bo,LIN Weiwei,LI Pengfei
Computer Science. 2019, No.3:918Abstract (656) PDF (1744KB) (2184) Stateoftheart and Development Trend of Artificial Intelligence Combined with Law (1167)
HUANG Qiaojuan, LUO Xudong
Computer Science. 2018, No.12:111Abstract (1167) PDF (1447KB) (2169) 
» Diagnosability of Discreteevent Systems Based on Temporal Computer Science. 2012 Vol. 39 (8): 210214,251 Cited by: Baidu(626) » Key Technologies and Applications of Internet of Things LIU Qiang,CUI Li,CHEN Haiming Computer Science. 2010 Vol. 37 (6): 14 Cited by: Baidu(444) » Research Survey of Cloud Computing LI Qiao,ZHENG Xiao Computer Science. 2011 Vol. 38 (4): 3237 Cited by: Baidu(194) » Psets and its Applied Characteristics SHI Kaiquan Computer Science. 2010 Vol. 37 (8): 18 Cited by: Baidu(135)