분산 메인 메모리 컬럼 데이터베이스에서의 K-means 알고리즘 구현

Abstract

여러 분야에서 다루는 데이터의 크기는 지속적으로 증가하는 추세이며 이런 대용량 데이터에 대해 효율적으로 데이터마이닝 기법을 적용하고자 하는 요구가 증가하고 있다. Hadoop과 같은 분산프레임웍을 이용하면 대용량 데이터를 다룰 수 있지만 인터페이스의 한계 등으로 최적의 성능을 얻기는 어렵다. 분산 메인 메모리 컬럼 데이터베이스를 이용할 경우 분산환경에서 대용량 데이터를 관리하기에 용이하고 메인 메모리 환경에서 빠른 연산이 가능하지만 분산 및 메인 메모리 환경을 제대로 활용한 데이터마이닝 구현은 제대로 제공하지 못하고 있다. 본 논문에서는 분산 메인 메모리 컬럼 데이터베이스 환경에서 대용량 데이터에 대해 효율적으로 K-means 알고리즘을 적용하는 방안을 모색하였다. 컬럼 테이블에 저장된 데이터를 효율적으로 이용하기 위해 컬럼 테이블에 적합한 K-means 알고리즘을 제안하였으며 stored procedure 및 내부 API를 이용하여 데이터 접근 및 분산환경에서의 데이터 동기화 과정을 빠르게 처리할 수 있게 구현하였다. 데이터는 partitioned 컬럼 테이블을 이용해 각 노드에 분산저장하며 내부 API를 통해 각 노드 간 데이터 동기화 과정을 효율적으로 처리하였다. 각 노드에서는 내부 API를 통해 할당된 partition에만 빠르게 접근하여 locality 정보를 살려 데이터 intensive한 계산과정을 수행하도록 하였다. 컬럼 테이블에 저장된 데이터에 대해 효율적으로 K-means를 적용하기 위해 dictionary encoding 및 inverted index를 이용해 컬럼 단위로 계산을 수행하는 알고리즘을 제안하였다. 위에서 언급한 내용을 바탕으로 데이터마이닝 알고리즘 중 잘 알려진 K-means 알고리즘(KM)과 triangle inequality를 이용한 optimized version의 K-means 알고리즘(EKM)을 분산 메인 메모리 컬럼 데이터베이스 상에서 구현하였다. 구현한 알고리즘의 scalability를 확인한 결과 데이터, 클러스터, 노드 등의 개수에 대해 linear scalability를 보였다. 분산환경에서 Hadoop과 성능을 비교한 결과 8배 정도의 성능 향상을 보였다. 또한 컬럼 테이블에 저장된 데이터를 더 효율적으로 처리할 수 있는 K-means 알고리즘(CEKM)을 구현하여 컬럼 테이블에서 효율적인 K-means 알고리즘의 적용이 가능함을 확인하였다.