Vol. 42, No. 3,
Mar. 2015
Digital Library
Workflow Based on Pipelining for Performance Improvement of Volcano Disaster Damage Prediction System
Daeyoung Heo, Donghwan Lee, Suntae Hwang
A volcano disaster damage prediction system supports decision making for counteracting volcanic disasters by simulating meteorological condition and volcanic eruptions. In this system, a program called Fall3D generates predicted results for the diffusion of ash after a volcanic eruption on the basis of meteorological information. The relevant meteorological information is generated by a weather numerical prediction model known as Weather Research & Forecasting (WRF). In order to reduce the entire processing time without modifying these two simulation programs, pipelining can be used by partly executing Fall3D whenever the hourly (partial) results of WRF are generated. To reduce the processing time, successor programs such as Fall3D require that certain features be suspended until the part of the results that is based on prior calculation is generated by a predecessor. Even though Fall3D does not have a suspend or resume feature, pipelining effect can be produced by using the program’s restart feature, which resumes simulation from the previous session. In this study, we suggest a workflow that can control the execution type.
Parallel Algorithms for Finding Consensus of Circular Strings
The consensus problem is finding a representative string, called a consensus, of a given set S of k strings. Circular strings are different from linear strings in that the last symbol precedes the first symbol. Given a set S of circular strings of length n over an alphabet ∑ , we first present an O(｜∑｜nlogn) time parallel algorithm for finding a consensus of S minimizing both radius and distance sum when k=3 using O(n) threads. Then we present an O(｜∑｜n²logn) time parallel algorithm for finding a consensus of S minimizing distance sum when k=4 using O(n) threads. Finally, we compare execution times of our algorithms implemented using CUDA with corresponding sequential algorithms.
MOnCa2: High-Level Context Reasoning Framework based on User Travel Behavior Recognition and Route Prediction for Intelligent Smartphone Applications
MOnCa2 is a framework for building intelligent smartphone applications based on smartphone sensors and ontology reasoning. In previous studies, MOnCa determined and inferred user situations based on sensor values represented by ontology instances. When this approach is applied, recognizing user space information or objects in user surroundings is possible, whereas determining the user’s physical context (travel behavior, travel destination) is impossible. In this paper, MOnCa2 is used to build recognition models for travel behavior and routes using smartphone sensors to analyze the user’s physical context, infer basic context regarding the user’s travel behavior and routes by adapting these models, and generate high-level context by applying ontology reasoning to the basic context for creating intelligent applications. This paper is focused on approaches that are able to recognize the user’s travel behavior using smartphone accelerometers, predict personal routes and destinations using GPS signals, and infer high-level context by applying realization.
A Scalable OWL Horst Lite Ontology Reasoning Approach based on Distributed Cluster Memories
Current ontology studies use the Hadoop distributed storage framework to perform map-reduce algorithm-based reasoning for scalable ontologies. In this paper, however, we propose a novel approach for scalable Web Ontology Language (OWL) Horst Lite ontology reasoning, based on distributed cluster memories. Rule-based reasoning, which is frequently used for scalable ontologies, iteratively executes triple-format ontology rules, until the inferred data no longer exists. Therefore, when the scalable ontology reasoning is performed on computer hard drives, the ontology reasoner suffers from performance limitations. In order to overcome this drawback, we propose an approach that loads the ontologies into distributed cluster memories, using Spark (a memory-based distributed computing framework), which executes the ontology reasoning. In order to implement an appropriate OWL Horst Lite ontology reasoning system on Spark, our method divides the scalable ontologies into blocks, loads each block into the cluster nodes, and subsequently handles the data in the distributed memories. We used the Lehigh University Benchmark, which is used to evaluate ontology inference and search speed, to experimentally evaluate the methods suggested in this paper, which we applied to LUBM8000 (1.1 billion triples, 155 gigabytes). When compared with WebPIE, a representative mapreduce algorithm-based scalable ontology reasoner, the proposed approach showed a throughput improvement of 320% (62k/s) over WebPIE (19k/s).
An Intention-Response Model based on Mirror Neuron and Theory of Mind using Modular Behavior Selection Networks
Although service robots in various fields are being commercialized, most of them have problems that depend on explicit commands by users and have difficulty to generate robust reactions of the robot in the unstable condition using insufficient sensor data. To solve these problems, we modeled mirror neuron and theory of mind systems, and applied them to a robot agent to show the usefulness. In order to implement quick and intuitive response of the mirror neuron, the proposed intention-response model utilized behavior selection networks considering external stimuli and a goal, and in order to perform reactions based on the long-term action plan of theory of mind system, we planned behaviors of the sub-goal unit using a hierarchical task network planning, and controled behavior selection network modules. Experiments with various scenarios revealed that appropriate reactions were generated according to external stimuli.
Methodology for Traceability Management and Impact Analysis for Efficient Change Management in Object-Oriented Development
Software requirements are continuously changed for various reasons, consequently changes of software are inevitable. In the case of changes necessitated by changes in requirements, it is necessary to precisely predict the ripple effects of the changes for efficient management of the changes. This paper proposes the management method of traceability information, which can be applied in object-oriented development. Furthermore, we introduce the guidelines for prediction of the ripple effects of changes based on traceability information among artifacts composing a system. We identify traceability items for the essential artifacts which were composed of the object-oriented system, and define relationships among them. The purpose of the method proposed in this paper is to identify the scope of change precisely through the guidelines. These can then be used for tracing and analyzing the impact of the changes both the forward and backward looking, based on the relationships of traceability items.
A Software Architecture Design Method that Matches Problem Frames and Architectural Patterns
Jungmin Kim, Sungwon Kang, Jihyun Lee
While architectural patterns provide software development solutions by providing schemas for structural organizations of software systems based on empirical knowledge, Jackson’s problem frames provide a method of analyzing software problems. Problem frames are useful to understanding the software development problem, by putting emphasis on the problem domain, rather than on the solution space. Research exists that relates problem frames and software architecture, but most of this research uses problem frames only to understand given problems. Moreover, none of the existing research derives architectural patterns by considering both problem frames and quality attributes. In this paper, we propose a software architecture design method for pattern-based architecture design, by matching problem frames and architectural patterns. To that end, our approach first develops the problem model based on the problem frames approach, and then uses it to match with candidate architectural patterns, from the perspectives of both functionality, and quality attributes. Functional matching uses the problem frame diagram to match the problem model of an architectural pattern. We conduct a case study to show that our approach can systematically decide the right architectural patterns, and provide a basis for fine-grained software architecture design.
A One-Gap Parsing with Extended PLR(1) Grammars
Gap parsing is an algorithm for parsing incomplete input strings which include some gaps. Gap parsing is different from conventional parsing, and as known results, one-gap parsing algorithms for arbitrary context-free grammar and LL(1) grammar have O(n³) and O(n²) time complexity, respectively.
This paper presents a one-gap parsing algorithm for extended PLR(1) grammars. Extended PLR(1) grammars are the class of grammars smaller than LR(1) but much larger than LL(1). The one-gap parsing algorithm of the grammar class is shown to have the time complexity of O(n²), which is equal to the complexity of one-gap parsing algorithms for LL(1) grammars.
Competition Relation Extraction based on Combining Machine Learning and Filtering
ChungHee Lee, YoungHoon Seo, HyunKi Kim
This study was directed at the design of a hybrid algorithm for competition relation extraction. Previous works on relation extraction have relied on various lexical and deep parsing indicators and mostly utilize only the machine learning method. We present a new algorithm integrating machine learning with various filtering methods. Some simple but useful features for competition relation extraction are also introduced, and an optimum feature set is proposed. The goal of this paper was to increase the precision of competition relation extraction by combining supervised learning with various filtering methods. Filtering methods were employed for classifying compete relation occurrence, using distance restriction for the filtering of feature pairs, and classifying whether or not the candidate entity pair is spam. For evaluation, a test set consisting of 2,565 sentences was examined. The proposed method was compared with the rule-based method and general relation extraction method. As a result, the rule-based method achieved positive precision of 0.812 and accuracy of 0.568, while the general relation extraction method achieved 0.612 and 0.563, respectively. The proposed system obtained positive precision of 0.922 and accuracy of 0.713. These results demonstrate that the developed method is effective for competition relation extraction.
A Comparative Study of PRAM-based Join Algorithms
Yongsung Choi, Byung-Won On, Gyu Sang Choi, Ingyu Lee
With the advent of non-volatile memories such as Phase Change Memory (PCM or PRAM) and Magneto Resistive RAM (MRAM), active studies have been carried out on how to replace Dynamic Random-Access Memory (DRAM) with PRAM. In this paper, we study both endurance and performance issues of existing join algorithms that are based on PRAM-based computer systems and have been widely used until now: Block Nested Loop Join, Sort-Merge Join, Grace Hash Join, and Hybrid Hash Join. Our experimental results show that the existing join algorithms need to be redesigned to improve both the endurance and performance of PRAMs. To the best of our knowledge, this is the first research to scientifically study the results of the four join algorithms running on PRAM-based systems. In this work, our main contribution is the modeling and implementation of a PRAM-based simulator for a comparative study of the existing join algorithms.
An Efficient Retrieval Technique for Spatial Web Objects
Spatial web objects refer to web documents that contain geographic information. Recently, services that create spatial web objects have increased greatly because of the advancements in devices such as smartphones. For services such as Twitter or Facebook, simple texts posted by users is stored along with information about the post’s location. To search for such spatial web objects, a method that uses spatial information and text information simultaneously is required. Conventional spatial web object search methods mostly use R-tree and inverted file methods. However, these methods have a disadvantage of requiring a large volume of space when building indices. Furthermore, such methods are efficient for searching with many keywords but are inefficient for searching with a few keywords.. In this paper, we propose a spatial web object search method that uses a quad-tree and a patricia-trie. We show that the proposed technique is more effective than existing ones in searching with a small number of keywords. Furthermore, we show through an experiment that the space required by the proposed technique is much smaller than that required by existing ones.
Analysis of Energy Consumption and Processing Delay of Wireless Sensor Networks according to the Characteristic of Applications
Chong Myung Park, Young Tak Han, Soobin Jeon, Inbum Jung
Wireless sensor networks are used for data collection and processing from the surrounding environment for various applications. Since wireless sensor nodes operate on low computing power, restrictive battery capacity, and low network bandwidth, their architecture model has greatly affected the performance of applications. If applications have high computation complexity or require the real-time processing, the centralized architecture in wireless sensor networks have a delay in data processing. Otherwise, if applications only performed simple data collection for long period, the distributed architecture wasted battery energy in wireless sensors. In this paper, the energy consumption and processing delay were analyzed in centralized and distributed sensor networks. In addition, we proposed a new hybrid architecture for wireless sensor networks. According to the characteristic of applications, the proposed method had the optimal number of wireless sensors in wireless sensor networks.
TAILWIND: Mobility information based Routing for Delay Tolerant Network
Seoik Cho, Sunhyun Kim, Soohoon Moon, Seungjae Han
In base station based networks, traffic overload at the base station is inevitable. Peerto-peer DTN which disperses the traffic overhead to each node can relieve the traffic overload at the base station. To increase the message delivery ratio and reduce the message overhead, we present novel routing using mobility information which can be obtained from each node, unlike the existing flooding based routings. In the proposed routing scheme, the routing decision metric, which is defined based on the node mobility information, is computed by using the expected distance between each node to the destination. The message is copied to other nodes that have lower expected distance to the destination than the value for the node willing to copy the message. We conducted simulations by using both a random mobility model and a real mobility trace to compare the performance of the proposed routing scheme to the existing routing scheme that does not utilize the mobility information. The performance evaluation showed the proposed routing successfully delivers messages with 10% to 30% less copies compared to previously proposed routing schemes.
Design of a Video Metadata Schema and Implementation of an Authoring Tool for User Edited Contents Creation
In this paper, we design new video metadata schema for searching video segments to create UEC (User Edited Contents). The proposed video metadata schema employs hierarchically structured units of ‘Title-Event-Place(Scene)-Shot’, and defines the fields of the semantic information as structured form in each segment unit. Since this video metadata schema is defined by analyzing the structure of existing UECs and by experimenting the tagging and searching the video segment units for creating the UECs, it helps the users to search useful video segments for UEC easily than MPEG-7 MDS (Multimedia Description Scheme) which is a general purpose international standard for video metadata schema.
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