반복되는 빈발 부분그래프 마이닝에서의 중복 연산 제거 기법

박기성, 한용구, 이영구 · 한국정보과학회 학술발표논문집 · 2011

빈발 부분그래프는 그래프 분류, 군집화, 인덱싱 등에서 그래프 데이터의 특징을 표현하기 위하여 사용된다. 최근에는 최소 지지도를 다르게 설정하거나 데이터베이스를 분할하며 반복적으로 빈발 부분 그래프 마이닝을 하는 방법이 사용된다. 이러한 경우 동일 그래프에 대한 중복 연산이 발생하여 수행시간이 증가한다. 본 논문에서는 빈발 부분그래프 마이닝 기법 중 가장 널리 사용되고 있는 gSpan의 반복적 실행을 분석하여, 가장 수행시간이 많이 요구되는 연산 중의 하나인 그래프 정규화 연산이 중복적으로 발생함을 논한다. 그리고, 중복되는 빈발 부분그래프 마이닝의 불필요한 정규화 연산을 제거하는 기법을 제안한다. 또한 모델 기반 탐색 트리를 사용하여 제안하는 기법이 기존의 방법보다 더 높은 성능을 보이는 것을 입증한다.

Cited by 0 works.

Authors