Volume 15,Issue 2,2004 Table of Contents

  • Display Type:
  • Text List
  • Abstract List
  • 1  Parallel Algorithms for Approximate String Matching on PRAM and LARPBS
    ZHONG Cheng CHEN Guo-Liang
    2004, 15(2):159-169.
    [Abstract](4680) [HTML](0) [PDF 938.28 K](5659)
    Abstract:
    Approximate string matching technique has been widely applied to many fields such as network information retrieval, digital library, pattern recognition, text mining, IP routing searching, network intrusion detection, bioinformatics, and computing in musicology. The two concise parallel dynamic programming algorithms for approximate string matching with k-differences on CREW-PRAM (parallel random access machine with concurrent read and exclusive write) are presented by parallel computing the edition distance matrix D in the wave-front approach and by parallel computing the edition distance matrix D along the diagonal and horizontal directions, respectively. The first algorithm requires O(n) time and obtains a linear speedup by (m+1) processors. The second algorithm needs O(n/a+m) time in use of a(m+1) processors, where 1
    2  Scalable Parallel Performance Optimization of the Gene Sequence Analyzing Software Hmmpfam
    CHEN Jun ZHAO Wen-Hui MO Ze-Yao LI Xiao-Mei
    2004, 15(2):170-178.
    [Abstract](4189) [HTML](0) [PDF 795.19 K](6184)
    Abstract:
    A scalable parallel MPI (message passing interface) version of the popular protein structure prediction tool Hmmpfam is presented, which is one of the kernel programs in the HMMER package. The master process in the previous PVM (parallel virtual machine) version is a communication bottleneck, and the speedup will decrease rapidly when running on large scale parallel systems. A novel three-level communication structure is presented, by which the parallel processing at sequence level and HMM model level is obtained in both. Meanwhile, the load-balance strategies to sequence level and HMM model level distribution are provided separately. Since disk access for getting HMM model costs very much, a so-called once load strategy is provided to reduce the cost. By all these optimization methods, 95% in parallel efficiency is achieved when running on a parallel computer containing more than 700 processors.
    3  Two Effective Functions on Hashing URL
    LI Xiao-Ming FENG Wang-Sen
    2004, 15(2):179-184.
    [Abstract](4741) [HTML](0) [PDF 1.49 M](5887)
    Abstract:
    Hashing large collection of URLs is an inevitable problem in many Web research activities. Through a large scale experiment, three hash functions are compared in this paper. Two metrics were developed for the comparison, which are related to web structure analysis and Web crawling, respectively. The finding is that the well-known function for hashing sequence of symbols, ELFhash, is not very good in this regard, and the other two functions are better and thus recommended.
    4  An Ant Colony Optimization Algorithm Based on Mutation and Dynamic Pheromone Updating
    ZHU Qing-Bao YANG Zhi-Jun
    2004, 15(2):185-192.
    [Abstract](4974) [HTML](0) [PDF 729.80 K](6832)
    Abstract:
    Despite the numerous applications of ACO (ant colony optimization) algorithm in optimization computation, it remains a computational bottleneck that the ACO algorithm costs too much time in order to find an optimal solution for large-scaled optimization problems. Therefore, a quickly convergent version of the ACO algorithm is presented. A novel strategy based on the dynamic pheromone updating is adopted to ensure that every ant contributes to the search during each search step. Meanwhile, a unique mutation scheme is employed to optimize the search results of each step. The computer experiments demonstrate that the proposed algorithm makes the speed of convergence hundreds of times faster than the latest improved ACO algorithm.
    5  A Restricted Double-Level Bayesian Classification Model
    SHI Hong-Bo WANG Zhi-Hai HUANG Hou-Kuan LI Xiao-Jian
    2004, 15(2):193-199.
    [Abstract](5062) [HTML](0) [PDF 737.68 K](9081)
    Abstract:
    Naive Bayes classifier is a simple and effective classification method, but its attribute independence assumption makes it unable to express the dependence among attributes, and affects its classification performance. On the basis of analyzing the classification principle of Bayesian classification model and a variant of Bayes theorem, a new classification model based on Bayes theorem, DLBAN (double-level Bayesian network augmented naive Bayes), which adds the dependence among attributes by selecting the key attributes, is proposed. DLBAN classifier is compared with Naive Bayes classifier and TAN (tree augmented naive Bayes) classifier by an experiment. Experimental results show this model has higher classification accuracy in most data sets.
    6  Successive Overrelaxation for Support Vector Regression
    QUAN Yong YANG Jie YAO Li-Xiu YE Chen-Zhou
    2004, 15(2):200-206.
    [Abstract](3846) [HTML](0) [PDF 613.32 K](5413)
    Abstract:
    Training a SVR(support vector regression)requires the solution of a very large QP(quadratic programming)optimization problem.Despite the fact that this type of problem is well understood,the existing training algorithms are very complex and slow.In order to solve these problems,this paper firstly introduces a new way to make SVR have the similar mathematic form as that of a support vector machine.Then a versatile iterative method,successive overrelaxation,is proposed.Experimental results show that this new method converges considerably faster than other methods that require the presence of a substantial amount of data in memory.The results give guidelines for the application of this method to large domains.
    7  An Aliasing Degree Pre-Estimated MAP Algorithm of Super-Resolution Processing
    MENG Qing-Wu
    2004, 15(2):207-214.
    [Abstract](4343) [HTML](0) [PDF 1.33 M](6108)
    Abstract:
    In this paper, a sort of aliasing degree pre-estimated MAP (maximum a posteriori) algorithm, PEMAP, is proposed. It is used in super-resolution processing of satellite images on the ground. The aliasing degree of satellite images is firstly determined in frequency domain by spectrum analysis, and then used in a joint estimation of the registration parameters and high-resolution image in space domain as a priori information. This algorithm overcomes the blindness and instability of the MAP algorithm and improve its flexibility. Good results have been shown in a practical satellite image processing.
    8  Rough Entropy Based on Generalized Rough Sets Covering Reduction
    HUANG Bing HE Xin ZHOU Xian-Zhong
    2004, 15(2):215-220.
    [Abstract](4975) [HTML](0) [PDF 518.74 K](4822)
    Abstract:
    In generalized rough set covering reduction theory,it is necessary to find a new measure to knowledge and rough set because the upper and lower approximations of rough sets are determined by their covering reduction.In this paper,information entropy is introduced to discuss the rough entropy of knowledge and the roughness of rough set,based on generalized rough set covering reduction.A new kind of measurement about the roughness of knowledge and rough set is presented.The conclusion that the rough entropy of knowledge and rough set decreases monotonously as the generalized rough set covering reduction becomes finer is obtained.This paper presents some useful exploration about the incomplete information system from information views.
    9  Low Bit-Rate Video Coding Based on Undecimated Wavelet Dictionary
    LIAO Bin XU Gang WANG Yu-Guo
    2004, 15(2):221-228.
    [Abstract](4165) [HTML](0) [PDF 807.48 K](5784)
    Abstract:
    Currently, the core techniques of most video coders are based on blocked DCT (discreted cosine transform) transform. At very low bit-rates, video coders of this class always produce visual-sensible block artifacts. Recently, the video coders based on matching pursuit have been proved to have super coding efficiency, compared with the H.263 standard. However, the computation complexity is much too higher, because of laboriously searching optimal atoms in a redundant dictionary. A video coding algorithm based on undecimated wavelet dictionary is proposed, which incorporates multiresolution characteristics of the wavelet transform and assorts to filter the scheme between dictionary functions, to reduce the computation complexity of the original algorithm greatly. Considering the continuity of motion information in the neighboring frames, an entropy coding method of atom position based on a hygrid structure is given. The experimental results show that this algorithm keeps the original coding results and has the desirable application value.
    10  Reliable Multicast for Real-Time Continuous-Media Streams over Switch Ethernet
    WANG Jun WU Zhi-Mei
    2004, 15(2):229-237.
    [Abstract](3851) [HTML](0) [PDF 738.08 K](5387)
    Abstract:
    A reliable multicast protocol for real-time continuous-media streams on switch Ethernet after research of the LANs special features for reliable multicast is proposed. The recovery of this protocol begins with the receivers detection of packet loss by packets number, and the second step of it is the NAK (negative acknowledgment) suppression procedure, and then the sender will retransmit the lost packet by the received NAK, and finally the receiver will discard or accept the recovered packet based on the limit of the real-time playback. The experimental results and the analysis of performance demonstrate the effectiveness and reliability of the approach.
    11  A Visible Digital Watermark Based on Integer Wavelet Transform with Parameters
    LUO Yong CHENG Li-Zhi XU Zhi-Hong WU Yi
    2004, 15(2):238-249.
    [Abstract](4407) [HTML](0) [PDF 1.54 M](5853)
    Abstract:
    An Integer Wavelet Transform with parameters is firstly constructed and the transmutative Rijndael code is used to construct a Hash function, and then a visible digital watermark algorithm based on the Integer Wavelet Translation with parameters, Discrete Cosine Transform (DCT) and the Transmutative Rijndael encryption algorithm are presented. The change of parameters of the integer wavelet and the Hash function guarantees the security of the watermark which satisfies the public-key system. By theoretical analysis and numerous experiments, it is shown that a wide prospect for this algorithm can guarantee the quality of the image and the safety of the watermark.
    12  Notes on Packet Marking for IP Traceback
    LI De-Quan SU Pu-Rui FENG Deng-Guo
    2004, 15(2):250-258.
    [Abstract](4787) [HTML](0) [PDF 650.79 K](5276)
    Abstract:
    Distributed Denial of Service(DDoS)attack is among the hardest network security problems to address.Recently,several countermeasures are proposed,among which,PPM(probabilistic packet marking)pioneered by Savage et al.is promising.In this paper,a brief review of countermeasures to DDoS is given and then an analysis on some of the packet marking schemes is provided.Some modifications are further provided.One modification to the basic PPM scheme can reduce its computation remarkably.
    13  Location Pre-Query Scheme to Internet Mobility Support
    HE Xiao-Ying LIU Qiong LEI Zhen-Ming
    2004, 15(2):259-267.
    [Abstract](3760) [HTML](0) [PDF 687.63 K](4730)
    Abstract:
    In this paper, an approach for IP mobility support with Location Pre-Query (MIP_Q) is put forward for solving the traffic bottleneck and single point error at home network, and also for improving the efficiency and reliability of communication. MIP_Q eliminates the agent of HA (home Agent) by extending the functions of DNS (domain name system) to manage and track the location database of mobile nodes. MIP_Q uses parallel handoff procedures and avoids the triangle routing and tunneling. The cost and handoff delay of MIP_Q by an effective algorithm with MIP and MIP_LR are analyzed and compared. The realization of MIP_Q is also discussed by referring to the widely used wide area cellular mobile networks. The analysis results show that MIP_Q precedes MIP and MIP_Q on handoff efficiency and the number of additional entities. MIP_Q can greatly reduce the mean cost of mobile communication and lead to a reasonable handoff delay. MIP_Q also has feasibility on implementation. Finally, the MIP_Qs simulation and implementation schemes are given out.
    14  Design of Distributed Storage System on Peer-to-Peer Structure
    XU Fei YANG Guang-Wen JU Da-Peng
    2004, 15(2):268-277.
    [Abstract](4863) [HTML](0) [PDF 838.77 K](7040)
    Abstract:
    Distributed storage system is an important research area in peer-to-peer technology. Current research on p2p structure has made a highly controlled routing scheme with limited hops of message transfer. People now turn to pursue lower network latency that is more factual. As a storage application, distributed system must have fault tolerance-recovery capability. Based on the analysis of current research, a computing modal more approximate to real time network is constructed. A computed shortest path of nodes is used to dynamically estimate the actual latency. Adjacent nodes are gathered under an evaluating algorithm to make node latency in the same group minimal. Thus a more efficient routing can be based on node grouping. For storage persistency, an interaction management and corresponded data transfer algorithm is presented. Its locality greatly enhances the system抯 response to all kinds of events, and ensures the system抯 availability. The simulation results are provided to show that the introduction of grouping truly helps to get an effective judgment on routing choice, and can be extend to a larger scale.
    15  Payload Analysis of Rerouting-Based Anonymous Communication Systems
    SUI Hong-Fei CHEN Song-Qiao CHEN Jian-Er WANG Jian-Xin WANG Wei-Ping
    2004, 15(2):278-285.
    [Abstract](4308) [HTML](0) [PDF 766.96 K](5527)
    Abstract:
    Rerouting mechanism is adopted by rerouting-based anonymous communication systems such as Mixes, Onion Routing, and Crowds, to store and forward data in application layer. With this, users can communicate in an indirect way. Thus, identity information such as IP addresses can be effectively hidden against eavesdropper. This mechanism, however, can result in extra overhead in performance such as communication delay and participant payload, which may affect the applications of anonymous communication systems. In this paper, the participant payload induced by the rerouting mechanism is studied quantitatively. By investigating the establishment of rerouting paths in detail, a probability formula for calculating the participant payload is derived, which proves that the participant payload is determined by the number of participants, the number of rerouting paths, and the probability distribution of length of the rerouting paths. By applying this formula to a practical anonymous communication system, Crowds, a precise expected participant payload 1/(1-Pf)+1 can be derived, which significantly improves Reiter and Rubin's original analysis O((n+1)/((1(Pf)2n), and demonstrates that the participant payload in Crowds remains constant and is independent of the variation of the number of participants in Crowds. Simulation results are presented to testify the theoretical analysis. The conclusions can provide a theoretical support for the design and implementation of anonymous communication systems.
    16  A Multicast Routing Protocol with Multiple QoS Constraints
    LI La-Yuan LI Chun-Lin
    2004, 15(2):286-291.
    [Abstract](4513) [HTML](0) [PDF 1015.43 K](5454)
    Abstract:
    Multicast routing is the process for establishing a tree which is rooted from the source node and contains all the multicast destinations. A multicast routing tree with multiple QoS constraints is the one in which the delay, delay jitter, packet loss and bandwidth should satisfy the pre-specified bounds. This paper discusses the multicast routing problem with multiple QoS constraints, deals with the delay, delay jitter, bandwidth and packet loss metrics, and describes a network model for investigating the routing problem. It presents a multicast routing protocol with multiple QoS constraints (MRPMQ). The MRPMQ attempts to significantly reduce the overhead for constructing a multicast tree with multiple QoS constraints. In the MPRMQ, a multicast group member can join or leave a multicast session dynamically without the disruption of the multicast tree. In this paper, the proof of correctness and the complexity analysis of the MRPMQ are also given. Simulation results show that the MRPMQ is an effective approach to multicast routing decision with multiple QoS constraints.
    17  Construction of Three-Dimensional Model of Platonic Solid Coloring Mode Based on Group Theory
    ZHANG Da-Kun WANG Guang-Xing
    2004, 15(2):292-299.
    [Abstract](3833) [HTML](0) [PDF 1.03 M](5112)
    Abstract:
    An idea of implementing three-dimensional model for coloring mode of Platonic solids in accordance with space rotational group of Platonic solids is raised, and the problem in constructing three-dimensional model directly related to symmetry is thus resolved. A new classification method of group elements in a rotational group of Platonic solids is given. Three new concepts such as abstracted symmetry of group elements, local number of colors and saturated number of colors are put forward. Constructing coloring mode for the abstracted object and then constructing a method that the abstracted coloring mode is mapped into a three-dimensional space are raised. An algorithm for implementing this method is developed, and the algorithm and the three-dimensional model are visualized by means of Visual C++6.0 and Direct 3D. The results validate both the method put forward in this paper and the correctness of the algorithm.
    18  Included Angle Chain:A Method for Curve Representation
    ZHAO Yu CHEN Yan-Qiu
    2004, 15(2):300-307.
    [Abstract](6078) [HTML](0) [PDF 976.51 K](9166)
    Abstract:
    A novel approach, Included Angle Chain, is presented for curve representation and encoding. In this framework, a curve is modeled by a number of linked equi-length line segments and a sequence of codes using the included angles between a pair of neighboring line segments is used for representing the curve. The number of the segments is determined by an area criterion, and the curves to be matched are represented by an included angle chain of the same length. The representation is invariant to rotation, scaling, and translation. A practical use of the proposed approach is to register a SAR (synthetic aperture Radar) image of certain region with maps.
    19  Dynamic Facial Texture Generation Based on Shape-Appearance Dependence Mapping Strategy
    DU Yang-Zhou LIN Xue-Yin
    2004, 15(2):308-316.
    [Abstract](4294) [HTML](0) [PDF 827.90 K](4889)
    Abstract:
    The subtle details on an expressional face,such as creases and furrows,are very important visual cues,but they are difficult to model and synthesize as they vary dynamically from one frame to another while people speak and make expression.A novel strategy,which is different from the traditional texture mapping methods,is proposed for generating such a kind of dynamic facial textures according to the motion of facial feature points.Based on the observation that shape and appearance on face images are highly correlated,a mapping is designed to transfer one image to the other.The mapping is called SADM(shape-appearance dependence mapping).The experimental results show that the synthesized faces with SADM are very close to the real ones.The proposed SADM strategy can be integrated into a wire-frame based head model to generate the realistic animation effects,or applied to a model-based video coding to produce more efficient bit-rates.

    Current Issue


    Volume , No.

    Table of Contents

    Archive

    Volume

    Issue

    联系方式
    • 《Journal of Software 》
    • 主办单位:Institute of Software, CAS, China
    • 邮编:100190
    • 电话:010-62562563
    • 电子邮箱:jos@iscas.ac.cn
    • 网址:https://www.jos.org.cn
    • 刊号:ISSN 1000-9825
    •           CN 11-2560/TP
    • 国内定价:70元
    You are the firstVisitors
    Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
    Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
    Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
    Technical Support:Beijing Qinyun Technology Development Co., Ltd.

    Beijing Public Network Security No. 11040202500063