Earticle

그래는 생물학, 화학, 사회 계망 데이터 등 복잡한 구조의 데이터를 모델링하는데 리 사용되는 자료구조이다. 이러한 그래 데이터에서 서로 유사한 데이터를 찾아내는 것은 매우 다양한 응용에서 필수으로 요구되는 작업이 다. 본 논문에서는 화학 그래에 을 맞추어, 필터링-검증 임워크 기반의 유사도 기반 그래 질의 처리 기 법을 제안한다. 계산량이 많은 그래 데이터의 특징에 맞는 필터링 방법을 제안하고, 후보 그래들을 효율으로 검증하기 한 기법을 제안한다. 한, 규모 데이터에서 실시간 분석이 가능할 수 있도록 MapReduce를 이용 하는 분산처리 기법을 제안하고, 실 데이터에 한 실험을 통해 본 논문에서 제안하는 방법이 유사도 기반 그래 질의 처리의 성능을 크게 개선함을 입증한다.

Graph is widely used to model complex structured data such as biomedical data, chemical data, and social network data. It is essential to find graphs similar to a given query in many applications. In this paper, we focus on chemical graph data and propose a graph similarity query processing technique based on a filtering and verification framework. We propose a filtering technique considering the heavy computation requirement of graph data and develop a novel technique to efficiently verify candidate graphs. We also propose a distributed processing framework using MapReduce to support large scale graph data. Through the experiments on real chemical data, we show that the proposed technique substantially improves the performance of query processing.

Attempts to hack online game servers and abusing problems in online games have been issues in gameindustry. Mobile games are famous these days thanks to the widespread of smart devices. Unfortunately, mobilegames have very short life cycle. Therefore, analysis of game log data becomes more important to overcome thehacking and abusing problems in online games and extend their life cycles in mobile games. In this paper, wepropose a new game log data analysis technique based on the MapReduce methodology. MapReduce is a widelyused programming model for analyzing and processing Big data. Instead of processing each analysis queryseparately, the proposed technique processes multiple analysis queries together in a batch by a single, optimizedMapReduce job. As a result, the number of queries processed per unit time increases significantly. Experimentresults show that the proposed technique improves the performance significantly compared to a naive method.

This study measured the stream data from the several sensors, and stores the database in MapReduce framework environment, and it aims to design system with the small performance and cluster analysis error rate through the KMSVM algorithm. Through the KM-SVM algorithm, the cluster analysis effective data was used for U-health system. In the results of experiment by using 2003 data sets obtained from 52 test subjects, the k-NN algorithm showed 79.29% cluster analysis accuracy, K-means algorithm showed 87.15 cluster analysis accuracy, and SVM algorithm showed 83.72%, KM-SVM showed 90.72%. As a result, the process speed and cluster analysis effective ratio of KM- SVM algorithm was better.

편집거리는 근사문자열매칭의 대표적인 점수척도로, 길이가 m, n인 두 문자열에 대한 편집거리는 동적프로그래밍 을 이용하여 O(mn) 시간에 계산할 수 있다. 편집거리 계산을 위한 다양한 알고리즘이 연구되고 있으며 그 중에는 병렬 알고리즘에 대한 연구도 포함되어 있다. 본 논문에서는 두 문자열에 대한 편집거리를 계산하는 맵리듀스 알고 리즘을 제시한다. O(mn) 시간에 동작하는 Wagner와 Fischer의 알고리즘과 O(mn/t) 시간에 동작하는 4-러 시안 알고리즘을 각각 맵리듀스 알고리즘으로 변환하고 설명한다. 그리고 맵리듀스 알고리즘들에 대한 이론적인 비용 분석과 함께 제안하는 알고리즘들이 순차 알고리즘보다 시간 효율성을 갖기 위한 조건도 제시한다.

The edit distance metric is one of the most widely used scoring metric for the approximate string matching. Given two strings with lengths m and n, we can compute the edit distance between them in O(mn) time using dynamic programming technique. There are several algorithms for the edit distance problem and some of them are parallel algorithms. In this paper, we present two MapReduce algorithms for the edit distance problem between two strings. We convert the Wagner and Fischer algorithm and the Four-Russians algorithms to the MapReduce algorithms and explain them. In addition, we explain some theoretical analysis for our algorithms using a cost model for MapReduce.

맵리듀스는 하둡의 필수 핵심 기술로 하둡 분산 파일 시스템을 기반으로 빅데이터를 처리하는 가장 보편화되어 사용되고 있다. 그러나 기존 맵리듀스 기반 빅데이터 처리 기법은 하둡 분산 파일 시스템에 정해진 블록의 크기대로 파일 나눠 저장되는 특징으로 인해 인프라 자원의 낭비가 극심하다. 이에 본 논문에서는 효율적인 맵리듀스 기반 빅데이터 처리 기법을 제안한다. 제안하는 기법은 처리할 데이터를 사전에 맵리듀스에서 처리하기 적합한 데이터 형태로 변환 및 압축하여 빅데이터 인프라 환경의 저장 효율성을 증가시킨다. 또한 제안하는 기법은 저장 효율성을 중점으로 구현했을 때 발생할 수 있는 데이터 처리 시간의 지연 문제를 해결한다.

MapReduce, the Hadoop's essential core technology, is most commonly used to process big data based on the Hadoop distributed file system. However, the existing MapReduce-based big data processing techniques have a feature of dividing and storing files in blocks predefined in the Hadoop distributed file system, thus wasting huge infrastructure resources. Therefore, in this paper, we propose an efficient MapReduce-based big data processing scheme. The proposed method enhances the storage efficiency of a big data infrastructure environment by converting and compressing the data to be processed into a data format in advance suitable for processing by MapReduce. In addition, the proposed method solves the problem of the data processing time delay arising from when implementing with focus on the storage efficiency.

최근 데이터의 폭발적인 증가로 인해 대규모 데이터의 분석에 대한 요구를 충족할 수 있는 방 법들이 계속 연구되고 있다. 본 논문에서는 맵리듀스를 이용한 분산 병렬 처리를 통해 대규모 데이터 큐브의 효율적인 계산이 가능한 MRIterativeBUC 알고리즘을 제안하였다. MRIterativeBUC 알고 리즘은 기존의 BUC 알고리즘을 맵리듀스의 반복적 단계에 따른 효율적인 동작이 가능하도록 개발되 었고, 기존의 대규모 데이터 큐브 계산에 따른 문제인 데이터 크기와 저장 및 처리 능력의 한계를 해 결하였다. 또한, 분석자의 관심 부분에 대해서만 계산하는 빙산 큐브 개념의 도입과 파티셔닝, 정렬과 같은 큐브 계산을 분산 병렬 처리하는 방법 등의 장점들을 통해 데이터 방출량을 줄여서 네트워크 부 하를 줄이고, 각 노드의 처리량을 줄이며, 궁극적으로 전체 큐브 계산 비용을 줄일 수 있다. 본 연구 결과는 맵리듀스를 이용한 데이터 큐브 계산에 대해서 상향식 처리와 반복적 알고리즘을 통해 다양한 확장이 가능하며, 여러 응용 분야에서 활용이 가능할 것으로 예상된다.

Due to the recent data explosion, methods which can meet the requirement of large data analysis has been studying. This paper proposes MRIterativeBUC algorithm which enables efficient computation of large data cube by distributed parallel processing with MapReduce framework. MRIterativeBUC algorithm is developed for efficient iterative operation of the BUC method with MapReduce, and overcomes the limitations about the storage size and processing ability caused by large data cube computation. It employs the idea from the iceberg cube which computes only the interesting aspect of analysts and the distributed parallel process of cube computation by partitioning and sorting. Thus, it reduces data emission so that it can reduce network overload, processing amount on each node, and eventually the cube computation cost. The bottom-up cube computation and iterative algorithm using MapReduce, proposed in this paper, can be expanded in various way, and will make full use of many applications.

효율적인 빈발 패턴 알고리즘은 연관 규칙 마이닝이나 융복합을 위한 마이닝 과정에서 필수적인 요소이며 많은 활용성을 가지고 있다. 패턴 마이닝을 위한 많은 모델들이 빈발 패턴에 관한 정보를 추출하여 FP-트리를 이용하여 저장하고 있다. 본 논문에서는 항목들의 무게중심을 이용한 새로운 빈발 패턴 알고리즘(CAWFP-Growth)을 제안하여 항목들이 가지는 가중치와 빈도수를 같이 고려하여 항목간의 중심을 계산하여 기존의 FP-Growth 알고리즘의 효율성을 향상시킨다. 제안한 방법은 하향 폐쇄의 성질을 유지하기 위한 기존의 전역적 최대치 가중치 지지도를 필요로 하지 않기 때문에 자연히 빈발 패턴의 탐색시간이 줄어들고 정보의 손실을 줄일 수 있다. 실험결과를 통하여 제안된 알고리즘이 기존의 동적 가중치를 이용하는 다른 방법과 비교해볼 때, 항목들의 무게중심이 빈발패턴의 정확한 정보를 유지하고 FP-트리의 처리 시간을 줄여주기 때문에 제안한 방법의 중요성을 보이고 있다 또한 가상 분산모드에서 맵리듀스 프레임을 기반으로 빅데이터를 모델링하고 향후 완전분산 모드에서 제안한 알고리즘의 모델링이 필요하다.

An efficient frequent pattern algorithm is essential for mining association rules as well as many other mining tasks for convergence with its application spread over a very broad spectrum. Models for mining pattern have been proposed using a FP-tree for storing compressed information about frequent patterns. In this paper, we propose a centroid frequent pattern growth algorithm which we called “CAWFP-Growth” that enhances he FP-Growth algorithm by making the center of weights and frequencies for the itemsets. Because the conventional constraint of maximum weighted support is not necessary to maintain the downward closure property, it is more likely to reduce the search time and the information loss of the frequent patterns. The experimental results show that the proposed algorithm achieves better performance than other algorithms without scarifying the accuracy and increasing the processing time via the centroid of the items. The MapReduce framework model is provided to handle large amounts of data via a pseudo-distributed computing environment. In addition, the modeling of the proposed algorithm is required in the fully distributed mode.

빅데이터는 현재 기업 경쟁력의 주요 자산으로 여겨지고 있고 향후에 그 영향력은 더욱 확대될 것으로 전망된다. 그 중요성을 인식한 기업들은 이미 빅데이터를 제품 개발과 마케팅에 적극적으로 활용하고 있으며 정치, 스포츠 등 사회 전반에 걸쳐 적용분야는 점점 늘어나고 있다. 그러나 시스템 구축에 따른 노하우 부족과 고비용은 빅데이터 시스템 도입에 여전히 큰 장애가 되고 있다. 본 논문에서는 중소규모 오프라인 마켓의 POS 판매 데이터를 빅데이터 시스템 중 오픈소스인 하둡(Hadoop) 및 하이브(Hive)를 기반으로 하는 빅데이터 시스템 구현을 목표로 한다. 이러한 융복합을 통해 단순히 손익분석과 재고관리 등에 집중되었던 기존 판매 시스템을 보완하여 고객의 소비 패턴과 선호도 조사, 수요에 대한 사전 예측이 가능하도록 하는 경영자의 합리적인 의사결정에 기초자료로 활용할 수 있을 것으로 기대된다.

Big Data is now seen as a major asset in the company's competitiveness, its influence in the future is expected to grow. Companies that recognize the importance are already actively engaged with Big Data in product development and marketing, which are increasingly applied across sectors of society, including politics, sports. However, lack of knowledge of the system implementation and high costs are still a big obstacles to the introduction of Big Data and systems. It is an objective in this study to build a Big Data system, which is based on open source Hadoop and Hive among Big Data systems, utilizing POS sales data of small and medium-sized offline markets. This approach of convergence is expected to improve existing sales systems that have been simply focusing on profit and loss analysis. It will also be able to use it as the basis for the decisions of the executive to enable prediction of the consumption patterns of customer preference and demand in advance.

정보화 시대는 다양한 형태로 빠르게 축적되고 있는 빅데이터를 저장, 관리 및 처리하기 위한 새로운 연구 접근법을 요구하고 있다. 본 논문은 시계열 특성을 가지는 디지털운행기록계 빅데이터의 처리 분석을 대한 연구를 진행하고, 하둡분산파일시스템과 맵리듀스를 이용하여 패턴 기반의 분석을 위한 분산 처리의 성능 향상을 이루는 방법론을 제안한다. 전처리 과정, 필터링, 이차정렬을 포함하는 본 논문의 메커니즘을 이용하면, 여러 파일에 분할 저장된 시계열 빅데이터에서 시계열 특성의 패턴 을 이벤트 형태로 분석 및 생성할 수 있다. 본 논문은 빅데이터의 전처리 과정을 통한 성능 향상 효과 와, 제안한 시계열 분석 방법론인 시계열 맵리듀스 메커니즘을 적용한 실험과 분석 결과를 통하여 본 논문이 제안한 방법론의 타당성, 정확성 및 고성능 향상성을 보인다.

The information era requires another new research approach to store, manage and process the big data accumulated rapidly in a variety of forms. This paper pursues the research on handling and analyzing digital tachograph big data, which is recorded in a time series manner. It also proposes the methodology of performance improvement in distributed processing for patternbased analysis over Hadoop Distributed File System and MapReduce. By means of our proposing mechanism that includes preprocessing, filtering, and secondary sorting, it is possible that the time series featured pattern is captured, analyzed and generated in the form of an event on the top of time series big data, which would be scattered over distributed files. This paper also shows the effect of performance progress with big data preprocessing, and verifies properness, correctness, and high-performance improvement via experiments with our proposing time series MapReduce mechanism.

본 논문에서 우리는 비공간 정보와 공간 정보 질의를 처리 방법을 논한 다. 비공간 정보로 범위 질의를 처리하기 위해서, 먼저 기존 검색 알고리즘을 소개한다. 그 후, 데이터 숫자를 줄이기 위해서 Hilbert R-tree 기반인 새로운 검색 알고리즘을 제안한 다. 기존 검색 알고리즘과 본 논문에서 제안한 알고리즘 둘 다 MapReduce를 이용한다. 전형적인 단일 machine 기반의 질의 처리 방식은 데이터 셋의 크기가 급증하게 되면 급격한 성능저하가 발생하기 때문이다. 시뮬레이션을 통해, 기존 검색 알고리즘과 본 논문에서 제안한 알고리즘의 성능을 비교한 다. 그리고 본 논문에서 제안한 알고리즘의 효율성을 증명한다..

본 연구는 전화통화에 의해 생성된 데이터에 대한 빅데이터 분석 접근을 제안한다. 전화통화 데 이터의 분석모형은 자연어의 어휘식별을 위한 PVPF(Parallel Variable-length Phrase Finding) 알 고리즘과 키워드의 사용빈도 측정을 위한 워드 카운트 알고리즘으로 구성된다. 제안한 분석모형에서 는 먼저 PVPF 알고리즘에 의해 연계 단어 추출을 통해 어휘를 식별하며, MapReduce의 워드 카운 트 알고리즘을 사용하여 식별된 어휘 및 단어의 사용빈도를 측정한다. 그 결과는 다양한 관점에서 해 석될 수 있다. 제안 분석모형의 효과성을 보이기 위해 HDFS(Hadoop Distributed File System)를 기반으로 분석모형을 설계 구현하였으며, 전화통화 데이터를 실험 적용한다. 실험결과, 키워드 상관관 계 분석 및 사용빈도 변화 분석을 통해 유의미한 결과를 도출한다.

This paper proposes an approach to big data analytics for phon call data. The analytical models for phon call data is composed of the PVPF (Parallel Variable-length Phrase Finding) algorithm for identifying verbal phrases of natural language and the word count algorithm for measuring the usage frequency of keywords. In the proposed model, we identify words using the PVPF algorithm, and measure the usage frequency of the identified words using word count algorithm in MapReduce. The results can be interpreted from various viewpoints. We design and implement the model based HDFS (Hadoop Distributed File System), verify the proposed approach through a case study of phon call data. So we extract useful results through analysis of keyword correlation and usage frequency.

Within last 10 years, internet has become a daily activity, and humankind had to face the Data Deluge, a dramatic increase of digital data (Economist 2012). Due to exponential increase in amount of digital data, large scale data has become a big issue and hence the term ‘big data’ appeared. There is no official agreement in quantitative and detailed definition of the ‘big data’, but the meaning is expanding to its value and efficacy. Big data not only has the standardized personal information (internal) like customer information, but also has complex data of external, atypical, social, and real time data. Big data’s technology has the concept that covers wide range technology, including ‘data achievement, save/manage, analysis, and application’. To define the connected technology of ‘big data’, there are Big Table, Cassandra, Hadoop, MapReduce, Hbase, and NoSQL, and for the sub-techniques, Text Mining, Opinion Mining, Social Network Analysis, Cluster Analysis are gaining attention. The three features that ‘bid data’ needs to have is about creating large amounts of individual elements (high-resolution) to variety of high-frequency data. Big data has three defining features of volume, variety, and velocity, which is called the ‘3V’. There is increase in complexity as the 4th feature, and as all 4features are satisfied, it becomes more suitable to a ‘big data’. In this study, we have looked at various reasons why companies need to impose ‘big data’, ways of application, and advanced cases of domestic and foreign applications. To correspond effectively to ‘big data’ revolution, paradigm shift in areas of data production, distribution, and consumption is needed, and insight of unfolding and preparing future business by considering the unpredictable market of technology, industry environment, and flow of social demand is desperately needed.

MapReduce is an effective programming model for large-scale data-intensive computing applications. Hadoop, an open-source implementation of MapReduce, has been widely used. The communication overhead from the big data sets’ transmission affects the performance of Hadoop greatly. In consideration of data locality, Hadoop schedules tasks to the nodes near the data locations preferentially to decrease data transmission overhead, which works well in homogeneous and dedicated MapReduce environments. However, due to practical considerations about cost and resource utilization, it is common to maintain heterogeneous clusters or share resources by multiple users. Unfortunately, it’s difficult to take advantage of data locality in these heterogeneous or shared environments. To improve the performance of MapReduce in heterogeneous or shared environments, a data prefetching mechanism is proposed in this paper, which can fetch the data to corresponding compute nodes in advance. It is proved that the proposal of this paper reduces data transmission overhead effectively with theoretical analysis. The mechanism is implemented and evaluated on Hadoop-1.0.4. Experiment results on real applications show that the data prefetching mechanism can reduce data transmission time by up to 94%.

As a widely used programming model for the purposes of processing large data sets, MapReduce (MR) becomes inevitable in data clusters or grids, e.g. a Hadoop environment. Load balancing as a key factor affecting the performance of map resource distribution, has recently gained high concerns to optimize. Current MR processes in the realization of distributed tasks to clusters use hashing with random modulo operations, which can lead to uneven data distribution and inclined loads, thereby obstruct the performance of the entire distribution system. In this paper, a virtual partition consistent hashing (VPCH) algorithm is proposed for the reduce stage of MR processes, in order to achieve such a trade-off on job allocation. Besides, experienced programmers are needed to decide the number of reducers used during the reduce phase of the MR, which makes the quality of MR scripts differ. So, an extreme learning method is employed to recommend potential number of reducer a mapped task needs. Execution time is also predicted for user to better arrange their tasks. According to the results, VPCH can lead to load balancing and our prediction model can provide fast prediction than SVM with similar accuracy maintained.

Evolution of IT and computer has made e-books popular day by day. In this paper, we are interested in searching a word in e-books. However, it is impossible to search a word in digitized e-books if they consist of image files such as JPG and PDF. Our solution to this problem is to transform the image file based e-books into text files based e-books to enable searching a word in e-books. We use EPUB, a XML-based text file, which is defined by IDPF(International Digital Publishing Forum). That is, we convert the image file based e-books into EPUB format e-books, so that searching a word in e-books can be done without any problem. The converting job should deal with very big data usually and require a lot of computing power. If we do the conversion in an usual personal computer, it would take a lot of processing time or it might be impossible for us to complete it. We used MapReduce model with a cluster system which enables us to perform the conversion successfully and reduce the processing time. This paper presents our Hadoop-based e-book Conversion System which is a distributed computing framework to transform the image based e-books into EPUB format e-books. Our experimental system consists of up to 15 cluster nodes. This paper evaluates the performance of the experimental system which processes the conversion of up to 2TB(Terra Byte) image files into EPUB files with a 15 nodes cluster system. We analyzed the processing time when the number of nodes in the cluster system was varied. We also analyzed the improvement effect when the dpi of the image file was varied. The performance evaluation confirmed us that the Hadoop-based e-book Conversion System successfully processed the big data for e-book.

Though MapReduce programming model simplifies the development of parallel program, ordinary users have difficulties in setting up the development environment for MapReduce. The online integrated development environment for MapReduce programming can solve this problem, thus users need not build the environment themselves, only need to focus on the logical design of the parallel program. During the software construction, the problem of independent space setting and naming conflict of the file in the multi-user environment, and the problem of online compiling, execution and instant feedback message to client are solved. The software has been deployed and tested in Hadoop cluster, and can meet users’ basic requirements for the development of MapReduce.

MapReduce is a popular framework for processing large datasets in parallel over a cluster. It has gained wide attention for its high scalability, reliability and low cost. However, its performance may be degraded by excessive network traffic when processing jobs, for such two problems as data locality in reduce task scheduling and partitioning skew. We propose a Minimum Transmission Cost Reduce task Scheduler (MTCRS) based on sampling evaluation to solve the two problems. The MTCRS takes the waiting time of each reduce task and the transmission cost set as indicators to decide appropriate launching locations for Reduce tasks. The transmission cost set is computed by a mathematical model, in which the parameters are the sizes and the locations of intermediate data partitions generated by Average Reservoir Sampling (ARS) algorithm. The experiments show that the MTCRS reduces network traffic by 8.4% compared with Fair scheduler.

Data analyzing and processing are important tasks in cloud computing. In this field, the MapReduce framework has become a more and more popular tool to analyze large-scale data over large clusters. Compared with the parallel relational database, it has the advantages of excellent scalability and good fault tolerance. However, the performance of join operation using MapReduce is not as good as that of parallel relational database. Thus, how to optimize theta-join operations using MapReduce is an attractive point to which researchers have been paying attention. In this paper, a randomized algorithm named Strict-Even-Join(SEJ) is designed to solve the multi-way theta-joins in a single MapReduce job. Moreover, a dynamic programming algorithm is elaborated to optimize the multi-way theta-joins by calling the SEJ algorithm. The results of experiments show that our approach is feasible and effective.

With manufacturing technology developing persistently, hardware manufacturing cost becomes lower and lower. More and more computers equipped with multiple CPUs and enormous data disk emerge. Existing programming modes make people unable to make effective use of growing computational resources. Hence cloud computing appears. With the utilization of Map Reduce parallelized model, existing computing and storage capabilities are effectively integrated and powerful distributed computing ability is provided. Firstly, transform Apriori algorithm to Map Reduce model; realize Apriori parallel transformation; then use the way of compressing original transaction sets to improve the performance of Apriori algorithm in Hadoop framework; lastly, Map Reduce-Apriori algorithm is realized which is highly scalable for running in cloud computing environment.