Loading...
  • 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Current Issue

    • State of the art analysis of China HPC 2019
      YUAN Guo-xing1,ZHANG Yun-quan2,YUAN Liang2
      2019, 41(12): 2095-2100. doi:
      Abstract ( 205 )   PDF (904KB) ( 173 )      Review attachment
      In this paper,according to the latest China HPC TOP100 rank list released by CCF TCHPC in the late November,the total performance trends of China HPC TOP100 and TOP 10 of 2019 are presented.Followed with this,characteristics of the performance,manufacturer,and application area are analyzed separately in detail.

       
      A virtual network mapping algorithm
      based on node connectivity ranking
      LIU Shao-nan,LI Ling,YUAN Ying,JIANG Guo-jia,WANG Cong,L Yan-xia
      2019, 41(12): 2101-2109. doi:
      Abstract ( 110 )   PDF (782KB) ( 182 )      Review attachment
      In today’s cloud environment, the on-demand leasing of virtual resources can provide great flexibility for data centers, especially the resource leasing with the granularity of virtual network can provide much better personalized demand support for users. To allocate reasonable physical host and network resources for user’s requirement including nodes and links is called Virtual Network Embedding (VNE) problem. Most of the existing VNE algorithms are general algorithms on random topology, and are not optimized for the topological structure of data centers. Therefore, the efficiency and optimization extent need be improved in dealing the VNE problem in data centers. According to the characteristics of data center topology, a virtual network embedding algorithm based on node connectivity ranking named BS-VNE is proposed. Firstly, a maximum spanning tree algorithm is designed to sort the virtual nodes. The sorting algorithm calculates the node connectivity according to both the bandwidth and connectivity of virtual nodes and the connectivity of virtual nodes in the whole network, so as to obtain more reasonable ranking results. Then, a discrete particle swarm optimization algorithm is used to solve the mapping solution of virtual networks according to the results of virtual node ranking result. In the process of solution searching, the heuristic rules for physical network topology of data center are introduced and combined into particles search process to improve the solution efficiency. Simulation results show that the proposed algorithm can improve the benefit/cost ratio and resource utilization ratio of physical network.
       
      3D-MMA:Matrix multiplication accelerator
      architecture based on 3D integrated circuits
      WANG Ji-jun,HAO Zi-yu,LI Hong-liang
      2019, 41(12): 2110-2118. doi:
      Abstract ( 150 )   PDF (748KB) ( 162 )      Review attachment
      With regular dataflow and large throughput, systolic array is widely used for designing high performance convolution and matrix multiplication accelerators. In the deep submicron process, extending the processing array size can improve the chip computation performance, but lead to frequency decrease and sharp power consumption increase. Therefore, based on 3D integrated circuits technology, we propose a double-precision floating-point matrix multiplication accelerator named 3D-MMA, which maps planar systolic arrays onto 3D integrated circuits. Firstly, we propose an efficient matrix multiplication scheduling algorithm for 3D-MMA. Secondly, we present an acceleration system based on 3D-MMA, and build an analytical performance model to quantitatively explore the design space. Finally, we evaluate the 3D-MMA implementation cost and compare the proposal with other existing advanced accelerators. The experimental results show that the integrated circuits with 4-layer 16×16 systolic array can reach up to 3 TFLOPS, its efficiency reach up to 99%, and its implementation cost is less than the planar solution. Under the same process, compared with linear array accelerator and K40 GPU, the performance of 3D-MMA is 1.36 and 1.92 times that of the latter, and its area is much smaller than that of the latter. This paper explores the advantages of 3D integrated circuits in designing high-performance matrix multiplication accelerators, which has certain reference for further improving performance of high-performance platforms in the future.

       
      Research advances in the solving methods of
      satisfiability modulo theories based on first-order logic
      ZHANG Jian-min,LI Tie-jun,MA Ke-fan,XIAO Li-quan
      2019, 41(12): 2119-2126. doi:
      Abstract ( 105 )   PDF (486KB) ( 183 )      Review attachment
      Since Boolean Satisfiability (SAT) based on propositional logic has the problems of weak expression ability, low abstract level, and high solving complexity, Satisfiability Modulo Theories (SMT) based on first-order logic makes up for the shortcomings of SAT. SMT adopts word-level modeling language, more powerful expression ability, higher abstract level, and avoids translating the real instances to bit-level. SMT has been applied widely in numerous fields such as hardware RTL verification, software program verification, real-time system verification, and so on. The existing SMT solving algorithms emerged in recent years are categorized and compared according to their computing engines. The three typical SMT solving methods: Eager method, Lazy method and DPLL(T) method are described and analyzed. Finally, we discuss the current challenges and our research results on SMT, and then outline the future research directions.
       
      Research and application of a multidimensional
      association rules mining algorithm based on Hadoop
      YANG Qing1,2,3,ZHANG Ya-wen1,2,ZHANG Qin1,YUAN Pei-ling1
      2019, 41(12): 2127-2133. doi:
      Abstract ( 140 )   PDF (599KB) ( 138 )      Review attachment
      The traditional Apriori algorithm has to scan the data set multiple times. With the rapid growth of data volume, it cannot be applied to big data analysis. For this problem, an improved parallel Apriori algorithm is designed. Firstly, an IApriori algorithm for multidimensional data is designed by pruning strategy. Secondly, the IApriori algorithm is combined with the Hadoop distributed framework to realize the parallelization of multidimensional association rules mining algorithm. This paper applies the IPApriori algorithm to the correlation analysis of mobile phone user behavior prediction, analyzes some main factors affecting the behavior of mobile phone users, and discovers the possible correlation between mobile phone user behavior and some attributes such as age dimension, gender dimension, time dimension, location dimension and mobile phone brand dimension. Finally, experiments prove that this parallelization algorithm process and the structure building method can reduce the I/O load of the system and improve the execution efficiency of the algorithm.
       
      A satellite network resource scheduling
      mechanism based on reinforcement learning
       
      ZHOU Bi-ying1,WANG Ai-ping1,FEI Chang-jiang2,YU Wan-rong2,ZHAO Bao-kang2
      2019, 41(12): 2134-2142. doi:
      Abstract ( 331 )   PDF (1054KB) ( 299 )      Review attachment
      Compared with the traditional geostationary earth orbit (GEO) satellite, the new generation of medium-low-orbit satellite Internet constellation represented by SpaceX, Starlink and O3b has significant advantages such as wide-area coverage, full-time interconnection and multi-star coordination, and has become one of the research focuses in the world today. The traditional satellite resource scheduling method mainly studies the resource scheduling problems with single GEO satellite, which is difficult to meet the resource scheduling requirements of the low-orbit satellite constellation characterized by multi-satellite coordination, joint networking, and mass users. Consequently, an intelligent multi-star collaborative resource scheduling model based on user satisfaction is constructed, and a satellite network resource scheduling mechanism named IRSUP based on reinforcement learning is proposed. IRSUP designs an intelligent user service preference optimization module for the personalized needs of user service customization and an intelligent scheduling module based on reinforcement learning for the problems with joint optimization of multi-star resources. The simulation results show that IRSUP can effectively improve the rationality of resource scheduling, link resource utilization and user satisfaction, among which the business capacity is increased by 30%~60%, and user satisfaction is increased by more than twice.
       
      A flooding protocol of wireless sensor
      network based on connected dominating set
       
      ZHANG Hua-nan1,JIN Hong2
      2019, 41(12): 2143-2153. doi:
      Abstract ( 169 )   PDF (990KB) ( 176 )      Review attachment
      Wireless sensor networks (WSNs) have important applications in many fields such as medical treatment and industry. WSNs typically consists of a large number of sensor nodes that rely on limited power supply in many applications. Therefore, improving the energy efficiency of WSNs has become an important research topic. As a basic service in WSNs, network flooding has the advantage that information can be distributed quickly and reliably in the whole network. However, due to a large number of redundant transmissions in the network, the energy efficiency of network flooding is low. We use the connected domination set (CDS) to improve the energy efficiency of network flooding by reducing the number of transmissions. A flooding protocol based on CDS, named CONE, is proposed. CONE inhibits nodes that are not in the CDS from rebroadcasting packets during the flooding process. In the simulation experiments, CONE performance is evaluated by comparing it with the baseline protocol. The experimental results show that the method improves the end-to-end reliability and reduces the duty ratio of network flooding. It is able to effectively decrease the average energy consumption.
       
      A multi-server multi-keyword multi-user
      searchable encryption scheme under public channel
      LANG Xiao-li,CAO Su-zhen,LIU Xiang-zhen,ZHANG Yu-lei,WANG Fei
      2019, 41(12): 2154-2159. doi:
      Abstract ( 117 )   PDF (471KB) ( 154 )      Review attachment
      In the searchable encryption services, data owners wish to store different data ciphertexts and keyword indexes on different servers, so as to avoid centralized search of servers and infer the ciphertext information. A multi-server multi-keyword multi-user searchable encryption scheme under public channel is proposed by combining multi-user searchable encryption and multi-server features. This scheme allows data owners and users use the cloud servers' public keys to generate ciphertext indexes and search trapdoors, thereby satisfying the transmission under public channel and reducing the communication cost. The analysis results show that the proposal has lower communication cost. In the random oracle model, the proposed scheme is ciphertext index indistinguishable under the adaptive selection of keyword attacks in the decisional Diffie-Hellman problem.

       

       
      A data security model based on heterogeneous network
      ZHOU Jing,CHEN Chen
      2019, 41(12): 2160-2165. doi:
      Abstract ( 82 )   PDF (619KB) ( 133 )      Review attachment
      In order to solve the problems of data availability, confidentiality and integrity in local heterogeneous networks, a three-stage system design model of terminal detection, data storage access, and secure channel establishment and transmission is proposed. Firstly, the terminal system is scanned and detected to avoid the data unavailability problem caused by attack or incomplete hardware layer cleaning. Secondly, the data encryption storage access and self-destruction mechanism are set to realize the data confidentiality function and eliminate the privacy disclosure problem. Finally, SSL and VPN technologies are used to realize the secure establishment of the channel and the complete and secure transmission of the data. Through the prototype model design and the simulation experiment, the test and analysis are carried out, and the results show that the available precision of terminal detection achieves more than 90%, the encryption speed of the security function is less than 0.5 MB/s, the self-destruction protection mechanism is effective, and the full transmission speed of the channel data is increased by about 275% on average. It can be found that the model can be of high reference value for network data security detection and protection.
       
      A deep learning based object detection
       algorithm for remote sensing images
      ZHAO Bao-kang,LI Jin-wen,YANG Fan,LIU Jia-hao
      2019, 41(12): 2166-2172. doi:
      Abstract ( 172 )   PDF (968KB) ( 218 )      Review attachment
      Remote sensing image analysis has extremely broad application prospects in the fields such as land and resources management and ocean monitoring. Deep learning technology has made breakthroughs in the field of image processing. However, due to the inherent characteristics such as large size and small and dense objects of remote sensing, the deep learning methods for common images has some problems such as inaccurate positioning, difficult small object detection, and low large image detection accuracy in object detection for remote sensing images. Aiming at the above problems, this paper proposes a new object detection algorithm DFS for remote sensing images. Compared with traditional machine learning methods, DFS optimizes and designs a new dimension clustering module, customized loss function and sliding window segmentation detection mechanism. Among them, dimension clustering module optimizes priori anchors by designing clustering mechanism to improve the positioning accuracy, the customized loss function improves detection accuracy of small objects such as ships, and the sliding window segmentation detection solves the problem of low detection accuracy of large images. The comparative experiments on the classical remote sensing datasets show that, compared with YOLOv2, DFS improves mAP by 25.6% and greatly improves the detection efficiency of small objects and large images.
       
      Research and realization of AR technology in ancient
      agricultural tools display in science and technology museum
      FENG Xiao-qi,LIU Nian,GUO Xiao-yu,ZHENG Shi-jue
      2019, 41(12): 2173-2178. doi:
      Abstract ( 119 )   PDF (684KB) ( 143 )     
      Augmented reality technology combines virtuality with reality organically, breaking the boundary between virtual world and real world. According to the characteristics of augmented reality, a framework of implementing augmented reality system is studied. Firstly, the scene is collected, and 3D Max is used to design and model the model. Then, aiming at the problem of image recognition, the high-pass Vuforia image processing is selected by comparing the features recognition and matching results of SIFT algorithm, SURF algorithm, ORB algorithm and high-pass Vuforia. For 3D rendering, Unity3D, a professional rendering engine, is used to develop interactive software in augmented reality. Based on this framework, we design and implement a system themed with ancient agricultural tools display in science and technology museum, which can bring visitors a new experience of AR interactive reading. It can reproduce the important historical materials of the inheritance of ancient agricultural tools in the traditional agricultural culture of China, so as to realize the digital protection and dissemination of ancient agricultural tools.
       
      null
      LI Cong,PAN Li-li,CHEN Rong-yu,ZHOU Yan,SHAO Wei-zhi
      2019, 41(12): 2179-2186. doi:
      Abstract ( 155 )   PDF (942KB) ( 210 )     

      null

      UG-based three-dimensional annotation and
      NC technology of explosion-proof cover plate of shearer
      WANG Zhen-yu1,YANG Hui2,YANG Meng-jie3,WEI Juan1
      2019, 41(12): 2187-2192. doi:
      Abstract ( 101 )   PDF (1002KB) ( 118 )      Review attachment
      With the development of 3D CAD technology, the repeated transmission of product manufacturing information between 3D models and 2D drawings has seriously affected the correct and rapid transmission of product manufacturing information. Based on the three-dimensional product manufacturing information technology, taking the explosion-proof cover of shearer as an example, the three-dimensional model of the explosion-proof cover plate is established in UG NX10.0 and the three-dimensional annotation is carried out. The machining process route is designed and the CNC machining tool path is planned. The machining simulation is carried out to verify the correctness of the CNC machining. On this basis, the three-dimensional design of the explosion-proof cover of the shearer is completed. The research is of great significance to the digital design and manufacturing research based on model definition and the realization of manufacturing informationization.
       
      A case similarity calculation model
      in case pushing of judicial documents
      WANG Jun-ze1,2,MA Hong-jing1,2,ZHANG Yi1,2,YANG Lan-rong1,2
      2019, 41(12): 2193-2201. doi:
      Abstract ( 164 )   PDF (526KB) ( 177 )      Review attachment
      The strategy of pushing similar cases of judicial documents is helpful to solve problems such as the disunity of judgment standard, the difference of judgment with similar cases and the irregularity of sentencing in the judicial process. Aiming at the similar cases pushing strategy of judicial documents, based on the written discourse structure and linguistic expression of judicial documents, we can carry out the research by extracting the contents of judicial documents, analyzing the weights of different speech words, recognizing the unknown Chinese words in the contents, and calculating the quantity expression similarity. Besides, we design the corresponding case similarity calculation model. Experiments on real judicial documents datasets prove the validity of the model.
       
      Parametric hesitant fuzzy entropy and its application
      MEI Feng-jiao,LI Yong-ming
      2019, 41(12): 2202-2210. doi:
      Abstract ( 120 )   PDF (470KB) ( 128 )      Review attachment
      Hesitant fuzzy entropy is an important tool for depicting the uncertainty degree of hesitant fuzzy set. In order to solve the shortcomings of the existing hesitant fuzzy entropies, the axiomatic definition of hesitant fuzzy entropy is proposed based on hesitant fuzzy set, and the parametric hesitant fuzzy entropy is constructed. Secondly, some numerical examples are given to compare the new parametric hesitant fuzzy entropy with the existing fuzzy entropies. The results show that the proposed entropy can describe the uncertainty degree of information more flexibly and effectively. Then, the application of parametric hesitation fuzzy entropy in multi-attribute decision-making problem is explored. The proposed entropy is used to determine the weight of the attribute. Technique for Order Preference by Similarity to an Ideal Solution (TOPSIS) and fractional function are adopted to present a method to solve the optimal scheme selection problem. Finally, an example is used to verify that the parametric hesitation fuzzy entropy and the proposed decision method has some practicability and feasibility.

       
      A hierarchical clustering based feature
      selection algorithm for ranking learning
       
      MENG Yu-yu,CHEN Shao-li,LIU Xing-chang
      2019, 41(12): 2211-2216. doi:
      Abstract ( 108 )   PDF (677KB) ( 126 )      Review attachment
      Large search systems are especially necessary for quick response to user queries. At the same time, strict backend delay constraints must be observed when calculating the feature relevance of candidate documents. Feature selection can improve the machine learning efficiency. Considering the characteristics that most of the initial points of fast feature selection in ranking learning start from the single feature, which has the best ranking effect, this paper first proposes an algorithm of generating initial points of fast feature selection by hierarchical clustering, and applies the algorithm to two existing fast feature selection algorithms. In addition, a new method that makes full use of clustering features is proposed to deal with feature selection. Experiments on two standard datasets show that the proposed algorithm can obtain a smaller feature subset without affecting the accuracy and obtain the best ranking accuracy on a medium subset.
       
      An anomaly detection algorithm based on
      Attention-GRU and iForest for periodic time series
      WANG Teng1,JIAO Xue-wei2,GAO Yang2
      2019, 41(12): 2217-2222. doi:
      Abstract ( 289 )   PDF (517KB) ( 244 )      Review attachment
      Abnormal patterns detection in data (abnormal detection) is a very important research direction in the field of data analysis, and especially the anomaly detection of time series is one of the difficulties. At present, there are many researches on anomaly detection of time series data. Different techniques such as sliding window, wavelet analysis, Probabilistic Graphical Model (PGM), and Recurrent Neural Network (RNN) are used to detect the abnormal patterns. However, these techniques still have some deficiencies in processing this problem, which cannot guarantee real-time efficiency and accuracy in real engineering. In this paper, an anomaly detection algorithm based on Attention-GRU and iForest is proposed for periodic time series. The model is constructed based on Attention-GRU to predict long data sequence and ensure the detection efficiency in engineering. iForest is used to establish a normal data fluctuation range, avoiding the error caused by hypothesis testing. Practice verification shows that this model can improve the anomaly detection efficiency of periodic time series data in actual engineering, and has better recall rate and accuracy.


       
      A path-based frequent subgraph mining algorithm
      TANG De-quan,ZHANG Bo-yun
      2019, 41(12): 2223-2230. doi:
      Abstract ( 149 )   PDF (598KB) ( 144 )     
      Graph mining is an important research area in data mining , while graph mining mainly focuses on frequent subgraph mining in graph datasets. The key step in the research of frequent subgraph mining techniques is to establish an effective mechanism to reduce the generation of redundant candidate subgraphs in order to efficiently calculate and process the required frequent subgraphs. A path-based frequent subgraph mining algorithm is proposed. The algorithm first finds all frequent edges to mine frequent single paths, then expands large frequent paths through combination operation and bijection sum operation, and then uses the connection operator to generate all frequent subgraph candidate sets. The correctness and completeness of the algorithm are proved by theorem. Theoretical analysis shows that the algorithm has lower time complexity than the existing algorithm. Finally, experiments are carried out on two graph datasets, and the results verify that the algorithm is superior in terms of quality and time performance when generating candidate sets.
       
      An improved Apriori algorithm
       based on Boolean matrix reduction
      LIAO Ji-yong,WU Sheng,LIU Ai-lian
      2019, 41(12): 2231-2238. doi:
      Abstract ( 154 )   PDF (803KB) ( 159 )     
      Aiming at the shortcomings of Apriori algorithm in association rules, an improved Apriori algorithm based on Boolean matrix reduction is proposed.In this algorithm, the transaction database is converted into a Boolean matrix, and one row and two columns are added at the end of the matrix to record the number of the same transactions and the number of 1 in the matrix row and column.According to the number of supports, the elements of each matrix column are arranged in ascending order, so the number of scanning matrix columns is reduced in the process of compressing the matrix and the time efficiency of the algorithm is improved. In addition, in order to improve the spatial efficiency of the algorithm, the operation of deleting infrequent itemsets is added.Experimental results and performance analysis prove that the improved algorithm has better performance than the existing Apriori algorithm, and can effectively improve the computational efficiency of the algorithm.
       
      An online pattern matchingsolving algorithm
       under the nonoverlapping condition
       
      WU You-xi,WANG Bo,GAO Xue-dong
      2019, 41(12): 2239-2246. doi:
      Abstract ( 97 )   PDF (780KB) ( 104 )     

      Pattern matching under the nonoverlapping condition is one of many pattern matching algorithms for gap constraint problems.Although it is proved that pattern matching under the nonoverlapping condition is a polynomial time complexity problem and an effective solving algorithm is proposed, the current solving algorithm adopts offline calculation, which has the disadvantage of high spatial complexity.In order to solve this problem, this paper designs an online solving algorithm. The algorithm reads the sequence string and finds the root-leaf path in the flow net tree that meets the constraint conditions, which realizes fast pruning of useless nodes and thus speeds up the matching speed.Compared with the spatial complexity of the offline algorithm, the spatial complexity of the online algorithm is O(m×maxlen×W), where m, maxlen, and W represent the pattern string length, the maximum pattern length constraint and the maximum gap constraint, respectively.Experimental results not only verify the completeness of our proposed algorithm, but also demonstrate that it consumes less memory than the existing algorithm.