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
      05 May 2009, Volume 24 Issue 3 Previous Issue    Next Issue
    For Selected: View Abstracts Toggle Thumbnails
    Distributed Computing and Systems
    Taxonomy of Data Prefetching for Multicore Processors
    Surendra Byna, Yong Chen, and Xian-He Sun
    Journal of Computer Science and Technology, 2009, 24 (3): 405-417. 
    Abstract   PDF(871KB) ( 3064 )   Chinese Summary

    Data prefetching is an effective data access latency hiding technique to mask the CPU stall caused by cache misses and to bridge the performance gap between processor and memory. With hardware and/or software support, data prefetching brings data closer to a processor before it is actually needed. Many prefetching techniques have been developed for single-core processors. Recent developments in processor technology have brought multicore processors into mainstream. While some of the single-core prefetching techniques are directly applicable to multicore processors, numerous novel strategies have been proposed in the past few years to take advantage of multiple cores. This paper aims to provide a comprehensive review of the state-of-the-art prefetching techniques, and proposes a taxonomy that classifies various design concerns in developing a prefetching strategy, especially for multicore processors. We compare various existing methods through analysis as well.

    References | Related Articles | Metrics
    Conditions for Set Agreement with an Application to Synchronous Systems
    Francois Bonnet and Michel Raynal
    Journal of Computer Science and Technology, 2009, 24 (3): 418-433. 
    Abstract   PDF(544KB) ( 1769 )   Chinese Summary

    The -set agreement problem is a generalization of the consensus problem: considering a system made up of processes where each process proposes a value, each non-faulty process has to decide a value such that a decided value is a proposed value, and no more than different values are decided. While this problem cannot be solved in an asynchronous system prone to process crashes when , it can always be solved in a synchronous system; is then a lower bound on the number of rounds (consecutive communication steps) for the non-faulty processes to decide. The {\it condition-based} approach has been introduced in the consensus context. Its aim was to both circumvent the consensus impossibility in asynchronous systems, and allow for more efficient consensus algorithms in synchronous systems. This paper addresses the condition-based approach in the context of the -set agreement problem. It has two main contributions. The first is the definition of a framework that allows defining conditions suited to the -set agreement problem and the second is a generic synchronous -set agreement algorithm based on conditions.

    References | Related Articles | Metrics
    Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters
    Xiao-Min Zhu and Pei-Zhong Lu
    Journal of Computer Science and Technology, 2009, 24 (3): 434-446. 
    Abstract   PDF(526KB) ( 2491 )   Chinese Summary

    Multiple performance requirements need to be guaranteed in some real-time applications such as multimedia data processing and real-time signal processing in addition to timing constraints. Unfortunately, most conventional scheduling algorithms only take one or two dimensions of them into account. Motivated by this fact, this paper investigates the problem of providing multiple performance guarantees including timeliness, QoS, throughput, QoS fairness and load balancing for a set of independent tasks by dynamic scheduling. We build a scheduler model that can be used for multi-dimensional scheduling. Based on the scheduler model, we propose a heuristic multi-dimensional scheduling strategy, MDSS, consisting of three steps. The first step can be of any existing real-time scheduling algorithm that determines to accept or reject a task. In step 2, we put forward a novel algorithm MQFQ to enhance the QoS levels of accepted tasks, and to make these tasks have fair QoS levels at the same time. Another new algorithm ITLB is proposed and used in step 3. The ITLB algorithm is capable of balancing load and improving throughput of the system. To evaluate the performance of MDSS, we perform extensive simulation experiments to compare MDSS strategy with MDSR strategy, DASAP and DALAP algorithms. Experimental results show that MDSS significantly outperforms MDSR, DASAP and DALAP.

    References | Related Articles | Metrics
    Building a Distributed Infrastructure for Scalable Triple Stores
    Jing Zhou, Member, ACM, Wendy Hall, Member, ACM, and David De Roure, Member, ACM
    Journal of Computer Science and Technology, 2009, 24 (3): 447-462. 
    Abstract   PDF(596KB) ( 2234 )   Chinese Summary

    Built specifically for the Semantic Web, triple stores are required to accommodate a large number of RDF triples and remain primarily centralized. As triple stores grow and evolve with time, there is a demanding need for scalable techniques to remove resource and performance bottlenecks in such systems. To this end, we propose a fully decentralized peer-to-peer architecture for large scale triple stores in which triples are maintained by individual stakeholders, and a semantics-directed search protocol, mediated by topology reorganization, for locating triples of interest. We test our design through simulations and the results show anticipated improvements over existing techniques for distributed triple stores. In addition to engineering future large scale triple stores, our work will in particular benefit the federation of stand-alone triple stores of today to achieve desired scalability.

    References | Related Articles | Metrics
    Neural Network Algorithm for Designing FIR Filters Utilizing Frequency-Response Masking Technique
    Xiao-Hua Wang, Yi-Gang He, Tian-Zan Li
    Journal of Computer Science and Technology, 2009, 24 (3): 463-471. 
    Abstract   PDF(479KB) ( 2375 )   Chinese Summary

    This paper presents a new joint optimization method for the design of sharp linear-phase finite-impulse response (FIR) digital filters which are synthesized by using basic and multistage frequency-response-masking (FRM) techniques. The method is based on a batch back-propagation neural network algorithm with a variable learning rate mode. We propose the following two-step optimization technique in order to reduce the complexity. At the first step, an initial FRM filter is designed by alternately optimizing the subfilters. At the second step, this solution is then used as a start-up solution to further optimization. The further optimization problem is highly nonlinear with respect to the coefficients of all the subfilters. Therefore, it is decomposed into several linear neural network optimization problems. Some examples from the literature are given, and the results show that the proposed algorithm can design better FRM filters than several existing methods.

    References | Related Articles | Metrics
    Computer Network and Internet
    A Distributed Mechanism for Handling of Adaptive/Intelligent Selfish Misbehaviour at MAC Layer in Mobile Ad Hoc Networks
    Raja Gunasekaran, Member, IEEE, Vaidheyanathan Rhymend Uthariaraj, Member, IEEE, Uamapathy Yamini, Member, IEEE, Rajagopalan Sudharsan, Member, IEEE, and Selvaraj Sujitha Priyadarshini
    Journal of Computer Science and Technology, 2009, 24 (3): 472-481. 
    Abstract   PDF(742KB) ( 2422 )   Chinese Summary

    Medium access control (MAC) protocols such as IEEE 802.11 are used in wireless networks for sharing of the wireless medium. The random nature of the protocol operation together with the inherent difficulty of monitoring in the open poses significant challenges. All nodes are expected to comply with the protocol rules. But, some nodes in order to gain greater benefits misbehave by not complying with the rules. One such selfish misbehavior is waiting for smaller back-off intervals when compared to the other nodes in the same subnet. Such selfish misbehavior is being tackled in this paper. A diagnosis scheme and a penalty scheme are being proposed for overcoming such selfish-misbehavior at MAC layer of mobile ad hoc networks which could be extended to other types of networks also.

    References | Related Articles | Metrics
    Towards Next Generation Internet Management: CNGI-CERNET2 Experiences
    Jia-Hai Yang, Senior Member, CCF, Member, IEEE, Hui Zhang, Member, ACM, IEEE, Jin-Xiang Zhang, and Chang-Qing An
    Journal of Computer Science and Technology, 2009, 24 (3): 482-494. 
    Abstract   PDF(3290KB) ( 2106 )   Chinese Summary

    Manageability is an important feature of next generation Internet; management and monitoring of IPv6-based networks are proving a big challenge. While leveraging current IPv4-based SNMP management scheme to IPv6 networks' management need is necessary, it is more urgent to coin a new network management architecture to accommodate the scalability and extensibility requirements of next generation Internet management. The paper proposes a novel network management architecture, IMN (Internet Management Network), which creates an overlay network of management nodes. While each management node can perform management tasks autonomously and independently, it can finish more sophisticated management tasks by collaboratively invoking management operations or sharing information provided by other management nodes. P2P-based communication services are introduced in IMN to enable such collaboration. The paper presents a prototyping implementation based on the Web service related technology, as well as some of the key technologies, especially solutions to those issues arising from the management practice of CERNET2. Experiences of deployment of CERNET2 operation and lessons learned from the management practice are discussed.

    References | Related Articles | Metrics
    An Improved Markov Model for IEEE 802.15.4 Slotted CSMA/CA Mechanism
    Hao Wen, Student Member, ACM, Chuang Lin, Member, CCF, Zhi-Jia Chen, Student Member, CCF, Hao Yin, Member, CCF, Tao He, and Eryk Dutkiewicz, Member, IEEE
    Journal of Computer Science and Technology, 2009, 24 (3): 495-504. 
    Abstract   PDF(775KB) ( 5608 )   Chinese Summary

    IEEE 802.15.4 protocol is proposed to meet the low latency and energy consumption needs in low-rate wireless applications, however, few analytical models are tractable enough for comprehensive evaluation of the protocol. To evaluate the IEEE 802.15.4 slotted CSMA/CA channel access mechanism in this paper, we propose a practical and accurate discrete Markov chain model, which can dynamically represent different network loads. By computing the steady-state distribution probability of the Markov chain, we obtain an evaluation formula for throughput, energy consumption, and access latency. Then we further analyze the parameters that influence performance including packet arrival rate, initial backoff exponent and maximum backoff number. Finally, NS2 simulator has been used to evaluate the performance of the 802.15.4 CSMA/CA mechanism under different scenarios and to validate the accuracy of the proposed model.

    References | Related Articles | Metrics
    Algorithm and Complexity
    Searching a Polygonal Region by a Boundary Searcher
    Xue-Hou Tan
    Journal of Computer Science and Technology, 2009, 24 (3): 505-516. 
    Abstract   PDF(729KB) ( 1912 )   Chinese Summary

    This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually "see" an intruder that is unpredictable and capable of moving arbitrarily fast. A searcher is called the {\it boundary searcher} if he continuously moves on the polygon boundary and can see only along the rays of the flashlights he holds at a time. We present necessary and sufficient conditions for an $n$-sided polygon to be searchable by a boundary searcher. Based on our characterization, the equivalence of the ability of the searchers having only one flashlight and the one of the searchers having full vision is simply established, and moreover, an optimal time and space algorithm for determining the searchability of simple polygons is obtained. We also give an time algorithm for generating a search schedule if it exists, where I is the number of search instructions reported. Our results improve upon the previously known time and space bounds.

    References | Related Articles | Metrics
    A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
    Shin-ichi Nakano, Member, ACM, IEEE, Ryuhei Uehara, Member, ACM, IEEE, and Takeaki Uno
    Journal of Computer Science and Technology, 2009, 24 (3): 517-533. 
    Abstract   PDF(807KB) ( 1910 )   Chinese Summary

    Algorithms used in data mining and bioinformatics have to deal with huge amount of data efficiently. In many applications, the data are supposed to have explicit or implicit structures. To develop efficient algorithms for such data, we have to propose possible structure models and test if the models are feasible. Hence, it is important to make a compact model for structured data, and enumerate all instances efficiently. There are few graph classes besides trees that can be used for a model. In this paper, we investigate distance-hereditary graphs. This class of graphs consists of isometric graphs and hence contains trees and cographs. First, a canonical and compact tree representation of the class is proposed. The tree representation can be constructed in linear time by using prefix trees. Usually, prefix trees are used to maintain a set of strings. In our algorithm, the prefix trees are used to maintain the neighborhood of vertices, which is a new approach unlike the lexicographically breadth-first search used in other studies. Based on the canonical tree representation, efficient algorithms for the distance-hereditary graphs are proposed, including linear time algorithms for graph recognition and graph isomorphism and an efficient enumeration algorithm. An efficient coding for the tree representation is also presented; it requires bits for a distance-hereditary graph of vertices and bits for a cograph. The results of coding improve previously known upper bounds (both are ) of the number of distance-hereditary graphs and cographs to and , respectively.

    References | Related Articles | Metrics
    Symbolic Algorithmic Analysis of Rectangular Hybrid Systems
    Hai-Bin Zhang and Zhen-Hua Duan, Senior Member, CCF, IEEE
    Journal of Computer Science and Technology, 2009, 24 (3): 534-543. 
    Abstract   PDF(387KB) ( 2440 )   Chinese Summary

    This paper investigates symbolic algorithmic analysis of rectangular hybrid systems. To deal with the symbolic reachability problem, a restricted constraint system called \emph{hybrid zone} is formalized for the representation and manipulation of rec\-tangular automata state-spaces. Hybrid zones are proved to be closed over symbolic reachability operations of rec\-tangular hybrid systems. They are also applied to model-checking procedures for verifying some important classes of timed computation tree logic formulas. To represent hybrid zones, a data structure called \emph{difference constraint matrix} is defined. These enable us to deal with the symbolic algorithmic analysis of rectangular hybrid systems in an efficient way.

    References | Related Articles | Metrics
    Computer Graphics and Visualization
    A New Line Symmetry Distance and Its Application to Data Clustering
    Sriparna Saha, Student Member, IEEE, and Sanghamitra Bandyopadhyay, Senior Member, IEEE
    Journal of Computer Science and Technology, 2009, 24 (3): 544-556. 
    Abstract   PDF(1841KB) ( 2573 )   Chinese Summary

    In this paper, at first a new line-symmetry-based distance is proposed. The properties of the proposed distance are then elaborately described. Kd-tree-based nearest neighbor search is used to reduce the complexity of computing the proposed line-symmetry-based distance. Thereafter an evolutionary clustering technique is developed that uses the new line-symmetry-based distance measure for assigning points to different clusters. Adaptive mutation and crossover probabilities are used to accelerate the proposed clustering technique. The proposed GA with line-symmetry-distance-based (GALSD) clustering technique is able to detect any type of clusters, irrespective of their geometrical shape and overlapping nature, as long as they possess the characteristics of line symmetry. GALSD is compared with the existing well-known K-means clustering algorithm and a newly developed genetic point-symmetry-distance-based clustering technique (GAPS) for three artificial and two real-life data sets. The efficacy of the proposed line-symmetry-based distance is then shown in recognizing human face from a given image.

    References | Related Articles | Metrics
    Pores-Preserving Face Cleaning Based on Improved Empirical Mode Decomposition
    Yan-Li Liu, Xiao-Gang Xu, Yan-Wen Guo, Jin Wang, Xin Duan, Xi Chen, and Qun-Sheng Peng, Senior Member, CCF
    Journal of Computer Science and Technology, 2009, 24 (3): 557-567. 
    Abstract   PDF(16288KB) ( 2376 )   Chinese Summary

    In this paper, we propose a novel method of cleaning up facial imperfections such as bumps and blemishes that may detract from a pleasing digital portrait. Contrasting with traditional methods which tend to blur facial details, our method fully retains fine scale skin textures (pores etc.) of the subject. Our key idea is to find a quantity, namely normalized local energy, to capture different characteristics of fine scale details and distractions, based on empirical mode decomposition, and then build a quantitative measurement of facial skin appearance which characterizes both imperfections and facial details in a unified framework. Finally, we use the quantitative measurement as a guide to enhance facial skin. We also introduce a few high-level, intuitive parameters for controlling the amount of enhancement. In addition, an adaptive local mean and neighborhood limited empirical mode decomposition algorithm is also developed to improve in two respects the performance of empirical mode decomposition. It can effectively avoid the gray spots effect commonly associated with traditional empirical mode decomposition when dealing with high-nonstationary images.

    References | Related Articles | Metrics
    Boolean Operations on Conic Polygons
    Yong-Xi Gong, Yu Liu, Lun Wu, and Yu-Bo Xie
    Journal of Computer Science and Technology, 2009, 24 (3): 568-577. 
    Abstract   PDF(853KB) ( 2382 )   Chinese Summary

    An algorithm for Boolean operations on conic polygons is proposed. Conic polygons are polygons consisting of conic segments or bounded conics with directions. Preliminaries of Boolean operations on general polygons are presented. In our algorithm, the intersection points and the topological relationships between two conic polygons are computed. Boundaries are obtained by tracking path and selecting uncrossed boundaries following rule tables to build resulting conic polygons. We define a set of rules for the intersection, union, and subtraction operations on conic polygons. The algorithm considers degeneration cases such as homology, complement, interior, and exterior. The algorithm is also evaluated and implemented.

    References | Related Articles | Metrics
    Lumiproxy: A Hybrid Representation of Image-Based Models
    Bin Sheng, Jian Zhu, En-Hua Wu, Member, CCF, ACM, IEEE, and Yan-Ci Zhang
    Journal of Computer Science and Technology, 2009, 24 (3): 578-587. 
    Abstract   PDF(21888KB) ( 2017 )   Chinese Summary

    In this paper, we present a hybrid representation of image-based models combining the textured planes and the hierarchical points. Taking a set of depth images as input, our method starts from classifying input pixels into two categories, indicating the planar and non-planar surfaces respectively. For the planar surfaces, the geometric coefficients are reconstructed to form the uniformly sampled textures. For nearly planar surfaces, some textured planes, called {\it lumiproxies}, are constructed to represent the equivalent visual appearance. The Hough transform is used to find the positions of these textured planes, and optic flow measures are used to determine their textures. For remaining pixels corresponding to the non-planar geometries, the point primitive is applied, reorganized as the OBB-tree structure. Then, texture mapping and point splatting are employed together to render the novel views, with the hardware acceleration.

    References | Related Articles | Metrics
    Self Localization Method Using Parallel Projection Model for Mobile Sensor in Navigation Applications
    Shung Han Cho, Student Member, IEEE, Yuntai Kyong, Student Member, IEEE, Sangjin Hong, Senior Member, IEEE, and We-Duke Cho, Member, IEEE
    Journal of Computer Science and Technology, 2009, 24 (3): 588-603. 
    Abstract   PDF(4323KB) ( 2479 )   Chinese Summary

    This paper presents a novel self localization method using parallel projection model for mobile sensor in navigation applications. The algorithm estimates the coordinate and the orientation of mobile sensor using projected references on visual image. The proposed method considers the lens non-linearity of the camera and compensates the distortion by using a calibration table. The method determines the coordinates and orientations with iterative process, which is very accurate with low computational demand. We identify various sources of error on the coordinate and orientation estimations, and present both static sensitivity analysis of the algorithm and dynamic behavior of the mobile sensor. The algorithm can be utilized in mobile robot navigation as well as positioning application where accurate self localization is necessary.

    References | Related Articles | Metrics
    Efficient Simplification Methods for Generating High Quality LODs of 3D Meshes
    Muhammad Hussain
    Journal of Computer Science and Technology, 2009, 24 (3): 604-inside back cover. 
    Abstract   PDF(28953KB) ( 1859 )   Chinese Summary

    Two simplification algorithms are proposed for automatic decimation of polygonal models, and for generating their LODs. Each algorithm orders vertices according to their priority values and then removes them iteratively. For setting the priority value of each vertex, exploiting normal field of its one-ring neighborhood, we introduce a new measure of geometric fidelity that reflects well the local geometric features of the vertex. After a vertex is selected, using other measures of geometric distortion that are based on normal field deviation and distance measure, it is decided which of the edges incident on the vertex is to be collapsed for removing it. The collapsed edge is substituted with a new vertex whose position is found by minimizing the local quadric error measure. A comparison with the state-of-the-art algorithms reveals that the proposed algorithms are simple to implement, are computationally more efficient, generate LODs with better quality, and preserve salient features even after drastic simplification. The methods are useful for applications such as 3D computer games, virtual reality, where focus is on fast running time, reduced memory overhead, and high quality LODs.

    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