집합 기반 유사 시퀀스 매칭의 성능 향상을 위한 최적화 방법 = An Optimization Method for Performance Improvement of Set-based Similar Sequence Matching

다국어 초록 (Multilingual Abstract)

The set-based similar sequence matching method involves searching for data set sequences that are similar to a query set sequence. In the method, the similarity between two sets is represented as the size of intersection between them. However, there is a critical performances issue for calculating intersection size if the number of sets is large. In the past, authors of the present work proposed a method to improve the performance of set-based similar sequence matching using simple index structure. In this paper, we propose an optimization method for more efficient running of set-based similar sequence matching. Our method is based on pruning that excludes unnecessary calculation. Through experiments, we show that the proposed method reduces the execution time by about 20% compared to the existing methods.

국문 초록 (Abstract)

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

참고문헌 (Reference)

1 이주원, "집합 유사 시퀀스 매칭의 성능 향상을 위한 인덱스 기반 검색 방법" 한국정보처리학회 6 (6): 507-520, 2017

2 이재원, "집합 기반 검색 및 연속 일치도에 기반한 자동 교정 POI 검색 기법" 한국정보과학회 19 (19): 462-468, 2013

3 Eunji, Yeo, "Setbased Subsequence Matching" 32 (32): 152-169, 2016

4 Faloutsos, Christos, "Fast subsequence matching in time-series database" 23 (23): 1994

5 Yang-Sae, Moon, "Efficient time-series subsequence matching using duality in constructing windows" 26 (26): 279-293, 2001

6 Eunji, Yeo, "A Similar Data Stream Matching Method by Using the Concept of Item-Set Time Series" 237-239, 2016

7 Eunji, Yeo, "A Data Stream Similar Sequence Matching technique Using the Concept of Item Set and Hierarchy" Yonsei University 2016