집합 기반 유사 시퀀스 매칭의 성능 향상을 위한 최적화 방법

임효상, 이주원

http://doi.org/10.5626/JOK.2018.45.4.403

집합 유사 시퀀스 매칭 방법은 교집합 기반의 유사도를 이용하여 질의 집합 시퀀스와 유사한 데이터 집합 시퀀스를 찾는다. 그러나 수많은 집합 간의 교집합 크기를 계산하는데 수행 시간이 오래 걸리는 성능상의 문제가 있다. 본 논문의 저자들은 간단한 집합 인덱스 구조를 사용한 성능 향상 방법을 제시한 바 있다. 본 논문은 불필요한 연산을 제외하는 프루닝(pruning) 기반 최적화 방법을 제시함으로써, 기존 방법보다 효율적으로 집합 기반 유사 시퀀스 매칭을 수행할 수 있는 방법에 대해 제안한다. 성능 평가 결과, 제안하는 방법이 기존 방법에 비해 약 20% 정도의 수행 시간 감소가 있음을 보인다.