Ebook: Intelligent Systems and Applications

International Computer Symposium (ICS) is a biennial event and is one of the largest joint international IT symposiums held in Taiwan. Founded in 1973, its aim was to provide a forum for researchers, educators, and professionals to exchange their discoveries and practices, and to explore future trends and applications in computer technologies. ICS 2014 consists of the following 14 workshops.

– Workshop on Algorithms and Computation Theory

– Workshop on Artificial Intelligence and Fuzzy Systems

– Workshop on Computer Architecture, Embedded Systems, SoC, and VLSI/EDA

– Workshop on Computer Networks and Web Service/Technologies

– Workshop on Cryptography and Information Security

– Workshop on Database, Data Mining, Big Data, and Information Retrieval

– Workshop on Digital Content, Digital Life, and Human Computer Interaction

– Workshop on Image Processing, Computer Graphics, and Multimedia Technologies

– Workshop on Information Literacy, e-Learning, and Social Media

– Workshop on Mobile Computing, Wireless Communications, and Vehicular Technologies

– Workshop on Parallel, Peer-to-peer, Distributed, and Cloud Computing

– Workshop on Software Engineering and Programming Languages

– Workshop on Healthcare and Bioinformatics

– Workshop on Information Technology Innovation, Industrial Application and Internet of Things

Totally, we received 308 submissions from Taiwan, China, Japan, Australia, Egypt, Malaysia, Thailand, and USA. The Program Committee finally selected 195 regular papers and 35 poster papers which presentation at the symposium. We would like to express our gratitude to all of the authors, the reviewers, and the attendees for their contributions and participation.

In ICS 2014, we are very pleased to have distinguished invited speakers, who delivered state-of-the-art information on the conference topics:

– Prof. Nabil R. Adam, Rutgers University, USA

– Prof. Yi-Bing Lin, National Chiao Tung University, Taiwan

– Prof. Jurg Gutknecht, Swiss Federal Institute of Technology, Switzerland

– Prof. Lakhmi C. Jain, University of South Australia, Australia

– Prof. Dieter Kratsch, Universit'e de Lorraine, Metz, France

– Prof. Sandy Li, Hong Kong Baptist University, Hong Kong

– Prof. Mark Pegrum, University of Western Australia, Australia

ICS 2014 would not have been possible without the support of many people and organizations that helped in various ways to make it a success. In particular, we would like to thank the Ministry of Education of ROC (especially, the Department of Information and Technology Education), Ministry of Science and Technology of ROC, Computer Society of The Republic of China, Taiwan Association of Cloud Computing, and Tunghai University for their assistance and financial supports. We acknowledge the support of IOS-Press for their continued help by publishing the ICS proceedings. We would like to thank all the members of the conference organising team for their tremendous efforts in making this event a real success.

December 2014

William Cheng-Chung Chu, Tunghai University, Taiwan

Han-Chieh Chao, National Ilan University, Taiwan

Stephen Jenn-Hwa Yang, National Central University, Taiwan

Editors

ICS'14

The minimum routing cost spanning tree problem is a classic NP-hard problem, even for metric graphs. Given an edge-weighted graph, the problem asks for a spanning tree minimizing the sum of distances between all pairs of vertices. In this paper, we investigate a new variant named clustered minimum routing cost tree (CLUSTER MRCT) problem on metric graphs, in which the vertices are partitioned into clusters and the subtrees spanning clusters must be mutually disjoint in a feasible clustered spanning tree. We design a 2-approximation algorithm with time complexity O(n²) for CLUSTER MRCT, where n is the number of vertices of input graph.

Given a graph G = (V, E), a P₂-packing [Pscr ] is a collection of vertex disjoint copies of P₂s in G where a P₂ is a simple path with three vertices and two edges. The MAXIMUM P₂-PACKING problem is to find a P₂-packing [Pscr ] in the input graph G of maximum cardinality. This problem is NP-hard for cubic graphs. In this paper, we give a branch-and-reduce algorithm for the MAXIMUM P₂-PACKING problem in cubic graphs. We analyze the running time of the algorithm using measure-and-conquer and show that it runs in time O^*(1.4366ⁿ) which is faster than previous known exact algorithms where n is the number of vertices in the input graph.

Block graphs are graphs in which every block (biconnected component) is a clique. A graph G = (V, E) is said to be an (unpartitioned) k-probe block graph if there exist k independent sets , 1≤i≤k, such that the graph G′ obtained from G by adding some new edges between certain vertices inside the sets , 1≤i≤k, is a block graph; if the independent sets are given, G is called a partitioned k-probe block graph. In this paper we give good characterizations for 2-probe block graphs, in both unpartitioned and partitioned cases. As an algorithmic implication, partitioned and unpartitioned 2-probe block graphs can be recognized in linear time, improving a recognition algorithm of cubic time complexity previously obtained by Chang et al. (2011) in [3].

In this paper we focus on improving the false positive rate of a bloom filter with a pre-filtering scheme. By applying this scheme on a bloom filter, we can quickly screen out lots of input before entering the bloom filter and hence improve the result of false positives. We demonstrate with experiments that this approach can yield at least 4 times and at most 45 times better results than a standard bloom filter implementation, meanwhile using the same amount of memory requirement as a standard one. The proposed approach, called the pre-filtered bloom filter (PFBF), outperforms existing approaches in most of the cases. Especially, our approach is attractive to those applications which have limited amount of memory with a lot of patterns to check, since, in this case we can get the most improvement out of it.

In this paper, we introduce and study the approximate string matching problem under non-overlapping inversion distance. Given a text t, a pattern p and a non-negative integer k, the goal of the problem is to find all locations in the text t that match the pattern p with at most k non-overlapping inversions. As a result, we use the dynamic programming approach to design an algorithm that solves this problem in O(nm²) time and O(m²) space, where n is the length of the text and m is the length of the pattern.

In this paper, we propose a data placement strategy to deal with the imbalanced workload problem on DataNodes. Basing on computing capability of each node in a heterogeneous Hadoop cluster, the proposed strategy can balance the data that was stored in the DataNode such that the cost of data transfer time can be tremendously reduced. As a result, the Hadoop overall performance can be greatly improved. Experimental results demonstrate that the proposed data placement strategy can highly decrease the execution time and thus improves Hadoop performance in a heterogeneous cluster.

The longest path problem is a generalization of the well known Hamiltonian path problem. It has been shown that the longest path problem is NP-complete. Many researchers try to solve it on some special classes of graphs. Another practical generalization is given two vertices and tries to find a longest path between these two vertices. It is called the end-to-end longest path problem. In this paper, we consider this general problem on a mesh. We generalize a previous work to solve the problem on meshes with one missing vertex in linear time. Further research opportunities and improvements are also suggested.

A one-to-two disjoint-path cover of a graph G is a pair (P₁, P₂) of two vertex-disjoint paths that connect one source to two sinks in G and span G. It is called ε-balanced if |ℓ(P₁)−ℓ(P₂)|=ε, where ℓ(P₁) and ℓ(P₂) denote the lengths of paths P₁ and P₂, respectively. The matching composition network is a family of interconnection networks, each of which connects two components with the same number of vertices by a perfect matching. This paper addresses some properties about one-to-two disjoint-path covers of matching composition networks. Applying the proposed main theorem, a one-to-two ε-balanced disjoint-path cover in some well-known interconnection networks, such as crossed cubes, twisted cubes, locally twisted cubes, etc., can be easily obtained for a given odd integer ε.

A set S of vertices in a graph G=(V,E) is an independent dominating set of G if no two vertices in S are adjacent and every vertex not in S is adjacent to a vertex in S. Suppose every vertex v∊V and every edge e∊E are associated with a cost which is a real number, denoted by c(v) and c(e), respectively. The weighted independent domination problem is to find an independent dominating set D such that its total cost c(D)=Σ_x∊Dc(x)+Σ_x∉Dmin {c(x,y), for y∊D and (x,y)∊E} is minimum. In this paper, we propose a linear time algorithm for solving this problem in series-parallel graphs.

Let χ_i(G) denote the incidence coloring number of a graph G. In this paper, we study the incidence coloring on generalized Petersen graphs GP(n,k). We first assure that 4≤χ_i(GP(n,k))≤5. Furthermore, we provide the following results: (i) χ_i(GP(n,k))=5 if n is odd, (ii) χ_i(GP(n,2))=5, and (iii) χ_i(GP(n,k))=4 if n≡0(mod 4) and k is odd.

Cayley graphs provide a group-theoretic model for designing and analyzing symmetric interconnection networks. In this paper, we give a sufficient condition for the existence of m vertex-disjoint shortest paths from one source vertex to other m (not necessarily distinct) destination vertices in a Cayley graph of an abelian group, where m≤n and n is the cardinality of a (group) generator of the abelian group. In addition, when the condition holds, the m vertex-disjoint shortest paths can be constructed in O(mn) time, which is optimal in the worst case when O(n)≤ the order of diameter. By applying our results, we can easily obtain the necessary and sufficient conditions, which can be verified in nearly optimal time, for the existence of all shortest vertex-disjoint paths in generalized hypercubes.

An n-dimensional folded hypercube FQ_n is an attractive variance of an n-dimensional hypercube Q_n, which is obtained by a standard hypercube with some extra edges established between its vertices. An n-dimensional folded hypercube (FQ_n for short) for any odd n is known to be bipartite. In this paper, let f be a faulty vertex in FQ_n. It has been shown that (1) Every edge of FQ_n−{f} lies on a fault-free cycle of every even length l with 4≤l≤2ⁿ−2 where n≥3; (2) Every edge of FQ_n−{f} lies on a fault-free cycle of every odd length l with n+1≤l≤2ⁿ−1, where n≥2 is even. In terms of every edge lies on a fault-free cycle of every odd length in FQ_n−{f}, our result extend the result of Cheng et al. (2013) where odd cycle length up to 2ⁿ−3.

In this research, we propose the nearest neighbor searching problem and we give an algorithm to solve the problem. Roughly speaking, the nearest neighbor searching problem is defined as follows: Give a text string T=t₁t₂…t_n and a pattern string P=p₁p₂…p_m, find all substrings in T whose edit distances with respect to P are the smallest among all substrings of T. Our algorithm is based upon two concepts: (1) There is a special property of dynamic programming matrix which is used to solve the approximate string matching problem. We call this property the small change property. (2) Values on the D matrix can be computed along the diagonals. Our experimental results showed that our algorithm is quite efficient.

In the paper, we propose the distributed detection and identification multi-agent system (DDIMAS) framework that is the first attempt to apply in solving distributed denial of service (DDoS) problem. It includes three stages which are information heuristic rule, meta-heuristic algorithm and backward and forward search (BFS) rule, respectively. Moreover, the framework is a flexible architecture that can incorporate into other algorithms or rules to improve the overall performance. From the evaluation design, the experiment results show that our method is with higher detection rate and better accuracy than standard repositories. The proposed framework resolves issues in other swarm optimization algorithms and reveals that the performance of DDIMAS is better than existing methods and the adaptive meta-heuristic algorithm framework outperforms other methods for detecting DDoS attacks.

This paper proposes a novel Takagi–Sugeno–Kang-type (TSK-type) neuro-fuzzy system (NFS), which utilizes the artificial bee colony (ABC) evolutionary algorithm for parameter optimization. The ABC evolutionary algorithm was developed based on imitating foraging behavior of natural bees for numerical optimization problems, and it has been proved to outperform other metaheuristic approaches on different constrain optimization problems in previous studies. The proposed NFS in this paper adopts an adaptive clustering method to generate fuzzy rules for determining the system architecture, and the TSK-type reasoning is employed for the consequent part of each rule. Subsequently, all free parameters in the NFS designed, including the premise and the consequent parameters, will be optimized by ABC algorithm. This study compares the performance of ABC algorithm with that of Genetic Algorithm (GA), Particle Swarm Optimization (PSO) and Differential Evolution (DE). The simulation results show that the performance of ABC algorithm is superior to that of the mentioned algorithms for solving dynamic system problems.

In this paper, we introduce a novel linear discriminate analysis (LDA) ensemble classifier utilizing the Mindo as a brain-computer interface (BCI) device to deal with the problem of motor imagery classification. With regard to the composition of the proposed system, we combine filter bank, sub-band common spatial pattern (SBCSP), LDA together for extracting features of EEG data and classifying the motor imagery with left or right states. In addition, we also employ a gradient descent (GD) algorithm to find the best weight associated with probability fusion function. This novel architecture not only boosts the accuracy of classification but maintains the computational efficiency of the system. Therefore, the proposed LDA-ensemble framework is able to be satisfied with each subject as demonstrated in Section III.

In this work, dynamic characteristic of a new amorphous silicon gate (ASG) driver circuit is optimized by using multi-objective evolutionary algorithm (MOEA) and hydrogenated amorphous silicon (a-Si:H) TFT circuit simulator on the unified optimization framework (UOF). The ASG driver circuit consisting of 14 a-Si:H TFTs is optimized for the given specifications of the fall time < 3 μs and the ripple voltage < −9 V with simultaneously minimizing the total layout area. More than 50% reductions on the falling time of the ASG driver circuit have been achieved by using the proposed optimization methodology together with a novel 3-level clock driving technique.

In this paper, we present a study of asset allocation using genetic algorithms. This method extends a previous version of a stock selection model using Genetic Algorithms (GA) for solving the problem of asset allocation. The GA is used for optimization of model parameters, feature selection as well as the construction of the Pareto front. On top of that, we proposed another GA to search for the optimal allocation of assets. We then present an investigation for this line of research using financial data of various industrial sectors in Taiwan's stock market. Our experimental results show that our proposed method is capable of significantly outperforming the benchmark and the canonical Markowitz method for asset allocation. Based upon these promising results, we expect this GA methodology to advance the current state of research in soft computing for the real-world applications in asset-allocation.

Traditional robots locomotion relied on the kinetic analysis to design a set of instructions to control the robot. When the surrounding environment changed, human had to develop a code to deal with the changes in the environment. Using evolutionary algorithm to solve this problem, evolutionary robot can adapt its behavior to fit the current environment immediately, which is the advantage of evolutionary robots in saturations that no human can help.

Evolutionary robot research has become an interesting topic recently and this research specifically focuses on evolution and learning. Evolution is the adaptation of robots to the environment. Learning is a task-oriented process whereby the robot gains the ability to achieve a given goal in the environment. In this paper, we apply traditional GA (Genetic Algorithm) and design the BRMA (Biomorphic Robot Memetic Algorithm) to control the robot. Our biomorphic robots have four legs and each leg has several joints. We also test the algorithms on a partially breakdown robot. Our study is a multi-objective evolutionary task since the robot has to evolve to fit several indexes.

In our experiments, we set up a beacon light as a target, and the robot evolves to move quickly and smoothly toward the target. We adopt online evolutionary algorithms and test them on the quadrupedal robot. The experimental results show that the robot, from totally random behaviors, can adjust its actions to move quickly and smoothly toward the target.

In this study, we propose a method for the quantitative analysis of exercise ventilation signal that is an important diagnostic tool to evaluate the prognosis of chronic heart failure (CHF) patients. An autoregressive (AR) model is used to filter the breath-by-breath measurement of ventilation. Then the signals before reaching the most ventilation are decomposed into intrinsic mode functions (IMF) by Hilbert-Huang transform (HHT). The average amplitude of the second IMF component AmpC2 is used as an indicator about pulmonary function for chronic heart failure patients.

The general-purpose graphic processing unit (GPGPU) is a popular accelerator for general applications such as scientific computing because the applications are massively parallel and the significant power of parallel computing inheriting from GPUs. However, distributing workload among the large number of cores as the execution configuration in a GPGPU is currently still a manual trial-and-error process. Programmers try out manually some configurations and might settle for a sub-optimal one leading to poor performance and/or high power consumption. The state-of-the-art methods for addressing this issue are mainly based on the heavy profiling of computation kernels. This paper presents an auto-tuning approach for GPGPU applications with the performance and power models. First, a model-based analytic approach for estimating performance and power consumption of kernels is proposed. Second, an auto-tuning framework is proposed for automatically obtaining a near-optimal configuration for a kernel computation. In this work, we formulate the problem as the constraint optimization and solve it using the optimization algorithms. Experimental results show the fidelity of our proposed models for performance and energy consumption, and prove the rationality of adopting the auto-tuning method with the models for minimizing overhead. Further, the efficiency of tuning procedure and the quality of outcome configuration in our proposed method show the superiorities over the previous methods.