Bimonthly    Since 1986
ISSN 1000-9000(Print)
CN 11-2296/TP
Indexed in:
Publication Details
Edited by: Editorial Board of Journal Of Computer Science and Technology
P.O. Box 2704, Beijing 100190, P.R. China
Sponsored by: Institute of Computing Technology, CAS & China Computer Federation
Undertaken by: Institute of Computing Technology, CAS
Distributed by:
China: All Local Post Offices
Other Countries: Springer
  • Table of Content
      15 January 2003, Volume 18 Issue 1 Previous Issue    Next Issue
    For Selected: View Abstracts Toggle Thumbnails
    A Simple Fault-Tolerant Adaptive and Minimal Routing Approach in 3-D Meshes
    WU Jie (吴杰)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(367KB) ( 1805 )   Chinese Summary
    In this paper we propose a suffient condition for minimal routing in 3-dimensional (3-D) meshes with faulty nodes. It is based on an early work of the author on minimal routing in 2-dimensional (2-D) meshes. Unlike many traditional models that assume all the nodes know global fault distribution or just adjacent fault information, our approach is based on the concept of limited global fault information. First, we propose a fault model called faulty cube in which all faulty nodes in the system are contained in a set of faulty cubes. Fault information is then distributed to limited number of nodes while it is still suffient to support minimal routing. The limited fault information collected at each node is represented by a vector called extended safety level. The extended safety level associated with a node can be used to determine the existence of a minimal path from this node to a given destination. Specifically, we study the existence of minimal paths at a given source node, limited distribution of fault information, minimal routing, and deadlock-free and livelock-free routing. Our results show that any minimal routing that is partially adaptive can be applied in our model as long as the destination node meets a certain condition. We also propose a dynamic planar-adaptive routing scheme that offers better fault tolerance and adaptivity than the planar-adaptive routing scheme in 3-D meshes. Our approach is the first attempt to address adaptive and minimal routing in 3-D meshes with faulty nodes using limited fault information.
    Related Articles | Metrics
    Secure Web Transaction with Anonymous Mobile Agent over Internet
    WANG ChangJie (王常杰), ZHANG FangGuo (张方国) and WANG YuMin (王育民)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(332KB) ( 1346 )   Chinese Summary
    A major problem of mobile agents is their apparent inability to authenticate transactions in hostile environments. In this paper, a new secure anonymous mobile agent scheme is proposed for the prevention of agent tempering without compromising the mobility or autonomy of the agent. In the scheme, a mobile agent can produce valid signature on website's bid (it means to transact a contact with the web site) on behalf of its customer, without revealing the customer's real private key. In addition, the anonymity of the customer is also achieved when its agent transacts with the websites. Furthermore, the customer who issues a malicious agent or denies the transaction can be identified and detected by Agent Management Center (AMC). Therefore, the scheme is practical in the future electronic commerce over Internet.
    Related Articles | Metrics
    Uni ed Parallel Lattice Structures for Block Time-Recursive Real-Valued Discrete Gabor Transforms
    TAO Liang(陶亮) and ZHUANG ZhenQuan(庄镇泉)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(321KB) ( 1376 )   Chinese Summary
    In this paper, the 1-D real-valued discrete Gabor transform (RDGT) proposed in the previous work and its relationship with the complex-valued discrete Gabor transform (CDGT) are briefly reviewed. Block time-recursive RDGT algorithms for the efficient and fast computation of the 1-D RDGT coefficiients and for the fast reconstruction of the original signal from the coefficients are developed in both critical sampling and oversampling cases. Unified parallel lattice structures for the implementation of the algorithms are studied. And the computational complexity analysis and comparison show that the proposed algorithms provide a more efficient and faster approach to the computation of the discrete Gabor transforms.
    Related Articles | Metrics
    Approach to the Correlation Discovery of Chinese Linguistic Parameters Based on Bayesian Method
    WANG Wei (王玮) and CAI LianHong (蔡莲红)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(275KB) ( 1477 )   Chinese Summary
    Bayesian approach is an important method in statistics. The Bayesian belief net- work is a powerful knowledge representation and reasoning tool under the conditions of uncertainty. It is a graphics model that encodes probabilistic relationships among variables of interest. In this paper, an approach to Bayesian network construction is given for discovering the Chinese linguistic parameter relationship in the corpus.
    Related Articles | Metrics
    A Programmable Approach to Maintenance of a Finite Knowledge Base
    LUAN ShangMin (栾尚敏), DAI GuoZhong (戴国忠) and LI Wei (李未)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(295KB) ( 1179 )   Chinese Summary
    In this paper, we present a programmable method of revising a nite clause set. We rst present a procedure whose formal parameters are a consistent clause set T and a clause A and whose output is a set of minimal subsets of T which are inconsistent with A. The maximal consistent subsets can be generated from all minimal inconsistent subsets. We develop a prototype system based on the above procedure, and discuss the implementation of knowledge base maintenance. At last, we compare the approach presented in this paper with other related approaches. The main characteristic of the approach is that it can be implemented by a computer program.
    Related Articles | Metrics
    Further Improvement on Dynamic Programming for Optimal Bit Allocation
    CHEN YiSong (陈毅松), WANG GuoPing (汪国平) and DONG ShiHai (董士海)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(243KB) ( 1441 )   Chinese Summary
    Dynamic programming algorithms based on Lagrange multiplier method is often used for obtaining an optimal bit allocation strategy to minimize the total distortion given a constrained rate budget in both source and channel coding applications. Due to possible large quantizer set and improper initialization, the algorithm often su ers from heavy computational complexity. There have been many solutions in recent years to the above question. In this paper, a simple but efficiient algorithm is presented to further speed up the convergence of the algorithm. This algorithm can be easily realized and get the final solution much faster. The experimental result shows that our new algorithm can figure out the optimal solution with a speed 5-7 times faster than the original algorithm.
    Related Articles | Metrics
    CALA: A Web Analysis Algorithm Combined with Content Correlation Analysis Method
    ZHANG Ling (张岭), MA FanYuan (马范援), YE YunMing (叶允明) and CHEN JianGuo (陈建国)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(262KB) ( 2078 )   Chinese Summary
    Web hyperlink structure analysis algorithm plays a signi cant role in improving the precision of Web information retrieval. Current link algorithms employ iteration function to compute the Web resource weight. The major drawback of this approach is that every Web document has a xed rank which is independent of Web queries. This paper proposes an improved algorithm that ranks the quality and the relevance of a page according to users' query dynamically. The experiments show that the current link analysis algorithm is improved.
    Related Articles | Metrics
    Fixed-Parameter Tractability of Disjunction-Free Default Reasoning
    ZHAO XiShun (赵希顺) and DING DeCheng (丁德成)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(290KB) ( 1343 )   Chinese Summary
    In this paper, the parameter which is the source of the complexity of disjunction- free default reasoning is determined. It is shown that when the value of this parameter is xed, the disjunction-free default reasoning can be solved in time bounded by a polynomial whose degree does not depend on the parameter. Consequently, disjunction-free default reasoning is xed parameter tractable.
    Related Articles | Metrics
    A New Approximation Algorithm for Sorting of Signed Permutations
    HE Yong (何勇) and CHEN Ting (陈汀)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(277KB) ( 1480 )   Chinese Summary
    Sequence comparison leads to a combinatorial optimization problem of sorting permutations by reversals and transpositions. Namely, given any two permutations, nd the short-est distance between them. This problem is related with genome rearrangement. The sorting of signed permutations is studied. Because in genome rearrangement, genes are oriented in DNA se-quences. The transpositions which have been studied in the literature can be viewed as operations working on two consecutive segments of the genome. In this paper, a new kind of transposition which can work on two arbitrary segments of the genome is proposed, and the sorting of signed permutations by reversals and this new kind of transpositions are studied. After establishing a lower bound on the number of operations needed, a 2-approximation algorithm is presented for this problem and an example is given to show that the performance ratio of the algorithm cannot be improved.
    Related Articles | Metrics
    Incorporating Linguistic Structure into Maximum Entropy Language Models
    FANG GaoLin (方高林), GAO Wen (高 文) and WANG ZhaoQi (王兆其)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(304KB) ( 1436 )   Chinese Summary
    In statistical language models, how to integrate diverse linguistic knowledge in a general framework for long-distance dependencies is a challenging issue. In this paper, an improved language model incorporating linguistic structure into maximum entropy framework is presented. The proposed model combines trigram with the structure knowledge of base phrase in which trigram is used to capture the local relation between words, while the structure knowledge of base phrase is considered to represent the long-distance relations between syntactical structures. The knowledge of syntax, semantics and vocabulary is integrated into the maximum entropy framework. Experimental results show that the proposed model improves by 24% for language model perplexity and increases about 3% for sign language recognition rate compared with the trigram model.
    Related Articles | Metrics
    A Fast Block-Matching Algorithm Using Smooth Motion Vector Field Adaptive Search Technique
    LI Bo(李波),LI Wei(李炜) and TU YaMing(涂亚明)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(377KB) ( 2590 )   Chinese Summary
    In many video standards based on inter-frame compression such as H.26x and MPEG, block-matching algorithm has been widely adopted as the method for motion estimation because of its simplicity and e ectiveness. Nevertheless, since motion estimation is very complex in computing. Fast algorithm for motion estimation has always been an important and attractive topic in video compression. From the viewpoint of making motion vector field smoother, this paper proposes a new algorithm SMVFAST. On the basis of motion correlation, it predicts the starting point by neighboring motion vectors according to their SADs. Adaptive search modes are used in its search process through simply classifying motion activity. After discovering the ubiquitous ratio between the SADs of the collocated blocks in the consecutive frames, the paper proposes an effective half-stop criterion that can quickly stop the search process with good enough results. Experiments show that SMVFAST obtains almost the same results as the full search at very low computation cost, and outperforms MVFAST and PMVFAST in speed and quality, which are adopted by MPEG-4.
    Related Articles | Metrics
    Image-Based Synthesis of Chinese Landscape Painting
    YU JinHui(于金辉),LUO GuoMing(罗国明) and PENG QunSheng(彭群生)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(343KB) ( 3396 )   Chinese Summary
    This paper describes a new framework for synthesizing Chinese landscape painting using an image-based approach. The framework involves two stages: a preprocessing phase, in which a few brush stroke texture primitivities (BSTP) are collected from samples of hand-made Chinese paintings, and the control picture is constructed to provide color IDs of mountains, and the on-line phases, in which the fog image is synthesized and mountains are \drawn" by mapping multiple layers of BSTP guided by the control picture. When more complex shading is needed, the shading picture is constructed and used during the BSTP mapping phase. Finally, the synthesized Chinese landscape paintings of a variety of styles are given and they look more close to the hand-made work than those produced with previous modeling methods.
    Related Articles | Metrics
    Automatic Target Detection by Optimal Morphological Filters
    YU Nong(余农),WU Hao(吴昊),WU Chang Yong(吴常泳) and LI YuShu(李予蜀)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(468KB) ( 1906 )   Chinese Summary
    It is widely accepted that the design of morphological filters, which are optimal in some sense, is a difficult task. In this paper a novel method for optimal learning of morphological filtering parameters (Genetic training algorithm for morphological lters, GTAMF) is presented. GTAMF adopts new crossover and mutation operators called the curved cylinder crossover and master-slave mutation to achieve optimal filtering parameters in a global searching. Experimental results show that this method is practical, easy to extend, and markedly improves the performances of morphological filters. The operation of a morphological filter can be divided into two basic problems including morphological operation and structuring element (SE) selection. The rules for morphological operations are predefined so that the filter's properties depend merely on the selection of SE. By means of adaptive optimization training, structuring elements possess the shape and structural characteristics of image targets, and give specific information to SE. Morphological lters formed in this way become certainly intelligent and can provide good filtering results and robust adaptability to image targets with clutter background.
    Related Articles | Metrics
    3DIVE: An Immersive Environment for Interactive Volume Data Exploration
    Michael Boyles and FANG ShiaoFen(方晓芬)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(256KB) ( 1573 )   Chinese Summary
    This paper describes an immersive system, called 3DIVE, for interactive volume data visualization and exploration inside the CAVE virtual environment. Combining interactive volume rendering and virtual reality provides a natural immersive environment for volumetric data visualization. More advanced data exploration operations, such as object level data manipulation, simulation and analysis, are supported in 3DIVE by several new techniques. In particular, volume primitives and texture regions are used for the rendering, manipulation, and collision detection of volumetric objects; and the region-based rendering pipeline is integrated with 3D image lters to provide an image-based mechanism for interactive transfer function design. The system has been recently released as public domain software for CAVE/ImmersaDesk users, and is currently being actively used by various scienti c and biomedical visualization projects.
    Related Articles | Metrics
    Accelerated Backward Warping
    ZHANG YanCi(张严辞), LIU XueHui(刘学慧) and WU EnHua(吴恩华)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(374KB) ( 1671 )   Chinese Summary
    In this paper a plane-based backward warping algorithm is proposed to generate novel views from multiple reference images. First, depth information is employed to reconstruct space planes from individual reference images and calculate the potential occluding relationship between these planes. Then the planes which represent each identical space plane from di erent reference images are compared with each other to decide the one with the best sample rate to be preserved and used in the later warping period while the other samples are abandoned. While the image of a novel view is produced, traditional methods in computer graphics, such as visibility test and clipping, are used to process the planes reconstructed. Then the planes processed are projected onto the desired image from the knowledge on which plane the desired image pixels are warped from can be acquired. Finally, pixels' depth of the desired image is calculated and then a backward warping is performed from these pixels to the reference images to obtain their colors. The storage requirement in the algorithm is small and increases slowly with the number of reference images increases. By combining the strategy of only preserving the best sample parts and the backward warping algorithm, the sample problem could be well tackled.
    Related Articles | Metrics
    Fuzzy Functional Dependencies and Bayesian Networks
    LIU WeiYi(刘惟一) and SONG Ning(宋宁)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(385KB) ( 1786 )   Chinese Summary
    Bayesian networks have become a popular technique for representing and reason- ing with probabilistic information. The fuzzy functional dependency is an important kind of data dependencies in relational databases with fuzzy values. The purpose of this paper is to set up a connection between these data dependencies and Bayesian networks. The connection is done through a set of methods that enable people to obtain the most information of independent conditions from fuzzy functional dependencies.
    Related Articles | Metrics
    Clustering in Very Large Databases Based on Distance and Density
    QIAN WeiNing (钱卫宁), GONG XueQing(宫学庆) and ZHOU AoYing (周傲英)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(328KB) ( 3006 )   Chinese Summary
    Clustering in very large databases or data warehouses, with many applications in areas such as spatial computation, web information collection, pattern recognition and economic analysis, is a huge task that challenges data mining researches. Current clustering methods always have the problems: 1) scanning the whole database leads to high I/O cost and expensive mainte-nance (e.g., R*-tree); 2) pre-specifying the uncertain parameter k, with which clustering can only be re ned by trial and test many times; 3) lacking high efficiency in treating arbitrary shape under very large data set environment. In this paper, we first present a new hybrid-clustering algorithm to solve these problems. This new algorithm, which combines both distance and density strategies, can handle any arbitrary shape clusters effectively. It makes full use of statistics information in mining to reduce the time complexity greatly while keeping good clustering quality. Furthermore, this algorithm can easily eliminate noises and identify outliers. An experimental evaluation is performed on a spatial database with this method and other popular clustering algorithms (CURE and DBSCAN). The results show that our algorithm outperforms them in terms of efficiency and cost, and even gets much more speedup as the data size scales up much larger.
    Related Articles | Metrics
    A Hybrid Distributed Optimistic Concurrency Control Method for High-Performance Real-Time Transaction Processing
    QIN Biao (覃飙) and LIU YunSheng (刘云生)
    Journal of Computer Science and Technology, 2003, 18 (1): 0-0. 
    Abstract   PDF(295KB) ( 1485 )   Chinese Summary
    The conventional lock scheme tends to suffer from a cascade of blockings, while the optimistic concurrency control (OCC) scheme may su er from wasting resources. To over-come these problems, some researchers have proposed a combination of OCC and lock in trans-action processing. Using this method, Thomasian proposed the hybrid method for conventional distributed transaction processing, and Lam proposed the DOCC-DA protocol for distributed real-time database system based on forward validation. This paper proposes a new protocol, called Hybrid Distributed Optimistic Concurrency Control Embedded in two-Phase Commit, which is based on back validation. The new protocol makes use of access invariance and runtime information which can guarantee a rerun transaction to meet its deadline and abort the fruitless run transactions as early as possible. A series of simulation experiments have been done to investigate the performance of the new protocol. The results show that its performance is consistently better than that of other protocols.
    Related Articles | Metrics
  Journal Online
Just Accepted
Top Cited Papers
Top 30 Most Read
Paper Lists of Areas
Special Issues
   ScholarOne Manuscripts
   Log In

User ID:


  Forgot your password?

Enter your e-mail address to receive your account information.

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved