구간 시계열 데이터를 위한 효율적인 유사 검색 방법

Abstract

This dissertation studies an efficient similarity search for time series data represented as interval sequences. This interval sequences consist of ordered sets of intervals instead of a single value as its components and have two different types. The first type is value-based interval sequences where each interval is represented by a range bounded by two end limits at a time point due to uncertainty or aggregation. The second type is time-based interval sequences such as phone call records, which consist of the start and end times of the call records. To support efficient similarity search for such sequences, we address desirable requirements for distance measures for the two types of interval sequences and propose new measures satisfying all the requirements. We then propose efficient indexing techniques for fast retrieval of similar interval sequences from large-scaled databases. More specifically, we propose: (1) to extract feature vectors for each type of interval sequence, and(2) to build the indexes using existing hierarchical index structures suitable for its corresponding feature vectors. Finally, we devise exact and fast approximate search algorithms. We empirically validate the efficiency and effectiveness of our proposed solutions.