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 July 2007, Volume 22 Issue 4 Previous Issue    Next Issue
    For Selected: View Abstracts Toggle Thumbnails
    Simultaneous Minimization of Capacity and Conflict Misses
    Zhiyuan Li
    Journal of Computer Science and Technology, 2007, 22 (4): 497-504 . 
    Abstract   PDF(748KB) ( 11077 )   Chinese Summary
    Loop tiling (or loop blocking) is a well-known loop transformation to improve temporal locality in nested loops which perform matrix computations. When targeting caches that have low associativities, one of the key challenges for loop tiling is to simultaneously minimize capacity misses and conflict misses. This paper analyzes the effect of the tile size and the array-dimension size on capacity misses and conflict misses. The analysis supports the approach of combining tile-size selection (to minimize capacity misses) with array padding (to minimize conflict misses).
    References | Related Articles | Metrics
    A model of grid service capacity
    Youcef Derbal
    Journal of Computer Science and Technology, 2007, 22 (4): 505-514 . 
    Abstract   PDF(1196KB) ( 5943 )   Chinese Summary
    Computational grids (CGs) are large scale networks of geographically distributed aggregates of resource clusters that may be contributed by distinct organizations for the provision of computing services such as model simulation, compute cycle and data mining. Traditionally, the decision-making strategies underlying the grid management mechanisms rely on the physical view of the grid resource model. This entails the need for complex multi-dimensional search strategies and a considerable level of resource state information exchange between the grid management domains. In this paper we argue that with the adoption of service oriented grid architectures, a logical service-oriented view of the resource model provides a more appropriate level of abstraction to express the grid capacity to handle incoming service requests. In this respect, we propose a quantification model of the aggregated service capacity of the hosting environment that is updated based on the monitored state of the various environmental resources required by the hosted services. A comparative experimental validation of the model shows its performance towards enabling an adequate exploitation of provisioned services.
    References | Related Articles | Metrics
    Next high performance and low power flash memory package structure
    Jung-Hoon Lee
    Journal of Computer Science and Technology, 2007, 22 (4): 515-520 . 
    Abstract   PDF(1301KB) ( 5749 )   Chinese Summary
    In general, NAND flash memory has advantages in low power consumption, storage capacity, and fast erase/write performance in contrast to NOR flash. But, main drawback of the NAND flash memory is the slow access time for random read operations. Therefore, we proposed the new NAND flash memory package for overcoming this major drawback. We present a high performance and low power NAND flash memory system with a dual cache memory. The proposed NAND flash package consists of two parts, i.e., an NAND flash memory module, and a dual cache module. The new NAND flash memory system can achieve dramatically higher performance and lower power consumption compared with any conventional NAND-type flash memory module. Our results show that the proposed system can reduce about 78% of write operations into the flash memory cell and about 70% of read operations from the flash memory cell by using only additional 3KB cache space. This value represents high potential to achieve low power consumption and high performance gain.
    References | Related Articles | Metrics
    Distributed Storage Cluster Design for Remote Mirroring Based on Storage Area Network
    Jun Yao, Ji-Wu Shu, and Wei-Min Zheng
    Journal of Computer Science and Technology, 2007, 22 (4): 521-526 . 
    Abstract   PDF(1007KB) ( 6376 )   Chinese Summary
    With the explosion of information nowadays, applying data storage safety requirements has become a new challenge, especially in high data available cluster environments. With the emergence of Storage Area Networks (SANs), storage can be network-based and consolidated, and mass data movements via Fiber Channels (FCs) can be of very high speed. Based on these features, this paper introduces a dual-node storage cluster designed for remote mirroring as a concurrent data replication method to protect data during system failures. This design takes full advantage of a SAN system's benefits, and it adopts a synchronous protocol to guarantee a fully up-to-date data copy on the remote site. By developing a Linux kernel module to control the I/O flow and by using the technologies of software Logic Unit Number (LUN) masking, background online resynchronization and a self-management daemon, we have achieved a reliable mirroring system with the characteristics of server-free data replication, fault tolerance, online disaster recovery and high performance. In this study, we implemented the design in a remote mirror subsystem built on a software Fiber Channel Storage Area Network (FC-SAN) system.
    References | Related Articles | Metrics
    Adaptive call admission control based on reward-penalty model in wireless/mobile network
    Jian-Hui Huang, De-Pei Qian, and Sheng-Ling Wang
    Journal of Computer Science and Technology, 2007, 22 (4): 527-531 . 
    Abstract   PDF(698KB) ( 4691 )   Chinese Summary
    A dynamic threshold-based Call Admission Control (CAC) scheme used in wireless/mobile network for multi-class services is proposed. In the scheme, each class's CAC thresholds are solved through establishing a reward-penalty model which strives to maximize network's revenue. In order to lower Handoff Dropping Probability (HDP), the scheme joints packet and connection levels Quality of Service constraints, designing a bandwidth degradation algorithm to accept handoff calls by degrading existing calls' bandwidth during network congestion. Analyses show that the CAC thresholds change adaptively with the average call arrival rate. The performance comparison shows that the proposed scheme outperforms the Mobile IP Reservation scheme.
    References | Related Articles | Metrics
    Engineering the Divide-and-Conquer Closest Pair Algorithm
    Minghui Jiang and Joel Gillespie
    Journal of Computer Science and Technology, 2007, 22 (4): 532-540 . 
    Abstract   PDF(891KB) ( 7590 )   Chinese Summary
    We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For $n$ points on the plane, our algorithm keeps the optimal $O(n \log n)$ time complexity and, using a circle-packing property, computes at most $7n/2$ Euclidean distances, which improves Ge {\it et al.}'s bound of $(3n\log n)/2$ Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.
    References | Related Articles | Metrics
    An Improvement of Herbrands Theorem and Its Application to Model Generation Theorem Proving
    Yu-Yan Chao, Li-Feng He, Tsuyoshi Nakamura, Zheng-Hao Shi, Kenji Suzuki, and Hidenori Itoh
    Journal of Computer Science and Technology, 2007, 22 (4): 541-553 . 
    Abstract   PDF(945KB) ( 4367 )   Chinese Summary

    This paper presents an improvement of Herbrand's theorem. We propose a method for specifying a sub-universe of the Herbrand universe of a clause set ${\cal S}$ for each argument of predicate symbols and function symbols in ${\cal S}$. We prove that a clause set ${\cal S}$ is unsatisfiable if and only if there is a finite unsatisfiable set of ground instances of clauses of ${\cal S}$ that are derived by only instantiating each variable, which appears as an argument of predicate symbols or function symbols, in ${\cal S}$ over its corresponding argument's sub-universe of the Herbrand universe of ${\cal S}$. Because such sub-universes are usually smaller (sometimes considerably) than the Herbrand universe of ${\cal S}$, the number of ground instances may decrease considerably in many cases. We present an algorithm for automatically deriving the sub-universes for arguments in a given clause set, and show the correctness of our improvement. Moreover, we introduce an application of our approach to model generation theorem proving for non-range-restricted problems, show the range-restriction transformation algorithm based on our improvement and provide examples on benchmark problems to demonstrate the power of our approach.

    References | Related Articles | Metrics
    Consistency Property of Finite FC-Normal Logic Programs
    Yi-Song Wang, Ming-Yi Zhang, and Yu-Ping Shen
    Journal of Computer Science and Technology, 2007, 22 (4): 554-561 . 
    Abstract   PDF(365KB) ( 4476 )   Chinese Summary
    Marek's forward-chaining construction is one of the important techniques for investigating the non-monotonic reasoning. By introduction of consistency property over a logic program, they proposed a class of logic programs, FC-normal programs, each of which has at least one stable model. However, it is not clear how to choose one appropriate consistency property for deciding whether or not a logic program is FC-normal. In this paper, we firstly discover that, for any finite logic program ${\it\Pi}$, there exists the least consistency property ${\it LCon}({\it\Pi})$ over ${\it\Pi}$, which just depends on ${\it\Pi}$ itself, such that, ${\it\Pi}$ is FC-normal if and only if ${\it\Pi}$ is FC-normal with respect to (w.r.t.) ${\it LCon}({\it\Pi})$. Actually, in order to determine the FC-normality of a logic program, it is sufficient to check the monotonic closed sets in ${\it LCon}({\it\Pi})$ for all non-monotonic rules, that is ${\it LFC}({\it\Pi})$. Secondly, we present an algorithm for computing ${\it LFC}({\it\Pi})$. Finally, we reveal that the brave reasoning task and cautious reasoning task for FC-normal logic programs are of the same difficulty as that of normal logic programs.
    References | Related Articles | Metrics
    Comparison of Semantics of Disjunctive Logic Programs Based on Model-Equivalent Reduction
    Xi-Shun Zhao and Yu-Ping Shen
    Journal of Computer Science and Technology, 2007, 22 (4): 562-568 . 
    Abstract   PDF(689KB) ( 5046 )   Chinese Summary
    In this paper, it is shown that stable model semantics, perfect model semantics, and partial stable model semantics of disjunctive logic programs have the same expressive power with respect to the polynomial-time model-equivalent reduction. That is, taking perfect model semantics and stable model semantic as an example, any logic program $P$ can be transformed in polynomial time to another logic program $P'$ such that perfect models (resp. stable models) of $P$ 1-1 correspond to stable models (resp. perfect models) of $P'$, and the correspondence can be computed also in polynomial time. However, the minimal model semantics has weaker expressiveness than other mentioned semantics, otherwise, the polynomial hierarchy would collapse to NP.
    References | Related Articles | Metrics
    Quasi-Physical Algorithm of an Off-Lattice Model for Protein Folding Problem
    Jing-Fa Liu and Wen-Qi Huang
    Journal of Computer Science and Technology, 2007, 22 (4): 569-574 . 
    Abstract   PDF(665KB) ( 4441 )   Chinese Summary
    Protein folding problem is one of the most prominent problems of bioinformatics. In this paper, we study a three-dimensional off-lattice protein AB model with two species of monomers, hydrophobic and hydrophilic, and present a heuristic quasi-physical algorithm. By elaborately simulating the movement of the smooth elastic balls in the physical world, the algorithm finds low-energy configurations for a given monomer chain. A subsequent ``off-trap'' strategy is proposed to trigger a jump for a stuck situation in order to get out of local minima. The methods have been tested in the off-lattice AB model. The computational results show promising performance. For all sequences with 13 to 55 monomers, the algorithm finds states with lower energy than previously proposed putative ground states. Furthermore, for the sequences with 21, 34 and 55 monomers, new putative ground states are found, which are different from those given in present literature.
    References | Related Articles | Metrics
    Barbed Congruence of Asymmetry and Mismatch
    Xiao-Ju Dong and Yu-Xi Fu
    Journal of Computer Science and Technology, 2007, 22 (4): 575-579 . 
    Abstract   PDF(658KB) ( 5144 )   Chinese Summary
    The $\chi$ calculus is a model of concurrent and mobile systems. It emphasizes that communications are information exchanges. In the paper, two constructions are incorporated into the framework of the chi calculus, which are asymmetric communication and mismatch condition widely used in applications. Since the barbed bisimilarity has proved its generality and gained its popularity as an effective approach to generating a reasonable observational equivalence, we study both the operational and algebraic properties of the barbed bisimilarity in this enriched calculus. The investigation supports an improved understanding of the bisimulation behaviors of the model. It also gives a general picture of how the two constructions affect the observational theory.
    References | Related Articles | Metrics
    Spatially Adaptive Image Restoration Using Fuzzy Punctual Kriging
    Anwar M. Mirza, Asmatullah Chaudhry, and Badre Munir
    Journal of Computer Science and Technology, 2007, 22 (4): 580-589 . 
    Abstract   PDF(1884KB) ( 5949 )   Chinese Summary
    We present a general formulation based on punctual kriging and fuzzy concepts for image restoration in spatial domain. Gray-level images degraded with Gaussian white noise have been considered. Based on the pixel local neighborhood, fuzzy logic has been employed intelligently to avoid unnecessary estimation of a pixel. The intensity estimation of the selected pixels is then carried out by employing punctual kriging in conjunction with the method of Lagrange multipliers and estimates of local semi-variances. Application of such a hybrid technique performing both selection and intensity estimation of a pixel demonstrates substantial improvement in the image quality as compared to the adaptive Wiener filter and existing fuzzy-kriging approaches. It has been found that these filters achieve noise reduction without loss of structural detail information, as indicated by their higher structure similarity indices, peak signal to noise ratios and the new variogram based quality measures.
    References | Related Articles | Metrics
    Real-Time Texture Synthesis Using s-Tile Set
    Feng Xue, You-Sheng Zhang, Ju-Lang Jiang, Min Hu, Xin-Dong Wu, and Rong-Gui Wang
    Journal of Computer Science and Technology, 2007, 22 (4): 590-596 . 
    Abstract   PDF(3839KB) ( 6589 )   Chinese Summary
    This paper presents a novel method of generating a set of texture tiles from samples, which can be seamlessly tiled into arbitrary size textures in real-time. Compared to existing methods, our approach is simpler and more advantageous in eliminating visual seams that may exist in each tile of the existing methods, especially when the samples have elaborate features or distinct colors. Texture tiles generated by our approach can be regarded as single-colored tiles on each orthogonal direction border, which are easier for tiling and more suitable for sentence tiling. Experimental results demonstrate the feasibility and effectiveness of our approach.
    References | Related Articles | Metrics
    AHT Bézier Curves and NUAHT B-Spline Curves
    Gang Xu and Guo-Zhao Wang
    Journal of Computer Science and Technology, 2007, 22 (4): 597-607 . 
    Abstract   PDF(2756KB) ( 7571 )   Chinese Summary
    In this paper, we present two new unified mathematics models of conics and polynomial curves, called {\it algebraic hyperbolic trigonometric} ({\it AHT}) {\it B\'{e}zier curves} and {\it non-uniform algebraic hyperbolic trigonometric $($NUAHT$)$ B-spline curves of order n}, which are generated over the space ${\rm span}\{\sin t,\cos t,\sinh t,\cosh t,1,t,\ldots,t^{n-5}\}$, $n\ge 5$. The two kinds of curves share most of the properties as those of the B\'{e}zier curves and B-spline curves in polynomial space. In particular, they can represent exactly some remarkable transcendental curves such as the helix, the cycloid and the catenary. The subdivision formulae of these new kinds of curves are also given. The generations of the tensor product surfaces are straightforward. Using the new mathematics models, we present the control mesh representations of two classes of minimal surfaces.
    References | Related Articles | Metrics
    Linguistic Theory Based Contextual Evidence Mining for Statistical Chinese Co-Reference Resolution
    Jun Zhao and Fei-Fan Liu
    Journal of Computer Science and Technology, 2007, 22 (4): 608-617 . 
    Abstract   PDF(887KB) ( 4842 )   Chinese Summary
    Under statistical learning framework, the paper focuses on how to use traditional linguistic findings on anaphora resolution as a guide for mining and organizing contextual features for Chinese co-reference resolution. The main achievements are as follows. (1) In order to simulate ``syntactic and semantic parallelism factor'', we extract ``bags of word form and POS'' feature and ``bag of semes'' feature from the contexts of the entity mentions and incorporate them into the baseline feature set. (2) Because it is too coarse to use the feature of bags of word form, POS tag and seme to determine the syntactic and semantic parallelism between two entity mentions, we propose a method for contextual feature reconstruction based on semantic similarity computation, in order that the reconstructed contextual features could better approximate the anaphora resolution factor of ``Syntactic and Semantic Parallelism Preferences''. (3) We use an entity-mention-based contextual feature representation instead of isolated word-based contextual feature representation, and expand the size of the contextual windows in addition, in order to approximately simulate ``the selectional restriction factor'' for anaphora resolution. The experiments show that the multi-level contextual features are useful for co-reference resolution, and the statistical system incorporated with these features performs well on the standard ACE datasets.
    References | Related Articles | Metrics
    Secure and Incidental Distortion Tolerant Digital Signature for Image Authentication
    Yong-Dong Zhang, Sheng Tang, and Jin-Tao Li
    Journal of Computer Science and Technology, 2007, 22 (4): 618-625 . 
    Abstract   PDF(1831KB) ( 5366 )   Chinese Summary

    In this paper, a secure and incidental distortion tolerant signature method for image authentication is proposed. The generation of authentication signature is based on Hotelling's T-square Statistic (HTS) via Principal Component Analysis (PCA) of block DCT coefficients. HTS values of all blocks construct a unique and stable ``block-edge image'', i.e., Structural and Statistical Signature (SSS). The characteristic of SSS is that it is short, and can tolerate content-preserving manipulations while keeping sensitive to content-changing attacks, and locate tampering easily. During signature matching, the Fisher criterion is used to obtain optimal threshold for automatically and universally distinguishing incidental manipulations from malicious attacks. Moreover, the security of SSS is achieved by encryption of the DCT coefficients with chaotic sequences before PCA. Experiments show that the novel method is effective for authentication.

    References | Related Articles | Metrics
    Facial Feature Extraction Method Based on Coefficients of Variances
    Feng-Xi Song, David Zhang, Cai-Kou Chen, and Jing-Yu Yang
    Journal of Computer Science and Technology, 2007, 22 (4): 626-632 . 
    Abstract   PDF(991KB) ( 4933 )   Chinese Summary
    Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) are two popular feature extraction techniques in statistical pattern recognition field. Due to small sample size problem LDA cannot be directly applied to appearance-based face recognition tasks. As a consequence, a lot of LDA-based facial feature extraction techniques are proposed to deal with the problem one after the other. Nullspace Method is one of the most effective methods among them. The Nullspace Method tries to find a set of discriminant vectors which maximize the between-class scatter in the null space of the within-class scatter matrix. The calculation of its discriminant vectors will involve performing singular value decomposition on a high-dimensional matrix. It is generally memory- and time-consuming. Borrowing the key idea in Nullspace method and the concept of coefficient of variance in statistical analysis we present a novel facial feature extraction method, i.e., Discriminant based on Coefficient of Variance (DCV) in this paper. Experimental results performed on the FERET and AR face image databases demonstrate that DCV is a promising technique in comparison with Eigenfaces, Nullspace Method, and other state-of-the-art facial feature extraction methods.
    References | Related Articles | Metrics
    Hierarchical Approximate Matching for Retrieval of Chinese Historical Calligraphy Character
    Xia-Fen Zhang, Yue-Ting Zhuang, Jiang-Qin Wu, and Fei Wu
    Journal of Computer Science and Technology, 2007, 22 (4): 633-640 . 
    Abstract   PDF(1635KB) ( 6402 )   Chinese Summary
    As historical Chinese calligraphy works are being digitized, the problem of retrieval becomes a new challenge. But, currently no OCR technique can convert calligraphy character images into text, nor can the existing Handwriting Character Recognition approach does not work for it. This paper proposes a novel approach to efficiently retrieving Chinese calligraphy characters on the basis of similarity: calligraphy character image is represented by a collection of discriminative features, and high retrieval speed with reasonable effectiveness is achieved. First, calligraphy characters that have no possibility similar to the query are filtered out step by step by comparing the character complexity, stroke density and stroke protrusion. Then, similar calligraphy characters are retrieved and ranked according to their matching cost produced by approximate shape match. In order to speed up the retrieval, we employed high dimensional data structure --- PK-tree. Finally, the efficiency of the algorithm is demonstrated by a preliminary experiment with 3012 calligraphy character images.
    References | 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