Bimonthly    Since 1986
ISSN 1004-9037
Indexed in:
Publication Details
Edited by: Editorial Board of Journal of Data Acquisition and Processing
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
  • Table of Content
      10 September 2008, Volume 23 Issue 5   
    For Selected: View Abstracts Toggle Thumbnails
    Special Section on Algorithms and Complexity
    t-Private and t-Secure Auctions
    Markus Hinkelmann, Andreas Jakoby, and Peer Stechert
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 694-710 . 
    Abstract   PDF(645KB) ( 1276 )  
    In most of the auction systems the values of bids are known to the auctioneer. This allows him to manipulate the outcome of the auction. Hence, one might be interested in hiding these values. Some cryptographically secure protocols for electronic auctions have been presented in the last decade. Our work extends these protocols in several ways. On the basis of garbled circuits, i.e., encrypted circuits, we present protocols for sealed-bid auctions that fulfill the following requirements: 1) protocols are information-theoretically $t$-private for {\em honest but curious parties}; 2) the number of bits that can be learned by {\em malicious adversaries} is bounded by the output length of the auction; 3) the computational requirements for participating parties are very low: only random bit choices and bitwise computation of the {\tt XOR}-function are necessary. Note that one can distinguish between the protocol that generates a garbled circuit for an auction and the protocol to evaluate the auction. In this paper we address both problems. We will present a $t$-private protocol for the construction of a garbled circuit that reaches the lower bound of $2t+1$ parties, and a more randomness efficient protocol for $(t+1)^2$ parties. Finally, we address the problem of bid changes in an auction.
    Design and Performance Evaluation of Sequence Partition Algorithms
    Bing Yang, Jing Chen, En-Yue Lu$^3, and Si-Qing Zheng$^{2,4}$
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 711-718 . 
    Abstract   PDF(911KB) ( 1422 )  
    Tradeoffs between time complexities and solution optimalities are important when selecting algorithms for an NP-hard problem in different applications. Also, the distinction between theoretical upper bound and actual solution optimality for realistic instances of an NP-hard problem is a factor in selecting algorithms in practice. We consider the problem of partitioning a sequence of $n$ distinct numbers into minimum number of monotone (increasing or decreasing) subsequences. This problem is NP-hard and the number of monotone subsequences can reach $\big\lfloor \sqrt{2n+\frac 14}-\frac 12 \big\rfloor$ in the worst case. We introduce a new algorithm, the modified version of the Yehuda-Fogel algorithm, that computes a solution of no more than $\big\lfloor \sqrt{2n+\frac 14}-\frac 12 \big\rfloor$ monotone subsequences in $O(n^{1.5})$ time. Then we perform a comparative experimental study on three algorithms, a known approximation algorithm of approximation ratio 1.71 and time complexity $O(n^3)$, a known greedy algorithm of time complexity $O(n^{1.5}\log n)$, and our new modified Yehuda-Fogel algorithm. Our results show that the solutions computed by the greedy algorithm and the modified Yehuda-Fogel algorithm are close to that computed by the approximation algorithm even though the theoretical worst-case error bounds of these two algorithms are not proved to be within a constant time of the optimal solution. Our study indicates that for practical use the greedy algorithm and the modified Yehuda-Fogel algorithm can be good choices if the running time is a major concern.
    Some Aspects of Synchronization of DFA
    Avraham Trahtman
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 719-727 . 
    Abstract   PDF(299KB) ( 1460 )  
    A word $w$ is called synchronizing (recurrent, reset, directable) word of deterministic finite automata (DFA) if $w$ brings all states of the automaton to a unique state. According to the famous conjecture of Cerny from 1964, every $n$-state synchronizing automaton possesses a synchronizing word of length at most $(n-1)^2$. The problem is still open. It will be proved that the Cerny conjecture holds good for synchronizing DFA with transition monoid having no involutions and for every $n$-state ($n>2$) synchronizing DFA with transition monoid having only trivial subgroups the minimal length of synchronizing word is not greater than $(n-1)^2/2$. The last important class of DFA involved and studied by Schutzenberger is called {\it aperiodic}; its automata accept precisely star-free languages. Some properties of an arbitrary synchronizing DFA were established. See http://www.cs.biu.ac.il/˜trakht/syn.html.
    Searching a Polygonal Region by Two Guards
    Xue-Hou Tan and Bo Jiang
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 728-739 . 
    Abstract   PDF(1044KB) ( 1734 )  
    We study the problem of searching for a mobile intruder in a polygonal region $P$ by two guards. The objective is to decide whether there should exist a {\it search schedule} for the two guards to detect the intruder, no matter how fast the intruder moves, and if so, generate a search schedule. During the search, the two guards are required to walk on the boundary of $P$ continuously and be mutually visible all the time. We present a characterization of the class of polygons searchable by two guards in terms of non-redundant components, and thus solve a long-standing open problem in computational geometry. Also, we give an optimal $O(n)$ time algorithm to determine the two-guard searchability in a polygon, and an $O(n \log n + m)$ time algorithm to generate a search schedule, if it exists, where $n$ is the number of vertices of $P$ and $m$ $(\le n^{2})$ is the number of search instructions reported.
    On Constrained Facility Location Problems
    Wei-Lin Li, Peng Zhang, and Da-Ming Zhu
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 740-748 . 
    Abstract   PDF(428KB) ( 1987 )  
    Approximation Algorithms for 3D Orthogonal Knapsack
    Florian Diedrich, Rolf Harren, Klaus Jansen, Ralf Thöle, and Henning Thomas
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 749-762 . 
    Abstract   PDF(667KB) ( 1385 )  
    We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9+ and 8+, as well as an algorithm with approximation ratio 7+ that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z-axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6+ and 5+, respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio $29/4$, improving the previously best known result of $45/4$.
    Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs
    Jian-Xin Wang, Xiao-Shuang Xu, and Jian-Er Chen
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 763-768 . 
    Abstract   PDF(187KB) ( 1401 )  
    The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant > 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size , our algorithm constructs a vertex cover of size , satisfying .
    Analysis and Implementation of an Open Programmable Router Based on Forwarding and Control Element Separation
    Wei-Ming Wang, Li-Gang Dong, and Bin Zhuge
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 769-779 . 
    Abstract   PDF(962KB) ( 2099 )  
    A router architecture based upon ForCES (Forwarding and Control Element Separation), which is being standardized by IETF ForCES working group, gains its competitive advantage over traditional router architectures in flexibility, programmability, and cost-effectiveness. In this paper, design and implementation of a ForCES-based router (ForTER) is illustrated. Firstly, the implementation architecture of ForTER is discussed. Then, a layered software model, which well illustrates ForCES features, is proposed. Based on the model, design and implementation of Control Element (CE) and Forwarding Element (FE) in ForTER are introduced in detail. Moreover, security for ForTER is considered and an algorithm to prevent DoS attacks is presented. Lastly, experiments of ForTER are illustrated for routing and running routing protocols, network management, DoS attack prevention, etc. The experimental results show the feasibility of the ForTER design. Consequently, the ForTER implementation basically testifies the feasibility of ForCES architecture and some IETF ForCES specifications.
    Scalable Base-Station Model-Based Multicast in Wireless Sensor Networks
    Shao-Liang Peng, Shan-Shan Li, Lei Chen, Yu-Xing Peng, and Nong Xiao
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 780-791 . 
    Abstract   PDF(9812KB) ( 1793 )  
    Multicast is essential for wireless sensor network (WSN) applications. Existing multicast protocols in WSNs are often designed in a P2P pattern, assuming small number of destination nodes and frequent changes in network topologies. In order to truly adopt multicast in WSNs, we propose a base-station model-based multicast, SenCast, to meet the general requirements of applications. SenCast is scalable and energy-efficient for large group communications in WSNs. Theoretical analysis shows that SenCast is able to approximate the Minimum Nonleaf Nodes (MNN) problem to a ratio of $\ln|R|$ $(R$ is the set of all destinations), the best known lowest bound. We evaluate our design through comprehensive simulations and prototype implementations on Mica2 motes. Experimental results demonstrate that SenCast outperforms previous multicast protocols including the most recent work uCast.
    Parallel Algorithm Core: A Novel IPSec Algorithm Engine for Both Exploiting Parallelism and Improving Scalability
    Dong-Nian Cheng, Yu-Xiang Hu, and Cai-Xia Liu
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 792-805 . 
    Abstract   PDF(598KB) ( 2193 )  
    To deal with the challenges of both {\it computation-complexity} and {\it algorithm-scalability} posed to the design of an IPSec engine, we develop PAC (parallel algorithm core), called PAC, employed in an IPSec engine, which can meet requirements of both exploiting parallelism existing in IPSec packets and offering scalability in both the scales and types of cryptographic algorithms. With three kinds of parallelism and two kinds of transparency defined, a novel hierarchy of the specifically-designed parallel structure for PAC is presented, followed by corresponding mechanisms. With a simulation, the scalability of PAC is examined. For the purpose of performance evaluation, a {\it Quasi Birth-and-Death} (QBD) process is then established to model a simplified version of the proposed PAC. Performance evaluation of PAC in terms of two representative measures, throughput and mean packet waiting time, is numerically investigated. A comparison study is done on a simulation basis. Conclusions are finally drawn for providing a helpful guideline for both the design and implementation of our proposal.
    Uplink Scheduling for Supporting Real Time Voice Traffic in IEEE 802.16 Backhaul Networks
    Lizhong Dai and Dongmei Zhao
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 806-814 . 
    Abstract   PDF(476KB) ( 1683 )  
    In this paper we propose simple enhancements to the bandwidth (BW) request messages in IEEE 802.16 for supporting real-time packet voice traffic. Three different BW request formats are proposed, each requiring a different amount of latency information about the buffered packets at the SS. On this basis, packet scheduling schemes are proposed for the BS to make resource allocations for real-time traffic. Our results show that the proposed BW request and scheduling schemes achieve significantly lower packet loss probability than the standard IEEE 802.16 BW request with round robin scheduling. The results further show that there is an optimum point about how much delay information the SS should report to the BS in order to best utilize the uplink resources while the SS provides satisfactory real-time performance for the voice traffic.
    Flood Avoidance Mechanisms for Bridged Resilient Packet Rings
    Pisai Setthawong and Surat Tanterdtid
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 815-824 . 
    Abstract   PDF(1803KB) ( 1282 )  
    Resilient Packet Ring (RPR), or the Standard IEEE 802.17, is a new IP-based network technology proposed to replace SONET/SDH in metropolitan area networks. RPR is well-adapted to handle multimedia traffic and is efficient. However, when RPR networks are bridged, inter-ring packets, or packets with the destination on a remote RPR network other than on the source network, are flooded on the source and the destination networks, and also on the path of the intermediate networks between the source and the destination networks. This decreases the available bandwidth for other traffic in those networks and is inefficient. As a result, we propose two solutions based on topology discovery, global topology discovery (GTD) and enhanced topology discovery (ETD), that prevent the flooding of inter-ring packets. GTD enables the bridges to determine the next-hop bridge for each destination. ETD enables the source node to determine a default ringlet, so that packets reach the next-hop bridge without flooding the source network. The proposed solutions were analyzed and the overhead bandwidth and stabilization time were shown to be bounded. Simulations performed showed that the proposed solutions successfully avoid flooding and achieve optimal efficiency in the intermediate and destination networks, and in the source networks with one bridge.
    A Class of Key Predistribution Schemes Based on Orthogonal Arrays
    Jun-Wu Dong, Ding-Yi Pei, and Xue-Li Wang
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 825-831 . 
    Abstract   PDF(525KB) ( 2228 )  
    Pairwise key establishment is a fundamental security service in sensor networks; it enables sensor nodes to communicate securely with each other using cryptographic techniques. In order to ensure this security, many approaches have been proposed recently. One of them is to use key predistribution schemes (KPSs) by means of combinatorial designs. In this paper, we use the Bush's construction of orthogonal arrays to present a class of key predistribution schemes for distributed sensor networks. The secure connectivity and resilience of the resulting sensor network are analyzed. This KPS constructed in our paper has some better properties than those of the existing schemes.
    A Provable Secure ID-Based Explicit Authenticated Key Agreement Protocol Without Random Oracles
    Hai-Bo Tian, Willy Susilo, Yang Ming, and Yu-Min Wang
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 832-842 . 
    Abstract   PDF(495KB) ( 2270 )  
    In this paper, we present an identity-based {\it explicit authenticated} key agreement protocol that is provably secure without random oracles. The protocol employs a new method to isolate a session key from key confirmation keys so that there is no direct usage of hash functions in the protocol. The protocol is proved secure without random oracles in a variant of Bellare and Rogaway style model, an exception to current proof method in this style model in the ID-based setting. We believe that this key isolation method is novel and can be further studied for constructing more efficient protocols.
    Some Notes on Generalized Cyclotomic Sequences of Length pq
    Zhi-Xiong Chen and Sheng-Qiang Li
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 843-850 . 
    Abstract   PDF(665KB) ( 1666 )  
    We review the constructions of two main kinds of generalized cyclotomic binary sequences with length {\it pq} (the product with two distinct primes). One is the White-generalized cyclotomic sequences, the other is the Ding-Helleseth(DH, for short)-generalized cyclotomic sequences. We present some new pseudo-random properties of DH-generalized cyclotomic sequences using the theory of character sums instead of the theory of cyclotomy, which is a conventional method for investigating generalized cyclotomic sequences.
    Palmprint Recognition by Applying Wavelet-Based Kernel PCA
    Murat Ekinci and Murat Aykut
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 851-861 . 
    Abstract   PDF(2940KB) ( 3439 )  
    This paper presents a wavelet-based kernel Principal Component Analysis (PCA) method by integrating the Daubechies wavelet representation of palm images and the kernel PCA method for palmprint recognition. Kernel PCA is a technique for nonlinear dimension reduction of data with an underlying nonlinear spatial structure. The intensity values of the palmprint image are first normalized by using mean and standard deviation. The palmprint is then transformed into the wavelet domain to decompose palm images and the lowest resolution subband coefficients are chosen for palm representation. The kernel PCA method is then applied to extract non-linear features from the subband coefficients. Finally, similarity measurement is accomplished by using weighted Euclidean linear distance-based nearest neighbor classifier. Experimental results on PolyU Palmprint Databases demonstrate that the proposed approach achieves highly competitive performance with respect to the published palmprint recognition approaches.
    Free-Form Deformation with Rational DMS-Spline Volumes
    Gang Xu, Guo-Zhao Wang, and Xiao-Diao Chen
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 862-873 . 
    Abstract   PDF(8049KB) ( 1985 )  
    In this paper, we propose a novel free-form deformation (FFD) technique, RDMS-FFD (Rational DMS-FFD), based on rational DMS-spline volumes. RDMS-FFD inherits some good properties of rational DMS-spline volumes and combines more deformation techniques than previous FFD methods in a consistent framework, such as local deformation, control lattice of arbitrary topology, smooth deformation, multiresolution deformation and direct manipulation of deformation. We first introduce the rational DMS-spline volume by directly generalizing the previous results related to DMS-splines. How to generate a tetrahedral domain that approximates the shape of the object to be deformed is also introduced in this paper. Unlike the traditional FFD techniques, we manipulate the vertices of the tetrahedral domain to achieve deformation results. Our system demonstrates that RDMS-FFD is powerful and intuitive in geometric modeling.
    Guiding Attention by Cooperative Cues
    KangWoo Lee
    Journal of Data Acquisition and Processing, 2008, 23 (5 ): 874-884 . 
    Abstract   PDF(15258KB) ( 1359 )  
    A common assumption in visual attention is based on the rationale of ``limited capacity of information processing''. From this view point there is little consideration of how different information channels or modules are cooperating because cells in processing stages are forced to compete for the limited resource. To examine the mechanism behind the cooperative behavior of information channels, a computational model of selective attention is implemented based on two hypotheses. Unlike the traditional view of visual attention, the cooperative behavior is assumed to be a dynamic integration process between the bottom-up and top-down information. Furthermore, top-down information is assumed to provide a contextual cue during selection process and to guide the attentional allocation among many bottom-up candidates. The result from a series of simulation with still and video images showed some interesting properties that could not be explained by the competitive aspect of selective attention alone.
SCImago Journal & Country Rank

ISSN 1004-9037


Editorial Board
Author Guidelines
Journal of Data Acquisition and Processing
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China

E-mail: info@sjcjycl.cn
  Copyright ©2015 JCST, All Rights Reserved