Institute of Information Science
Recent Research Results
Authors: Chun-Ming Chang, Cheng-Hsin Hsu, Chih-Fan Hsu, and Kuan-Ta Chen

We propose the very first non-intrusive measurement methodology for quantifying the performance of commodity Virtual Reality (VR) systems. Our methodology considers the VR system under test as a black-box and works with any VR applications. Multiple performance metrics on timing and positioning accuracy are considered, and detailed testbed setup and measurement steps are presented. We also apply our methodology to several VR systems in the market, and carefully analyze the experiment results. We make several observations: (i) 3D scene complexity affects the timing accuracy the most, (ii) most VR systems implement the dead reckoning algorithm, which incurs a non-trivial correction latency after incorrect predictions, and (iii) there exists an inherent trade-off between two positioning accuracy metrics: precision and sensitivity.
"A Disturbance-aware Sub-Block Design to Improve Reliability of 3D MLC Flash Memory," ACM/IEEE International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), October 2016.
Authors: Hung-Sheng Chang, Yuan-Hao Chang, Tei-Wei Kuo, Yu-Ming Chang, and Hsiang-Pang Li

The reliability problem of modern flash-memory chips quickly deteriorates because of the nature of MLC chips. Although the vertical stacking of storage cells in 3D flash-memory chips dramatically increases the bit density, compared to 2D chips, it also results in severe disturbance problems. In this work, we propose to create sub-blocks in the MTD layer by considering different program disturb resistance patterns, without any hardware cost. In particular, a disturbance-aware sub-block design is proposed to utilize the hotness information of data to further improve the reliability of 3D MLC flash memory by smartly choosing sub-blocks to use when extra information is available from the flash translation layer. The proposed design was evaluated by a series of experiments over traces from SNIA. It was shown that the disturb errors could be reduced by at least 50% under DFTL and BL, i.e., a page-level FTL and a block-level FTL design, compared to the conventional MLC programming designs.
"How to Enable Software Isolation and Boost System Performance with Sub-block Erase over 3D Flash Memory," ACM/IEEE International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), October 2016.
Authors: Hsin-Yu Chang, Chien-Chung Ho, Yuan-Hao Chang, Yu-Ming Chang, and Tei-Wei Kuo

The write amplification problem deteriorates as the block size of modern flash-memory chips keeps increasing. Without careful garbage collection, significant live-page copying might even worsen the reliability problem, that is already severe to 3D flash memory. In this work, we propose a sub-block erase design to not only alleviate the write amplification problem by reducing live-page copying but also improve the system reliability with a software isolation strategy. In particular, sub-blocks are carefully allocated to satisfy write requests so as to reduce disturbance by using free or invalid sub-blocks as isolation layers among sub-blocks, without additional hardware cost and capacity loss. A series of experiments were conducted to evaluate the capability of the proposed design. The results show that the proposed design is very effective in improving the system performance by reducing garbage collection overheads and in improving the device reliability/lifetime.
"Towards Ultra-Low-Bitrate Video Conferencing Using Facial Landmarks," Proceedings of ACM Multimedia 2016, October 2016.
Authors: Pin Chun Wang, Ching-Ling Fan, Chun-Ying Huang, Kuan-Ta Chen, and Cheng-Hsin Hsu

Providing high-quality video conferencing experience over the best-effort Internet and wireless networks is challenging, because 2D videos are bulky. In this paper, we exploit the common structure of conferencing videos for an ultra-low-bitrate video conferencing system. In particular, we design, implement, optimize, and evaluate a video conferencing system, which: (i) extracts facial landmarks, (ii) transmits the selected facial landmarks and 2D images, and (iii) warps the untransmitted 2D images at the receiver. Several optimization techniques are adopted for minimizing the running time and maximizing the video quality, e.g., the image and warping frames are optimally determined based on network conditions and video content. The experiment results from real conferencing videos reveal that our proposed system: (i) outperforms the stateof- the-art x265 by up to 11.05 dB in PSNR (Peak Signal-to-Noise Ratio), (ii) adapts to different video content and network conditions, and (iii) runs in real-time at about 12 frame-per-second.
"Realizing Erase-free SLC Flash Memory with Rewritable Programming Design," ACM/IEEE International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), October 2016.
Authors: Yu-Ming Chang, Yung-Chun Li, Ping-Hsien Lin, Hsiang-Pang Li, and Yuan-Hao Chang

Over the past years, the adaptation of flash memory has seen a tremendous growth in a wide range of fields, with high-end applications demanding ever higher reliability and performance for storage devices. Even though a single-level-cell (SLC) flash memory can have a higher endurance and a lower access latency to better meet that requirement in comparison with a multi-level-cell (MLC) one, the rapid deterioration of reliability due to advanced shrinking technology means that a flash block can only survive over a smaller and smaller number of erase cycles. This work proposes an erase-free scheme, which comprises the design of rewritable programming and software management, to enable a rewritable usage model that can reuse flash blocks several times without using erase operations in an SLC flash memory based storage system. The evaluation results show that the proposed scheme achieves 6-time rewritable capability such that 83% erase operations can be removed; in the best settings, the write latency can be reduced by 3.67x on average under various workloads.
"Queueing and glueing for optimal partitioning," 21st ACM SIGPLAN International Conference on Functional Programming (ICFP 2016), September 2016.
Authors: Shin-Cheng Mu, Yu-Hsi Chiang, and Yu-Han Lyu

The queueing-glueing algorithm is the nickname we give to an algorithmic pattern that provides amortised linear time solutions to a number of optimal list partition problems that have a peculiar property: at various moments we know that two of three candidate solutions could be optimal. The algorithm works by keeping a queue of lists, glueing them from one end, while chopping from the other end, hence the name. We give a formal derivation of the algorithm, and demonstrate it with several non-trivial examples.
Code accompanying this paper is available on GitHub:
Current Research Results
"Multi-grained Block Management to Enhance the Space Utilization of File Systems on PCM Storages," IEEE Transactions on Computers (TC), June 2016.
Authors: Tseng-Yi Chen, Yuan-Hao Chang, Ming-Chang Yang, Yun-Jhu Chen, Hsin-Wen Wei, and Wei-Kuan Shih

Phase-change memory (PCM) is a promising candidate as a storage medium to resolve the performance gap between main memory and storage in battery-powered mobile computing systems. However, it is more expensive than flash memory, and thus introduces a more serious storage capacity issue for low-cost solutions. This issue is further exacerbated by the fact that existing file systems are usually designed to trade space utilization for performance over block-oriented storage devices. In this work, we propose a multi-grained block management strategy to improve the space utilization of file systems over PCM-based storage systems. By utilizing the byte-addressability and fast read/write feature of PCM, a methodology is proposed to dynamically allocate multiple sizes of blocks to fit the size of each file, so as to resolve the space fragmentation issue with minimized space and management overheads. The space utilization of file systems is analyzed with consideration of block sizes. A series of experiments was conducted to evaluate the efficacy of the proposed strategy, and the results show that the proposed strategy can significantly improve the space utilization of file systems.
Current Research Results
"Byte-addressable Update Scheme to Minimize the Energy Consumption of PCM-based Storage Systems," ACM Transactions on Embedded Computing Systems (TECS), June 2016.
Authors: Ming-Chang Yang, Yuan-Hao Chang, and Che-Wei Tsao

In recent years, phase-change memory (PCM) has generated a great deal of interest because of its byte-addressability and non-volatility properties. It is regarded as a good alternative storage medium that can reduce the performance gap between the main memory and the secondary storage in computing systems. However its high energy consumption on writes is a challenging issue in the design of battery-powered mobile computing systems. To reduce the energy consumption, we exploit the byte-addressability and the asymmetric read-write energy/latency of PCM in an energy-efficient update scheme for journaling file systems. We also introduce a concept called the fifty-percent rule to determine/recommend the best update strategy for block updates. The proposed scheme only writes modified data, instead of the whole updated block, to PCM-based storage devices without extra hardware support. Moreover, it guarantees the sanity/integrity of file systems even if the computing system crashes or there is a power failure during the data update process. We implemented the proposed scheme on the Linux system and conducted a series of experiments to evaluate the scheme. The results are very encouraging.
Current Research Results
"A Computer-Assistance Learning System for Emotional Wording," IEEE Transactions on Knowledge and Data Engineering, May 2016.
Authors: Wei-Fan Chen, Mei-Hua Chen, Ming-Lung Chen, and Lun-Wei Ku

Lun-Wei KuWei-Fan ChenAbstract:
Language learners' limited lexical knowledge leads to imprecise wording. This is especially true when they attempt to express their emotions. Many learners rely heavily on the traditional thesaurus. Unfortunately, this fails to provide appropriate suggestions for lexical choices. To better aid English-as-a-second-language learners with word choices, we propose RESOLVE, which provides ranked synonyms of emotion words based on contextual information. RESOLVE suggests precise emotion words regarding the events in the relevant context. Patterns are learned to capture emotion events, and various factors are considered in the scoring function for ranking emotion words. We also describe an online writing system developed using RESOLVE and evaluate its effectiveness for learning assistance with a writing task. Experimental results showed that RESOLVE yielded a superior performance on NDCG@5 which significantly outperformed both PMI and SVM approaches, and offered better suggestions than Roget's Thesaurus and PIGAI (an online automated essay scoring system). Moreover, when applying it to the writing task, students' appropriateness with emotion words was 30 percent improved. Less-proficient learners benefited more from RESOLVE than highly-proficient learners. Post-tests also showed that after using RESOLVE, less-proficient learners' ability to use emotion words approached that of highly-proficient learners. RESOLVE thus enables learners to use precise emotion words.
"When Social Influence Meets Item Inference," ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM KDD), August 2016.
Authors: H.-J. Hung, H.-H. Shuai, D.-N. Yang, L.-H. Huang, W.-C. Lee, J. Pei, and M.-S. Chen

Research issues and data mining techniques for product recommendation and viral marketing have been widely studied. Existing works on seed selection in social networks do not take into account the effect of product recommendations in e-commerce stores. In this paper, we investigate the seed selection problem for viral marketing that considers both effects of item inference recommendation and social influence. We develop a new model, Social Item Graph (SIG), that captures both effects in form of hyperedges and learn the corresponding probability by EMS framework. Accordingly, we formulate a new optimization problem, called Social Item Maximization Problem (SIMP), to simultaneously exploit influence from friends and recommendations from stores for effective viral marketing. We prove that SIMP is inapproximable within $n^{c} $ for any $c<1$, and design an efficient $n$-approximation algorithm. Experimental results demonstrate the accuracy of the proposed model and show the effectiveness and efficiency of the proposed algorithm.
"Routing and Scheduling of Social Influence Diffusion in Online Social Networks," IEEE International Conference on Distributed Computing Systems (IEEE ICDCS), June 2016.
Authors: H.-J. Hung, D.-N. Yang, and W.-C. Lee

Owing to the rising popularity of online social networking services (OSNs), studies on social influence and its diffusion have received significant attention from the research community. Prior research has mostly studied the impact of single-hop influence diffusion and multi-hop influence broadcast in online social networks. Very little research explores the idea of guiding (routing) multi-hop social influence towards a specific target. In this paper, we motivate the needs of timely routing social influence to formulate a new optimization problem, namely, Routing And Scheduling of Target-Oriented Social Influence Diffusion (RAS-TOSID). Accordingly, we propose the Efficient Routing And Scheduling with Social and Temporal decOmposition (ERASSTO) algorithm, which finds the optimal solution to RAS-TOSID in polynomial time. We carry out a user study by implementing ERASSTO in Facebook and conduct a comprehensive evaluation on ERASSTO and alternative approaches by simulation. The result shows that ERASSTO significantly outperforms other algorithms regarding solution quality and computational efficiency.
Current Research Results
"Disturbance Relaxation for 3D Flash Memory," IEEE Transactions on Computers (TC), May 2016.
Authors: Yu-Ming Chang, Yuan-Hao Chang, Tei-Wei Kuo, Yung-Chun Li, and Hsiang-Pang Li

Even though 3D flash memory presents a grand opportunity to huge-capacity non-volatile memory, it suffers from serious program disturbance problems. In contrast to the past efforts in error correction codes and the work in trading the space utilization for reliability, we propose a disturbance-relaxation scheme that can alleviate the negative effects caused by program disturbance inside a physical block. This scheme does not introduce any 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 disturbance errors to 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
"Reducing Data Migration Overheads of Flash Wear Leveling in a Progressive Way," IEEE Transactions on Very Large Scale Integration Systems (TVLSI), May 2016.
Authors: Ming-Chang Yang, Yuan-Hao Chang, Tei-Wei Kuo, and Fu-Hsin Chen

As the endurance of flash memory keeps deteriorating, exploiting wear leveling techniques to improve the lifetime/endurance of flash memory has become a critical issue in the design of flash storage devices. Nevertheless, the deteriorated access performance of high-density flash memory makes the performance overheads introduced by wear leveling non-negligible. In particular, the existing wear-leveling designs usually aggressively distribute the erases to all flash blocks evenly in a regular basis. As a result, a lot of non-negligible unnecessary data migrations would be imposed in the early stages of the device lifespan, and would be further exacerbated if a wear leveling design selects improper victim blocks for erases. In contrast to the existing wear-leveling approaches, we propose a progressive wear leveling design to perform wear leveling in a ``progressive'' way to prevent any block from being worn out prematurely with minimized performance overheads caused by the unnecessary data migration. The experiments were conducted based on representative realistic workloads to evaluate the efficacy of the proposed design. The results reveal that instead of sacrificing the device lifetime, performing wear leveling in such a progressive way can not only minimize the performance overheads but also have potentials to extend the device lifetime.
Current Research Results
"Optimal Time-Convex Hull for a Straight-Line Highway in Lp-Metrics," Computational Geometry: Theory and Applications, February 2016.
Authors: B.-S. Dai, Mong-Jen Kao and D.T. Lee

Der- TsaiLeeAbstract:
We consider the problem of computing the time-convex hull of a point set under the general Lp -metric in the presence of a straight-line highway in the plane. The traveling speed along the highway is assumed to be faster than that off the highway, and the shortest time-path between a distant pair may involve traveling along the highway. The time-convex hull TCH(P)of a point set P is the smallest set containing both P and all shortest time-paths between any two points in TCH(P). In this paper we give an algorithm that computes the time-convex hull under the Lp -metric in optimal O(nlogn) time for a given set of n points and a real number p with 1 ≤p ≤∞. 
Current Research Results
Authors: T. Mamie Lih, Wai-Kok Choong, Chen-Chun Chen, Cheng-Wei Cheng, Hsin-Nan Lin, Ching-Tai Chen, Hui-Yin Chang, Wen-Lian Hsu and Ting-Yi Sung

Ting-YiSungWen-LianHsuHui-YinChangChing-TaiCasterChenCheng-Wei ChengWai-Kok ChoongTung-ShingLihAbstract:
MAGIC-web is the first web server, to the best of our knowledge, that performs both untargeted and targeted analyses of mass spectrometry-based glycoproteomics data for site-specific N-linked glycoprotein identification. The first two modules, MAGIC and MAGIC+, are designed for untargeted and targeted analysis, respectively. MAGIC is implemented with our previously proposed novel Y1-ion pattern matching method, which adequately detects Y1- and Y0-ion without prior information of proteins and glycans, and then generates in silico MS 2 spectra that serve as input to a database search engine (e.g. Mascot) to search against a large-scale protein sequence database. On top of that, the newly implemented MAGIC+ allows users to determine glycopeptide sequences using their own protein sequence file. The third module, Reports Integrator, provides the service of combining protein identification results from Mascot and glycan-related information from MAGIC-web to generate a complete site-specific protein-glycan summary report. The last module, Glycan Search, is designed for the users who are interested in finding possible glycan structures with specific numbers and types of monosaccharides. The results from MAGIC, MAGIC+ and Reports Integrator can be downloaded via provided links whereas the annotated spectra and glycan structures can be visualized in the browser. MAGIC-web is accessible from
Current Research Results
Authors: Ya-Xuan Hung, Pei-Chen Huang, Kuan-Ta Chen, and Woeichyn Chu

Stroke is one of the most common causes of physical disability, and early, intensive, and repetitive rehabilitation exercises are crucial to the recovery of stroke survivors. Unfortunately, research shows that only one third of stroke patients actually perform recommended exercises at home, because of the repetitive and mundane nature of conventional rehabilitation exercises. Thus, to motivate stroke survivors to engage in monotonous rehabilitation is a significant issue in the therapy process. Game-based rehabilitation systems have the potential to encourage patients continuing rehabilitation exercises at home. However, these systems are still rarely adopted at patients' places. Discovering and eliminating the obstacles in promoting game-based rehabilitation at home is therefore essential. For this purpose, we conducted a study to collect and analyze the opinions and expectations of stroke patients and clinical therapists. The study is composed of two parts: (i) Rehab-preference survey: interviews to both patients and therapists to understand the current practices, challenges, and expectations on game-based rehabilitation systems, and (ii) Rehab-compatibility survey: a gaming experiment with therapists to elaborate what commercial games are compatible with rehabilitation. The study is conducted with 30 outpatients with stroke and 19 occupational therapists from two rehabilitation centers in Taiwan. Our surveys show that game-based rehabilitation systems can turn the rehabilitation exercises more appealing and provide personalized motivation for various stroke patients. Patients prefer to perform rehabilitation exercises with more diverse and fun games, and need cost-effective rehabilitation systems, which are often built on commodity hardware. Our study also sheds light on incorporating the existing design-for-fun games into rehabilitation system. We envision the results are helpful in developing a platform which enables rehab-compatible (i.e. existing, appropriately selected) games to be operated on commodity hardware and brings cost-effective rehabilitation systems to more and more patients' home for long-term recovery.


Academia Sinica Institue of Information Science Academia Sinica