■ 스트리밍 환경에서 빠른 삭제 수행 성능을 가진 동적 클러스터링 알고리즘 개발
■ 시시각각 변화하는 클러스터의 탐지가 요구되는 다양한 응용 분야에 적용 가능

클러스터링이란 많은 데이터들 속에서 유사한 데이터들의 그룹을 찾는 분석 방법으로서 방대한 데이터에서 의미 있는 정보를 찾는데 활용된다. <a href='http://dbs.snu.ac.kr/' target='_self'>문봉기교수 연구진</a>은 이번 연구에서 스트리밍 환경에서 삭제 연산을 효율적으로 처리하는 밀도 기반 클러스터링 알고리즘을 개발하였다. 이를 통해 클러스터의 변화를 빠르게 감지할 수 있게 됨으로써 시시각각 변화하는 클러스터의 탐지가 요구되는 다양한 응용 분야에 적용 가능할 것으로 기대한다.

기존의 밀도 기반 클러스터링 알고리즘들은 각각의 클러스터를 논리적 혹은 물리적인 그래프의 형태로 관리하여 비정형의 클러스터 조차도 탐지 및 관리할 수 있는 장점을 갖고 있다. 그러나 데이터 삭제 시에 클러스터를 업데이트 하는데 많은 시간이 소요되는 문제로 인하여 실시간 적용을 불가능하게 한다. <a href='http://dbs.snu.ac.kr/' target='_self'>문봉기교수 연구진</a>은 이 해묵은 난제를 극복하기 위하여 클러스터링 알고리즘 덴포레스트(DenForest) 를 개발하였다. 덴포레스트는 스트리밍 환경에서 밀도 기반의 클러스터를 효율적으로 추적 및 관리하는 알고리즘이다. 기존의 알고리즘들과 달리 덴포레스트는 데이터에 내재된 클러스터를 신장 트리(Spanning Tree) 형태로 관리함을 통하여 삭제 시간을 획기적으로 단축하였으며, 이는 다양한 데이터에서의 실험과 이론적인 증명을 통해 검증되었다. 기존의 알고리즘 대비, 덴포레스트는 150배 가까운 빠른 삭제 성능을 보인다.

<a href='https://icde2021.gr' target='_self'>2021년 ICDE (International Conference on Data Engineering)</a> 학회에 발표된 선행 연구인 디스크 (DISC) 알고리즘과 더불어 본 연구 결과는 실시간 동적 클러스터링 작업의 성능 향상에 큰 기여를 할 것으로 기대된다.

이번 연구 결과는 오는 6월 <a href='https://sigmod.org/' target='_self'>ACM SIGMOD(Special Interest Group on Management of Data)</a>에 게재될 예정이다.

“DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows”, Bogyeong Kim, Kyoseung Koo, Undraa Enkhbat, and Bongki Moon.