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

Current Issue

    • A high-radix hybrid topology in interconnection networks
      LU Wen-bin,SONG Xin-liang,LU Hong-sheng,DING Ya-jun
      2017, 39(10): 1781-1787. doi:
      Abstract ( 175 )   PDF (686KB) ( 263 )     
      With the continuous expansion of high performance computer systems to meet the increasing requirements for high performance computers, the interconnectiction network system has become the key factor that influences the performance. How to design larger-scale networks faster with lower latency and lower cost, and larger throughput based on high-radix router by making full use of the features of high-radix router is currently the main research direction. We analyze the features of the high-radix network and synthesize the torus and fat-tree topology, and put forward a new hierarchical hybrid interconnection network topology. The proposed topology has satisfactory scalability and communication capability. We finally use the network simulator NetSim to simulate and analyze its performance.
       
      Design and implementation of a prefix computation
      model of leading zero anticipator algorithm
      FU Kun1,2,WEI Si-jie1,2,GENG Yue-hua3
      2017, 39(10): 1788-1793. doi:
      Abstract ( 235 )   PDF (564KB) ( 272 )      Review attachment
      The leading zero anticipator (LZA) algorithm is very important for studying floating-point addition operation, and the analysis of floating-point addition indicates that the LZA  module plays a critical role in the performance improvement of  floating-point addition operations. We define a series of definitions and theorems from the perspective of prefix computation, and prove that the LZA algorithm can be attributed to a prefix computation problem in nature. Thus, the problem can be solved by the dichotomy recursive method. In LZA process, we firstly convert the prediction problem of two operations  to a digital string feature detection problem on numeric character set of {1,0, 1} by performing the subtraction of "Borrow Retirement" on addition operations. Secondly, a unified form of bit strings is obtained via the recoding technique which eliminates the continuous string of "1". Finally, the dichotomy recursive algorithm is designed based on the bit string structure of leading zero digits.
       
      Design and implementation of
      a new elastic buffer for USB 3.0
      CHANG Hong,MENG Jian,PENG Te,KE Dao-ming
      2017, 39(10): 1794-1800. doi:
      Abstract ( 185 )   PDF (1496KB) ( 195 )      Review attachment

      The process of adding SKP is usually completed by breakpoint restoration and pointer jump in an elastic buffer. Aiming at the problems of complex asynchronous logic circuit design and possible timing errors caused by this realization method, we propose a novel technique to achieve SKP adding by the read pointer pause. Firstly, the threshold monitor checks the amount of valid data, which are then compared with the adding threshold to generate an adding instruction. Secondly, we make the read pointer pause and add the SKP to the output data, which guarantees the state of elastic buffer at half-full by raising the volume of effective data. Experimental results show that the proposed elastic buffer can achieve the function of SKP adding and removing correctly while both the read and write frequencies of the buffer can reach 500MHz, which meets the design requirements of universal serial bus 3.0 (USB 3.0).

      A parallel MRACO-PAM clustering
      algorithm based on MapReduce
       
      ZHAO Bao-wen,XU Hua
      2017, 39(10): 1801-1806. doi:
      Abstract ( 130 )   PDF (502KB) ( 198 )      Review attachment

      Clustering analysis is one of the most commonly used data processing algorithms, and the partitioning around medoid (PAM) has been one of the most popular clustering algorithms since it was proposed in 1990. The PAM clustering algorithm solves the problem that the K-Means algorithm encounters when processing outlier data, which is sensitive to dirty data in clustering process. However, the original PAM’s convergence speed is slow and it works inefficiently for large datasets due to its time complexity. To address this problem, we enhance the global and local searching capabilities of the PAM by taking advantage of the ant colony algorithm, and propose a parallel MRACO-PAM clustering algorithm based on MapReduce programming framework. Experimental results demonstrate that the parallel MRACO-PAM algorithm based on MapReduce  improves the convergence speed and is capable of dealing with large-scale data with good scalability.

      A document similarity calculation method based on fully
      homomorphic encryption technology for cloud storage
      JIANG Xiao-ping,ZHANG Wei,LI Cheng-hua,ZHOU Hang,SUN Jing
      2017, 39(10): 1807-1811. doi:
      Abstract ( 132 )   PDF (1551KB) ( 186 )      Review attachment

      In order to preserve user privacy in cloud storage services, we propose a method for calculating the similarity of documents under the ciphertext environment. After the data owner uploads the document ID, the ciphertext of document and the ciphertext of document simhash to Cloud servers, the cloud server performs fully homomorphic addition operations on the simhash ciphertext of the document whose similarity is expected and the simhash ciphertext of the data owner's document. Then the ciphertext of the Hamming distance between documents  is obtained. The data owner can get the results of document similarity ranking by decrypting the ciphertext of the Hamming distance. The goal of privacy preservation can be achieved by this method because the cloud server can complete  similarity calculation without any plaintext information, neither the document text nor its simhash value. We explain the proposed method in detail and the related experimental data verify its feasibility and correctness.

      An overall scheme and a software tool of coordination and control
      of accessories stock for cloud service platform of industrial chian
      Lv Rui1,2,SUN Lin-fu1,2
      2017, 39(10): 1812-1818. doi:
      Abstract ( 88 )   PDF (840KB) ( 149 )     

      To meet the spare parts collaborative needs of manufacturing industry chain collaborative platform, we propose a cross-enterprise inventory control solution and establish a near-term demand forecasting model. In order to ensure the effectiveness of the inventory control program, we dynamically extract historical transaction data of each node and real-time inventory data, and obtain the optimal solution based on the genetic algorithm. We use the MapReduce framework to calculate model parameters and improve the processing speed. By pushing the results to downstream service providers, the feedback information can control the dynamically generated orders. The application in the automotive industry chain cloud services platform demonstrates that the response time of the industry chain is compressed.

      A constrained pseudo-random function
      construction  scheme based on hierarchical proxy
      ZHANG Li-na1,2,ZHOU Yan-wei2,HOU Hong-xia2,3
      2017, 39(10): 1819-1824. doi:
      Abstract ( 115 )   PDF (431KB) ( 151 )      Review attachment

      The concept of constrained pseudo-random functions (CPRF) was proposed independently by Boneh and Waters, Boyle etc., Kiayias etc. in 2013. In a CPRF a constrained key  ks can be derived from the master key  k. Both  ks and   k can be used to calculate the same pseudo-random function (PRF) value. Based on the CPRF with bit-fixing structure proposed by Boneh and Waters, we propose a construction of hierarchical proxy based on constrained pseudorandom functions. The size of the constrained set cannot be influenced by the layer number of the hierarchical proxy. The proposed scheme is proved to be secure in the standard model under the multilinear decisional Diffie-Hellman assumption. And it can be used to generate the encryption key of broadcast encryption or the session key of the identity-based non-interactive key exchange under the hierarchical proxy in practice.

      An enhanced naive Bayesian relationship
      prediction model in complex networks
      WU Jie-hua1,2,SHEN Jing1,ZHOU Bei1
      2017, 39(10): 1825-1831. doi:
      Abstract ( 88 )   PDF (708KB) ( 165 )      Review attachment
      Complex networks include biological information networks, collaboration networks and social networks. Studying the relationship prediction of complex networks helps predict relationship between proteins, find out cooperation relationship among scientists, as well as mine potential social networks. Currently, most relationship prediction algorithms are realized by similarity-based models, however, this type of algorithms based on network topology feature are explicitly constructed, which ignore latent information behind generated relationship. To solve this problem, we propose an enhanced naive Bayesian relation prediction model (ELNB), which defines a conditional probability to model the local sub-graph structure. It can effectively alleviate the independence assumption of LNB and realize a quantitative calculation of neighbors contribution. Experiments on artificial datasets and real datasets show that the proposed model is better than the baselines and some recently proposed models. Meanwhile,the idea of ELNB can be extended to other similarity algorithms based on common neighbor nodes, which provides a new method for the research of such kind of model.
       
      Attack and improvement on an ID-based
      partially blind signature scheme
       
      ZUO Li-ming1,2,ZHANG Ting-ting1,2,GUO Hong-li1,2,CHEN Zuo-song1,2
      2017, 39(10): 1832-1836. doi:
      Abstract ( 87 )   PDF (414KB) ( 135 )      Review attachment
      The partially blind signature scheme is an important foundation signature scheme widely used in anonymous applications such as electronic cash, electronic payment and electronic voting. Through the crypt analysis of the ID-based partially blind signature scheme proposed by Yin et al. We find that there are forgery signature defects between multiple users in the scheme. The attacker can forge the signature by indexing the key parameters and using the repeated parameters. We therefore propose an improved partially blind signature scheme and it proves to be existentially unforgeable against adaptive chosen message in random oracle model. The new signature can resist indexing attacks and be applied to certificateless  electronic voting occasions.
       
      A hybrid feature-based detection method on Android malware
      XU Lin-xi,GUO Fan
      2017, 39(10): 1837-1846. doi:
      Abstract ( 112 )   PDF (1273KB) ( 192 )      Review attachment
      Currently, Android malware detection is one of the hotpots in the security research field. Since Android is open source and very popular, the Android platform becomes a target of most malwares. Current approaches only extract syntax features or semantic features respectively so that it is difficult for them to know the real intention of the malware exactly. We propose a hybrid feature extraction method, using the set of class-based taint propagation paths as semantic features and claiming permissions and Intent-Actions as syntax features. We normalize all the extracted features before training and clustering data sets by K-means, and then produce feature vectors of each malware family. Finally we adopt the Euclidean distance computation to measure the similarity between the unknown program and feature vectors. The prototype is implemented on top of FlowDroid to analyze 400 real programs, and the results demonstrate that the method has higher precision.
       
      A geographic location routing method for
       energy balance in wireless sensor networks
      LI Lan-ying,JIANG Wei-cheng,HE Yong,LI Xiao-fang
      2017, 39(10): 1847-1853. doi:
      Abstract ( 89 )   PDF (552KB) ( 135 )     
      The wireless sensor network routing algorithm based on geographical position only focuses on the geographic
      information. We propose a multi-path routing algorithm based on energy of nodes. We use geographic location
      and energy to establish a 3D coordinate system and calculate the probability of the next hop according to the
      effective forward distance and the energy of neighbor nodes. The energy consumption is scattered in the
      neighbor nodes which are effective to move forward so the network survival time is prolonged. Routing holes
      are reduced and delayed. Experimental results show that the number of dead nodes, surviving nodes and routing
      holes are significantly improved in comparison with the two-phase geographic greedy forwarding (TPGF)
      algorithm. The validity of the algorithm is verified.
       
      Application of discrete Walsh transform
      in  digital multiplexer network design
       
      JAING En-hua,JIANG Wen-bin
      2017, 39(10): 1854-1861. doi:
      Abstract ( 76 )   PDF (728KB) ( 160 )      Review attachment
      We study the applications of discrete Walsh transform in the design of digital multiplexer networks, and
      propose a computer aided design theory and an algorithm of the multiplexer networks based on the Walsh
      spectral techniques. We also present a practical application example, which shows that the algorithm can
      minimize or nearly minimize the multiplexer tree-type network, and that the method is effective and suitable
      for computer aided design of multiplexer tree-type networks. By using CMOS circuits, the 1-of-4 multiplexer
      module and the designed multiplexer network with minimal size are realized. HSPICE simulation results show
      that the designed circuit has correct logic functions.

       

      Robust visual odometry based on front and back cameras
       
      SHI Xiao-tian1,ZHANG Yu2,FANG Zhou1
      2017, 39(10): 1862-1869. doi:
      Abstract ( 97 )   PDF (980KB) ( 181 )     
      We propose a new visual odometry method to use front and back cameras at the same time due to the terrible
      impact of luminance on indoor visual odometry and the dual-camera feature of modern  mobile devices. By the
      state estimation of the visual odometry on each side, we can achieve the sustained output even when one side
      fails, and the robustness of visual odometry is improved. In addition, we fusion the output of the two-side
      visual odometry by Kalman filter to improve the accuracy when the two sides both run normally. Experimental
      results under various practical environments in various velocities show that the system can output regularly
      even when one side fails and the accuracy of the output is improved when the two sides work normally.
      A multi-threshold 3D reconstruction algorithm
      based on labeled medical images
      XIAO Hong-xu,YANG Zhi-yong,JIANG Shan,HUANG Zhe,ZHAO Sheng-li
      2017, 39(10): 1870-1876. doi:
      Abstract ( 73 )   PDF (902KB) ( 138 )      Review attachment
      As a traditional surface reconstruction algorithm the marching cubes (MC) is unable to extract multi-
      threshold organs at one time. We propose a multi-threshold reconstruction algorithm to divide the target area
      and surrounding tissues in the MRI image into several label values. Changing the lables of multi-threshold
      organs into brief numbers can decrease the memory space and accelerate the speed of drawing contour surfaces.
      We also define the index way of voxel vertexes and isosurface intersecting morphology of multi-threshold
      three-dimensional reconstruction, which can avoid the situation of triangle facets and vertexes reuse of the
      MC. Furthermore, the contour surface reconstruction of the multi-organ requires only one time scanning of the
      MRI image. Experimental results show that the number of facets and vertices is decreased more significantly
      when the number of organs is larger and their relationship is closer in comparison with the traditional MC
      algorithm, and the reconstruction speed is improved by 30% while the reconstruction effect is guaranteed.
      An improved sparse iterative closest point algorithm
      ZHOU You,GENG Nan,ZHANG Zhi-yi
      2017, 39(10): 1877-1883. doi:
      Abstract ( 95 )   PDF (865KB) ( 221 )      Review attachment
      The sparse iterative closest point algorithm for point cloud with noise points is sensitive to the outliers
      contained in the target point cloud, and is inefficient. To solve the problems, we find the corresponding
      point-pairs based on neighborhood information to improve the sparse iterative closest point algorithm. The
      improved sparse iterative closest point algorithm firstly uses the improved registration based on the PCA to
      adjust the position of the two point clouds, and then finds the corresponding point-pairs based on
      neighborhood information. Finally we use the alternating direction method of multipliers (ADMM) to get the
      optimal transformational matrix for corresponding point-pairs. Experiments on Stanford rabbit and potted
      model show that the improved algorithm can handle the outliers contained in the target point cloud, and the
      algorithm speed can be increased by 30%.
      Murals inpainting based on generalized
      regression neural network
      REN Xiao-kang,CHEN Pei-lin
      2017, 39(10): 1884-1889. doi:
      Abstract ( 104 )   PDF (902KB) ( 216 )      Review attachment
      We propose a digital inpainting and protection method for Dunghuang murals through the application of the
      generalized regression neural network. The damaged mural images are denoised with the anisotropic diffusion
      method. Morphological dilation operator is applied to extract the boundary pixels in the damaged region. The
      sample blocks of pixels similar to those around the boundary of the damaged region serve as input training
      samples of the generalized regression neural network. The pixel values of the sample blocks are input into
      the generalized regression neural network by the zigzag scanning. Adaptive smoothing parameters, in addition,
      are also used. Finally, an approximate inpainting model is obtained, which can predict the information of the
      pixels in the damaged region. Experimental results indicate that the proposed method is effective in the
      digital inpainting of murals.
      A SURF image registration algorithm based on fusion features
      QIN Yu1,WU Jing-jing 1,2,AN Wei1,2,ZHANG Mei-juan3
      2017, 39(10): 1890-1895. doi:
      Abstract ( 76 )   PDF (894KB) ( 145 )      Review attachment
      The speed-up robust features (SURF) algorithm is a scale-invariant, rotation-invariant and robust
      registration algorithm. However, since the color features of the image can be lost, its registration effect
      of color images is poor. We therefore propose a SURF registration algorithm based on fusion features.
      Firstly, we utilize the color invariant and the double local binary pattern (DLBP) texture features of the
      color image to construct the grayscale of fusion features. Meanwhile, we propose an adaptive method to adjust
      the weights of fusion features based on the color histogram of the color image. Then, the SURF algorithm is
      used to extract and match the feature points on the grayscale of fusion features. Finally, the improved
      random sample consensus (RANSAC) algorithm is used to remove the mismatch points. Experimental results show
      that the proposed algorithm can effectively increase the feature points and speed up the registration rate
      for color images.
      Application of spectrum and Kuhn-Munkres
      algorithm in graph matching
       
      LI Chang-hua,LI Zhi-jie,GAO Yang
      2017, 39(10): 1896-1900. doi:
      Abstract ( 94 )   PDF (607KB) ( 153 )      Review attachment
      In order to match and analyze effectively of the structured graph in the database, we present an improved
      Kuhn-Munkres algorithm based on the global similarity matrix and location similarity matrix. Firstly, we
      construct a global matrix and a location matrix from graph data. The global similarity matrix is constructed
      with the adjacency matrix and the Laplacian spectrum of feature structures. As for the location similarity
      matrix, we use the Gaussian kernel function to perform the normalized calculation of the relative position
      and construct  the matrix with the spectral features. The nodes location similarity matrix describes the
      relative position of all nodes in the graph, which can offset the drawback of the global similarity matrix,
      which means it can only depict the overall structure of the graph. Finally, we use the Kuhn-Munkres algorithm
      to do graph matching, and get the maximum weight matching in bipartite graphs. Experiments show that the
      improved Kuhn-Munkres algorithm can effectively enhance matching accuracy between nodes.
       
      A new summation multi-kernel learning
      method based on sample weighting
      SHEN Jian,JIANG Yun,ZHANG Ya-nan,HU Xue-wei
      2017, 39(10): 1901-1907. doi:
      Abstract ( 78 )   PDF (516KB) ( 165 )      Review attachment
      Multi-kernel learning is a new research hotspot in current kernel machine learning field. By mapping data
      into the high dimensional space, kernel methods increase the computing performance of linear classifiers such
      as support vector machines, and it is a convenient and effective way to deal with nonlinear pattern
      recognition and classification. However, in some complex situations, such as heterogeneous data or irregular
      data, large sample size and non-flat sample distribution, the kernel learning method based on single kernel
      function cannot completely meet the requirement, so it is necessary to develop multiple kernel functions in
      order to get better results. We propose a new summation multi-kernel learning method based on sample
      weighting which can be weighted by the capability of how much a single kernel function can fit the sample.
      Experiment analysis on several data sets shows that the proposed method can obtain high classification
      accuracy.
      Target threat assessment based on
      improved grey correlation algorithm
      ZHANG Hao-wei,XIE Jun-wei,SHEN Chuan,ZHANG Zhao-jian
      2017, 39(10): 1908-1914. doi:
      Abstract ( 98 )   PDF (709KB) ( 198 )      Review attachment
      Aiming at the threat assessment of targets in air defense combats, we propose a new target assessment method
      based on improved grey correlation algorithm. Time sequence weights are introduced to construct the dynamic
      threat assessment model of targets, which improves traditional methods by on-ly assessing current targets’
      threat. According to subjective and objective properties, the weights of tar-gets threat elements are
      calculated in real time, which are then converted to the same layer by using the set pair analysis theory.
      Finally, the improved grey correlation algorithm based on the technique for or-der preference by similarity
      to an ideal solution (TOPSIS) is applied to get the final targets threat order. Theoretical analysis and
      simulation results prove the reliability and validity of the method.