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

Current Issue

    • Edge weight selection of the aggregation-type
      algebraic multigrid preconditioner from top to bottom
      WU Jianping,YIN Fukang,PENG Jun,YANG Jinhui
      2019, 41(02): 191-196. doi:
      Abstract ( 188 )   PDF (418KB) ( 240 )      Review attachment
      Aiming at the top-bottom aggregation-type multigrid preconditioner from top to bottom based on graph partitioning, we investigate the multigrid construction method using METIS software package. Given that software package METIS can only process integer weights but not float-type weights, we propose an effective scheme to convert float-type edge weights to integer edge weights. Then it is used to select edge weights in the METIS graph partitioning software, and we propose an improved algorithm for aggregation-type multigrid preconditioner from top to bottom. Numerical experiments on the solution to the sparse linear system derived from two-dimensional and three-dimensional model partial differential equations show that the improved method with edge weights can greatly improve the iterative efficiency of the multigrid preconditioned conjugate-gradient method, and the improvement for anisotropic problems are especially significant.
       
      Data quality assurance based on
      metamodel control in big data environment
      YANG Dongju1,2,XU Chenyang1,2
      2019, 41(02): 197-206. doi:
      Abstract ( 155 )   PDF (2553KB) ( 240 )      Review attachment
      In  data integration process, more and more heterogeneous data sources bring new challenges and difficulties to the improvement of data quality after integration. Aiming at the data quality problems, such as data redundancy, invalidity, duplication, missing, inconsistency, error value and format error of the traditional ETL model after data integration, we propose an ETL integration model based on metadata model control. The mapping rules are defined in detail. By combining the metamodel and the mapping mechanism in extraction, transformation and loading phases, we can effectively guarantee the quality of integrated data. The proposed metamodel has been applied to the data integration business of scientific and technological resource management. The analysis on data integration examples of scientific and technological resources management shows that this data integration solution can effectively support the construction of data warehouses in the big data environment and improve data quality after integration.
       
      A NAND Flash static wear leveling
      mechanism based on weighted heap sort
      LIU Yan,XU Jilong,ZHU Lei
      2019, 41(02): 207-213. doi:
      Abstract ( 224 )   PDF (894KB) ( 263 )      Review attachment
      As one of the basic mechanisms of the flash translation layer, the wear leveling mechanism is a software algorithm that is applied to extend the life of the flash disk and improve the reliability of stored data. However, existing wear leveling mechanisms are too aggressive to balance the erasure counts of the entire flash memory and ignore the unnecessary data migration overhead due to the unreasonable selection of victim blocks during wear leveling operations, thereby affecting the overall read and write performance of the solid state disk. To solve this problem, we firstly propose a NAND Flash static wear leveling mechanism based on weighted heap sort, namely WHWL. We introduce a weight calculation method based on page data access frequency and the weight of erase counts of the block, which can effectively improve the hit rate of the target blocks with a small number of erases (cold blocks) and a low frequency of data access (cold data), and avoid redundant data migration operations. Secondly, we also propose a victim block selection algorithm based on weighted heap sort to speed up the selection of victim blocks. Experimental results show that compared with the existing PWL and BET algorithms, using the same mapping mechanism, the WHWL can increase the life span of solid state disks by 1.28 and 5.83 times, and also greatly decrease the number of migrations.
       
      Selecting distance metrics for incremental
      clustering algorithm of high dimensional data
      SHAO Junjian,WANG Shitong
      2019, 41(02): 214-223. doi:
      Abstract ( 220 )   PDF (510KB) ( 220 )      Review attachment
      Appropriate distance metric functions have an important effect on clustering results. For large-scale and high-dimensional datasets, the incremental fuzzy clustering algorithm is used to analyze the selection of distance metrics. Since the SpFCM algorithm divides a large-scale dataset into small samples for incremental batch clustering, it can get better clustering results in limited computer memory. Different distance metric functions are applied into the traditional SpFCM algorithm in order to measure the similarities between different samples to check the effect of different distance metrics on the SpFCM algorithm. Four distance metrics, which are the Euclidean metric, the cosine metric, the correlation distance metric and the extended Jaccard similarity metric, are used to calculate the distance for different large-scale high dimensional datasets. Experimental results show that, the latter three distance metrics can greatly improve the clustering effect. The correlation distance metric gets a better clustering result while the cosine distance metric and the extended Jaccard similarity distance get an average result.
       
      An anomaly detection system
      based on express big data
      ZHANG Man,YU Zhiwen,GUO Bin,REN Siyuan,YUE Chaogang
      2019, 41(02): 224-232. doi:
      Abstract ( 228 )   PDF (883KB) ( 276 )      Review attachment
      With the advent of the information age, the express delivery industry has developed rapidly, which has promoted the transformation of circulation methods and the consumption upgrading. While enjoying the tremendous convenience of the development of the express delivery industry, people are also facing uncontrollable liquidity risks, and serious challenges are posed to public safety. For example, stolen goods are sold by express delivery, and dangerous goods such as drugs and explosives are transported by express delivery. Given the abovementioned considerations, we focus on the crimes of using express delivery to deal with stolen goods based on the analysis of actual historical records of express delivery, and then take the identification of such criminal suspects as the research target to conduct detailed analysis from the aspects of statistics, time, and geography. In addition, we also present a twostep anomaly detection method for suspect identification. The first step is to filter normal users, and the second step is to identify suspects. Experimental results show that in comparison with traditional methods, this method can accurately identify suspects, effectively solve the problem of positive and negative data imbalance, and significantly reduce false detection rate. Therefore, it has high practical value.
       
      Design and implementation of dual-channel
      serial RapidIO for multiple transmission modes
      GUO Xintong,LEI Yuanwu,GUO Yang
      2019, 41(02): 233-239. doi:
      Abstract ( 162 )   PDF (1325KB) ( 216 )      Review attachment
      The traditional serial RapidIO2.1 supports 3 lane modes (1×, 2×, and 4×). In 1× or 2× modes,  only 1 or 2 lanes out of 4 work for data-transmission while the others are in idle, which brings a result of bandwidth waste. In addition, one RapidIO interface can merely be connected with one destination. We design a dualchannel serial RapidIO interface based on traditional serial RapidIO interface protocol, which supports 14 transmission modes by a configurable crossbar switch on the PCS layer. It can connect 2 serial RapidIO interfaces simultaneously when it works in the dual-channel mode. This design improves the interconnected flexibility and transmission bandwidth of the RapidIO system. Simulation tests prove that the transmission bandwidth of the dualchannel RapidIO is approximately two times of that of the single channel RapidIO under 1× or 2× modes, and approximately equal to that of the single channel serial RapidIO interface under 4× mode.
       
      An efficient solver for large-scale triangular linear equations
      JIA Xun,WU Guiming,QIAN Lei,XIE Xianghui,WU Dong
      2019, 41(02): 240-245. doi:
      Abstract ( 128 )   PDF (707KB) ( 204 )      Review attachment
      Largescale triangular solver is an important computational kernel in scientific and engineering applications. However, execution of this kernel is not efficient on existing CPU and GPU platforms, due to limited cache capacity and the underlying problems of the architecture design. In the block solving of large-scale triangular linear equations, matrix multiplication is the main operation and its computational efficiency is crucial for improving the computational efficiency of solving triangular linear equations. Taking advantage of the high computation efficiency of the matrix multiplication coprocessor as the computing platform, and according its architectural features, we propose a block solving method and a performance analysis model of large-scale triangular linear equations on the matrix multiplication coprocessor. Experimental results show that a highly-efficient largescale triangular solver can be implemented on the matrix multiplication coprocessor with a computational efficiency up to 85.9%. Compared with the GPUs under the same process technology mode, the proposed triangular solver on the coprocessor can achieve 2.42× actual performance and 10.72× resource utilization.
      Fault diagnosis of analog circuits based on
      ELM optimized by an adaptive wolf pack algorithm
       
      YAN Xuelong,WANG Binbin
      2019, 41(02): 246-252. doi:
      Abstract ( 119 )   PDF (900KB) ( 218 )      Review attachment
      In order to detect and diagnose faulty components in analog circuits more efficiently, we propose to use the adaptive wolf pack algorithm to optimize the extreme learning machine(ELM). The method includes the adaptive genetic algorithm which effectively selects feature parameters to generate optimal feature subsets. They are then used to construct the samples which are input into the ELM network to classify the faults. Given that the connection weights between the input layer and hidden layer in the ELM network, and the deviation of the hidden layer can affect the learning speed and classification accuracy, we apply our method to optimize them and select the corresponding optimal value, thus improving the training stability of the ELM network and the success rate of fault diagnosis. The specific realization process of these methods is given through the diagnosis of two typical analog circuits, and their fault diagnosis rates are over 99%. Simulation results show that the method has good accuracy and stability for fault diagnosis of analog circuits.
      Link representation and prediction
      based on the simplest subgraph
      SHANG Zhenhao,CHENG Hua,FANG Yiquan
      2019, 41(02): 253-259. doi:
      Abstract ( 123 )   PDF (695KB) ( 223 )      Review attachment
      Traditional link prediction methods of sparse networks have low accuracy. In order to capture the possibility of link establishment among sparse network nodes, we propose the concept of simplest subgraph based on the shortest path between a pair of nodes, which reflects the tight topology relationship between nodes. Based on the node2vec node vectorization method, the link representation based on the shortest path is implemented. To complete the link classification task, we use the long short-term memory (LSTM) recurrent neural network to learn the characteristics of long-link node sequences. Compared with existing methods, the proposed method can increase the AUC value on 4 different datasets by 11.6% averagely, and the AP value by an average of 13.3%.


       
      Review on network function virtualization technology
      GOU Jianguo,L Gaofeng,SUN Zhigang,GOU Liping
      2019, 41(02): 260-267. doi:
      Abstract ( 238 )   PDF (741KB) ( 517 )     
      A large number of network function devices are deployed in enterprise networks and data centers to implement related application functions, improve network performance, and strengthen network security. Most of these network function devices are based on hardware, and have problems such as functional hardening, poor scalability, and unified management difficulties. In order to solve the above problems, both the industry and academia have turned their attention to the network function virtualization (NFV) technology. By decoupling network functions from the physical devices on which they run, network functions are not constrained by physical devices, facilitating the upgrades and updates of  network device services. At the same time, NFV provides possibility for new architectures, systems, and applications. We first introduce the NFV technology and compare it with cloud computing and SDN. Then we elaborate current research results from six dimensions, which are virtual network function (VNF) system architecture, data plane, control plane, deployment mode, implementation language and application. Finally, we summarize and provide an outlook of future NFV research direction.
       
      A positioning algorithm with twice grid
      scanning and triangle centroid iteration
      SONG Haisheng,ZHOU Hao,ZHU Changju,WU Jiaxin
      2019, 41(02): 268-274. doi:
      Abstract ( 155 )   PDF (807KB) ( 245 )     
      In order to improve the positioning accuracy of wireless sensor networks, we improve a twice grid scanning positioning algorithm based on the GridScan algorithm, and further improve the positioning accuracy by using the triangle centroid iteration localization algorithm (TCILA). Firstly, the nearest neighbor anchor node is found by comparing the signal strength of all the neighbor anchor nodes of the unknown node to the unknown node, and the nearest neighbor anchor node is used to scan the estimated area of the relocated unknown node two times. And then the PIT rule is used to further reduce the positioning area. Finally, the centroid of the centroid triangle is iteratively calculated to get the final location. Simulation results show that in the same network environment, the improved algorithm can significantly improve the average relative positioning accuracy in comparison with traditional algorithms.
       
      A caching decision and replacement strategy based
      on dynamic content popularity for NDN
      YU Meiju,LI Ru
      2019, 41(02): 275-280. doi:
      Abstract ( 178 )   PDF (596KB) ( 207 )     

      In the named data networking (NDN), routers have the capacity of in-network cache, which greatly improve the efficiency of data distribution and retrieval in the network. However, because of the limited cache capacity in routers, how to design an effective caching strategy is still a grave challenge. To solve the problem, we present a caching decision and replacement strategy  based on dynamic content popularity (DPDR). It fully considers content popularity and caching capacity and utilizes an additive increase multiplicative decrease (AIMD) algorithm to dynamically adjust the popularity threshold to store the arriving data whose popularity exceeds the popularity threshold in the cache space. In addition, we also propose a caching replacement algorithm, which takes the historical information of content popularity and the last request time into account to remove the contents with lowest replacement value from the cache store (CS). Simulation results show that compared with other schemes, the DPDR strategy can effectively improve cache hit rate, reduce average cache hit distance and decrease network throughput.

      Complete weight enumerators of a class of linear codes
      YANG Shudi1,2,YUE Qin1
      2019, 41(02): 281-285. doi:
      Abstract ( 145 )   PDF (349KB) ( 185 )     
      We construct a new class of linear codes with defining set. Their complete weight enumerators and weight enumerators are determined explicitly by applying the calculation technique of exponential sums and the theory of cyclotomic numbers over finite fields. They are twoweight codes and can be applied in strongly regular graph construction and secret sharing schemes.

       
      A cognitive full-duplex relay selection
      strategy based on potential game
      LI Zhaoyi,LIU Zhanjun,XUE Yaru,LIU Hongxia
      2019, 41(02): 286-292. doi:
      Abstract ( 127 )   PDF (586KB) ( 198 )     
      Aiming at the high complexity of the cognitive relay selection strategy algorithm in cognitive collaborative networks under the interference power constraint from secondary users to the primary receivers, the selfinterference constraint at each secondary relay and the total power constraint for the secondary system, we propose a full duplex relay selection strategy based on potential game. The relay selection problem is modeled as a potential game where the total rate of cognitive collaborative networks is regarded as the common utility function. Then the game model is analyzed. On the premise of the absence of the information of the infeasible strategy sets, we solve the conditions which guarantee the existence and feasibility of the pure Nash Equilibrium (NE) in the proposed game. Furthermore, in order to achieve a pure strategy NE, we propose a cognitive fullduplex relay iterative algorithm, and discuss the complexity of the proposed algorithm. Simulation results show that the proposed algorithm can obtain a performance of optimal or near optimal rate with low complexity, and achieve a significant performance gain compared with the traditional half duplex mode.
       
      A TLD object tracking algorithm based on KCF similarity
      ZHANG Jing1,2,XIONG Xiaoyu1,BAO Yibo3
      2019, 41(02): 293-301. doi:
      Abstract ( 203 )   PDF (1724KB) ( 211 )     
      The architecture of the trackinglearningdetection (TLD) algorithm is a good reference  for studying longtime single object tracking algorithms. However, due to some defects of its own, the TLD algorithm tends to cause the accumulation of errors and the occurrence of losing objects in complex situations such as fast moving, occlusion and light changes. Given the limitation of the median flow algorithm as the tracker in the tracking module of the TLD algorithm, we propose a TLD object tracking algorithm based on KCF similarity (TLD-KCFS). The KCF algorithm is used to monitor the TLD tracking in real time. The similarity is calculated via the tracking results to judge the switching of the detection module, and the bounding box is adjusted by the combination of the two results. Tests on several different types of videos show that the TLD-KCFS algorithm can achieve stable and good tracking output in complex situations such as blur, fast moving, occlusion, and light changes. It is robust and suitable for longtime object tracking.
       
      A combined calibration and correction
       method for dual-camera module
      YANG Fengkai1,YANG Hongliang2,CHENG Suxia1
      2019, 41(02): 303-307. doi:
      Abstract ( 135 )   PDF (482KB) ( 236 )     
      We propose a  combined calibration and correction method for dual-camera module, which can merge the two processes of traditional calibration and correction into one procedure. The calibration and correction of the dual-camera module does not rely on external measuring devices, and only requires a picture of the target template by the two cameras simultaneously. Firstly, we calculate the radial distortion coefficient of the camera based on crossratio invariance, and transform the camera distortion imaging model into a linear model by which the two cameras are respectively calibrated. Then the pose offset parameters between the two cameras are calculated, the right camera position is adjusted, and the pose correction between the two cameras is achieved. Finally, the pose parameters between the two cameras are calibrated. Actual application results show that the proposed calibration and correction method for dual-camera module has high precision, shortens the processing time, improves the processing efficiency , and can satisfy the requirements of packaging and production technology of dualcamera modules.
       
      An anisotropic bandwidth-adaptive tracking
      algorithm for surface moving targets
      JIN Qiaoyuan,WAN Lei,SHENG Mingwei,TANG Songqi
      2019, 41(02): 308-314. doi:
      Abstract ( 162 )   PDF (1147KB) ( 252 )     
      The traditional mean-shift (MS) tracking algorithm lacks an effective bandwidth update strategy for surface moving targets in unmanned boats with
       anisotropic changes in contour. To address the challenge, we propose an anisotropic bandwidth-adaptive MS tracking algorithm. Firstly, the Riemann integral is used to approximate the  normalized constant Ch of the probability density of the feature sub model into the integral form.
      Thus, the relationship between Ch corresponding to different scale parameters h is obtained. Secondly, the gradient ascent method is applied to make the similarity function between target model and target candidate model reach the local maximum, thereby the bandwidth and position of the target in the next frame can be estimated. Finally, two regularization parameters are introduced to correct the scale parameters to prevent the bandwidth updating from being too small or too large. Experimentsal results show that compared with the traditional MS and isotropic bandwidth-adaptive MS, the accuracy of the center location of our algorithm is increased by about 77.2% and 31.1%,   and its running speed is up to 20.7 fps, which proves its ability of anisotropic bandwidthadaptive adjustment, as well as its robustness and real-time.
       
      A clause-based dynamical necessary
      literal checking SAT solver
      CHANG Wenjing1,2,XU Yang2
      2019, 41(02): 315-320. doi:
      Abstract ( 113 )   PDF (1017KB) ( 184 )     
      Necessary literal checking is an important preprocessing technique. by learning clauses, this paper proposes a clausebased dynamical necessary literal checking strategy (CNL) used in the solving process, and designs a lowcost data structure.  We implement two solvers, Glucose_PRE and Glucose_CNL. The former adopts the necessary literal checking as the preprocessing technique at the beginning of the solving process, and the latter implements the proposed clausebased dynamical necessary literal checking strategy. Experimental results show that the Glucose_CNL solves more instances with less time than the Glucose_PRE and Glucose 3.0 when solving the applicationtype instances in 2015 and 2016 SAT competitions, demonstrating the significance of the proposed strategy and data structure.

       
      A slotting optimization model and algorithm
      for general stereoscopic warehouses
      LI Yongwei1,2,LIU Shuan3,GUO Jinqin1
      2019, 41(02): 321-327. doi:
      Abstract ( 159 )   PDF (640KB) ( 376 )     

      It is well known that inventory cost takes up a large proportion of the total cost of logistics and warehousing. Enterprises have been trying to improve and optimize the storage process in the warehouse in order to reduce inventory cost. Based on the study on general stereoscopic warehouses, considering the constraints of forklift load, cargo capacity, and storage strategy, we establish a slotting optimization model whose goal is to achieve a minimum distance of staff walking during storage operation in warehouses. According to the characteristics of the problem and the model, we transform the slotting optimization problem to a twolayered optimization issue: slot selection optimization and slot order optimization. An improved genetic algorithm and
      a heuristic algorithm are combined to  solve the model. Finally, simulation results verify the rationality and feasibility of the model and algorithm, which can be used to solve the problem of slotting optimization of most general warehouses.

      Application of ensemble learning algorithm in
      Chinese medicine syndrome classification prediction
      ZHANG Shoubin,ZHU Xijun
      2019, 41(02): 328-334. doi:
      Abstract ( 123 )   PDF (716KB) ( 209 )     
      In order to improve the intelligence and dialectical accuracy of the diagnosis of Chinese medicine, we propose an ensemble learning algorithm based on multimodal perturbation strategy, called MPEL algorithm. Firstly, different sample subspaces of the sample domain are generated by multiple sampling. Secondly, different attribute subspaces are separated by  an improved hierarchical clustering feature selection algorithm in the attribute space, and base classifiers with great diversity are trained. Thirdly, the optimal combination of base classifiers is selected through the greedy strategy so that the overall performance of the algorithm is improved. The medical records of Chinese medicine asthma symptomssyndromes are selected to verify the performance of the proposed algorithm. Experimental results show that the proposed algorithm has faster training speed and higher recognition accuracy in the prediction of asthma symptomssyndromes than other current ensemble learning algorithms, and the highest recognition accuracy of the MPEL can reach up to 98.16%.