가상 윈도우 기반 인스턴스 레벨 서브시퀀스 매칭 방안
Instance-Level Subsequence Matching Method based on a Virtual Window
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
시계열 데이터는 시간에 따라 변화되는 실수 값을 저장한 것이다. 시계열 데이터에서 사용자 질의 시퀀스가 주어졌을 때, 유사한 서브시퀀스를 가지는 데이터 시퀀스를 검색하는 서브시퀀스 매칭은 매우 중요한 문제이다. 본 논문에서는 인스턴스 레벨의 새로운 서브시퀀스 매칭 방법인 I-Match (Instance-Match)를 제안한다. I-Match는 인스턴스 레벨에서 가상 윈도우를 생성하여 질의 시퀀스와 데이터 시퀀스를 비교하여 착오 해답을 줄이는 방법으로 기존 방법인 Dual Match에 비해 후보의 개수를 줄임으로써 성능을 향상시켰다. 실험을 통해 I-Match의 질의 처리 시간이 Dual Match와 비교하여 최대 2.95배 빠르며, 후보의 개수를 줄임을 보인다.
Abstract
A time-series data is the collection of real numbers over the time intervals. One of the main tasks in time-series data is efficiently to find subsequences similar to a given query sequence. In this paper, we propose an efficient subsequence matching method, which is called Instance-Match (I-Match). I-Match constructs a virtual window in order to reduce false alarms. Through the experiment with real data set and query sets, we show that I-Match improves query processing time by up to 2.95 times and significantly reduces the number of candidates comparing to Dual Match.
참고문헌 (8)
- C. Faloutsos, "Fast Subsequence Matching in Time-Series Databases", Proceeding of International Conference on Management of Data (ACM SIGMOD), pp.419~429 (1994)
- S. H. Lim, "Using Multiple Indexes for Efficient Subsequence Matching in Time-Series Databases", Proceedings of the Database Systems for Advanced Applications (DASFAA), pp.65~79 (2006)
- H. Wu, "Structured Time Series Stream Data", pp.2005
- Y. S. Moon, "Duality-based subsequence matching in time-series databases", Proceedings of the 17th International Conference on Data Engineering (ICDE), pp.263~272 (2001)
- Mohammad. H. Pandi, "A Novel Similarity Measure for Sequence Data", JIPS(Journal of Information Processing Systems), 7(3), pp.413~424 (2011), 한국정보처리학회
- S. H. Lim, "Using multiple indexes for efficient subsequence matching in time-series databases", Journal of Information Science, 170(24), pp.5691~5706 (2007)
- Y. S. Moon, "General Match:A Subsequence Matching Method in Time-Series Database Based on Generalized Windows", Proceedings of International Conference on Management of Data (ACM SIGMOD), pp.382~393 (2002)
- S. Y. Ihm, "Efficient duality-based subsequent matching on time-series data in gree computing", Journal of Supercomputing (2013)[DOI]