Earticle

아파치 스파크(Apache Spark)는 오픈 소스, 분산, 인메모리 컴퓨팅 프레임워크 및 아키텍처이다. 아파치 스파크를 통해 데이터 병렬 및 내결함성을 갖춘 분산 시스템 클러스터에서 실행되기 때문에 농업, 정보통신 산업 등 다양한 분야에 적용 및 활용할 수 있다. 한편, 빅데이터 시대를 맞아 많은 시공간 데이터가 발생하고 있다. 그러나, 아파치 스파크를 통한 분산 컴퓨팅 환경에서 많은 연산이 필요한 조인과 같은 연산을 제공하고 있지 않기 때문에 효율적으로 처리하지 못한다. 따라서, 본 논문에서는 대용량 시공간 데이터를 이용하여 그리드 분할 기법에 근거한 withindistance, contain 조인 질의처리 알고리즘을 제안한다. 성능평가 결과, 제안한 알고리즘이 기존 알고리즘보다 약 20%의 우수한 성능을 보인다.

Apache Spark is an open source, distributed, in-memory computing framework and architecture. Because it runs on a distributed system cluster with data parallelism and fault tolerance through Apache Spark, it can be applied and utilized in various fields such as agriculture, information and communication industries. Meanwhile, in the era of big data, large amount of spatio-temporal data is being generated. However, Apache Spark cannot efficiently process join operation because it does not support join operation that requires many computations in a distributed computing environment. Therefore, in this paper, we proposed an join query processing algorithm, i.e., withindistance and contain join, based on grid partitioning technique using large-scale spatio-temporal data. As a result of performance evaluation, our algorithm shows 20% better performance than the existing algorithm in terms of query processing time.

대용량 데이터를 분석하기 위한 맵리듀스 기반 k-NN 조인 질의처리 알고리즘은 최근 데이터 마이닝 및 분석을 기반으로 하는 응용 분야에서 매우 중요하게 활용되고 있다. 그러나, 대표적인 연구인 보로노이 기반 k-NN 조인 질의처리 알고리즘은 보로노이 인덱스 구축 비용이 매우 크기 때문에 대용량 데이터에 적합하지 못하다. 아울러 보로노이 셀 정보를 저장하기 위해 사용하는 R-트리는 맵리듀스 환경의 분산 병렬 처리에 적합하지 않다. 따라서 본 논문에서는 새로운 그리드 인덱스 기반의 k-NN 조인 질의 처리 알고리즘을 제안한다. 첫째, 높은 인덱스 구축 비용 문제를 해결하기 위해, 데이터 분포를 고려한 동적 그리드 인덱스 생성 기법을 제안한다. 둘째, 맵리듀스 환경에서 효율적으로 k-NN 조인 질의를 수행하기 위해, 인접셀 정보를 시그니처로 활용하는 후보영역 탐색 및 필터링 알고리즘을 제안한다. 마지막으로 성능 평가를 통해 제안하는 기법이 질의 처리 시간 측면에서 기존 기법에 비해 최대 3배 높은 질의 처리 성능을 나타냄을 보인다.

최근 대용량 데이터에 대한 효율적인 데이터 분석 기법이 활발히 연구되고 있다. 대표적인 기법으로는 맵리듀스 환경에서 보로노이 다이어그램을 이용한 k 최근접점 조인(VkNN-join) 알고리즘이 존재한다. VkNN-join 알고리즘은 부분집합 Ri에 연관된 부분집합 Sj만을 후보탐색 영역으로 선정하여 질의를 처리하기 때문에 질의처리 시간을 감소시킨다. 그러나 VkNN-join은 색인 구축 비용이 높으며, kNN 연산 오버헤드가 큰 문제점이 존재한다. 이를 해결하기 위해, 본 논문에서는 대용량 데이터 분석을 위한 맵리듀스 기반 kNN join 질의처리 알고리즘을 제안한다. 제안하는 알고리즘은 시드 기반의 동적 분할을 통해 색인구조 구축비용을 감소시킨다. 또한 시드 간 평균 거리를 기반으로 후보 영역을 선정함으로써, 연산 오버헤드를 감소시킨다. 아울러, 성능 평가를 통해 제안하는 기법이 질의처리 시간 측면에서 기존 기법에 비해 우수함을 나타낸다.

하둡 맵리듀스와 같은 분산 컴퓨팅 플랫폼이 개발됨에 따라, 기존 단일 컴퓨터 상에서 수행되는 질의 처리 기법을 분산 컴퓨팅 환경에서 효율적으로 수행하는 것이 필요하다. 특히, 주어진 두 데이터 집합에서 유사도가 높은 모든 데이터 쌍을 탐색하는 유사 조인 질의를 분산 컴퓨팅 환경에서 수행하려는 연구가 있어 왔다. 그러나 분산 병렬 환경에서의 기존 유사 조인 질의처리 기법은 데이터 전송 비용만을 고려하기 때문에 클러스터 간에 비균등 연산 부하 분산의 문제점이 존재한다. 본 논문에서는 분산 컴퓨팅 환경에서 효율적인 유사 조인 처리를 위한 행렬 기반 부하 분산 알고리즘을 제안한다. 제안하는 알고리즘은 클러스터의 균등 부하 분산을 위해 행렬을 이용하여 예상되는 연산 부하를 측정하고 이에 따라 파티션을 생성한다. 아울러, 클러스터에서 질의 처리에 사용되지 않는 데이터를 필터링함으로서 연산 부하를 감소시킨다. 마지막으로 성능 평가를 통해 제안하는 알고리즘이 기존 기법에 비해 질의 처리 성능 측면에서 우수함을 보인다.

As distributed computing platforms like Hadoop MapReduce have been developed, it is necessary to perform the conventional query processing techniques, which have been executed in a single computing machine, in distributed computing environments efficiently. Especially, studies on similarity join query processing in distributed computing environments have been done where similarity join means retrieving all data pairs with high similarity between given two data sets. But the existing similarity join query processing schemes for distributed computing environments have a problem of skewed computing load balance between clusters because they consider only the data transmission cost. In this paper, we propose Matrix-based Load-balancing Algorithm for efficient similarity join query processing in distributed computing environment. In order to uniform load balancing of clusters, the proposed algorithm estimates expected computing cost by using matrix and generates partitions based on the estimated cost. In addition, it can reduce computing loads by filtering out data which are not used in query processing in clusters. Finally, it is shown from our performance evaluation that the proposed algorithm is better on query processing performance than the existing one.