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 January 2012, Volume 27 Issue 1 Previous Issue    Next Issue
    For Selected: View Abstracts Toggle Thumbnails
    Artificial Intelligent and Pattern Recognition
    Dynamic Uncertain Causality Graph for Knowledge Representation and Reasoning: Discrete DAG Cases
    Qin Zhang (张勤)
    Journal of Computer Science and Technology, 2012, 27 (1): 1-23.  DOI: 10.1007/s11390-012-1202-7
    Abstract   PDF(1257KB) ( 2428 )   Chinese Summary
    Developed from the dynamic causality diagram (DCD) model, a new approach for knowledge representation and reasoning named as dynamic uncertain causality graph (DUCG) is presented, which focuses on the compact representation of complex uncertain causalities and efficient probabilistic inference. It is pointed out that the existing models of compact representation and inference in Bayesian Network (BN) is applicable in single-valued cases, but may not be suitable to be applied in multi-valued cases. DUCG overcomes this problem and beyond. The main features of DUCG are: 1) compactly and graphically representing complex conditional probability distributions (CPDs), regardless of whether the cases are single-valued or multi-valued; 2) able to perform exact reasoning in the case of the incomplete knowledge representation; 3) simplifying the graphical knowledge base conditional on observations before other calculations, so that the scale and complexity of problem can be reduced exponentially; 4) the efficient two-step inference algorithm consisting of (a) logic operation to find all possible hypotheses in concern for given observations and (b) the probability calculation for these hypotheses; and 5) much less relying on the parameter accuracy. An alarm system example is provided to illustrate the DUCG methodology.
    References | Related Articles | Metrics
    Publishing Set-Valued Data Against Realistic Adversaries
    Jun-Qiang Liu (刘君强)
    Journal of Computer Science and Technology, 2012, 27 (1): 24-36.  DOI: 10.1007/s11390-012-1203-6
    Abstract   PDF(459KB) ( 1829 )   Chinese Summary
    Privacy protection in publishing set-valued data is an important problem. However, privacy notions proposed in prior works either assume that the adversary has unbounded knowledge and hence provide over-protection that causes excessive distortion, or ignore the knowledge about the absence of certain items and do not prevent attacks based on such knowledge. To address these issues, we propose a new privacy notion, (k,l)(m,n)-privacy, which prevents both the identity disclosure and the sensitive item disclosure to a realistic privacy adversary who has bounded knowledge about the presence of items and the bounded knowledge about the absence of items. In addition to the new notion, our contribution is an efficient algorithm that finds a near-optimal solution and is applicable for anonymizing real world databases. Extensive experiments on real world databases showed that our algorithm outperforms the state of the art algorithms.
    References | Related Articles | Metrics
    Integrating Standard Dependency Schemes in QCSP Solvers
    Ji-Wei Jin (金继伟), Fei-Fei Ma (马菲菲), Member, ACM and Jian Zhang (张健), Senior Member, CCF, ACM, IEEE
    Journal of Computer Science and Technology, 2012, 27 (1): 37-41.  DOI: 10.1007/s11390-012-1204-5
    Abstract   PDF(411KB) ( 1396 )   Chinese Summary
    Quantified constraint satisfaction problems (QCSPs) are an extension to constraint satisfaction problems (CSPs) with both universal quantifiers and existential quantifiers. In this paper we apply variable ordering heuristics and integrate standard dependency schemes in QCSP solvers. The technique can help to decide the next variable to be assigned in QCSP solving. We also introduce a new factor into the variable ordering heuristics: a variable's dep is the number of variables depending on it. This factor represents the probability of getting more candidates for the next variable to be assigned. Experimental results show that variable ordering heuristics with standard dependency schemes and the new factor dep can improve the performance of QCSP solvers.
    References | Related Articles | Metrics
    Architecture and VLSI Design
    Providing Source Code Level Portability Between CPU and GPU with MapCG
    Chun-Tao Hong (洪春涛), Member, CCF, De-Hao Chen (陈德颢), Member, CCF, Yu-Bei Chen (陈羽北), Wen-Guang Chen (陈文光), Member, CCF, ACM, IEEE, Wei-Min Zheng (郑纬民), Member, CCF, ACM, IEEE and Hai-Bo Lin (林海波), Member, ACM, IEEE
    Journal of Computer Science and Technology, 2012, 27 (1): 42-56.  DOI: 10.1007/s11390-012-1205-4
    Abstract   PDF(565KB) ( 2187 )   Chinese Summary
    Graphics processing units (GPU) have taken an important role in the general purpose computing market in recent years. At present, the common approach to programming GPU units is to write GPU specific code with low level GPU APIs such as CUDA. Although this approach can achieve good performance, it creates serious portability issues as programmers are required to write a specific version of the code for each potential target architecture. This results in high development and maintenance costs. We believe it is desirable to have a programming model which provides source code portability between CPUs and GPUs, as well as different GPUs. This would allow programmers to write one version of the code, which can be compiled and executed on either CPUs or GPUs efficiently without modification. In this paper, we propose MapCG, a MapReduce framework to provide source code level portability between CPUs and GPUs. In contrast to other approaches such as OpenCL, our framework, based on MapReduce, provides a high level programming model and makes programming much easier. We describe the design of MapCG, including the MapReduce-style high-level programming framework and the runtime system on the CPU and GPU. A prototype of the MapCG runtime, supporting multi-core CPUs and NVIDIA GPUs, was implemented. Our experimental results show that this implementation can execute the same source code efficiently on multi-core CPU platforms and GPUs, achieving an average speedup of 1.6?2.5x over previous implementations of MapReduce on eight commonly used applications.
    References | Related Articles | Metrics
    A Hybrid Circular Queue Method for Iterative Stencil Computations on GPUs
    Yang Yang (杨杨), Hui-Min Cui (崔慧敏), Xiao-Bing Feng (冯晓兵), Member, CCF and Jing-Ling Xue (薛京灵), Senior Member, IEEE
    Journal of Computer Science and Technology, 2012, 27 (1): 57-74.  DOI: 10.1007/s11390-012-1206-3
    Abstract   PDF(881KB) ( 2967 )   Chinese Summary
    In this paper, we present a hybrid circular queue method that can significantly boost the performance of stencil computations on GPU by carefully balancing usage of registers and shared-memory. Unlike earlier methods that rely on circular queues predominantly implemented using indirectly addressable shared memory, our hybrid method exploits a new reuse pattern spanning across the multiple time steps in stencil computations so that circular queues can be implemented by both shared memory and registers effectively in a balanced manner. We describe a framework that automatically finds the best placement of data in registers and shared memory in order to maximize the performance of stencil computations. Validation using four different types of stencils on three different GPU platforms shows that our hybrid method achieves speedups up to 2.93X over methods that use circular queues implemented with shared-memory only.
    References | Related Articles | Metrics
    Efficient Handling of Lock Hand-off in DSM Multiprocessors with Buffering Coherence Controllers
    Benjamín Sahelices, Agustín de Dios, Pablo Ibáñez, Member, IEEE, Víctor Viñals-Yúfera, Member, ACM, IEEE, and José María Llabería
    Journal of Computer Science and Technology, 2012, 27 (1): 75-91.  DOI: 10.1007/s11390-012-1207-2
    Abstract   PDF(1747KB) ( 1148 )   Chinese Summary
    Synchronization in parallel programs is a major performance bottleneck in multiprocessor systems. Shared data is protected by locks and a lot of time is spent on the competition arising at the lock hand-off. In order to be serialized, requests to the same cache line can either be bounced (NACKed) or buffered in the coherence controller. In this paper, we focus mainly on systems whose coherence controllers buffer requests. In a lock hand-off, a burst of requests to the same line arrive at the coherence controller. During lock hand-off only the requests from the winning processor contribute to progress of the computation, since the winning processor is the only one that will advance the work. This key observation leads us to propose a hardware mechanism we call request bypassing, which allows requests from the winning processor to bypass the requests buffered in the coherence controller keeping the lock line. We present an inexpensive implementation of request bypassing that reduces the time spent on all the execution phases of a critical section (acquiring the lock, accessing shared data, and releasing the lock) and which, as a consequence, speeds up the whole parallel computation. This mechanism requires neither compiler or programmer support nor ISA or coherence protocol changes. By simulating a 32-processor system, we show that using request bypassing does not degrade but rather improves performance in three applications with low synchronization rates, while in those having a large amount of synchronization activity (the remaining four), we see reductions in execution time and in lock stall time ranging from 14% to 39% and from 52% to 71%, respectively. We compare request bypassing with a previously proposed technique called read combining and with a system that bounces requests, observing a significantly lower execution time with the bypassing scheme. Finally, we analyze the sensitivity of our results to some key hardware and software parameters.
    References | Related Articles | Metrics
    Mercury: Combining Performance with Dependability Using Self-Virtualization
    Hai-Bo Chen (陈海波), Member, CCF, ACM, IEEE, Feng-Zhe Zhang (张逢喆), Member, CCF, ACM, Rong Chen (陈榕), Bin-Yu Zang (臧斌宇), Senior Member, CCF, Member, ACM and Pen-Chung Yew (游本中), Fellow, IEEE
    Journal of Computer Science and Technology, 2012, 27 (1): 92-104.  DOI: 10.1007/s11390-012-1208-1
    Abstract   PDF(743KB) ( 1506 )   Chinese Summary
    Virtualization has recently gained popularity largely due to its promise in increasing utilization, improving availability and enhancing security. Very often, the role of computer systems needs to change as the business environment changes. Initially, the system may only need to host one operating system and seek full execution speed. Later, it may be required to add other functionalities such as allowing easy software/hardware maintenance, surviving system failures and hosting multiple operating systems. Virtualization allows these functionalities to be supported easily and effectively. However, virtualization techniques generally incur non-negligible performance penalty. Fortunately, many virtualization-enabled features such as online software/hardware maintenance and fault tolerance do not require virtualization standby all the time. Based on this observation, this paper proposes a technique, called Self-virtualization, which provides the operating system with the capability to turn on and off virtualization on demand, without disturbing running applications. This technique enables computer systems to reap most benefits from virtualization without sacrificing performance. This paper presents the design and implementation of Mercury, a working prototype based on Linux and Xen virtual machine monitor. The performance measurement shows that Mercury incurs very little overhead: about 0.2 ms on 3 GHz Xeon CPU to complete a mode switch, and negligible performance degradation compared to Linux.
    References | Related Articles | Metrics
    Optimal Checkpoint Placement on Real-Time Tasks with Harmonic Periods
    Seong Woo Kwak and Jung-Min Yang
    Journal of Computer Science and Technology, 2012, 27 (1): 105-112.  DOI: 10.1007/s11390-012-1209-0
    Abstract   PDF(585KB) ( 1847 )   Chinese Summary
    This paper presents an optimal checkpoint strategy for fault-tolerance in real-time systems where transient faults occur in Poisson distribution. In our environment, multiple real-time tasks with different deadlines and harmonic periods are scheduled in the system by rate-monotonic algorithm, and checkpoints are inserted at a constant interval in each task. When a fault is detected, the system carries out rollback to the latest checkpoint and re-executes tasks. The maximum number of re-executable checkpoints and an equation to check schedulability are derived, and the optimal number of checkpoints is selected to maximize the probability of completing all the tasks within their deadlines.
    References | Related Articles | Metrics
    Cell Mapping for Nanohybrid Circuit Architecture Using Genetic Algorithm
    Zhu-Fei Chu (储著飞), Student Member, IEEE, Yin-Shui Xia (夏银水), and Lun-Yao Wang (王伦耀)
    Journal of Computer Science and Technology, 2012, 27 (1): 113-120.  DOI: 10.1007/s11390-012-1210-7
    Abstract   PDF(454KB) ( 1749 )   Chinese Summary
    Nanoelectronics constructed by nanoscale devices seems promising for the advanced development of inte-grated circuits (ICs). However, the lack of computer aided design (CAD) tools seriously hinders its development and applications. To investigate the cell mapping task in CAD flow, we present a genetic algorithm (GA) based method for Cmos/nanowire/MOLecular hybrid (CMOL), which is a nanohybrid circuit architecture. By designing several crossover operators and analyzing their performance, an efficient crossover operator is proposed. Combining a mutation operator, a GA based algorithm is presented and tested on the International Symposium on Circuits and Systems (ISCAS) benchmarks. The results show that the proposed method not only can obtain better area utilization and smaller delay, but also can handle larger benchmarks with CPU time improvement compared with the published methods.
    References | Related Articles | Metrics
    Graphics, Visualization, and Image Processing
    Fast Multi-Operator Image Resizing and Evaluation
    Wei-Ming Dong (董未名), Member, CCF, ACM, IEEE, Guan-Bo Bao (鲍冠伯), Xiao-Peng Zhang (张晓鹏), Member, ACM, and Jean-Claude Paul
    Journal of Computer Science and Technology, 2012, 27 (1): 121-134.  DOI: 10.1007/s11390-012-1211-6
    Abstract   PDF(1270KB) ( 1821 )   Chinese Summary
    Current multi-operator image resizing methods succeed in generating impressive results by using image simi-larity measure to guide the resizing process. An optimal operation path is found in the resizing space. However, their slow resizing speed caused by inefficient computation strategy of the bidirectional patch matching becomes a drawback in practical use. In this paper, we present a novel method to address this problem. By combining seam carving with scaling and cropping, our method can realize content-aware image resizing very fast. We define cost functions combing image energy and dominant color descriptor for all the operators to evaluate the damage to both local image content and global visual effect. Therefore our algorithm can automatically find an optimal sequence of operations to resize the image by using dynamic programming or greedy algorithm. We also extend our algorithm to indirect image resizing which can protect the aspect ratio of the dominant object in an image.
    References | Related Articles | Metrics
    Real-Time Simulation of Aeolian Sand Movement and Sand Ripple Evolution: A Method Based on the Physics of Blown Sand
    Ning Wang (王宁) and Bao-Gang Hu (胡包钢), Senior Member, IEEE
    Journal of Computer Science and Technology, 2012, 27 (1): 135-146.  DOI: 10.1007/s11390-012-1212-5
    Abstract   PDF(805KB) ( 1518 )   Chinese Summary
    Simulation and visualization of aeolian sand movement and sand ripple evolution are a challenging subject. In this paper, we propose a physically based modeling and simulating method that can be used to synthesize sandy terrain in various patterns. Our method is based on the mechanical behavior of individual sand grains, which are widely studied in the physics of blown sand. We accounted significant mechanisms of sand transportation into the sand model, such as saltation, successive saltation and collapsing, while simplified the vegetation model and wind field model to make the simulation feasible and affordable. We implemented the proposed method on the programming graphics processing unit (GPU) to get real-time simulation and rendering. Finally, we proved that our method can reflect many characteristics of sand ripple evolution through several demonstrations. We also gave several synthesized desert scenes made from the simulated height field to display its significance on application.
    References | Related Articles | Metrics
    HBIR: Hypercube-Based Image Retrieval
    Hossein Ajorloo and Abolfazl Lakdashti
    Journal of Computer Science and Technology, 2012, 27 (1): 147-162.  DOI: 10.1007/s11390-012-1213-4
    Abstract   PDF(2035KB) ( 1785 )   Chinese Summary
    In this paper, we propose a mapping from low level feature space to the semantic space drawn by the users through relevance feedback to enhance the performance of current content based image retrieval (CBIR) systems. The proposed approach makes a rule base for its inference and configures it using the feedbacks gathered from users during the life cycle of the system. Each rule makes a hypercube (HC) in the feature space corresponding to a semantic concept in the semantic space. Both short and long term strategies are taken to improve the accuracy of the system in response to each feedback of the user and gradually bridge the semantic gap. A scoring paradigm is designed to determine the effective rules and suppress the inefficient ones. For improving the response time, an HC merging approach and, for reducing the conflicts, an HC splitting method is designed. Our experiments on a set of 11 000 images from the Corel database show that the proposed approach can better describe the semantic content of images for image retrieval with respect to some existing approaches reported recently in the literature. Moreover, our approach can be better trained and is not saturated in long time, i.e., any feedback improves the precision and recall of the system. Another strength of our method is its ability to address the dynamic nature of the image database such that it can follow the changes occurred instantaneously and permanently by adding and dropping images.
    References | Related Articles | Metrics
    Feature-Preserving Mesh Denoising via Anisotropic Surface Fitting
    Jun Wang (汪俊), Member, ACM, IEEE, and Zeyun Yu (余泽云), Member, ACM, IEEE
    Journal of Computer Science and Technology, 2012, 27 (1): 163-173.  DOI: 10.1007/s11390-012-1214-3
    Abstract   PDF(1227KB) ( 1463 )   Chinese Summary
    We propose in this paper a robust surface mesh denoising method that can effectively remove mesh noise while faithfully preserving sharp features. This method utilizes surface fitting and projection techniques. Sharp features are preserved in the surface fitting algorithm by considering an anisotropic neighborhood of each vertex detected by the normal-weighted distance. In addition, to handle the mesh with a high level of noise, we perform a pre-filtering of surface normals prior to the neighborhood searching. A number of experimental results and comparisons demonstrate the excellent performance of our method in preserving important surface geometries while filtering mesh noise.
    References | Related Articles | Metrics
    New Explorations on Cannon's Contributions and Generalized Solutions for Uniform Linear Motion Blur Identification
    Lu Wang (王璐), Hong-Yan Zhang (张鸿燕), and Si-Long Peng (彭思龙)
    Journal of Computer Science and Technology, 2012, 27 (1): 174-186.  DOI: 10.1007/s11390-012-1215-2
    Abstract   PDF(819KB) ( 1872 )   Chinese Summary
    Existing frequency-domain-oriented methods of parameter identification for uniform linear motion blur (ULMB) images usually dealt with special scenarios. For example, blur-kernel directions were horizontal or vertical, or degraded images were of foursquare dimension. This excludes those identification methods from being applied to real images, especially to estimate undersized or oversized blur kernels. Pointing against the limitations of blur-kernel identifications, discrete Fourier transform (DFT)-based blur-kernel estimation methods are proposed in this paper. We analyze in depth the Fourier frequency response of generalized ULMB kernels, demonstrate in detail its related phase form and properties thereof, and put forward the concept of quasi-cepstrum. On this basis, methods of estimating ULMB-kernel parameters using amplitude spectrum and quasi-cepstrum are presented, respectively. The quasi-cepstrum-oriented approach increases the identifiable blur-kernel length, up to a maximum of half the diagonal length of the image. Meanwhile, directing toward the image of undersized ULMB, an improved method based on quasi-cepstrum is presented, which ameliorates the identification quality of undersized ULMB kernels. The quasi-cepstrum-oriented approach popularizes and applies the simulation-experiment-focused DFT theory to the estimation of real ULMB images. Compared against the amplitude-spectrum-oriented method, the quasi-cepstrum-oriented approach is more convenient and robust, with lower identification errors and of better noise-immunity.
    References | Related Articles | Metrics
    Extended Approach to Water Flow Algorithm for Text Line Segmentation
    Darko Brodić, Student Member, IEEE
    Journal of Computer Science and Technology, 2012, 27 (1): 187-194.  DOI: 10.1007/s11390-012-1216-1
    Abstract   PDF(386KB) ( 1684 )   Chinese Summary
    This paper proposes a new approach to the water flow algorithm for text line segmentation. In the basic method the hypothetical water flows under few specified angles which have been defined by water flow angle as parameter. It is applied to the document image frame from left to right and vice versa. As a result, the unwetted and wetted areas are established. These areas separate text from non-text elements in each text line, respectively. Hence, they represent the control areas that are of major importance for text line segmentation. Primarily, an extended approach means extraction of the connected-components by bounding boxes over text. By this way, each connected component is mutually separated. Hence, the water flow angle, which defines the unwetted areas, is determined adaptively. By choosing appropriate water flow angle, the unwetted areas are lengthening which leads to the better text line segmentation. Results of this approach are encouraging due to the text line segmentation improvement which is the most challenging step in document image processing.
    References | Related Articles | Metrics
    Database and Data Management
    Related Axis: The Extension to XPath Towards Effective XML Search
    Jun-Feng Zhou (周军锋), Member, CCF, Tok Wang Ling (林卓旺), Senior Member, ACM, IEEE, Zhi-Feng Bao (鲍芝峰), and Xiao-Feng Meng (孟小峰), Senior Member, CCF, Member, ACM, IEEE
    Journal of Computer Science and Technology, 2012, 27 (1): 195-212.  DOI: 10.1007/s11390-012-1217-0
    Abstract   PDF(1127KB) ( 1451 )   Chinese Summary
    We investigate the limitations of existing XML search methods and propose a new semantics, related relation-ship, to effectively capture meaningful relationships of data elements from XML data in the absence of structural constraints. Then we make an extension to XPath by introducing a new axis, related axis, to specify the related relationship between query nodes so as to enhance the flexibility of XPath. We propose to reduce the cost of computing the related relationship by a new schema summary that summarizes the related relationship from the original schema without any loss. Based on this schema summary, we introduce two indices to improve the performance of query processing. Our algorithm shows that the evaluation of most queries can be equivalently transformed into just a few selection and value join operations, thus avoids the costly structural join operations. The experimental results show that our method is effective and efficient in terms of comparing the effectiveness of the related relationship with existing keyword search semantics and comparing the efficiency of our evaluation methods with existing query engines.
    References | Related Articles | Metrics
    A Reprocessing Model for Complete Execution of RFID Access Operations on Tag Memory
    Wooseok Ryu, Bonghee Hong, Member, ACM, IEEE, Joonho Kwon and Ge Yu (于戈), Senior Member, CCF, Member, ACM, IEEE
    Journal of Computer Science and Technology, 2012, 27 (1): 213-224.  DOI: 10.1007/s11390-012-1218-z
    Abstract   PDF(493KB) ( 1570 )   Chinese Summary
    This paper investigates the problem of inconsistent states of radio frequency identification (RFID) tag data caused by incomplete execution of read/write operations during access to RFID tag memory. Passive RFID tags require RF communication to access memory data. This study is motivated by the volatility of RF communication, where instability is caused by intermittent connections and uncertain communication. If a given tag disappears from the communication area of the reader during the reading or writing of tag data, the operation is incomplete, resulting in an inconsistent state of tag data. To avoid this inconsistency, it is necessary to ensure that any operations on tag memory are completed. In this paper, we propose an asynchronous reprocessing model for finalizing any incomplete execution of read/write operations to remove inconsistent states. The basic idea is to resume incomplete operations autonomously by detecting a tag's re-observation from any reader. To achieve this, we present a concurrency control mechanism based on continuous query processing that enables the suspended tag operations to be re-executed. The performance study shows that our model improves the number of successful operations considerably in addition to suppressing inconsistent data access completely.
    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