Vol. 42, No. 2,
Feb. 2015
Digital Library
A Path Fragment Management Structure for Fast Projection Candidate Selection of the Path Prediction Algorithm
Dongwon Jeong, Sukhoon Lee, Doo-Kwon Baik
This paper proposes an enhanced projection candidate selection algorithm to improve the performance of the existing path prediction algorithm. Various user path prediction algorithms have previously been developed, but those algorithms are inappropriate for a real-time and close user path prediction environment. To resolve this issue, a new prediction algorithm has been proposed, but several problems still remain. In particular, this algorithm should be enhanced to provide much faster processing performance. The major cause of the high processing time of the previous path prediction algorithm is the high time complexity of its projection candidate selection. Therefore, this paper proposes a new path fragment management structure and an improved projection candidate selection algorithm to improve the processing speed of the existing projection candidate selection algorithm. This paper also shows the effectiveness of the algorithm herein proposed through a comparative performance evaluation.
On-the-fly Monitoring Tool for Detecting Data Races in Multithread Programs
Bong-Jun Paeng, Se-Won Park, In-Bon Kuh, Ok-Kyoon Ha, Yong-Kee Jun
It is difficult and cumbersome to figure out whether a multithread program runs with concurrency bugs, such as data races and atomicity violations, because there are many possible executions of the program and a lot of the defects are hard to reproduce. Hence, monitoring techniques for collecting and analyzing the information from program execution, such as thread executions, memory accesses, and synchronization information, are important to locate data races for debugging multithread programs. This paper presents an efficient and practical monitoring tool, called VcTrace, that analyzes the partial ordering of concurrent threads and events during an execution of the program based on the vector clock system. Empirical results on C/C++ benchmarks using Pthreads show that VcTrace is a sound and practical tool for on-the-fly data race detection as well as for analyzing multithread programs.
Geometry Transformation in Spatial Domain Using Coefficient Changes in Frequency Domain toward Lightweight Image Encryption
Image data is mostly stored in compressed form because of its huge size. Therefore, a series of cumbersome procedures is required to apply a transformation to image data: decompression, extraction of spatial data, transformation and recompression. In this paper, we employ DCT(Discrete Cosine Transform) coefficients to change the spatial presentation of images. DCT is commonly used in still image compression standards such as JPEG and moving picture compression standards such as MPEG-2, MPEG-4, and H.264. In this paper, we derived mathematically the relationship between the geometry transformation in the spatial domain and coefficient changes in the DCT domain and verified it with images in the JPEG file format. Because of the efficiency of transformation in the frequency domain, our findings can be utilized for light-weight partial image encryption for privacy data protection or entertainment contents protection.
Storage I/O Subsystem for Guaranteeing Atomic Write in Database Systems
Kyuhwa Han, Dongkun Shin, Yongserk Kim
The atomic write technique is a good solution to solve the problem of the double write buffer. The atomic write technique needs modified I/O subsystems (i.e., file system and I/O schedulers) and a special SSD that guarantees the atomicity of the write request. In this paper, we propose the writing unit aligned block allocation technique (for EXT4 file system) and the merge prevention of requests technique for the CFQ scheduler. We also propose an atomic write-supporting SSD which stores the atomicity information in the spare area of the flash memory page. We evaluate the performance of the proposed atomic write scheme in MariaDB using the tpcc-mysql and SysBench benchmarks. The experimental results show that the proposed atomic write technique shows a performance improvement of 1.4～1.5 times compared to the double write buffer technique.
Performance Comparison between Hardware & Software Cache Partitioning Techniques
JiWoong Park, HeonYoung Yeom, Hyeonsang Eom
The era of multi-core processors has begun since the limit of the clock speed has been reached. These days, multi-core technology is used not only in desktops, servers, and table PCs, but also in smartphones. In this architecture, there is always interference between processes, because of the sharing of system resources. To address this problem, cache partitioning is used, which can be roughly divided into two types: software and hardware cache partitioning. When it comes to dynamic cache partitioning, hardware cache partitioning is superior to software cache partitioning, because it needs no page copy. In this paper, we compare the effectiveness of hardware and software cache partitioning on the AMD Opteron 6282 SE, which is the only commodity processor providing hardware cache partitioning, to see whether this technique can be effectively deployed in dynamic environments.
Hybrid Main Memory Systems Using Next Generation Memories Based on their Access Characteristics
Recently, computer systems have encountered difficulties in making further progress due to the technical limitations of DRAM based main memory technologies. This has motivated the development of next generation memory technologies that have high density and non-volatility. However, these new memory technologies also have their own intrinsic limitations, making it difficult for them to currently be used as main memory. In order to overcome these problems, we propose a hybrid main memory system, namely HyMN, which utilizes the merits of next generation memory technologies by combining two types of memory: Write-Affable RAM(WAM) and Read-Affable RAM(ReAM). In so doing, we analyze the appropriate WAM size for HyMN, at which we can avoid the performance degradation. Further, we show that the execution time performance of HyMN, which provides an additional benefit of durability against unexpected blackouts, is almost comparable to legacy DRAM systems under normal operations.
Robust Particle Filter Based Route Inference for Intelligent Personal Assistants on Smartphones
Much research has been conducted on location-based intelligent personal assistants that can understand a user"s intention by learning the user"s route model and then inferring the user"s destinations and routes using data of GPS and other sensors in a smartphone. The intelligence of the location-based personal assistant is contingent on the accuracy and efficiency of the real-time predictions of the user"s intended destinations and routes by processing movement information based on uncertain sensor data. We propose a robust particle filter based on Dynamic Bayesian Network model to infer the user"s routes. The proposed robust particle filter includes a particle generator to supplement the incorrect and incomplete sensor information, an efficient switching function and an weight function to reduce the computation complexity as well as a resampler to enhance the accuracy of the particles. The proposed method improves the accuracy and efficiency of determining a user"s routes and destinations.
An Illumination Invariant Traffic Sign Recognition in the Driving Environment for Intelligence Vehicles
Taewoo Lee, Kwangyong Lim, Guntae Bae, Hyeran Byun, Yeongwoo Choi
This paper proposes a traffic sign recognition method in real road environments. The video stream in driving environments has two different characteristics compared to a general object video stream. First, the number of traffic sign types is limited and their shapes are mostly simple. Second, the camera cannot take clear pictures in the road scenes since there are many illumination changes and weather conditions are continuously changing. In this paper, we improve a modified census transform(MCT) to extract features effectively from the road scenes that have many illumination changes. The extracted features are collected by histograms and are transformed by the dense descriptors into very high dimensional vectors. Then, the high dimensional descriptors are encoded into a low dimensional feature vector by Fisher-vector coding and Gaussian Mixture Model. The proposed method shows illumination invariant detection and recognition, and the performance is sufficient to detect and recognize traffic signs in real-time with high accuracy.
A Method of Interoperating Heterogeneous Simulation Middleware for L-V-C Combined Environment
Kunryun Cho, Giseop No, Sihyun Jung, Nopphon Keerativoranan, Chongkwon Kim
Simulation is used these days to verify the hypothesis or the new technology. In particular, National Defense Modeling & Simulation (M&S) is used to predict wartime situation and conduct the military training. National Defense M&S can be divided into three parts, live simulation, virtual simulation, and constructive simulation. Live simulation is based on the real environment, which allows more realistic sumulation; however, it has decreased budget efficiency, but reduced depictions of reality. In contrast, virtual and constructive simulations which are based on the virtual environment, have increased budget efficiency, but reduced depictions of reality. Thus, if the three parts of the M&S are combined to make the L-V-C combined environment, the disadvantages of each simulation can be complemented to increases the quality of the simulation. In this paper, a method of interworking heterogeneous simulation middeware for L-V-C combined environment is proposed, and the test results of interworking between Data Distribution Service (DDS) and High Level Architecture (HLA) are shown.
Korean Semantic Role Labeling Using Structured SVM
Changki Lee, Soojong Lim, Hyunki Kim
Semantic role labeling (SRL) systems determine the semantic role labels of the arguments of predicates in natural language text. An SRL system usually needs to perform four tasks in sequence: Predicate Identification (PI), Predicate Classification (PC), Argument Identification (AI), and Argument Classification (AC). In this paper, we use the Korean Propbank to develop our Korean semantic role labeling system. We describe our Korean semantic role labeling system that uses sequence labeling with structured Support Vector Machine (SVM). The results of our experiments on the Korean Propbank dataset reveal that our method obtains a 97.13% F1 score on Predicate Identification and Classification (PIC), and a 76.96% F1 score on Argument Identification and Classification (AIC).
Learning Multiple Instance Support Vector Machine through Positive Data Distribution
Joong-Won Hwang, Seong-Bae Park, Sang-Jo Lee
This paper proposes a modified MI-SVM algorithm by considering data distribution. The previous MI-SVM algorithm seeks the margin by considering the “most positive” instance in a positive bag. Positive instances included in positive bags are located in a similar area in a feature space. In order to reflect this characteristic of positive instances, the proposed method selects the “most positive” instance by calculating the distance between each instance in the bag and a pivot point that is the intersection point of all positive instances. This paper suggests two ways to select the “most positive” pivot point in the training data. First, the algorithm seeks the “most positive” pivot point along the current predicted parameter, and then selects the nearest instance in the bag as a representative from the pivot point. Second, the algorithm finds the “most positive” pivot point by using a Diverse Density framework. Our experiments on 12 benchmark multi-instance data sets show that the proposed method results in higher performance than the previous MI-SVM algorithm.
Locally Linear Embedding for Face Recognition with Simultaneous Diagonalization
Eun-Sol Kim, Yung-Kyun Noh, Byoung-Tak Zhang
Locally linear embedding (LLE) [1] is a type of manifold algorithms, which preserves inner product value between high-dimensional data when embedding the high-dimensional data to low-dimensional space. LLE closely embeds data points on the same subspace in low-dimensional space, because the data points have significant inner product values. On the other hand, if the data points are located orthogonal to each other, these are separately embedded in low-dimensional space, even though they are in close proximity to each other in high-dimensional space. Meanwhile, it is well known that the facial images of the same person under varying illumination lie in a low-dimensional linear subspace [2]. In this study, we suggest an improved LLE method for face recognition problem. The method maximizes the characteristic of LLE, which embeds the data points totally separately when they are located orthogonal to each other. To accomplish this, all of the subspaces made by each class are forced to locate orthogonally. To make all of the subspaces orthogonal, the simultaneous Diagonalization (SD) technique was applied. From experimental results, the suggested method is shown to dramatically improve the embedding results and classification performance.
Efficient Multi-Step k-NN Search Methods Using Multidimensional Indexes in Large Databases
Sanghun Lee, Bum-Soo Kim, Mi-Jung Choi, Yang-Sae Moon
In this paper, we address the problem of improving the performance of multi-step k-NN search using multi-dimensional indexes. Due to information loss by lower-dimensional transformations, existing multi-step k-NN search solutions produce a large tolerance (i.e., a large search range), and thus, incur a large number of candidates, which are retrieved by a range query. Those many candidates lead to overwhelming I/O and CPU overheads in the postprocessing step. To overcome this problem, we propose two efficient solutions that improve the search performance by reducing the tolerance of a range query, and accordingly, reducing the number of candidates. First, we propose a tolerance reduction-based (approximate) solution that forcibly decreases the tolerance, which is determined by
a k-NN query on the index, by the average ratio of high- and low-dimensional distances. Second, we propose a coefficient control-based (exact) solution that uses c?k instead of k in a k-NN query to obtain a tigher tolerance and performs a range query using this tigher tolerance. Experimental results show that the proposed solutions significantly reduce the number of candidates, and accordingly, improve the search performance in comparison with the existing multi-step k-NN solution.
A Path Prediction-Based Sensor Registry System for Stable Use of Sensor Information
The sensor registry system has been developed for instant use and seamless interpretation of sensor data in a heterogeneous sensor network environment. However, the existing sensor registry system cannot provide information for interpretation of the sensor data in situations in which the network is unstable. This limitation causes several problems such as sensor data loss, inaccuracy of processed results, and low service quality. A method to resolve such problems in the aspect of software is presented herein. In other words, an extended sensor registry system is proposed to enable the stable use of sensor information, even under conditions of unstable network connection, by providing sensor information with a mobile device in advance through the user path prediction. The results of experiments and evaluation are also presented. The extended sensor registry system proposed in this paper enhances the stable usability of sensor information as well as improves the quality of sensor-based services.
Performance Analysis on an Object Location Estimation Algorithm Using a Single Receiver
Enkhzaya Myagmar, Soonryang Kwon, Dong Myung Lee
The general way to use a triangulation method is based on PTMP communication between an object and wireless modules in an environment, which is established by more than three wireless modules, to recognize the location of an object. Thus, this method has a problem that the PTMP-based system can only be applied in an environment where the wireless infra is already established. In order to solve this problem, the PTP communication schemes have been proposed but they are insufficient to generalize because they lack specific verification. In this paper, problems of an existed location estimation algorithm based on PTP communication are analyzed, and we propose a location estimation algorithm of a fixed object that satisfyies the condition of a single receiver being substituted to multiple receivers. A location estimation system we designed and implemented using CSS wireless communication modules to evaluate the proposed algorithm. We verify, by experimental results, that the optimum moving interval for the location estimation is 3m in indoor environment of 10m × 16m × 1m.
A Subway Arrival Notification System Using iBeacon
Hyun-Hee Jung, Choon-Sung Nam, Dong-Ryeol Shin
Concurrent with the more widespread usage of smart devices, mobile users’ desires are becoming much more complex. Most IT experts insist that smart devices should have additional functions to satisfy these requirements. In particular, research has concentrated on LBS (Locationbased Service), because it is considered one of the most common mobile service types. Generally, Wi-Fi has a critical limitation for use for LBS services, because it requires new network connection points whenever its location (Network Zone) changes. Unfortunately, GPS also has a systematic problem in providing LBS service in the indoor environment, because of its inaccuracy in processing data. So, to redress these limitations, iBeacon technology has been designed, and is currently used for LBS service instead of Wi-Fi or GPS. By using iBeacon, which is based on Bluetooth 4.0 LE technology, we propose a M-SAS (Mobile-Subway-Alarm-Service System) that could accurately and timely provide its users with various mLBS (micro LBS) services, such as current user location, and subway arrival time.
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