특집 02 : 빅데이터 응용 ; 전력 사업의 빅데이터 활용 사례 연구 및 최신 경향 분석

길명선,김광호,문양세,원희선 한국정보처리학회 2015 정보처리학회지 Vol.22 No.4

데이터 스트림의 샘플링 및 필터링을 위한 고속 분산 처리 플랫폼

길명선,문양세,최형진 한국정보과학회 2021 데이타베이스 연구 Vol.37 No.3

In this paper, we propose a novel intelligent platform that applies data purification, a representative technology of data quality management, to the data stream environment. First, we analyze three problems of the existing purification technology: Unsuitability on high-speed stream environment, Lack of stream-based purification methods, and High-difficulty in utilizing purification technologies. Next, to solve those problems, we derive a new high-speed stream processing platform based on open-source projects. The proposed platform consists of Data Stream Processing Engine, Purification Library, Plan Manager, and Shared Storage, and we implement our platform based on Apache Storm and Apache Kafka. Stream processing speed and throughput of these elements are very important performance measures. Thus, we address a performance improvement method using RDMA-Storm (Remote Direct Memory Access based Storm) to increase these performance measures. Through extensive experiments, we showed that the throughput of the proposed platform improved by over 28 times and 2,473 times of processing time compared to the existing Ethernet environment. To our best knowledge, the proposed stream purification platform is the first integrated platform that supports stable purification on an ultra-high speed and big data stream environment. 본 논문에서는 데이터 품질 관리의 대표 기술인 데이터 정제(purification)를 스트림 환경에 적용할 수 있는새로운 분산 처리 플랫폼을 제안한다. 이를 위해, 먼저 기존 정제 기술의 세 가지 문제점을 분석한다. 그리고, 각문제점의 해결 방안으로 오픈소스 프로젝트 기반의 새로운 고속 스트림 처리 플랫폼을 제시한다. 제안 플랫폼은데이터 스트림 처리 엔진, 정제 라이브러리, 플랜 매니저, 공유 스토리지로 구성되며, Apache Storm 및 Apache Kafka를 기반으로 설계한다. 해당 요소들은 스트림 처리 속도 및 처리량이 매우 중요한 성능 지표로, 본 논문에서는 RDMA(Remote Direct Memory Access)를 활용하여 성능을 향상시킨다. 제안 플랫폼의 성능 평가에는 총아홉 대 노드로 구성된 분산 클러스터 환경을 사용하며, 이를 기반으로 각 컴포넌트를 구현 및 평가하였다. 실험을통해 제안 플랫폼의 스트림 처리량이 기존 이더넷 환경 대비 평균 28배 이상, 처리시간은 평균 2,473배 이상 향상되었음을 확인하였다. 결과적으로, 본 논문에서 제안한 스트림 정제 플랫폼은 초고속, 대용량으로 발생하는 스트림의 효율적인 정제를 지원하는 최초의 통합 플랫폼이라 할 수 있다.

왜곡 제거 시계열 서브시퀀스 매칭에서 빠른 인덱스 구성법

길명선(Myeong-Seon Gil),김범수(Bum-Soo Kim),문양세(Yang-Sae Moon),김진호(Jinho Kim) 한국정보과학회 2011 정보과학회논문지 : 데이타베이스 Vol.38 No.6

본 논문에서는 왜곡 제거 시계열 서브시퀀스 매칭에서 인덱스를 효율적으로 구성하는 방법을 다룬다. 기존의 왜곡 제거 시계열 서브시퀀스 매칭에서는 인덱스 구축에 매우 많은 시간이 걸리는데, 이는 왜곡 제거의 모든 가능한 경우를 고려하기 위해 너무 많은 윈도우가 생성되기 때문이다. 실제로 길이 30 만의 시계열인 경우에도 인덱스 구축을 위해 약 100분의 많은 시간이 걸려, 대용량 시계열 데이터에 대해서는 인덱스 구축이 매우 어려운 단점이 있다. 본 논문에서는 기존 인덱스 구축 과정을 단계별로 정형적으로 분석한 후, 각 단계별 성능 극대화 방법을 제안한다. 특히, 동적 프로그래밍 기법을 이용하여 PAA- 버킷 및 DF-버킷(distortion-free bucket)의 개념을 제안하는데, 이는 반복되는 계산 결과를 저장-후-재 사용(store-and-reuse)하는 기법으로, 이를 사용하여 기존 방법에 비해 효율적인 인덱스 구축이 가능하다. 본 논문에서는 복잡도 분석 및 실험 평가를 통해 제안한 방법의 우수성을 입증한다. In this paper we present an efficient approach of constructing a multidimensional index in distortion-free time-series subsequence matching. Index construction of previous distortion-free subsequence matching algorithms is a very time-consuming process since it generates a huge number of windows to consider all possible positions and all possible query lengths. According to the real experiment, the index construction time reaches approximately 100 minutes for a time-series of length 300K, and this means that the index construction itself is very difficult for very large time-series databases. To solve this problem, in this paper we first thoroughly analyze the index construction steps, then discuss how to improve the performance of each step, and finally propose two advanced algorithms of efficiently constructing an index. In particular, by exploiting dynamic programming techniques, we present the concepts of PAA-bucket and DF(distortion-free)-bucket, which store-and-reuse the intermediate results repeatedly computed. Through the store-and-reuse technique, the proposed algorithms construct a multidimensional index very faster than the previous algorithm. Through analytical and empirical evaluations, we showcased the superiority of the proposed algorithms.

왜곡 제거 시계열 서브시퀀스 매칭에서 빠른 인덱스 구성법

길명선(Myeong-Seon Gil),김범수(Bum-Soo Kim),문양세(Yang-Sae Moon),김진호(Jinho Kim) 한국정보과학회 2011 한국정보과학회 학술발표논문집 Vol.38 No.1A

본 논문에서는 기존 단일 인덱스 기반의 왜곡 제거 시계열 서브시퀀스 매칭의 인덱스 구성 알고리즘을 분석하여 보다 효율적인 인덱스 구성 알고리즘을 제안하였다. 기존 왜곡 제거 시계열 서브시퀀스 매칭의 단일 인덱스 구성 알고리즘은 대용량 시계열 데이터인 경우 왜곡 제거를 고려해야 되는 많은 윈도우로 인해 실제 인덱스 생성에 매우 많은 시간이 걸린다. 본 논문에서는 기존 선형 제거 서브시퀀스 매칭의 인덱스 구성 알고리즘을 예로서 인덱스를 구성하는 각 과정을 체계적으로 분석하여, 각 과정에서 필요한 연산 횟수를 줄이는 방법을 제안한다. 이를 위해, 저차원 변환하는 과정에서 발생하는 중복되는 연산들을 한 번씩 미리 수행하여 배열에 저장한 후 재사용하는 DF-버킷(DF-bucket)의 개념을 제시한다. 실험 결과, 저장 후 재사용 원칙에 따라 인덱스 구성의 효율성을 증대시킨 접근법이 그렇지 않은 접근법에 비해서 인덱스 구성 시간을 평균 32%에서 55%까지 줄인 것으로 나타났다.

시계열 데이터베이스에서 선형 추세 제거 서브시퀀스 매칭

길명선(Myeong?Seon Gil),김범수(Bum?Soo Kim),문양세(Yang?Sae Moon),김진호(Jinho Kim) 한국정보과학회 2009 한국정보과학회 학술발표논문집 Vol.36 No.2A

시계열 데이터베이스에서 선형 추세 제거 서브시퀀스 매칭

길명선(Myeong-Seon Gil),김범수(Bum-Soo Kim),문양세(Yang-Sae Moon),김진호(Jinho Kim) 한국정보과학회 2010 정보과학회 컴퓨팅의 실제 논문지 Vol.16 No.5

본 논문에서는 선형 추세 제거 서브시퀀스 매칭을 정의하고, 이를 효율적으로 수행하기 위한 인덱스 기반 해결책을 제안한다. 이를 위해, 먼저 윈도우 자체의 선형 추세가 아닌 해당 윈도우를 포함하는 서브시퀀스의 선형 추세를 제거하여 얻은 새로운 윈도우인 LD-윈도우 개념을 제시한다. 다음으로, LD-윈도우를 이용하여 제안하는 인덱스 기반 해결책의 이론적 근거인 하한 조건을 제시하고, 이를 정형적으로 증명한다. 이러한 하한 조건에 기반하여, 본 논문에서는 또한 인덱스 구성 및 서브시퀀스 매칭 알고리즘을 각각 제안한다. 마지막으로, 실험을 통해 제안하는 인덱스 기반 해결책의 우수성을 입증한다. In this paper we formally define the linear detrending subsequence matching and propose its efficient index-based solution. To this end, we first present the notion of LD-windows. We eliminate the linear trend from a subsequence rather than each window itself and obtain LD-windows by dividing the subsequence into windows. Using the LD-windows we present a lower bounding theorem of the index-based solution and formally prove its correctness. Based on this lower bounding theorem, we then propose the index building and subsequence matching algorithms, respectively. Finally, we show the superiority of our indexbased solution through experiments.

효율적인 빅데이터 처리를 위한 고속 분산 클러스터 기반 RDMA 라이브러리

정래원,길명선,문양세,최형진 한국정보과학회 2022 데이타베이스 연구 Vol.38 No.3

본 논문에서는 분산 클러스터에 최적화된 RDMA(Remote Direct Memory Access) 라이브러리를 제안한다. RDMA는 CPU를 거치지 않고 노드 간 메모리에 직접 데이터를 송수신하는 고성능 네트워크 프로토콜이다. 그러나, 기존 RDMA 개발 방식은 복잡도가 매우 높고, 일대일 통신 기반 모델로 인해 다수 노드 환경에 적용이 어려운 문제가 있다. 이를 해결하기 위해, 본 논문에서는 기존 API를 일반화하여 다수 노드에도 쉽게 적용할 수 있는 새로운 RDMA 라이브러리를 설계하고 구현한다. 제안 라이브러리는 1) 변수 설정, 2) 통신 정보 생성, 3) RDMA 수행, 4) RDMA 종료의 네 단계로 통신을 수행한다. 제안한 RDMA 라이브러리를 사용한 통신 모듈 구현 결과, 다수 노드 간의 데이터 송수신이 정상적으로 수행됨을 실제 실험을 통해 확인하였다. 결과적으로, 제안 라이브러리는 진입 장벽이 높았던 RDMA 응용 개발 난이도를 낮추고, 기존 분산 처리 환경에도 쉽게 활용할 수 있는 효율적인 연구 결과라 사료된다.

대규모 계층적 데이터의 중첩 정규화 및 테이블 마이그레이션 자동화 프레임워크

김다솔,길명선,원희선,문양세 한국정보과학회 2023 정보과학회논문지 Vol.50 No.6

오픈 데이터 포털에서는 많은 데이터가 계층 구조인 XML, JSON 포맷으로 배포되며, 그 규모가 매우 크다. 이러한 계층적 데이터는 구조 특성상 다수의 중첩(nesting)을 포함한다. 이로 인해, 대규모 오픈 데이터 활용에 제약이 되는 중첩 테이블 정규화 문제와 스케일 제한 문제가 발생한다. 본 논문에서는 계층적 파일들의 테이블 마이그레이션을 위해 오픈소스 ELT 플랫폼인 Airbyte를 채택하고, 이를 자동화하는 새로운 프레임워크를 제안한다. 또한, Airbyte의 중첩 JSON 처리 문제를 최초로 보고하여 문제 해결에 기여한다. 실제 미국 데이터 포털을 대상으로 제안 프레임워크를 평가한 결과, 다수의 중첩이 포함된 구조에 대해서도 정상 동작하며, 자동화 처리 로직의 제공으로 1.6K 이상의 대규모 마이그레이션 처리가 가능함을 보인다. 본 논문의 결과는 계층적 데이터의 중첩 정규화를 지원하고 안정적인 대규모 마이그레이션 기능을 제공하는 매우 실용적인 프레임워크라 사료된다.

안전한 문서 검색을 위한 저차원 변환 기반의 2단계 프로토콜

김상필,길명선,최형진,김장환,문양세 한국정보과학회 2016 데이타베이스 연구 Vol.32 No.2

SSDD(secure similar document detection) identifies similar documents of two parties while not disclosing their sensitive documents. In this paper we propose an efficient two-step approach for SSDD by using the lower-dimensional transformation. We first analyze that the existing 1-step protocol causes serious computing and communications overhead. To solve this problem, we next propose a 2-step protocol based on RP(random projection), the simplest lower-dimensional transformation and prove its correctness. We also propose another 2-step protocol by using DF(document frequency) to improve the filtering effect of RP. Finally, we empirically show that the DF-based 2-step protocol significantly outperforms the base protocol by up to 147 times. 안전한 유사 문서 검색(secure similar document detection: SSDD)은 두 파티가 서로의 민감한 문서는 공개하지 않으면서도 유사 문서를 판별하는 기법이다. 본 논문에서는 저차원 변환을 사용하여 SSDD를 효율적으로 수행하는 2-단계 프로토콜을 제시한다. 우선, 기존 1-단계 프로토콜이 고차원 문서 벡터에 대해 심각한컴퓨팅 및 통신 오버헤드를 발생시킴을 분석한다. 다음으로, 가장 간단한 저차원 변환인 RP(random projection)를 사용한 2-단계 프로토콜을 제시하고, 그 정확성을 증명한다. 마지막으로, RP의 낮은 필터링효과를 개선하기 위해 DF(document frequency)를 저차원 변환으로 사용한 2-단계 프로토콜을 제시한다. 실험 결과, 제안한 DF 기반의 2-단계 프로토콜은 기존 1-단계 프로토콜에 비해 성능을 최대 147배까지 향상시킨 것으로 나타났다.

인피니밴드 네트워크에서 분산 병렬 그래프 데이터 처리의 성능 개선

김현종,길명선,문양세 한국정보과학회 2023 정보과학회논문지 Vol.50 No.4

Graph data, which values the relationship of each object, is widely used for new rules or association analysis that cannot be found in relational databases. However, there is a limit to high-speed processing due to its complex structure and massive data size. In this paper, we propose PIGraph (Pregel and InfiniBand-based Graph processing engine) to improve the processing performance of graph data. PIGraph is an advanced graph processing engine based on Pregel, which is a representative graph processing model. PIGraph supports the distributed parallel structure using InfiniBand and RDMA (Remote Direct Memory Access) technology to reduce the management complexity of distributed graph processing. In particular, PIGraph improves the processing performance of graph data by optimizing the RDMA communication with segment-based transmissions. Experimental results show that PIGraph improves the processing time by up to 190% compared to Apache Giraph. 각 객체의 관계를 중시하는 그래프 데이터는 관계형 데이터베이스에서는 찾아낼 수 없는 새로운 규칙이나 연관성 분석에 많이 사용되지만, 복잡한 구조와 방대한 양으로 인해 빠른 처리에는 한계가 있다. 본 논문에서는 이러한 그래프 데이터 처리의 성능 향상을 위해 PIGraph(Pregel and InfiniBand- based Graph processing engine)를 제안한다. PIGraph는 대표적인 그래프 처리 모델인 Pregel 기반 그래프 처리 엔진이다. PIGraph는 분산 그래프 처리의 관리 복잡도 감소를 위해 인피니밴드와 RDMA (Remote Direct Memory Access) 기술을 활용한 분산 병렬 구조를 지원한다. 특히, 세그먼트 단위 전송으로 RDMA 통신을 최적화하여 그래프 데이터의 처리 성능 한계를 개선한다. 성능 평가 결과, PIGraph가 비교 시스템인 Apache Giraph에 비해 최대 190% 이상 빠른 처리 시간을 보임을 확인하였다.