Vol. 42, No. 11,
Nov. 2015
Digital Library
Grid-based Index Generation and k-nearest-neighbor Join Query-processing Algorithm using MapReduce
MapReduce provides high levels of system scalability and fault tolerance for large-size data processing. A MapReduce-based k-nearest-neighbor(k-NN) join algorithm seeks to produce the k nearest-neighbors of each point of a dataset from another dataset. The algorithm has been considered important in bigdata analysis. However, the existing k-NN join query-processing algorithm suffers from a high index-construction cost that makes it unsuitable for the processing of bigdata. To solve the corresponding problems, we propose a new grid-based, k-NN join query-processing algorithm. Our algorithm retrieves only the neighboring data from a query cell and sends them to each MapReduce task, making it possible to improve the overhead data transmission and computation. Our performance analysis shows that our algorithm outperforms the existing scheme by up to seven-fold in terms of the query-processing time, while also achieving high extent of query-result accuracy.
Hybrid Main Memory based Buffer Cache Scheme by Using Characteristics of Mobile Applications
Chansoo Oh, Dong Hyun Kang, Minho Lee, Young Ik Eom
Mobile devices employ buffer cache mechanisms, just as in computer systems such as desktops or servers, to mitigate the performance gap between main memory and secondary storage. However, DRAM has a problem in that it accelerates battery consumption by performing refresh operations periodically to maintain the stored data. In this paper, we propose a novel buffer cache scheme to increase the battery lifecycle in mobile devices based on a hybrid main memory architecture consisting of DRAM and non-volatile PCM. We also suggest a new buffer cache policy that allocates buffers based on process states to optimize the performance and endurance of PCM. In particular, our algorithm allocates each page to the appropriate position corresponding to the state of the application that owns the page, and tries to ensure a rapid response of foreground applications even with a small amount of DRAM memory. The experimental results indicate that the proposed scheme reduces the elapsed time of foreground applications by 58% on average and power consumption by 23% on average without negatively impacting the performance of background applications.
Event Routing Scheme to Improve I/O Latency of SMP VM
According to the hypervisor scheduler, the vCPU (virtual CPU) operates under two states: the running state and the stop state. When the vCPU is in the stop state, incoming events are delayed until that vCPU"s state changes to the running state. The latency in handling such events that are sent to the vCPU is regarded as the I/O latency. Since a SMP (symmetric multiprocessing) VM (virtual machine) incorporates multiple vCPUs, the event latency on a SMP VM can vary according to specific vCPU that receives the event. In this paper, we propose a new scheme named event routing that sends events according to the operation state of each vCPU to reduce the event latency on an SMP VM. We implemented the proposed event routing scheme in Xen ARM hypervisor and confirmed the reduction of I/O latency from measuring the network RTT (round trip time) and the TCP bandwidth under a variety of testing conditions. The network RTT decreases by up to 94% and the TCP bandwidth increases up to 35% when compare to native Xen ARM.
High-Performance Multi-GPU Rendering Based on Implicit Synchronization
Recently, growing attention has been paid to multi-GPU rendering to support real-time high-quality rendering at high resolution. In order to attain high performance in real-time multi-GPU rendering, great care needs to be taken to reduce the overhead of data transfer among GPUs and frame composition. This paper presents a novel multi-GPU algorithm that greatly enhances split frame rendering with implicit query-based synchronization. In order to support implicit synchronization in frame composition, we further present a message queue-based scheduling algorithm. We carried out an experiment to evaluate our algorithm, and found that our algorithm improved rendering performance up to 200% more than previously existing algorithms.
Service-Dependability-Case based Self-Adaptation in Service-Oriented Environment
In a distributed system environment based on a service-oriented architecture, separate systems collaborate to achieve the goals of the entire system by using services provided other systems. A service quality violation from using one service can cause runtime system failure in the environment. The existing self-adaptation methods follow fault tolerance mechanism that responds to a failure after a service quality violation. In other words, these methods are limited to responsive action. Therefore, a service-dependability-case based self-adaptation mechanism is necessary to preserve the dependability of the self-adaptive system. This paper demonstrates that the service-dependability-case based self-adaptation mechanism is better than QoS(quality of service)-based self-adaptation with fault tolerance to preserve the dependability of the self-adaptive system. Additionally, this paper suggests a method to present and analyze service dependability by using GSN(Goal Structuring Notation) which is the existing modeling method for the presentation of assurance cases, an action mechanism adapted using an analysis result of service-dependability-cases, a methods of leveraging the service-dependability - case based self-adaptation mechanism by following the service’s life cycle, and the framework architecture including the major components and the interactions between the components in the control loop of the self-adaptation process.
A Method to Establish Severity Weight of Defect Factors for Application Software using ANP
In order to improve software quality, it is necessary to efficiently and effectively remove software defects in source codes. In the development field, defects are removed according to removal ratio or severity of defects. There are several studies on the removal of defects based on software quality attributes, and several other studies have been done to improve the software quality using classification of the severity of defects, when working on projects. These studies have thus far been insufficient in terms of identifying if there exists relationships between defects or whether any type of defect is more important than others. Therefore, in this study, we collected various types of software defects, standards organization, companies, and researchers. We modeled the defects types using an ANP model, and developed the weighted severities of the defects types, with respect to the general application software, using the ANP model. When general application software is developed, we will be able to use the weight for each severity of defect type, and we expect to be able to remove defects efficiently and effectively.
Quality Metrics of Cloud Service Based on Cross-cutting and SLA Specification Mechanism
Youngmin An, Joonseok Park, Keunhyuk Yeom
Depending on the increase amongst various cloud services, the technology of the Cloud Service Broker (CSB) to find the most appropriate services to meet the needs of cloud service consumers has emerged. In order to advance for cloud services to be used through the CSB, it is important to ensure the quality level that meets the demands of consumers through a negotiation process based on the Service Level Agreement (SLA). However, quality metrics of cloud services are different from each other based on the measurement scale, which represents the quality level, and the calculation for each type of cloud services. Therefore, it is necessary to analyze the variability of the quality of cloud services and establish a SLA model for ensuring and improving the level of quality. In this paper, we analyze the quality metrics for the specific type of cloud services by applying the cross-cutting concept and propose a Virtual SLA (VSLA) meta-model.
Analysis of Feature Extraction Methods for Distinguishing the Speech of Cleft Palate Patients
Sung Min Kim, Wooil Kim, Tack-Kyun Kwon, Myung-Whun Sung, Mee Young Sung
This paper presents an analysis of feature extraction methods used for distinguishing the speech of patients with cleft palates and people with normal palates. This research is a basic study on the development of a software system for automatic recognition and restoration of speech disorders, in pursuit of improving the welfare of speech disabled persons. Monosyllable voice data for experiments were collected for three groups: normal speech, cleft palate speech, and simulated clef palate speech. The data consists of 14 basic Korean consonants, 5 complex consonants, and 7 vowels. Feature extractions are performed using three well-known methods: LPC, MFCC, and PLP. The pattern recognition process is executed using the acoustic model GMM. From our experiments, we concluded that the MFCC method is generally the most effective way to identify speech distortions. These results may contribute to the automatic detection and correction of the distorted speech of cleft palate patients, along with the development of an identification tool for levels of speech distortion.
A Strategy for Neighborhood Selection in Collaborative Filtering-based Recommender Systems
Collaborative filtering is one of the most successfully used methods for recommender systems and has been utilized in various areas such as books and music. The key point of this method is selecting the most proper recommenders, for which various similarity measures have been studied. To improve recommendation performance, this study analyzes problems of existing recommender selection methods based on similarity and presents a method of dynamically determining recommenders based on the rate of co-rated items as well as similarity. Examination of performance with varying thresholds through experiments revealed that the proposed method yielded greatly improved results in both prediction and recommendation qualities, and that in particular, this method showed performance improvements with only a few recommenders satisfying the given thresholds.
A GUI State Comparison Technique for Effective Model-based Android GUI Testing
Youngmin Baek, Gwangui Hong, Doo-hwan Bae
Graphical user interface testing (GUI testing) techniques have been widely used to test the functionality of Android applications (apps) and to detect faults for verification of the reliability and usability of apps. To adequately test the behaviors of apps, a number of studies on model-based GUI testing techniques have been performed on Android apps. However, the effectiveness of model-based techniques greatly depends on the quality of the GUI model, because model-based GUI testing techniques generate test inputs based on this model. Therefore, in order to improve testing effectiveness in model-based techniques, accurate and efficient GUI model generation has to be achieved using an improved model generation technique with concrete definition of GUI states. For accurate and efficient generation of a GUI model and test inputs, this study suggests a hierarchical GUI state comparison technique and evaluates this technique through comparison with the existing model-based techniques, considering activities as GUI states. Our results show that the proposed technique outperforms existing approaches and has the potential to improve the performance of model-based GUI testing techniques for Android apps.
A Semi-automatic Construction method of a Named Entity Dictionary Based on Wikipedia
Yeongkil Song, Seokwon Jeong, Harksoo Kim
A named entity(NE) dictionary is an important resource for the performance of NE recognition. However, it is not easy to construct a NE dictionary manually since human annotation is time consuming and labor-intensive. To save construction time and reduce human labor, we propose a semi-automatic system for the construction of a NE dictionary. The proposed system constructs a pseudo-document with Wiki-categories per NE class by using an active learning technique. Then, it calculates similarities between Wiki entries and pseudo-documents using the BM25 model, a well-known information retrieval model. Finally, it classifies each Wiki entry into NE classes based on similarities. In experiments with three different types of NE class sets, the proposed system showed high performance(macro-average F1-score of 0.9028 and micro-average F1-score 0.9554).
Tunable Static Analysis Framework for JavaScript Applications
In this paper, we present a novel approach to analyzing large-scale JavaScript applications statically by tuning the analysis scalability, possibly sacrificing soundness. For a given sound static baseline analysis of JavaScript programs, our framework allows users to define a sound approximation of selected executions that they wish to analyze, and it derives a tuned static analysis that can analyze the selected executions practically. The selected executions serve as parameters of the framework by taking a trade-off between the scalability and the soundness of the derived analyses. We formally describe our framework in the abstract interpretation setting and present two instances of the framework.
A Binary Decision Diagram-based Modeling Rule for Object-Relational Transformation Methodology
Sooyoung Cha, Sukhoon Lee, Doo-Kwon Baik
In order to design a system, software developers use an object model such as the UML class diagram. Object-Relational Transformation Methodology (ORTM) is a methodology to transform the relationships that are expressed in the object model into relational database tables, and it is applied for the implementation of the designed system. Previous ORTM studies have suggested a number of transformation methods to represent one relationship. However, there is an implementation problem that is difficult to apply because the usage criteria for each transformation method do not exist. Therefore, this paper proposes a binary decision diagram-based modeling rule for each relationship. Hence, we define the conditions for distinguishing the transformation methods. By measuring the query execution time, we also evaluate the modeling rules that are required for the verification. After evaluation, we re-define the final modeling rules which are represented by propositional logic, and show that our proposed modeling rules are useful for the implementation of the designed system through a case study.
A Markov Game based QoS Control Scheme for the Next Generation Internet of Things
The Internet of Things (IoT) is a new concept associated with the future Internet, and it has recently become a popular concept to build a dynamic, global network infrastructure. However, the deployment of IoT creates difficulties in satisfying different Quality of Service (QoS) requirements and achieving rapid service composition and deployment. In this paper, we propose a new QoS control scheme for IoT systems. The Markov game model is applied in our proposed scheme to effectively allocate IoT resources while maximizing system performance. The results of our study are validated by running a simulation to prove that the proposed scheme can promptly evaluate current IoT situations and select the best action. Thus, our scheme approximates the optimum system performance.
Cluster-based Energy-aware Data Sharing Scheme to Support a Mobile Sink in Solar-Powered Wireless Sensor Networks
Hong Seob Lee, Jun Min Yi, Jaeung Kim, Dong Kun Noh
In contrast with battery-based wireless sensor networks (WSNs), solar-powered WSNs can operate for a longtime assuming that there is no hardware fault. Meanwhile, a mobile sink can save the energy consumption of WSN, but its ineffective movement may incur so much energy waste of not only itself but also an entire network. To solve this problem, many approaches, in which a mobile sink visits only on clustering-head nodes, have been proposed. But, the clustering scheme also has its own problems such as energy imbalance and data instability. In this study, therefore, a cluster-based energy-aware data-sharing scheme (CE-DSS) is proposed to effectively support a mobile sink in a solar-powered WSN. By utilizing the redundant energy efficiently, CE-DSS shares the gathered data among cluster-heads, while minimizing the unexpected black-out time. The simulation results show that CE-DSS increases the data reliability as well as conserves the energy of the mobile sink.
Design and Implementation of DNS Name Autoconfiguration for Internet of Things Devices
As one of the most spotlighted research areas, these days, the Internet of Things (IoT) aims to provide users with various services through many devices. Since there exist so many devices in IoT environments, it is inefficient to manually configure the domain name system (DNS) names of such devices. Thus, for IPv6-based IoT environments, this paper proposes a scheme called the DNS Name Autoconfiguration (DNSNA) that autoconfigures an IoT device’s DNS name and manages it. In the procedure for generating and registering an IoT device’s DNS name, the standard protocols of the Internet Engineering Task Force (IETF) are used. Since the proposed scheme resolves an IoT device’s DNS name into an IPv6 address in unicast through a DNS server, it generates less traffic than multicast-based mDNS (Multicast DNS) which is a legacy DNS application for the DNS name service in the smart home. Thus, the proposed scheme is more appropriate in multi-hop IoT networks than mDNS. This paper explains the design of the proposed scheme and its service scenarios, such as smart home and smart road. It also explains the implementation and testing of the proposed scheme in the smart grid.
Error Correction in Korean Morpheme Recovery using Deep Learning
Korean Morphological Analysis is a difficult process. Because Korean is an agglutinative language, one of the most important processes in Morphological Analysis is Morpheme Recovery. There are some methods using Heuristic rules and Pre-Analyzed Partial Words that were examined for this process. These methods have performance limits as a result of not using contextual information. In this study, we built a Korean morpheme recovery system using deep learning, and this system used word embedding for the utilization of contextual information. In ‘들/VV’ and ‘듣/VV’ morpheme recovery, the system showed 97.97% accuracy, a better performance than with SVM(Support Vector Machine) which showed 96.22% accuracy.
Quantified Lockscreen: Integration of Personalized Facial Expression Detection and Mobile Lockscreen application for Emotion Mining and Quantified Self
Sung Sil Kim, Junsoo Park, Woontack Woo
Lockscreen is one of the most frequently encountered interfaces by smartphone users. Although users perform unlocking actions every day, there are no benefits in using lockscreens apart from security and authentication purposes. In this paper, we replace the traditional lockscreen with an application that analyzes facial expressions in order to collect facial expression data and provide real-time feedback to users. To evaluate this concept, we have implemented Quantified Lockscreen application, supporting the following contributions of this paper: 1) an unobtrusive interface for collecting facial expression data and evaluating emotional patterns, 2) an improvement in accuracy of facial expression detection through a personalized machine learning process, and 3) an enhancement of the validity of emotion data through bidirectional, multi-channel and multi-input methodology.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr