Vol. 45, No. 11,
Nov. 2018
Digital Library
An Order-Preserving Pattern Matching Algorithm using Fingerprints of Two q-grams
Gwangmo Yoo, Youngho Kim, Jeong Seop Sim
http://doi.org/10.5626/JOK.2018.45.11.1111
Given a text T of length n and a pattern P of length m, the order-preserving pattern matching problem is to find all substrings in T that have the same relative orders as P. Recently, an O(nm+nqlogq+q!)-time order-preserving pattern matching algorithm was proposed that uses fingerprints of q-grams. In this paper, we propose an order-preserving pattern matching algorithm using the fingerprints of two q-grams to improve execution times. The experimental results for randomly generated T (n = 5,000,000) and P (m = 5,10,15) show that our algorithm runs up to approximately 12% faster than the previous algorithm. Also, for T using Dow Jones Industrial Average (n = 34,658) and P (m = 5,10,15) randomly extracted from T, our algorithm runs up to approximately 10% faster than the previous algorithm.
Design and Implementation of a Log-structured Buffer Based on Non-volatile Memory
http://doi.org/10.5626/JOK.2018.45.11.1117
Next-generation non-volatile memory (NVM) technologies, such as PCM and STTMRAM, provide low latency, high bandwidth, non-volatility, and high capacity. Such NVMs are widely used and studied in the field of computer systems and databases for high performance computing. For example, recent researchers have used NVM for journaling buffers and database logging of file systems and have conducted many optimization studies accordingly. As a complement to existing work, this paper focuses on the atomic page update of applications. For example, in a data management application such as a database system, the atomicity of the pages is ensured by performing a redundant write operation with a temporary buffer in order to atomically update multiple pages. However, this redundant write operation can reduce the performance. Therefore, in this paper, we introduce a log-structured buffer manager (LSMB) to improve the performance while ensuring the consistency. LSBM updates the page to NVM by logging and provides buffering. In addition, if there are duplicated pages in the buffer, the old version of the page is removed to reflect only the latest page, which minimizes the I/O and write amount. Experimental results show that LSBM improves the performance of the application and reduces the total write amount.
User Behavior Analysis for Predicting Churn of Loyal Customers in Online Games based on Social Relationships and Degree of Participation
Eunbi Seo, Jiyoung Woo, Huy Kang Kim
http://doi.org/10.5626/JOK.2018.45.11.1124
Game users in MMORPGs engage in a variety of social activities. However, a few users tend to play games alone, and are designated ‘loners’ similar to modern society. We classified game guilds and game users based on similar user behaviors and community characteristics. We propose a model that predicts churn users by measuring the participation of users in each group. Users in each group show similar behavioral patterns, suggesting that we can classify churn users along with ordinary users. We tested this model for NCsoft’s MMORPG, Aion. Using Randomforest, the recall was measured at an average of 75%.
Design and Implementation of Mobile Application Speed Index Measuring Tool
Hyunsik Yoo, Hyunsu Mun, Youngseok Lee
http://doi.org/10.5626/JOK.2018.45.11.1135
Because the speed of mobile applications(apps) has a considerably large impact on user experience, developers consider increasing app speed to improve user satisfaction. However, the measurement method employed in the Android development tool does not indicate the actual speed experienced by the user because it does not measure the rendering time of the download content. This study proposes a method to measure the speed of a mobile app by applying a speed index, which is a web performance index, to a mobile app. In this study, we developed a random user event generator and a mobile speed analyzer. By calculating the speed index for 1093 apps on the Google Play Store Top Charts, we found that 8% of the apps were slow.
Ontology-based Approach to Determine the Conflicts between Security and Usability Requirements in the Requirements Engineering Process
http://doi.org/10.5626/JOK.2018.45.11.1142
Considering the trade-offs or conflicts between security and usability during the requirements engineering (RE) process is a complicated task. This is due to the contrary characteristics of security and usability as well as a lack of research on finding a consensus on the semantics of quality attributes, especially for security and usability. Furthermore, the number of security experts available is decreasing, while a methodology to determine the conflicts between security and usability during the RE process has not yet been developed. We, therefore, propose a novel approach to construct a three-layer ontological knowledge base by linking the keywords from definitions, criteria, and metrics of security and usability. In addition, we discuss the applicability of this knowledge base by examining two case studies with software engineering (SE) students. These case studies show that the participants using the proposed approach (Team A) can derive conflicts that are more precise compared to the participants who did not use the knowledge base (Team B). Moreover, the number of conflicts derived by Team A is half that by Team B. Regardless of the knowledge level, the proposed approach can determine the conflicts between security and usability during the RE process. Also, while practical RE studies have often been considered difficult to handle, the proposed approach can show the applicability of RE research.
An Integrated Analysis Method Considering Security in ISO 26262 for Improving the Safety of the Vehicle
http://doi.org/10.5626/JOK.2018.45.11.1156
Recently, new technologies and services such as autonomous driving, Connected Car, ADAS and V2X have been applied to vehicles. With more than 1G byte of code and more than 70 ECUs, the automotive is continuously getting complex and connected. These situations have led to the emergency of security problems along with increase in security risks. However, there respectively exist safety processes dealing with automobile safety and security processes dealing with security, so that automobile safety problems arising from security threats are not prepared. Furthermore, ISO 26262 Second Edition calls for consideration of the mutual influence of security and security. In this paper, we propose an integrated analysis method considering security in ISO 26262 with aim of contribution towards improvement the safety of the vehicle.
Partial Embedding Approach for Knowledge Completion
Wan-Gon Lee, Batselem Jagvaral, Ji-Hun Hong, Hyun-Young Choi, Young-Tack Park
http://doi.org/10.5626/JOK.2018.45.11.1168
Knowledge graphs are large networks that describe real world entities and their relationships with triples. Most of the knowledge graphs are far from being complete, and many previous studies have addressed this problem using low dimensional graph embeddings. Such methods assume that knowledge graphs are fixed and do not change. However, real-world knowledge graphs evolve at a rapid pace with the addition of new triples.Repeated retraining of embedding models for the entire graph is computationally expensive and impractical. In this paper, we propose a partial embedding method for partial completion of evolving knowledge graphs. Our method employs ontological axioms and contextual information to extract relations of interest and builds entity and relation embedding models based on instances of such relations. Our experiments demonstrated that the proposed partial embedding method can produce comparable results on knowledge graph completion with state-of-the-art methods while significantly reducing the computation time of entity and relation embeddings by 49%–90% for the Freebase and WiseKB datasets.
Implementing Structural Operational Semantics in Python
http://doi.org/10.5626/JOK.2018.45.11.1176
Operational semantics is the most commonly used technique to formally define the semantics of a programming language. It defines the meaning of a program in terms of how it is executed or interpreted as a sequence of computational steps. This paper introduces an implementation technique for small-step structural operational semantics for a simple ML-style functional language using visitor patterns and exception handling in Python. The secondary objective of this paper is to explain the core concepts of programming language theory and the techniques for implementing these concepts using Python, instead of traditional functional languages such as ML, Haskell, and Scheme. Since Python has a wide abundant user base due to its rich library and flexibility, it is more suitable to explain operational semantics for common users than functional languages, which are relatively less known and have a high learning curve.
Semi-Supervised Learning for Detecting of Abusive Sentence on Twitter using Deep Neural Network with Fuzzy Category Representation
http://doi.org/10.5626/JOK.2018.45.11.1185
The number of people embracing damage caused by hate speech on the SNS(Social Network Service) is increasing rapidly. In this paper, we propose a detection method using Semi-supervised learning and Deep Neural Network from a large file to determine whether implied meaning of sentence beyond hate speech detection through comparison with a simple dictionary in twitter sentence is abusive or not. Most of the methods judge the hate speech sentence by comparing with a blacklist comprising of hate speech words. However, the reported methods have a disadvantage that skillful and subtle expression of hate speech cannot be identified. So, we created a corpus with a label on whether or not to hate speech on Korean twitter sentence. The training corpus in twitter comprised of 44,000 sentences and the test corpus comprised of 13,082 sentences. The system performance about the explicit abusive sentences of the F1 score was 86.13% on the model using 1-layer syllable CNN and sequence vector. And the system performance about the implicit abusive sentences of the F1 score 25.53% on the model using 1-layer syllable CNN and 2-layer syllable CNN and sequence vector. The proposed method can be used as a method for detecting cyber-bullying.
A Persistent Log Buffer Technique using Non-volatile Memory for In-Memory Key-Value Databases
Doyoung Kim, Won Gi Choi, Hanseung Sung, Jihwan Lee, Sanghyun Park
http://doi.org/10.5626/JOK.2018.45.11.1193
Redis, an In-Memory Key-Value Database, is widely used in services that require real time data processing and storage. Since main memory is volatile, Redis has a problem of data loss if the system is terminated abnormally. To prevent this problem, Redis stores logs on disk, preventing data loss by restoring logs when the system is terminated. The AOF recovery mechanism, a method of appending requested commands in disk as a log format, operates with the “everysec” policy that writes logs every second, and the “always” policy that writes a log every time a command is requested. The “everysec” policy does not degrade performance of Redis, but data loss can occur if the system is terminated abnormally within one second. Conversely, the “always” policy does not cause data loss, but it requires disk operation for every command, causing performance degradation. We propose a system model that constructs AOF buffer in non-volatile memory and stores logs in the buffer, which are not synchronized to disk in the “everysec” policy. The proposed model prevents data loss and has approximately 100 times better performance than the “always” policy.
Reverse Path Activation-based Reverse Influence Maximization in Social Networks
Ashis Talukder, Anupam Kumar Bairagi, Do Hyeon Kim, Choong Seon Hong
http://doi.org/10.5626/JOK.2018.45.11.1203
Influence Maximization (IM) deals with finding influential users for viral marketing in social networks, whereas Reverse Influence Maximization (RIM), a new research direction in the influence-maximization domain, deals with seeding cost, also known as opportunity cost. The IM estimates a small seed set in such a way that by targeting those seed nodes, the influence is maximized in the network. Generally, the seed nodes are assumed to be activated initially in the IM problem. However, we argue that seed nodes need to be influenced by some of their in-neighbor nodes in a similar way how an activated node influences its out-neighbors to be activated. The RIM problem finds the seeding cost, which is defined by the minimum number of nodes that must be activated in order to activate all the seed nodes. In this paper, we propose an Active Reverse Path-based Reverse Influence Maximization (ARP-RIM) model to find the minimum seeding cost. Our model is based on the voting model and the classic Independent Cascade model. We simulate our model with three real datasets of three popular social networks. The experimental result shows that the ARP-RIM model outperforms existing RIM models.
Knowing the Cost of Synchronization Primitives on Modern Hardware
SeongJae Park, Hyuck Han, Heon Y. Yeom
http://doi.org/10.5626/JOK.2018.45.11.1210
In multi-core systems, which are widely prevalent, it is important to use an efficient concurrency control algorithm that utilizes every core. However, Amdahl’s Law states that a program cannot scale infinitely if it contains any unscalable sub-section. Furthermore, the Laws of Orders state that the expensive cost of synchronization for ordering in a concurrent algorithm cannot be eliminated. As a consequence, knowing the cost of each synchronization primitive is important for making tradeoff decisions regarding an algorithm. Although the rough costs of common synchronization primitives are already known, the result may be not applicable or inaccurate for a specific system, because the cost is hardware dependent. In this paper, we evaluate the cost of famous synchronization primitives on a modern system and discuss the results.
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