Institute of Information Science
Recent Research Results
Current Research Results
"A quantitative high-resolution genetic profile rapidly identifies sequence determinants of viral fitness and drug sensitivity," PLoS Pathogens, July 2014.
Authors: Hangfei Qi, C. Anders Olson, Nicholas C. Wu, Ruian Ke, Claude Loverdo, Roland Remenyi, Virginia Chu, Shawna Truong, Zugen Chen, Yushen Du, Sheng-Yao Su, Laith Q. Al-Mawsawi, Ting-Ting Wu, Shu-Hua Chen, Chung-Yen Lin, Weidong Zhong, James O. Lloyd-Smith, Ren Sun

Widely used chemical genetic screens have greatly facilitated the identification of many antiviral agents. However, the regions of interaction and inhibitory mechanisms of many therapeutic candidates have yet to be elucidated. Previous chemical screens identified Daclatasvir (BMS- 790052) as a potent nonstructural protein 5A (NS5A) inhibitor for Hepatitis C virus (HCV)  infection with an unclear inhibitory mechanism. Here we have developed a quantitative high resolution genetic (qHRG) approach to systematically map the drug-protein interactions between  Daclatasvir and NS5A and profile genetic barriers to Daclatasvir resistance. We implemented  saturation mutagenesis in combination with next-generation sequencing technology to  systematically quantify the effect of every possible amino acid substitution in the drug-targeted  region (domain IA of NS5A) on replication fitness and sensitivity to Daclatasvir. This enabled  determination of the residues governing drug-protein interactions. The relative fitness and drug  sensitivity profiles also provide a comprehensive reference of the genetic barriers for all possible  single amino acid changes during viral evolution, which we utilized to predict clinical outcomes  using mathematical models. We envision that this high-resolution profiling methodology will be  useful for next-generation drug development to select drugs with higher fitness costs to  resistance, and also for informing the rational use of drugs based on viral variant spectra from  patients.
"On Trading Wear-leveling with Heal-leveling," ACM/IEEE Design Automation Conference (DAC), June 2014.
Authors: Yu-Ming Chang, Yuan-Hao Chang, Jian-Jia Chen, Tei-Wei Kuo, Hsiang-Pang Li, and Hang-Ting Lue

The density of flash memory keeps increasing because of the strong demand on the storage capacity. However, such a development trend significantly reduces the reliability and endurance of flash memory in terms of erase cycles, even when the wear leveling technology is adopted to extend the lifetime of flash memory by evenly distributing the erase cycles to every flash block. To address this issue, the self-healing technology is proposed to recover a flash block before the flash block is worn out, but such a technology still has a limitation on recovering flash blocks. In contrast to the existing wear leveling designs, we adopt the self-healing technology to propose a heal-leveling design that evenly distribute the healing cycles to flash blocks so as to ultimately extend the lifetime of flash memory without the huge amount of live-data copying overheads imposed by existing wear leveling designs. A series of experiments was conducted to evaluate the capability of the proposed design. The results show that our design can significantly improve the access performance and the effective lifetime of flash memory without the unnecessary overheads caused by wear leveling technology.
"Effective pseudo-relevance feedback for language modeling in extractive speech summarization," IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), May 2014.
Authors: Shih-Hung Liu, Kuan-Yu Chen, Yu-Lun Hsieh, Berlin Chen, Hsin-Min Wang, Hsu-Chun Yen, Wen-Lian Hsu

Extractive speech summarization, aiming to automatically select an indicative set of sentences from a spoken document so as to concisely represent the most important aspects of the document, has become an active area for research and experimentation. An emerging stream of work is to employ the language modeling framework along with the Kullback-Leibler divergence measure for extractive speech summarization, which can perform important sentence selection in an unsupervised manner and has shown preliminary success. This paper presents a continuation of such a general line of research and its main contribution is two-fold. First, by virtue of pseudo-relevance feedback, we explore several effective sentence modeling formulations to enhance the sentence models involved in the LM-based summarization framework. Second, the utilities of our summarization methods and several widely-used methods are analyzed and compared extensively, which demonstrates the effectiveness of our methods.
"Efficient Memory Virtualization for Cross-ISA System Mode Emulation," ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments (VEE 2014), March 2014.
Authors: Chao-Jui Chang, Jan-Jan Wu, Wei-Chung Hsu, Pangfeng Liu, Pen-Chung Yew

Cross-ISA system-mode emulation has many important applications. For example, Cross-ISA system-mode emula-tion helps computer architects and OS developers trace and debug kernel execution-flow efficiently by emulating a slower platform (such as ARM) on a more powerful plat-form (such as an x86 machine). Cross-ISA system-mode emulation also enables workload consolidation in data centers with platforms of different instruction-set architec-tures (ISAs). However, system-mode emulation is much slower. One major overhead in system-mode emulation is the multi-level memory address translation that maps guest virtual address to host physical address. Shadow page ta-bles (SPT) have been used to reduce such overheads, but primarily for same-ISA virtualization. In this paper we propose a novel approach called embedded shadow page tables (ESPT). EPST embeds a shadow page table into the address space of a cross-ISA dynamic binary translation (DBT) and uses hardware memory management unit in the CPU to translate memory addresses, instead of software translation in a current DBT emulator like QEMU. We also use the larger address space on modern 64-bit CPUs to accommodate our DBT emulator so that it will not interfere with the guest operating system. We incorporate our new scheme into QEMU, a popular, retargetable cross-ISA system emulator. SPEC CINT2006 benchmark results indi-cate that our technique achieves an average speedup of 1.51 times in system mode when emulating ARM on x86, and a 1.59 times speedup for emulating IA32 on x86_64.
Current Research Results
"Efficient and Retargetable Dynamic Binary Translation on Multicores," IEEE Trans. on Parallel and Distributed Systems, February 2014.
Authors: Ding-Yong Hong, Jan-Jan Wu, Pen-Chung Yew, Wei-Chung Hsu, Chun-Chen Hsu, Pangfeng Liu, Chien-Min Wang, Yeh-Ching Chung

Dynamic binary translation (DBT) is a core technology to many important applications such as system virtualization, dynamic binary instrumentation and security. However, there are several factors that often impede its performance: (1) emulation overhead before translation; (2) translation and optimization overhead, and (3) translated code quality. The issues also include its retargetability that supports guest applications from different instruction-set architectures (ISAs) to host machines also with different ISAs -- an important feature to system virtualization. In this work, we take advantage of the ubiquitous multicore platforms, and use a multithreaded approach to implement DBT. By running the translator and the dynamic binary optimizer on different cores with different threads, it could off-load the overhead incurred by DBT on the target applications; thus, afford DBT of more sophisticated optimization techniques as well as its retargetability. Using QEMU (a popular retargetable DBT for system virtualization) and LLVM (Low-Level Virtual Machine) as our building blocks, we demonstrated in a multi-threaded DBT prototype, called HQEMU (Hybrid-QEMU), that it could improve QEMU performance by a factor of 2.6X and 4.1X on the SPEC CPU2006 integer and floating point benchmarks, respectively, for dynamic translation of x86 code to run on x86-64 platforms. For ARM codes to x86-64 platforms, HQEMU can gain a factor of 2.5X speedup over QEMU for the SPEC CPU2006 integer benchmarks. We also address the performance scalability issue of multithreaded applications across ISAs. We identify two major impediments to performance scalability in QEMU: (1) coarse-grained locks used to protect shared data structures, and (2) inefficient emulation of atomic instructions across ISA's. We proposed two techniques to mitigate those problems: (1) using Indirect Branch Translation Caching (IBTC) to avoid frequent accesses to locks, and (2) using lightweight memory transactions to emulate atomic instructions across ISAs. Our experimental results show that, for multithreaded applications, HQEMU achieves 25X speedups over QEMU for the PARSEC benchmarks.
"A Composite Kernel Approach for Detecting Interactive Segments in Chinese Topic Documents," the 9th Asia Information Retrieval Societies Conference (AIRS 2013), December 2013.
Authors: Yung-Chun Chang, Chien Chin Chen, and Wen-Lian Hsu

Discovering the interactions between persons mentioned in a set of topic documents can help readers construct the background of a topic and facilitate comprehension. In this paper, we propose a rich interactive tree structure to represent syntactic, content, and semantic information in text. We also present a composite kernel classification method that integrates the tree structure with a bigram kernel to identify text segments that mention person interactions in topic documents. Empirical evaluations demonstrate that the proposed tree structure and bigram kernel are effective and the composite kernel approach outperforms well-known relation extraction and PPI methods.
"Active Disaster Response System for Smart Buildings," Proceedings of International Symposium on Computer, Consumer and Control, June 2014.
Authors: C.-Y. Lin, E. T. H. Chu, L.-W. Ku and J. W. S. Liu

Jane Win ShihLiuAbstract:
 In recent years, major natural disasters have made it more challenging for us to protect human lives. Examples include the 2011 Japan Tohoku earthquake and Typhoon Morakot in 2009 in Taiwan. However, modern disaster warning systems cannot automatically respond efficiently and effectively to disasters. As a result, it is necessary to develop an automatic response system to prevent, diminish or eliminate the damages caused by disasters. In this paper, we develop an active emergency response system to automatically process standard warning messages, such as CAP (Common Alerting Protocol) messages. After receiving official warning messages of earthquakes, our system automatically shuts down natural gas lines in order to prevent buildings from fire and opens the building doors for easy evacuation. Our system also stops elevators when they reach the closest floor. In addition, our system can be applied to hospitals to tell surgeons to pause on-going operations, or to supermarkets to inform consumers of the way to exit the building. According to our experiment results, the proposed system can avoid possible dangers and save human lives during major disasters. 
"Space-Efficient Multiversion Index Scheme for PCM-based Embedded Database Systems," ACM/IEEE Design Automation Conference (DAC), June 2014.
Authors: Yuan-Hung Kuan, Yuan-Hao Chang, Po-Chun Huang, and Kam-Yiu Lam

Embedded database systems are widely adopted in various control and motoring systems, e.g., cyber-physical systems. To support the functionality to access the historical data, a multiversion index is adopted to simultaneously maintain multiple versions of data items and their index information. However, cyber-physical systems are usually battery-powered embedded systems that have limited energy, computing power, and storage space. In this work, we consider the systems with phase-change memory (PCM) as their storage due to its non-volatility and low energy consumption. In order to resolve the problem of the limited storage space and the fact that existing multiversion index designs are lack of space efficiency, we propose a space-efficient multiversion index scheme to enhance the space utilization and access performance of embedded multiversion database systems on PCM by utilizing the byte-addressability and write asymmetry of PCM. A series of experiments was conducted to evaluate the efficacy of the proposed scheme. The results show that the proposed scheme achieves very high space utilization and has good performance on serving update transactions and range queries.
"Garbage Collection for Multi-version Index on Flash Memory," ACM/IEEE Design, Automation and Test in Europe (DATE), March 2014.
Authors: Kam-Yiu Lam, Jian-Tao Wang, Yuan-Hao Chang, Po-Chun Huang, Jen-Wei Hsieh, Chung Keung Poon, and ChunJiang Zhu

In this paper, we study the important performance issues in using the purging-range query to reclaim old data versions to be free blocks in a flash-based multi-version database. To reduce the overheads for processing the purging-range query,
the physical block labeling (PBL) scheme is proposed to provide a better estimation on the purging version number to be used for purging old data versions. With the use of the frequencybased placement (FBP) scheme to place data versions in a block, the efficiency in garbage collection can be further enhanced by increasing the deadspans of data versions and reducing reallocation cost especially when the spaces of the flash memory for the databases are limited.
Current Research Results
Authors: Chia-Feng Tsai, Chuan-Chih Hsu, Jo-Nan Hung, Yi-Ting Wang, Wai-Kok Choong, Ming-Yao Zeng, Pei-Yi Lin, Ruo-Wei Hong, Ting-Yi Sung, and Yu-Ju Chen

Methodologies to enrich heterogeneous types of phosphopeptides are critical for comprehensive mapping of the under-explored phosphoproteome. Taking advantage of the distinct binding affinities of Ga3+ and Fe3+ for phosphopeptides, we designed a metal-directed immobilized metal ion affinity chromatography for the sequential enrichment of phosphopeptides. In Raji B cells, the sequential Ga3+ - Fe3+-immobilized metal affinity hromatography (IMAC) strategy displayed a 1.5−3.5-fold superior phosphoproteomic coverage compared to single IMAC (Fe3+,Ti4+,Ga3+, and Al3+). In addition, up to 92% of the
6283 phosphopeptides were uniquely enriched in either the first Ga3+-IMAC (41%) or second Fe3+-IMAC (51%). The complementary properties of Ga3+ and Fe3+ were further demonstrated through the exclusive enrichment of almost all of 1214 multiply phosphorylated peptides (99.4%) in the Ga3+-IMAC, whereas only 10% of 5069 monophosphorylated phosphopeptides were commonly enriched in both fractions. The application of sequential Ga3+-Fe3+-IMAC to human lung cancer tissue allowed the identification of 2560 unique phosphopeptides with only 8% overlap. In addition to the above-mentioned mono- and multiply phosphorylated peptides, this fractionation ability was also demonstrated on the basic and acidic phosphopeptides: acidophilic phosphorylation sites were predominately enriched in the first Ga3+-IMAC (72%), while Pro-directed (85%) and basophilic (79%) phosphorylation sites were enriched in the second Fe3+-IMAC. This strategy provided complementary mapping of different kinase substrates in multiple cellular pathways related to cancer invasion and metastasis of lung cancer. Given the fractionation ability and ease of tip preparation of this Ga3+-Fe3+-IMAC, we propose that this strategy allows more comprehensive characterization of the phosphoproteome both in vitro and in vivo.
Current Research Results
Authors: Jun Ming Chen, Meng Chang Chen and Yeali S. Sun

Meng ChangChenAbstract:
Prior knowledge is an important issue in the study of concept acquisition among students. Traditional studies on prior knowledge generation during reading activities have focused on extracting sentences from reading materials that are manually generated by website administrators and educators. This is time-consuming and strenuous, and hence personalized prior knowledge recommendation is difficult to perform. To cope with this problem, we combine the concept of prior knowledge with social tagging methods to assist the reading comprehension of students studying English. We incorporate tags into a tag based learning approach, which then identifies suitable supplementary materials for quickly constructing a student’s prior knowledge reservoir. The experimental results demonstrate that the proposed approach benefits the students by embedding the additional information in social knowledge, and hence significantly improve their on-line reading efficiency.
Current Research Results
"Example-based Human Motion Extrapolation and Motion Repairing Using Contour Manifold," IEEE Transactions on Multimedia, January 2014.
Authors: Nick C. Tang, C. T. Hsu, M. F. Weng, T. Y. Lin, and H. Y. Mark Liao

MarkLiaoNick C. TangAbstract:
We propose a human motion extrapolation algorithm that synthesizes new motions of a human object in a still image from a given reference motion sequence. The algorithm is implemented in two major steps: contour manifold construction and object motion synthesis. Contour manifold construction searches for low-dimensional manifolds that represent the temporal-domain deformation of the reference motion sequence. Since the derived manifolds capture the motion information of the reference sequence, the representation is more robust to variations in shape and size. With this compact representation, we can easily modify and manipulate human motions through interpolation or extrapolation in the contour manifold space. In the object motion synthesis step, the proposed algorithm generates a sequence of new shapes of the input human object in the contour manifold space and then renders the textures of those shapes to synthesize a new motion sequence. We demonstrate the efficacy of the algorithm on different types of practical applications, namely, motion extrapolation and motion repair.
Current Research Results
"A Resource-Driven DVFS Scheme for Smart Handheld Devices," ACM Transactions on Embedded Computing Systems, December 2013.
Authors: Yu-Ming Chang, Pi-Cheng Hsiu, Yuan-Hao Chang, and Che-Wei Chang

Reducing the energy consumption of the emerging genre of smart handheld devices while simultaneously maintaining mobile applications and services is a major challenge. This work is inspired by an observation on the resource usage patterns of mobile applications. In contrast to existing DVFS scheduling algorithms and history-based prediction techniques, we propose a resource-driven DVFS scheme, in which resource state machines are designed to model the resource usage patterns in an online fashion to guide DVFS. We have implemented the proposed scheme on Android smartphones and conducted experiments based on realworld applications. The results are very encouraging and demonstrate the efficacy of the proposed scheme.
Current Research Results
"On the Quality of Service of Cloud Gaming Systems," IEEE Transactions on Multimedia, February 2014.
Authors: Kuan-Ta Chen, Yu-Chun Chang, Hwai-Jung Hsu, De-Yu Chen, Chun-Ying Huang, and Cheng-Hsin Hsu

Cloud gaming, i.e., real-time game playing via thin clients, relieves users from being forced to upgrade their com- puters and resolve the incompatibility issues between games and computers. As a result, cloud gaming is generating a great deal of interests among entrepreneurs, venture capitalists, general publics, and researchers. However, given the large design space, it is not yet known which cloud gaming system delivers the best user-perceived Quality of Service (QoS) and what design elements constitute a good cloud gaming system.

This study is motivated by the question: How good is the QoS of current cloud gaming systems? Answering the question is challenging because most cloud gaming systems are proprietary and closed, and thus their internal mechanisms are not accessible for the research community. In this paper, we propose a suite of measurement techniques to evaluate the QoS of cloud gaming systems and prove the effectiveness of our schemes using a case study comprising two well-known cloud gaming systems: OnLive and StreamMyGame. Our results show that OnLive performs better, because it provides adaptable frame rates, better graphic quality, and shorter server processing delays, while consuming less network bandwidth. Our measurement techniques are general and can be applied to any cloud gaming systems, so that researchers, users, and service providers may systematically quantify the QoS of these systems. To the best of our knowledge, the proposed suite of measurement techniques have never been presented in the literature.

Current Research Results
"Reliability Enhancement of Flash-Memory Storage Systems: An Efficient Version-Based Design," IEEE Transactions on Computers, December 2013.
Authors: Yuan-Hao Chang, Po-Chun Huang, Pei-Han Hsu, Lue-Jane Lee, Tei-Wei Kuo and David Hung-Chang Du

In recent years, reliability has become one critical issue in the designs of flash-memory file/storage systems, due to the growing unreliability of advanced flash-memory chips. In this paper, a version-based strategy is proposed to effectively and efficiently maintain the consistency among page versions of a file for potential recovery needs. In particular, a two-version one for a native file system is presented with the minimal overheads in version maintenance. A recovery scheme is then presented to restore a corrupted file back to the latest consistent version. The strategy is later extended to maintain multiple data versions with the considerations of the write constraints of multi-level-cell flash memory. It was shown that the proposed strategy could significantly improve the reliability of flash memory with limited management and space overheads.
"Selective Profiling for OS Scalability Study on Multicore Systems," IEEE International Conference on Service-Oriented Computing and Applications (SOCA), December 2013.
Authors: Kuo-Yi Chen, Yuan-Hao Chang, Pei-Shu Liao, Pen-Chung Yew, Sheng-Wei Cheng, and Tien-Fu Chen

With the wide deployment of multi-core processors, the scalability is becoming an important issue of modern computers.  In order to detail the scalability issues of an operating system, the performance profilers are usually used to detect the scalability bottlenecks. However, profilers usually go alone with the significant overheads. The overheads not only reduce the accuracy of scalability profiling, but also mislead to the actual scalability bottlenecks. In order to improve this issue, a selective-profiling approach is proposed to analyze the scalability of an operating system precisely with minimum overheads. In proposed selective-profiling approach, the possible scalability bottleneck hotspots are located by the tracers first, and then the information of possible bottleneck hotspots is passed to the sampler to detect actual bottlenecks.  Since the sampler only concentrates on the possible bottleneck hotspots instead of a whole system, the overhead can be reduced significantly. Therefore, the proposed selective-profiling approach takes the advantages of performance tracers and samplers both to reduce the overhead and still reach the accurate bottleneck analysis for an operating system in multi-core systems.
Current Research Results
"What Distinguish One from Its Peers in Social Networks," Data Mining and Knowledge Discovery, November 2013.
Authors: Yi-Chen Lo, Jhao-Yin Li, Mi-Yen Yeh, Shou-De Lin, Jian Pei

Being able to discover the uniqueness of an individual is a meaningful task in social network analysis. This paper proposes two novel problems in social network analysis: how to identify the uniqueness of a given query vertex, and how to identify a group of vertices that can mutually identify each other. We further propose intuitive yet effective methods to identify the uniqueness identification sets and the mutual identification groups of different properties. We further conduct an extensive experiment on both real and synthetic datasets to demonstrate the effectiveness of our model.
"A Disturb-Alleviation Scheme for 3D Flash Memory," ACM/IEEE International Conference on Computer-Aided Design (ICCAD), November 2013.
Authors: Yu-Ming Chang, Yuan-Hao Chang, Tei-Wei Kuo, Hsiang-Pang Li, and Yung-Chun Li

Even though 3D flash memory presents a grand opportunity for huge-capacity non-volatile memory, it suffers from serious program disturb problems. Different from the past efforts in error correction codes or the work in trading the space utilization with reliability, we propose a disturb-alleviation scheme that can alleviate the negative effects caused by program disturb, especially inside a block, without introducing extra overheads on encoding or storing of extra redundant data. In particular, a methodology is proposed to reduce the data error rate by distributing unavoidable disturb errors over the flash-memory space of invalid data, with the considerations of the physical organization of 3D flash memory. A series of experiments was conducted based on real multi-layer 3D flash chips, and it showed that the proposed scheme could significantly enhance the reliability of 3D flash memory.
Current Research Results
"Multicast with Intra-Flow Network Coding in Multi-Rate Multi-Channel Wireless Mesh Networks," IEEE Trans. on Vehicular Technology, November 2013.
Authors: C.-J Lin and D.-N. Yang

It has been shown that intra-flow network coding can improve the multicast throughput in single-channel single rate wireless mesh networks. Most existing studies focus on developing a practical intra-flow network-coding multicast protocol. With the ripe of the wireless products supporting multi-rate multi-channel communications, nowadays it becomes increasingly important to improve the network coding gain by utilizing multiple bit-rates and non-overlapping channels, but new challenges also arise due to various tradeoffs. In a multi-rate, multi-channel, multi-hop network, overhearing opportunities and bandwidth utilization are highly correlated to the selection of the channel and rate, which, in turn, determines the achievable throughput of multicast with intra-flow network coding. Specifically, wireless nodes can transmit at higher bit-rates over orthogonal channels to increase the forwarding throughput, but the strategy reduces overhearing opportunities and the coding gain in multicast with intra-flow network coding. To achieve the best trade-off between the above two aspects, we formulate a new optimization model called multi-Rate multi-Channel Multicast with intra-flow Network Coding (RCMNC), which solves the joint channel assignment, rate selection and flow allocation problems for multi-hop intraflow network coding multicast. We then reformulate the primal problem as the Lagrangian dual problem, and propose an algorithm to approximate the solution of the dual problem in polynomial-time. Simulation results show that, by assigning a suitable rate and channel to each network interface, multicast throughput with intra-flow network coding under RCMNC is up to 3.3 times higher than that achieved by the existing approach in a multi-rate multi-channel wireless mesh network.


Academia Sinica Institue of Information Science Academia Sinica