2007 Technical Report

Code

TR-IIS-07-001

Subject / Author / Abstract

Consistency and Feasibility of Flexible Demand-Supply Constraints
P. H. Tsai and J. W. S. Liu

View

Fulltext

Code

TR-IIS-07-002

Subject / Author / Abstract

Automatic Derivation of Compositional Rules in Automated Compositional Reasoning
Bow-Yaw Wang

Soundness of compositional reasoning rules depends on computational models and sometimes is rather involved. Since it is tedious to establish new rules, verifiers are forced to mould verification problems into a handful of proof rules available to them. In this paper, a syntactic approach to establishing soundness of proof rules in automated compositional reasoning is shown. Not only can our work justify all proof rules known to us automatically, but also derive new circular rules by intuitionistic reasoning without human intervention. Practitioners can now develop their own rules in automated compositional reasoning through learning rather easily.

View

Fulltext

Code

TR-IIS-07-003

Subject / Author / Abstract

Exact Collision Detection for Scaled Convex Polyhedral Objects
Jing-Sin Liu, Y.H. Tsao, Wen-Yang Ku, Wen-Hwa Pan and Y.-Z. Chang

This paper addresses the following collision detection problem: determine the collision status for a pair of stationary convex polyhedral objects whose allowed deformation is uniform but arbitrary scaling of vertices within given upper and lower limits. We present an exact overlap checking method based on the characterization of all contact configurations. The set of all scaling pairs that two objects contact each other externally is characterized by a decending piecewise linear curve where the switching point of this piecewise linear curve represents the scaling pair as long as the contact configuration changes feature. Then, using this piecewise linear curve, the rectangle of allowable scaling pairs is partitioned into an exact overlap and an exact non-overlap sub-regions. A corresponding decision curve for exact overlap checking is constructed from this scaling decision curve via parametric intersection points of each polyhedron with the shortest path between inner ellipsoids of deformation bounds. Index Terms - collision detection, convex polyhedra, deformation, scaling

View

Fulltext

Code

TR-IIS-07-004

Subject / Author / Abstract

Point-of-Care Support for Error-Free Medication Process
J. W. S. Liu, C. S. Shih, P. H. Tsai, H. C. Yeh, P. C. Hsiu, C. Y. Yu, and W. H. Chang

Technological advances and critical needs have led to a variety of smart devices designed for prevention and reduction of medication errors. The focus of this paper is on devices and tools that support medication administration for this purpose. They include smart medication carts, robots and dispensers for professionals, as well as smart dispensers for naïve users. The paper describes device architectures, interfaces and support environment needed to increase the effectiveness of such devices in prevention of medication errors, as well as missing standards that will enable their integration in medication process tool chains and their wide spread use. Copyright @ February 2007

View

Fulltext

Code

TR-IIS-07-005

Subject / Author / Abstract

Distributed Video Coding Based on Coding Mode-aided Motion Compensation and Robust Media Hashing
Li-Wei Kang and Chun-Shien Lu

To meet the requirement of distributed video coding (DVC) in resource-limited sensor networks, Wyner-Ziv theorem-based source coding with side information only available at the decoder states that an intraframe encoder with interframe decoder system can achieve comparable coding efficiency of a conventional interframe encoder and interframe decoder system. In this paper, firstly, a block discrete cosine transform (DCT)-based Wyner-Ziv video codec with coding mode-aided motion compensation at the decoder is proposed, denoted by “ProposedDVC1.” The major characteristic is that for motion compensation at the decoder, side information generation and error correcting code (ECC) decoding are jointly performed to find the final side information. Similar to most existing Wyner-Ziv video coding systems, “ProposedDVC1” is with light encoder and heavy decoder. However, in some video communication scenarios, low complexity in both the encoder and decoder is required. In this study, another Wyner-Ziv video codec based on robust media hashing without needing to perform motion estimation at both the encoder and decoder is proposed, denoted by “ProposedDVC2.” The particular contribution of ProposedDVC2 is its low complexity in both the encoder and decoder. Simulation results demonstrate the achievable coding efficiency of ProposedDVC2 is comparable with that of ProposedDVC1 while the complexity of ProposedDVC2 is much lower than that of ProposedDVC1. In addition, both ProposedDVC1 and ProposedDVC2 need no feedback channel. Keywords: distributed video coding, Wyner-Ziv video coding, motion compensation, media hash, video communication, video sensor network.

View

Fulltext

Code

TR-IIS-07-006

Subject / Author / Abstract

Video JET: Packet Loss-Resilient Video Joint Encryption and Transmission based on Media-Hash-Embedded Residual Data
Shih-Wei Sun, Jan-Ru Chen, Chun-Shien Lu, and Pao-Chi Chang

Media encryption technologies actively play the first line of defense in securing the access of multimedia data. Traditional cryptographic encryption can achieve provable security but is unfortunately sensitive to a single bit error, which will cause an unreliable packet to be dropped creating packet loss. In order to achieve robust media encryption, the requirement of error resilience can be achieved with error-resilient media transmission. This study proposes a video joint encryption and transmission (video JET) scheme by exploiting media hash-embedded residual data to achieve motion estimation and compensation for recovering lost packets, while maintaining format compliance and cryptographic provable security. Interestingly, since video block hash preserves the condensed content to facilitate search of similar blocks, motion estimation is implicitly performed through robust media hash matching – which is the unique characteristic of our method. We analyze and compare the performance of resilience to (bursty) packet loss between the proposed method and forward error correction (FEC), which has been extensively employed to protect video packets over error-prone networks. The feasibility of our packet loss-resilient video JET approach is further demonstrated through experimental results. Keywords: (Selective) Encryption, Embedding, Error concealment, Error resilience, Media hashing, Motion estimation/compensation, Packet loss

View

Fulltext

Code

TR-IIS-07-007

Subject / Author / Abstract

Component Model for SISARL Devices and Systems
T. Y. Chen, T. S. Chou, P. H. Tsai, A. Thamizhmani, T. W. Kuo, C. S. Shih, and J. W. S. Liu

This paper describes a component model, called SISARL model. It is the basis of component-based approach to building families of smart devices and systems that enhance life quality and well being of elderly individuals. In addition to providing the traditional view of hardware, firmware and software components, as do existing component models, SISARL model also provides developers with an operational view. The view enables the developer to specify device-user interactions as executable workflows and allows the device operations and user actions to be experimented with and their correctness ascertained throughout the design, development and assessment process. After describing the elements and usages of the model, the paper presents a simulation environment for this purpose. Categories and Subject Descriptors: J.7 [Computers in Other Systems] D.2.2 [Design Tools and Techniques]: General Terms: Design, Experimentation, Human Factors Keywords: Component-based design, Modules and interfaces, Activities and workflows, Operational specifications, Simulation environment

View

Fulltext

Code

TR-IIS-07-008

Subject / Author / Abstract

A Language Modeling Approach to Atomic Human Action Recognition
Yu-Ming Liang, Sheng-Wen Shih, Arthur Chun-Chieh Shih, Hong-Yuan Mark Liao, and Cheng-Chung Lin

Visual analysis of human behavior has generated considerable interest in the field of computer vision because it has a wide spectrum of potential applications. A human behavior analysis system must address three main tasks: object detection, human tracking, and understanding behavior. In this paper, we propose a language modeling framework for handling the third task. The framework is comprised of two modules: a posture labeling module, and an atomic action learning and recognition module. A posture template selection algorithm is developed based on a modified shape context matching technique. The posture templates form a codebook that is used to convert input posture sequences into training symbol sequences or recognition symbol sequences. Finally, a variable-length Markov model technique is applied to learn and recognize the input symbol sequences of atomic actions. Experiments on real data demonstrate the efficacy of the proposed system.

View

Fulltext

Code

TR-IIS-07-009

Subject / Author / Abstract

On Using Probabilistic Forwarding to Improve HEC-based Data Forwarding in Opportunistic Networks
Ling-Jyh Chen, Cheng-Long Tseng, and Cheng-Fu Chou

As the number of opportunistic networking applications continues to surge, the need for an effective routing scheme that can accommodate the various types of intricate behavior observed in opportunistic networks is becoming increasingly urgent. In this paper, we propose the HEC-PF scheme, an enhancement of our previous H-EC scheme for effective data forwarding in opportunistic networks. The enhanced scheme modifies the aggressive forwarding phase of the H-EC scheme by implementing a new Probabilistic Forwarding feature, which decides whether to forward a message to a newly encountered node based on the delivery probability. Using simulations as well as realistic network traces, we evaluate the performance of the proposed scheme in terms of delivery latency and completion ratio. The results show that the HEC-PF scheme outperforms the EC and H-EC schemes in all test cases, and the performance gain is even more substantial when network connectivity is extremely poor. By varying the parameters of the HEC-PF scheme, we show that its completion ratio improves as the maximum forwarding distance or the hop distance considered when calculating the delivery probability increases. The effectiveness of the HEC-PF scheme makes it an ideal solution that goes a long way toward ensuring effective data delivery in opportunistic networks. Keywords: Opportunistic Networks; Routing; Probabilistic Forwarding; Erasure Coding; H-EC Data Forwarding

View

Fulltext

Code

TR-IIS-07-010

Subject / Author / Abstract

ON THE ACCURACY OF TRANSMEMBRANE HELIX PREDICTION METHODS USING AN UPDATED BENCHMARK
Allan Lo, Hua-Sheng Chiu, Ting-Yi Sung, Wen-Lian Hsu

The prediction of transmembrane (TM) helix and topology is an important field of bioinformatics owing to the difficulties in obtaining high-resolution structures of membrane proteins. Many methods have been developed and several evaluations have compared the performance of individual methods using benchmarks from various sources. We present an analysis of a popular evaluation method by Kernytsky and Rost, which is created using data sets from more than six years ago. Our analysis shows that the benchmark contains data that have substantial disagreements in comparison with the current annotations in SwissProt Release 54.1. Furthermore, the benchmark also contains issues such as annotations of low reliability, sequence redundancy, and presence of signal peptides. We perform updating and cleansing of the above issues in the benchmark, and evaluate eleven widely used methods, including SVMtop, a hierarchical classification method based on support vector machines (SVM). The results show that SVMtop is ranked highly among the top-performing methods for helix prediction, correctly predicting the location of helices for more than 80% of the updated benchmark. Given the discrepancies and noises in the original benchmark, it should be used with discretion for assessing the performance of TM helix predictions. The analysis also implies that there is an urgent need for creating a new benchmark for an accurate and objective comparison. The updated benchmark is available for public use at http://bio-cluster.iis.sinica.edu.tw/~bioapp/SVMtop/dataset.htm. Keywords membrane protein, transmembrane helix, topology prediction, support vector machines, structure prediction

View

Fulltext

Code

TR-IIS-07-011

Subject / Author / Abstract

PPWeb: A Peer-to-Peer Approach for Web Surfing On the Go
Ling-Jyh Chen and Ting-Kai Huang

With wireless technologies extending to every part of our daily lives, mobile networking applications are becoming increasingly popular for accessing the Internet. Among them, web surfing is one of the most important applications because the World Wide Web has accelerated the dissemination of information and knowledge via the Internet unencumbered by geographic boundaries. In this paper, we propose a peer-to-peer approach, called PPWeb, for mobile web surfing. Unlike traditional approaches, the proposed scheme implements a Collaborative Forwarding algorithm that takes advantage of opportunistic wireless connections, thereby improving network capacity by exploiting the diversity of network mobility. Using simulations as well as real-world network scenarios, we demonstrate that the proposed scheme provides a better web surfing service than traditional schemes, and thus facilitates more effective web surfing on the go.

View

Fulltext

Code

TR-IIS-07-012

Subject / Author / Abstract

TJ²aEM: Targeted Aggressive Extrapolation Method for Accelerating the EM Algorithm
Han-Shen Huang, Bo-Hou Yang, and Chun-Nan Hsu

The Expectation-Maximization (EM) algorithm is one of the most popular algorithms for parameter estimation from incomplete data, but its convergence can be slow for some large-scale or complex machine learning problems. Extrapolation methods can effectively accelerate EM, but to ensure stability, the learning rate of extrapolation must be compromised. This paper describes the TJ²aEM algorithm, a targeted aggressive extrapolation method that can make much more aggressive extrapolations without causing instability problems. We show that for a wide variety of probabilistic models, TJ²aEM can converge many times faster than other acceleration methods under different data distributions and initial conditions. In addition to EM, TJ²aEM can also be applied to other bound optimization methods, including generalized iterative scaling, non-negative matrix factorization and concave-convex procedure. Keywords: Expectation-Maximization (EM), Aitken Acceleration, Extrapolation, Optimization, Triple-Jump Acceleration

View

Fulltext

Code

TR-IIS-07-013

Subject / Author / Abstract

Global and Componentwise Extrapolations for Accelerating Training of Bayesian Networks and Conditional Random Fields
Chun-Nan Hsu, Han-Shen Huang, Bo-Hou Yang, and Yu-Ming Chang

The triple jump extrapolation method is an effective approximation of Aitken’s acceleration that can accelerate the convergence of many parameter learning algorithms, including EM and generalized iterative scaling. It has two options — global and componentwise extrapolation. Empirical studies showed that neither can dominate the other in all cases and it is not known which one is better under what condition. In this paper, we investigate this problem and conclude that, when the Jacobian is (block) diagonal, componentwise extrapolation will be more effective. We derive two hints that allow us to determine the block diagonality. The first hint is that when we have a highly sparse data set, the Jacobian of the EM mapping for training a Bayesian network will be block diagonal. The second hint is that the block diagonality of the Jacobian of the GIS mapping for training CRF is negatively correlated with the strength of feature dependencies. We empirically verify these hints with controlled and real-world data sets. The results show that our hints can accurately predict which method will be superior. The results also show that both global and componentwise extrapolation can provide substantial acceleration. In particular, when applied to train large-scale CRF models, the GIS variant accelerated by componentwise extrapolation not only outperforms its global extrapolation counterpart, as our hint predicts, but can also compete with limited-memory BFGS (L-BFGS), the de facto standard for CRF training, in terms of both computational efficiency and F-scores. Keywords: Bayesian Networks, Conditional Random Fields, Expectation-Maximization (EM) Algorithm, Generalized Iterative Scaling, Triple-Jump Extrapolation

View

Fulltext

Code

TR-IIS-07-014

Subject / Author / Abstract

Boosting Multiclass Learning with Repeating Codes
Yu-Shi Lin and Chun-Nan Hsu

A long-standing goal of machine learning is to build a system which can detect a large number of classes with accuracy and efficiency. Some relationships between classes would become a scale-free network in which we can classify the assigned class very fast. Many available methods for multiclass problems have been proposed in the literatures, such as AdaBoost.ECC [4], AdaBoost.ERP, [7] and JointBoost [12]. However, many of them are inaccurate or time-consuming on training. In this paper, we propose a new algorithm, called AdaBoost.ERC, which combines the approach of Dietterich and Bakiri [2] based on error correcting output codes (ECOC) and Shapire’s boosting algorithm [3] [10]. With advantages of both concepts, our new approach achieves better performance compared to AdaBoost.ECC, AdaBoost.ERP, and JointBoost. Keywords: multiclass learning, scale-free network, ECOC, AdaBoost

View

Fulltext

Code

TR-IIS-07-015

Subject / Author / Abstract

Optimizing Server Placement for Parallel I/O in Switch-Based Clusters
Jan-Jan Wu, Yih-Fang Lin, Da-Wei Wang, Chien-Min Wang

In this paper, we consider how to optimize I/O server placement in order to improve parallel I/O performance in switch-based clusters. The significant advances in cluster networks in recent years have made it practical to connect tens of thousands of hosts via networks that have enormous and scalable total capacity, and in which communications between a host and any other host incur the same cost. The same cost property frees users from consideration of network contention and allows them to concentrate on load-balancing issues. We formulate the server placement problem on a cluster that has the same cost property as a weighted bipartite matching with the goal of balancing the workload on the I/O nodes. To find an optimal solution to this problem, we propose an O(n3/2m(logn+logm)) algorithm, called Load Balance Matching (LBM), where n is the number of compute nodes and m is the number of I/O servers. We also investigate server placement for general clusters in which multiple same-cost subclusters are interconnected to form a large cluster. This class of clusters typically adopt irregular topologies that allow the construction of scalable systems with an incremental expansion capability. Also, due to the limited bandwidth on network links between subclusters, network link contention is a major concern when distributing servers over the entire network. We show that finding an optimal placement strategy for general clusters with the goal of minimizing link contention is computationally intractable. To resolve this problem, we propose a hierarchical strategy that places servers in two steps. First, to minimize link contention, we decide which subcluster each server should be assigned to. We propose a recursive tree-based heuristic algorithm, called Load Balance Traversing (LBT), which approximates an optimal solution to this problem. In the second step, the LBM algorithm decides the location of each server within a subcluster. Our simulation results demonstrate that LBT achieves a significant improvement in parallel I/O performance over four other algorithms (randomized, even distribution, Shortest-Path, and Request-Volume). Keywords: parallel I/O, I/O server placement, load balancing, switch-based cluster, irregular network, load-balancing matching algorithm, load-balancing tree-traversing algorithm.

View

Fulltext

Code

TR-IIS-07-016

Subject / Author / Abstract

Optimal Replica Placement in Data Grid Environments with Locality Assurance
Pangfeng Liu, Yi-Fang Lin, Jan-Jan Wu

Data replication is typically used to improve access performance and data availability in Data Grid systems. To date, research on data replication in Grid systems has focused on infrastructures for replication and mechanisms for creating/deleting replicas. The important problem of choosing suitable locations to place replicas in Data Grids has not been well studied. In this paper, we address three issues concerning data replica placement in Data Grids. The first is how to ensure load balance among replicas. To achieve this, we propose a placement algorithm that finds the optimal locations for replicas so that their workload is balanced. The second issue is how to minimize the number of replicas. To solve this problem, we propose an algorithm that determines the minimum number of replicas required when the maximum workload capacity of each replica server is known. Finally, we address the issue of service quality by proposing a new model in which each request must be given a quality-of-service guarantee. We describe new algorithms that ensure both workload balance and quality of service simultaneously. Keywords: Data grid systems, Replica placement, Load balancing, Locality assurance.

View

Fulltext

Code

TR-IIS-07-017

Subject / Author / Abstract

BibPro: A Citation Parser Based on Sequence Alignment Techniques
Kai-Hsiang Yang, Chien-Chih Chen, Jan-Ming Ho

The dramatic increase in the number of academic publications has led to a growing demand for efficient organization of the resources to meet researchers’ specific needs. As a result, a number of network services have compiled databases from the public resources scattered over the Internet. Furthermore, because the publications utilize many different citation formats, the problem of accurately extracting metadata from a publication list has also attracted a great deal of attention in recent years. In this paper, we extend our previous work by using a gene sequence alignment tool to recognize and parse citation strings from publication lists into citation metadata. We also propose a new tool called BibPro. The main difference between BibPro and our previously proposed tool is that BibPro does not need any knowledge databases (e.g., an author name database) to generate a feature index for a citation string. Instead, BibPro only uses the order of punctuation marks in a citation string as its feature index to represent the string’s citation format. Second, by using this feature index, BibPro employs the Basic Local Alignment Search Tool (BLAST) to match the feature’s citation sequence with the most similar citation formats in the citation database. The Needleman-Wunsch algorithm is then used to determine the best citation format for extracting the desired citation metadata. By utilizing the alignment information, which is determined by the best template, BibPro can systematically extract the fields of author, title, journal, volume, number (issue), month, year, and page information from different citation formats with a high level of precision. The experiment results show that, in terms of precision and recall, BibPro outperforms other systems (e.g., INFOMAP and ParaCite). The results also show that BibPro scales very well.

View

Fulltext

Institute of Information Science, Academia Sinica

Library

2007 Technical Report