Parallel Nested Loop Algorithm for Set Similarity Join Based on CUDA

Abstract

현대 사회에서 사람들이 행하는 행위와 개인의 속성은 다양한 방식으로 여러 기기들을 통하여 데이터로서 기록되어 저장된다. 과거 전기 신호로 구성된 수리적인 수치에 지나지 않았던 데이터는 이제 하나의 인간을 능히 규정할 수 있는 지경에 이르렀다. 충분히 첨단화된 사회는 그 사회 구성원이 하루를 어떻게 보냈는지, 어떠한 이동수단을 사용하였는지, 무엇을 구매하였는지 데이터화하여 기록한다.

오늘날 많은 기업과 기관들은 이러한 데이터로부터 유용한 정보를 이끌어내기 위해 방대한 분량의 데이터를 분석한다. 분석된 데이터는 기업들에게 매력적이고 유효한 상업적 정보를 제공하며, 비영리적인 단체 또한 데이터를 통해 많은 도움을 받을 수 있다. 데이터는 사용자 혹은 기기 간의 기록을 비교하여 특정 객체에게 관심을 끌 수 있는 정보를 제공하기도 하며, 나아가 미래의 행동을 예측하기도 한다. 데이터 분석에서 많이 사용되는 기본적 연산 중 하나는 두 데이터 간의 유사도를 비교하는 연산이다. 하지만 유사도 연산을 진행하는 데에는 기술적 어려움이 존재한다. 평균적으로 유사도 연산에는 n개의 데이터가 주어졌을 때 필요한 연산량이 일반적으로 O(n^2)이라는 점이 그것이다. 때문에 모든 데이터 쌍 간의 유사도를 계산하는 과정에는 효율적인 알고리즘이 요구된다.

본 논문에서는 병렬 컴퓨팅을 이용한 네스티드 루프 기반의 조인 알고리즘을 제안한다. 제안하는 알고리즘은 정렬된 상태에서 더 이상 계산하지 않아도 되는 부분을 파악하고 이 지점에 도달하면 계산을 하지 않는 방법으로 계산량을 줄인다. 이는 임계값을 이용하지 않고 필터링을 진행하기 때문에 임계값에 구애받지 않고 값이 낮든 높든 균질한 효율을 낼 수 있다는 장점이 있다. 또한 NVIDIA에서 개발한 병렬 컴퓨팅 아키텍처인 CUDA의 기술적 특징을 분석하고, 이를 병렬 컴퓨팅 기반의 유사도 조인 알고리즘을 구현하는데 활용한다. 또한 CUDA 스레드의 알고리즘 작동 과정에서의 양태를 분석하고, 이를 효율적으로 활용 가능한 단계 절감 기법도 추가로 제시한다. 최종적으로 실험을 통해 본 논문에서 제안하는 알고리즘이 데이터셋의 양상에 따라 보이는 효율성을 분석하고 기존 연구의 유사도 조인 알고리즘과의 성능을 비교하였다.; In our modern society, people’s behavior and personal attributes are being recorded and stored as data through various methods and devices. This data, which was once merely numerical values composed of electrical signals, is now able to define a human being. A sufficiently advanced society records data on how its members spend their days, what transportation methods they use, and what they purchase.

Today, many companies and institutions analyze enormous quantities of data to extract useful information. This analyzed data provides companies with attractive and useful commercial information and can prove very useful to non-profit organizations as well. Data records between users or devices can be compared to provide information of interest to a particular object and can also be further used to predict future behavior. Among the basic operations often used in data analysis are operations comparing the similarity between two sets of data. However, there is a technological difficulty in performing similarity operations: in similarity operations, on average, given n-size data typically requires the computation of O(n^2). As a result, an efficient algorithm is needed for calculating the similarity between all data pairs.

This paper proposes a parallel join algorithm based on a nested loop using parallel computing. The proposed algorithm reduces computation by identifying the section that no longer needs to be calculated in the sorted state and no longer calculating when this point is reached. As this uses filtering rather than the threshold, it is able to achieve homogeneous efficiency regardless of if the threshold is high or low. In addition, we analyze the technological properties of Compute Unified Device Architecture (CUDA), a parallel computing architecture developed by NVIDIA, and use it to implement the similarity join algorithm based on parallel computing. We also analyzed the aspect of the algorithm operation process of the CUDA thread and proposed an additional step reduction technique that can use this efficiently. Finally, we analyzed the efficiency shown by the algorithm in experiments according to the state of the dataset and compared it with the performance of similarity join algorithms proposed in previous studies.