Vol. 43, No. 2,
Feb. 2016
Digital Library
Spatiotemporal Data Visualization using Gravity Model
Seokyeon Kim, Hanbyul Yeon, Yun Jang
Visual analysis of spatiotemporal data has focused on a variety of techniques for analyzing and exploring the data. The goal of these techniques is to explore the spatiotemporal data using time information, discover patterns in the data, and analyze spatiotemporal data. The overall trend flow patterns help users analyze geo-referenced temporal events. However, it is difficult to extract and visualize overall trend flow patterns using data that has no trajectory information for movements. In order to visualize overall trend flow patterns, in this paper, we estimate continuous distributions of discrete events over time using KDE, and we extract vector fields from the continuous distributions using the gravity model. We then apply our technique on twitter data to validate techniques.
Encrypted Data Deduplication Using Key Issuing Server
Hyun-il Kim, Cheolhee Park, Dowon Hong, Changho Seo
Data deduplication is an important technique for cloud storage savings. These techniques are especially important for encrypted data because data deduplication over plaintext is basically vulnerable for data confidentiality. We examined encrypted data deduplication with the aid of a key issuing server and compared Convergent Encryption with a technique created by M.Bellare et al. In addition, we implemented this technique over not only Dropbox but also an open cloud storage service, Openstack Swift. We measured the performance for this technique over Dropbox and Openstack Swift. According to our results, we verified that the encrypted data deduplication technique with the aid of a key issuing server is a feasible and versatile method.
Garbage Collection Technique for Non-volatile Memory by Using Tree Data Structure
Most traditional garbage collectors commonly use the language level metadata, which is designed for pointer type searching. However, because it is difficult to use this metadata in non-volatile memory allocation platforms, a new garbage collection technique is essential for nonvolatile memory utilization. In this paper, we design new metadata for managing information regarding non-volatile memory allocation called "Allocation Tree". This metadata is comprised of tree data structure for fast information lookup and a node that holds an allocation address and an object ID pair in key-value form. The Garbage Collector starts collecting when there are insufficient non-volatile memory spaces, and it compares user data and the allocation tree for garbage detection. We develop this algorithm in a persistent heap based non-volatile memory allocation platform called "HEAPO" for demonstration.
Task-to-Tile Binding Technique for NoC-based Manycore Platform with Multiple Memory Tiles
Jintaek Kang, Taeyoung Kim, Sungchan Kim, Soonhoi Ha
The contention overhead on the same channel in an NoC architecture can significantly increase a communication delay due to the simultaneous communication requests that occur. To reduce the overall overhead, we propose task-to-tile binding techniques for an NoC-based manycore platform, whereby it is assumed that the task mapping decision has already made. Since the NoC architecture may have multiple memory tiles as its size grows, memory clustering is used to balance the load of memory by making applications access different memory tiles. We assume that the information on the communication overhead of each application is known since it is specified in a dataflow task graph. Using this information, this paper proposes two heurisitics that perform binding of multiple tasks at once based on a proper memory clustering method. Experiments with an NoC simulator prove that the proposed heurisitic shows performance gains that are 25% greater than that of the previous binding heuristic.
Dual Write Buffer Algorithm for Improving Performance and Lifetime of SSDs
Se Jun Han, Dong Hyun Kang, Young Ik Eom
In this paper, we propose a hybrid write buffer architecture comprised of DRAM and NVRAM on SSD and a write buffer algorithm for the hybrid write buffer architecture. Unlike other write buffer algorithms, the proposed algorithm considers read pages as well as write pages to improve the performance of storage devices because most actual workloads are read-write mixed workloads. Through effectively managing NVRAM pages, the proposed algorithm extends the endurance of SSD by reducing the number of erase operations on NAND flash memory. Our experimental results show that our algorithm improved the buffer hit ratio by up to 116.51% and reduced the number of erase operations of NAND flash memory by up to 56.66%.
Vehicle License Plate Detection in Road Images
Kwangyong Lim, Hyeran Byun, Yeongwoo Choi
This paper proposes a vehicle license plate detection method in real road environments using 8 bit-MCT features and a landmark-based Adaboost method. The proposed method allows identification of the potential license plate region, and generates a saliency map that presents the license plate’s location probability based on the Adaboost classification score. The candidate regions whose scores are higher than the given threshold are chosen from the saliency map. Each candidate region is adjusted by the local image variance and verified by the SVM and the histograms of the 8bit-MCT features. The proposed method achieves a detection accuracy of 85% from various road images in Korea and Europe.
Automatic Prioritization of Requirements using Topic Modeling and Stakeholder Needs-Artifacts
Due to the limitations of budget, resources, and time invested in a project, software requirements should be prioritized and be implemented in order of importance. Existing approaches to prioritizing requirements mostly depend on human decisions. The manual prioritization process is based on intensive interactions with the stakeholders, thus raising the issues of scalability and biased prioritization. To solve these problems, we propose a fully automated requirements prioritization approach, ToMSN (Topic Modeling Stakeholder Needs for requirements prioritization), by topic modeling the stakeholder needs-artifacts earned in the requirements elicitation phase. The requirements dataset of a 30,000-user system was utilized for the performance evaluation. ToMSN showed competitive prioritizing accuracy with existing approaches without human aids, therefore solving scalability and biased prioritization issues.
An Automatic Rhythm and Melody Composition System Considering User Parameters and Chord Progression Based on a Genetic Algorithm
In this paper, we propose an automatic melody composition system that can generate a sophisticated melody by adding non-harmony tone in the given chord progression. An overall procedure consists of two steps, which are the rhythm generation and melody generation parts. In the rhythm generation part, we designed new fitness functions for rhythm that can be controlled by a user setting parameters. In the melody generation part, we designed new fitness functions for melody based on harmony theory. We also designed evolutionary operators that are conducted by considering a musical context to improve computational efficiency. In the experiments, we compared four metaheuristics to optimize the rhythm fitness functions: Simple Genetic Algorithm (SGA), Elitism Genetic Algorithm (EGA), Differential Evolution (DE), and Particle Swarm Optimization (PSO). Furthermore, we compared proposed genetic algorithm for melody with the four algorithms for verifying performance. In addition, composition results are introduced and analyzed with respect to musical correctness.
A Runtime Inspection Technique with Intent Specification for Developing Robust Android Apps
Myungpil-Ko, Kwanghoon Choi, Byeong-Mo Chang
Android apps suffer from intent vulnerabilities in that they abnormally stop execution when Android components such as, activity, service, and broadcast receiver, take malformed intents. This paper proposes a method to prevent intent vulnerabilities by allowing programmers to write a specification on intents that a component expects to have, and by checking intents against the specification in runtime. By declaring intent specifications, we can solve the problem that one may miss writing conditional statements, which check the validity of intents, or one may mix those statements with another regular code, so making it difficult to maintain them. We perform an experiment by applying the proposed method to 7 Android apps, and confirm that many of abnormal termination of the apps because of malformed intents can be avoided by the intent specification based runtime assertion.
Implementation of Adaptive Navigation for NPCs in Computer Games
Eunsol Kim, Hyeyeon Kim, Kyeonah Yu
Uniform navigation of NPCs in computer games is an important factor that can decrease the interest of game players. This problem is particularly noticeable in pathfinding when using a waypoint graph because the NPCs navigate using only predefined locations. In this paper we propose a method that enables adaptive navigations of NPCs by observing player movements. The proposed method involves modification of waypoints dynamically by observing the player"s point designation and use of the modified waypoints for NPC"s pathfinding. Also, we propose an algorithm to find the NPC-specific path by learning the landform preferences of players. We simulate the implemented algorithm in an RPG game made with Unity 4.0 and confirm that NPC navigations had more variety and improved according to player navigations.
Using a Greedy Algorithm for the Improvement of a MapReduce, Theta join, M-Bucket-I Heuristic
Theta join is one of the essential and important types of queries in database systems. As the amount of data needs to be processed increases, processing theta joins with a single machine becomes impractical. Therefore, theta join algorithms using distributed computing frameworks have been studied widely. Although one of the state-of-the-art theta-join algorithms uses M-Bucket-I heuristic, it is hard to use since running time of M-Bucket-I heuristic, which computes a mapping from a record to a reducer (i.e., reducer mapping), is O(n) where n is the size of input data. In this paper, we propose MBI-I algorithm which reduces the running time of M-Bucket-I heuristic to O(rmaxlogn and gives the same result as M-Bucket-I heuristic does. We also conducted several experiments to show algorithm and confirmed that our algorithm can improve the performance of a theta join by 10%.
A Review of Science of Databases and Analysis of Its Case Studies
Young-Kyoon Suh, Jong Wook Kim
In this paper we introduce a novel database research area called science of databases (SoDB) and carry out a comprehensive analysis of its case studies. SoDB aims to better understand interesting phenomena observed across multiple database management systems (DBMSes). While mathematical and engineering work in the database field has been dominant, less attention has been given to scientific approaches through which DBMSes can be better understood. Scientific investigations can lead to better engineered designs through deeper understanding of query optimizers and transaction processing. The SoDB research has investigated several interesting phenomena observed across different DBMSes and provided several engineering implications based on our uncovered results. In this paper we introduce a novel scientific, empirical methodology and describe the research infrastructure to enable the methodology. We then review each of a selected group of phenomena studied and present an identified structural causal model associated with each phenomenon. We also conduct a comprehensive analysis on the case studies. Finally, we suggest future directions to expand the SoDB research.
Long-Term Performance Evaluation of Scheduling Disciplines in OFDMA Multi-Rate Video Multicast Transmission
The orthogonal frequency-division multiple access (OFDMA) systems are well suited to multi-rate multicast transmission, as they allow flexible resource allocation across both frequency and time, and provide adaptive modulation and coding schemes. Unlike layered video coding, the multiple description coding (MDC) enables flexible decomposition of the raw video stream into two or more substreams. The quality of the video stream is expected to be roughly proportional to data rate sustained by the receiver. This paper describes a mathematical model of resource allocation and throughput in the multi-rate video multicast for the OFDMA wireless and mobile networks. The impact on mean opinion score (MOS), as a measurement of user-perceived quality (by employing a variety of scheduling disciplines) is discussed in terms of utility maximization and proportional fairness. We propose a pruning algorithm to ensure a minimum video quality even for a subset of users at the resource limitation, and show the optimal number of substreams and their rates can sustain.
The Application and Integration of an Improvement Technique for Layers of NETCONF
Modern networks consisting of various heterogeneous equipment are often installed in a distributed manner. Thus the NETCONF standard was established to manage networks centrally and efficiently. In this paper, we present a method that integrates each NETCONF layer into a single system based on the results of previous studies. In the RPC Layer, an asynchronous communication channel and parallel processes are possible using multi-threading. In the Operation Layer, operational efficiency is increased by using a data group with dependencies between the equipment configuration data and by improving the data structure, enabling efficiently processing of XML queries even with multiple managers. The data modeling techniques and grouping methods in the Content Layer are presented in detail for interoperability between the Operation Layer and the Content Layer. Finally, the GUI program was implemented and its implementation is reported. We performed an experiment comparing the improved NETCONF with the standard NETCONF to measure factors, such as query processing ratio, query processing speed, and CPU utilization. The improved NETCONF demonstrated excellent query processing ratio and query processing speed, whereas the standard NETCONF had excellent CPU utilization.
Named Entity Recognition Using Distant Supervision and Active Bagging
Seong-hee Lee, Yeong-kil Song, Hark-soo Kim
Named entity recognition is a process which extracts named entities in sentences and determines categories of the named entities. Previous studies on named entity recognition have primarily been used for supervised learning. For supervised learning, a large training corpus manually annotated with named entity categories is needed, and it is a time-consuming and labor-intensive job to manually construct a large training corpus. We propose a semi-supervised learning method to minimize the cost needed for training corpus construction and to rapidly enhance the performance of named entity recognition. The proposed method uses distance supervision for the construction of the initial training corpus. It can then effectively remove noise sentences in the initial training corpus through the use of an active bagging method, an ensemble method of bagging and active learning. In the experiments, the proposed method improved the F1-score of named entity recognition from 67.36% to 76.42% after active bagging for 15 times.
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