본 발명은 시계열 데이터베이스에서 서브시퀀스 매칭의 후처리 최적화 방법에 관한 것으로서 보다 상세하게는, 인덱스 검색 결과로 얻어진 후보 서브시퀀스들을 이진 탐색 트리 내에 삽입하여 정렬하고 상기 후보 서브시퀀스들을 포함하는 같은 시퀀스를 한번만 액세스하여 상기 후보 서브시퀀스들을 질의 시퀀스와 비교함으로써 서브시퀀스 매칭을 효과적으로 처리하는 시계열 데이터베이스에서 서브시퀀스 매칭의 후처리 최적화 방법에 관한 것이다.The present invention relates to a post-processing optimization method of subsequence matching in a time-series database. More particularly, the method includes inserting candidate subsequences obtained from an index search result into a binary search tree and sorting the same sequence including the candidate subsequences only once. The present invention relates to a post-processing optimization method of subsequence matching in a time series database that accesses and compares the candidate subsequences with a query sequence to efficiently process subsequence matching.
최근 컴퓨터 기술이 발전함에 따라 시계열 데이터를 활용하고자 하는 연구가 활발하게 진행되고 있으며 또한, 실제로 주식 데이터, 의료 데이터, 환율변동 데이터 등과 같은 다양한 분야에서 많은 양의 시계열 데이터가 이용되고 있다.Recently, with the development of computer technology, researches for utilizing time series data have been actively conducted. In addition, a large amount of time series data is used in various fields such as stock data, medical data, and exchange rate fluctuation data.
일반적으로 시계열 데이터베이스(time-series database)는 시간별로 측정된 개체의 값을 연속적으로 구성한 시계열 데이터를 저장하는 데이터베이스를 의미한다. 이러한 시계열 데이터베이스에 저장된 시계열 데이터를 데이터 시퀀스라 하며 질의 시퀀스는 사용자에 의해 주어지는 검색하고자 하는 패턴의 시퀀스를 의미한다. 상기와 같이 사용자에 의해 질의 시퀀스와 유사한 데이터 시퀀스를 데이터베이스에서 검색하는 것을 유사 시퀀스 매칭이라 한다. 상기 시계열 데이터에 대한 유사 시퀀스 매칭은 시계열 데이터베이스를 기반으로 하는 새로운 응용분야인 데이터 마이닝(data mining) 및 데이터 웨어하우징(data warehousing) 분야에서 중요한 연산으로 사용된다.In general, a time-series database refers to a database that stores time series data that is a series of values of an object measured by time. Time series data stored in such a time series database is called a data sequence, and a query sequence means a sequence of patterns to be searched given by a user. As described above, retrieving a data sequence similar to the query sequence by the user from the database is called similar sequence matching. Similar sequence matching for the time series data is used as an important operation in the fields of data mining and data warehousing, which are new applications based on a time series database.
일반적으로 하나의 시퀀스가 다른 시퀀스의 일부분인 경우 전자는 후자의 서브시퀀스가 된다.In general, if one sequence is part of another sequence, the former becomes the latter subsequence.
유사 시퀀스 매칭은 크게 전체 매칭과 서브시퀀스 매칭으로 분류된다. 상기 전체 매칭은 모든 데이터 시퀀스들과 질의 시퀀스의 길이가 항상 동일하다는 전제하에 상기 질의 시퀀스와 유사한 시퀀스를 데이터베이스로부터 검색하는 것을 말한다. 반면, 상기 서브시퀀스 매칭은 다양한 길이의 데이터 시퀀스들이 존재하는 것을 허용하며 데이터베이스로부터 질의 시퀀스와 유사한 서브시퀀스의 오프셋을 검색한다. 이와 같이 서브시퀀스 매칭은 길이에 대한 제약이 없으므로 다양한 실제 응용 분야에서 널리 사용된다.Similar sequence matching is largely classified into full matching and subsequence matching. The overall matching refers to retrieving a sequence similar to the query sequence from the database provided that the length of all data sequences and the query sequence is always the same. Subsequence matching, on the other hand, allows for data sequences of varying lengths and retrieves offsets of subsequences similar to query sequences from a database. As such, subsequence matching is widely used in various practical applications because there is no length limitation.
서브시퀀스 매칭의 처리과정은 사용자에 의해 주어지는 질의 시퀀스와 유사한 서브시퀀스를 검색하는 인덱스 검색과정과 상기 검색되어 반환된 서브시퀀스에 대한 액세스를 실행하여 상기 검색된 서브시퀀스와 상기 질의 시퀀스의 유사성을 비교하여 최종적인 결과를 다시 사용자에게 되돌려주는 후처리과정으로 나누어 진다. 상기와 같이 임의의 시퀀스와 유사한 서브시퀀스를 검색하는 방법으로는 두 시퀀스간의 거리가 설정된 유사 허용치 이하이면 '유사하다'고 간주한다. 상기 거리 계산방법은 다양하게 적용될 수 있으나 본 발명에서는 특정한 거리 계산방법에 한정되지 않는다. 그러나, 이하에서 본 발명의 이해를 돕기 위해 거리 계산방법의 일실시예를 들어 유사 서브시퀀스 매칭을 설명한다. 예를 들어, 시계열 데이터베이스 D, 길이 n의 질의 시퀀스 Q = (q[0], q[1], ..., q[n-1]), 그리고 유사 허용치 ε이 주어질 때, 서브시퀀스 매칭 문제는 다음과 같이 정의된다.Subsequence matching is performed by performing an index search process for searching a subsequence similar to a query sequence given by a user and accessing the searched and returned subsequences to compare the similarity between the searched subsequence and the query sequence. It is divided into post-processing that returns the final result back to the user. As described above, a method of searching for a subsequence similar to an arbitrary sequence is regarded as 'similar' if the distance between two sequences is less than or equal to a set similarity tolerance. The distance calculation method may be variously applied, but the present invention is not limited to a specific distance calculation method. However, hereinafter, similar subsequence matching will be described as an example of the distance calculation method to help the understanding of the present invention. For example, given a time series database D, a query sequence Q of length n = (q [0], q [1], ..., q [n-1]), and a similar tolerance ε, the subsequence matching problem Is defined as
D에 저장된 길이 N의 임의의 시퀀스 S = (s[0], s[1], ..., s[N-1]) 내에 존재하는 길이 n의 임의의 서브시퀀스 X = (x[0], x[1], ..., x[n-1])가 하기 수식 1의 조건을 만족하면, 상기 서브시퀀스 X와 상기 질의 시퀀스 Q는 '유사하다'고 간주한다.Any subsequence of length n present in any sequence S = (s [0], s [1], ..., s [N-1]) of length N stored in D X = (x [0] , x [1], ..., x [n-1]) satisfy the condition of Equation 1 below, and the subsequence X and the query sequence Q are considered to be similar.
[수식 1][Equation 1]
상기 수식 1에서 d(X,Q)는 유클리드 거리(Euclidean distance)라 하며 상기 유클리드 거리가 주어진 유사 허용치 ε이하인 경우, 상기 서브시퀀스 X와 상기 질의 시퀀스 Q를 유사하다고 간주한다.In Equation 1, d (X, Q) is called an Euclidean distance, and when the Euclidean distance is equal to or less than a given similarity tolerance ε, the subsequence X and the query sequence Q are considered to be similar.
종래의 서브시퀀스 매칭을 위한 해결 방법에서는 미리 고정된 크기 w를 갖는 윈도우(window) 개념을 이용한다. 상기 윈도우(window)는 시퀀스를 분할하는 단위로서, 분할하는 방법에 따라 슬라이딩 윈도우(sliding window)와 디스조인트 윈도우(disjoint window)로 구분한다. 상기 슬라이딩 윈도우는 시퀀스의 가능한 모든 위치를 시작 위치로 하여 구성한 윈도우를 의미하며 상기 디스조인트 윈도우는 윈도의 크기의 배수가 되는 위치를 시작 위치로 하여 구성한 윈도우를 의미한다.The conventional solution for subsequence matching uses the concept of a window having a fixed size w in advance. The window is a unit for dividing a sequence, and is divided into a sliding window and a disjoint window according to the dividing method. The sliding window refers to a window configured with all possible positions of the sequence as a starting position, and the disjoint window refers to a window configured with a starting position that is a multiple of the size of the window.
도 1은 상기한 시퀀스를 윈도우로 분할하는 예시도를 도시한 것이다. 도 1(a)는 시퀀스를 슬라이딩 윈도우로 분할하는 방법에 대한 예시도를 나타낸 것으로서 시퀀스(11)를 크기가 4인 슬라이딩 윈도우(12)들로 나눈 예이다. 도 1(b)는 시퀀스를 디스조인트 윈도우로 분할하는 방법에 대한 예시도를 나타낸 것으로서 시퀀스(13)를 크기가 4인 디스조인트 윈도우(14)들로 나눈 예이다.1 illustrates an example of dividing the above sequence into windows. FIG. 1A illustrates an example of a method of dividing a sequence into sliding windows, which is an example of dividing the sequence 11 into sliding windows 12 having a size of 4. FIG. 1B illustrates an example of a method of dividing a sequence into disjoint windows. The sequence 13 is divided into four disjoint windows 14 of size.
이하, 종래의 시계열 데이터에 대한 유사 서브시퀀스 매칭방법을 간략하게 설명한다. 참고문헌 [Fal94] C. Faloutsos, M, Ranganathan, and Y. Manolopoulos, "Fast Subsequence Matching in Time-series Databases," In Proc. Int'l. Conf. on Management of Data, ACM SIGMOD, pp. 419-429, May 1994. 의 논문에서는 상기한 윈도의 개념을 이용하여 서브시퀀스 매칭방법을 제안하였다.Hereinafter, a conventional subsequence matching method for time series data will be briefly described. References [Fal94] C. Faloutsos, M, Ranganathan, and Y. Manolopoulos, "Fast Subsequence Matching in Time-series Databases," In Proc. Int'l. Conf. on Management of Data, ACM SIGMOD, pp. 419-429, May 1994. In this paper, we propose a subsequence matching method using the concept of window.
상기 논문을 참조하면, 각 시퀀스로부터 모든 가능한 위치에서 시작되는 길이 w의 슬라이딩 윈도우들을 추출하고 각 윈도우를 이산 퓨리에 변환(discrete Fourier transform; DFT)을 이용하여 저차원 공간상의 점으로 변환한다. 상기 논문에서는 이 점을 데이터 윈도우 점(data window point)이라 정의한다. 인덱싱의 대상이 되는 윈도우 점들의 수가 매우 많으므로, FRM에서는 이들을 다수의 점들을 포함하는 최소 포함 사각형(minimum bounding rectangle;MBR)들로 구성한 후, 상기 MBR들을 다차원 인덱스(multidimensional index)의 하나인 R-트리에 저장한다.Referring to the above paper, sliding windows of length w starting at every possible position from each sequence are extracted and each window is transformed into a point in low dimensional space using a discrete Fourier transform (DFT). This paper defines this point as the data window point. Since the number of window points to be indexed is very large, in FRM, they are composed of minimum bounding rectangles (MBRs) that contain a number of points, and then the MBRs are R, one of the multidimensional indexes. Store in tree
서브시퀀스 매칭을 위해서는 질의 시퀀스로부터 크기 w의 디스조인트 윈도우들을 추출하고 윈도우들을 DFT하여 저차원 공간상의 윈도우 점들로 변환한다. 이를 질의 윈도우 점(query window point)이라 한다. 각 윈도우 점에 대하여 ε/ p1/2를 허용치로 갖는 범위 질의를 R-트리 상에서 수행한다. 여기서, 상기 p = (질의 시퀀스 길이 / w) 이다. 이러한 범위 질의의 결과로 얻어진 데이터 윈도우 점들을 조사함으로써 최종 결과에 포함될 가능성이 높은 후보 서브시퀀스(candidate subsequence)들을 파악한다. 이어, 상기 후보 서브시퀀스들을 디스크로부터 액세스하여 질의 시퀀스와의 유클리드 거리를 실제로 계산하여 최종적인 진위를 판단하게 된다.For subsequence matching, disjoint windows of size w are extracted from the query sequence, and the DFTs are transformed into window points in the low dimensional space. This is called a query window point. For each window point, a range query with ε / p1/2 is allowed on the R-tree. Where p = (query sequence length / w). Examining the data window points resulting from this range query identifies candidate subsequences that are likely to be included in the final result. The candidate subsequences are then accessed from the disc to actually calculate the Euclidean distance from the query sequence to determine the final authenticity.
상기와 같은 방법은 인덱싱을 위한 저장 공간의 오버헤드를 줄이기 위하여 개별적 윈도우 점들 대신 다수의 윈도우 점들을 포함하는 MBR들을 R-트리 내에 저장한다. 이러한 MBR 내부에는 죽은 공간(dead space)이 존재하게 되므로 이로 인하여 후보 서브시퀀스의 착오 채택(false alarm)이 발생되며 이것은 곧 처리 성능 저하를 초래하는 문제점이 있었다.Such a method stores MBRs containing multiple window points instead of individual window points in the R-tree to reduce the overhead of storage space for indexing. Since dead space exists inside the MBR, this causes a false alarm of the candidate subsequences, which causes a problem in processing performance.
이러한 문제를 극복하기 위한 한 예로서, 참고문헌 [Moo01] Y. S. Moon, K, Y. Whang, W. K. Loh, "Duality-Based Subsequence Matching in Time-Series Databases," In Proc. IEEE Int'l Conf. on Data Engineering, IEEE ICDE, pp. 263-272, 2001. 의 논문에 이원성 기반 서브시퀀스 매칭(Dual-Match)이 제시되어 있다. 상기 참고문헌에서는 데이터 시퀀스로부터 슬라이딩 윈도우를 추출하고 질의 시퀀스로부터 디스조인트 윈도우를 추출하는 FRM과는 반대로 데이터 시퀀스로부터 디스조인트 윈도우를 추출하고 질의 시퀀스로부터는 슬라이딩 윈도우를 추출하는 방식을 사용한다. 이와 같은 역할 교환을 통해 상기 Dual-Match에서는 R-트리에 저장할 윈도우들의 수를 FRM의 약 1/w로 줄일 수 있다. 이 결과, MBR들을 저장하는 FRM과는 달리 상기 Dual-Match에서는 윈도우 점 자체를 R-트리에 저장하는 것이 가능해 진다. 따라서 MBR 내의 죽은 공간으로 인한 후보 서브시퀀스의 착오 채택이 발생하지 않으므로 처리 성능이 개선된다.As an example to overcome this problem, see, eg, reference [Moo01] Y. S. Moon, K, Y. Whang, W. K. Loh, "Duality-Based Subsequence Matching in Time-Series Databases," In Proc. IEEE Int'l Conf. on Data Engineering, IEEE ICDE, pp. 263-272, 2001. Duality-based subsequence matching (Dual-Match) is presented. In the above reference, a disjoint window is extracted from a data sequence and a sliding window is extracted from a query sequence, as opposed to an FRM which extracts a sliding window from a data sequence and a disjoint window from a query sequence. Through this role exchange, the Dual-Match can reduce the number of windows to be stored in the R-tree to about 1 / w of the FRM. As a result, unlike the FRM which stores the MBRs, it is possible to store the window point itself in the R-tree in the Dual-Match. Thus, error adoption of candidate subsequences due to dead space in the MBR does not occur, thereby improving processing performance.
도 2는 상기한 R-트리를 위한 인덱스 검색과 후처리 과정으로 구성되는 서브시퀀스 매칭의 처리과정을 나타낸 것이다. 상술한 두 참고문헌 [Fal94],[Moo01]의 논문에서는 모두 이러한 공통된 두 과정을 거치게 된다. 도 2에 도시된 바와 같이 큰 이등변 삼각형(21)은 R-트리를 나타내며 하단의 사각형은 각 시퀀스(22)를 나타낸다.2 shows a process of subsequence matching consisting of the index search and post-processing for the R-tree. In the above-mentioned two papers [Fal94] and [Moo01], all of these two processes go through these common processes. As shown in FIG. 2, a large isosceles triangle 21 represents an R-tree and the bottom square represents each sequence 22.
상기 인덱스 검색은 각각의 질의 윈도우 점에 대하여 범위가 ε/ p1/2인 질의를 R-트리에 수행하는 과정이다. 도 2에서 사선으로 채워진 부분의 삼각형(23)은 각 질의 윈도우 점을 이용하여 범위 질의를 처리할 때 R-트리 내에서 액세스되는 부분이다. 각 범위 질의의 결과는 그 범위 질의에서 사용된 질의 윈도우 점과 유클리드 거리가 ε/ p1/2이내인 데이터 윈도우들의 집합이다. 이들을 후보 윈도우(candidate window)라 정의한다. 이러한 처리를 하는 이론적인 배경은 "서로 다른 두 시퀀스의 유클리드 거리가 ε이내이기 위한 필요 조건은 대응되는 윈도우 쌍 중 적어도 하나가 ε/ p1/2 이내여야 한다"는 상기 전자의 논문 [Fal94]의 정리에 근거한다. 이와 같이 인덱스 검색에서는 사용자에 의해 주어지는 질의 윈도우와 유사한 후보 윈도우를 상기 R-트리에서 검색하여 후처리 과정으로 반환한다.The index search is a process of performing a query having a range of ε / p1/2 on the R-tree for each query window point. In Fig. 2, the triangle 23 in the diagonally filled portion is a portion accessed in the R-tree when processing the range query using each query window point. The result of each range query is a set of data windows whose Euclidean distance and query window points used in the range query are within ε / p1/2 . These are defined as candidate windows. The theoretical background of this process is that the requirement for the Euclidean distance of two different sequences to be within ε is that at least one of the corresponding window pairs must be within ε / p1/2. Based on the theorem. As such, the index search searches for the candidate window similar to the query window given by the user in the R-tree and returns to the post-processing process.
한편, 후처리 과정에서는 상기와 같이 인덱스 검색에서 반환되는 각 후보 윈도우에 대하여 그 후보 윈도우가 속하는 서브시퀀스를 파악한다. 이를 후보 서브시퀀스(candidate subsequence)라 정의한다. 이후, 상기 후보 서브시퀀스가 포함되는 데이터 시퀀스를 디스크로부터 액세스하고 상기 후보 서브시퀀스와 질의 시퀀스와의 유클리드 거리를 실제로 계산함으로써 착오 채택의 여부를 확인한다.Meanwhile, in the post-processing process, the subsequence to which the candidate window belongs is identified for each candidate window returned by the index search as described above. This is defined as a candidate subsequence. Then, the data sequence including the candidate subsequence is accessed from the disk and the error acceptance is confirmed by actually calculating the Euclidean distance between the candidate subsequence and the query sequence.
도 2에 도시된 바와 같이, R-트리 내에서 윈도우 점들은 모두 독립적으로 관리된다. 또한, 상기 두 논문에서 개시된 종래의 두 매칭방법의 후처리 과정에서는 인덱스 검색을 통하여 반환되는 순서로 각 후보 윈도우가 포함되는 후보 서브시퀀스를 질의 시퀀스와 비교한다. 즉, 각 후보 윈도우가 반환될 때마다 상기 후보 윈도우가 포함되는 후보 서브시퀀스를 질의 시퀀스와 비교하기 때문에 비효율적이며 특히 하기와 같은 두 가지 측면에서 성능상의 문제들을 야기시킨다.As shown in FIG. 2, all window points in the R-tree are managed independently. In addition, in the post-processing process of the two conventional matching methods disclosed in the above two papers, candidate subsequences including each candidate window are compared with a query sequence in the order returned through an index search. That is, since each candidate window is returned, the candidate subsequence including the candidate window is compared with the query sequence, which is inefficient and causes performance problems in two aspects as follows.
첫째는 디스크 액세스 오버헤드로서, 동일한 데이터 시퀀스를 디스크로부터 반복적으로 액세스함으로써 발생하는 성능상의 문제이다. 상기 문제는 인덱스 검색의 결과, 같은 데이터 시퀀스에 속하는 서로 다른 윈도우들이 후보 윈도우로 채택되는 경우에 발생한다. 즉, 같은 시퀀스에 속하는 후보 윈도우들이라 할 지라도 인덱스 검색의 결과로 반환되는 시점이 다르므로 같은 데이터 시퀀스를 디스크로부터 여러 번 액세스해야 하는 것이다. 도 2에 도시된 바와 같이 A, B, C, D는 모두 후보 윈도우를 포함하는 후보 시퀀스들이며 이들은 후처리 과정에서 각각 1, 8, 3, 2회 디스크로부터 액세스되어야 함을 알 수 있다. 이와 같은 디스크로부터의 동일한 시퀀스의 중복 액세스는 전체 서브시퀀스 매칭의 성능을 저하시키는 중요한 원인이 되었다.The first is disk access overhead, which is a performance problem caused by repeatedly accessing the same sequence of data from disk. This problem occurs when, as a result of the index search, different windows belonging to the same data sequence are adopted as candidate windows. In other words, even if the candidate windows belonging to the same sequence are returned at different times, the same data sequence must be accessed from the disk several times. As shown in FIG. 2, A, B, C, and D are candidate sequences including candidate windows, and they can be seen that they must be accessed from 1, 8, 3, and 2 discs in the post-processing process. Redundant access of the same sequence from such disks has been a significant cause of degrading the performance of the entire subsequence matching.
두 번째로 CPU 처리 오버헤드로서, 동일한 서브시퀀스를 질의 시퀀스와 두 번 이상 비교함으로써 발생하는 CPU 성능상의 문제이다. 상기 문제는 인덱스 검색 결과, 동일한 데이터 서브시퀀스에 속하는 서로 다른 윈도우들이 후보 윈도우로 선택되는 경우에 발생한다. 도 3은 질의 시퀀스와 데이터 서브시퀀스의 비교도이다. 도 3에 도시된 바와 같이, 질의 시퀀스 Q 내에 Qw[1]에서 Qw[k]까지의 k 개의 연속적인 윈도우들과 대응되는 데이터 시퀀스 S 내 Sw[1]에서 Sw[k]까지의 윈도우들이 모두 후보 윈도우로 반환되면, 질의 시퀀스는 동일한 상기 서브시퀀스와 k번 중복하여 비교하게 된다. 이러한 불필요한 중복 비교로 인하여 CPU 시간의 낭비를 초래하는 문제점이 있었다.Secondly, CPU processing overhead, a CPU performance problem caused by comparing the same subsequence with a query sequence more than once. The problem arises when, as a result of an index search, different windows belonging to the same data subsequence are selected as candidate windows. 3 is a comparison of query sequences and data subsequences. As shown in Fig. 3, all the windows from Sw [1] to Sw [k] in the data sequence S correspond to k consecutive windows from Qw [1] to Qw [k] in the query sequence Q. When returned to the candidate window, the query sequence is compared k times with the same subsequence. There is a problem that waste of CPU time due to such unnecessary duplication comparison.
따라서, 본 발명에서는 상기와 같은 문제점을 해결하기 위한 것으로 본 발명은 인덱스 검색 결과로 반환되는 후보 서브시퀀스들에 관한 정보를 이진 탐색 트리 내에 삽입하여 정렬하고 상기 후보 서브시퀀스들을 포함하는 같은 시퀀스를 한번만 액세스하여 상기 후보 서브시퀀스들을 질의 시퀀스와 비교함으로써 상기 후보 서브시퀀스에 대한 디스크 액세스 및 상기 후보 서브시퀀스 비교과정에서 발생하는 중복을 제거하여 서브시퀀스 매칭의 후처리 과정을 최적으로 처리하는 방법을 제공하는데 그 목적이 있다.Accordingly, the present invention solves the above problems, and the present invention inserts and sorts information about candidate subsequences returned as an index search result in a binary search tree and repeats the same sequence including the candidate subsequences only once. By accessing and comparing the candidate subsequences with the query sequence to provide a method for optimally processing the post-sequence of subsequence matching by eliminating the duplication occurring in the disk access and candidate subsequence comparison process for the candidate subsequences Its purpose is.
상기 목적을 달성하기 위한 구성수단으로서의 본 발명은, 질의 시퀀스와 유사한 서브시퀀스를 검색하여 매칭하는 시계열 데이터베이스에서 서브시퀀스 매칭의 후처리 최적화 방법에 있어서,According to an aspect of the present invention, there is provided a post-processing optimization method of subsequence matching in a time series database that searches and matches a subsequence similar to a query sequence.
인덱스 검색 결과로부터 반환되는 하나 이상의 후보 서브시퀀스에 대응하는 각 시퀀스를 디스크에 정렬하는 제1 단계;Aligning each sequence corresponding to the one or more candidate subsequences returned from the index search result onto a disc;
상기 디스크로부터 상기 시퀀스를 정렬된 순서로 액세스하여 읽어들이는 제2 단계;A second step of accessing and reading the sequence from the disc in sorted order;
상기 시퀀스 내에 상기 후보 서브시퀀스를 확인하고 상기 후보 서브시퀀스와 질의 시퀀스와의 거리를 허용치와 비교하는 제3 단계; 및Identifying the candidate subsequence within the sequence and comparing the distance between the candidate subsequence and the query sequence with a tolerance; And
상기 제3 단계의 판단결과 상기 거리가 상기 허용치 이내이면 상기 후보 서브시퀀스를 질의 결과로 반환하고 상기 거리가 상기 허용치를 초과하면 착오 채택으로 간주하는 제4 단계를 포함한다.And a fourth step of returning the candidate subsequence as a query result if the distance is within the allowable value as the determination result of the third step, and deeming a mistaken adoption if the distance exceeds the allowable value.
본 발명에 따른 서브시퀀스 매칭의 후처리 방법에서는 인덱스 검색의 결과에 포함되는 후보 윈도우들이 무작위 순서대로 반환되어 중복되는 문제를 해결하기 위해 반환되는 후보 윈도우들을 위한 후처리 과정을 바로 수행하지 않고 같은 시퀀스에 속하는 후보 윈도우들, 같은 서브시퀀스에 속하는 후보 윈도우들을 한꺼번에 처리하는 방법을 제공한다. 여기서, 상기 인덱스 검색은 일반적으로 널리 제안된 R-트리 검색 알고리즘을 그대로 사용한다.In the post-processing method of subsequence matching according to the present invention, the candidate sequence included in the result of the index search is returned in a random order so that the same sequence is not immediately performed without performing the post-processing process for the returned candidate windows. Provides a method for processing candidate windows belonging to and candidate windows belonging to the same subsequence at once. In this case, the index search generally uses the widely proposed R-tree search algorithm as it is.
본 발명에 따른 서브시퀀스 매칭의 처리는 크게 인덱스 검색과정, 정렬과정 및 후처리 과정의 세 가지 과정으로 이루어진다. 상기 인덱스 검색과정에서는 질의 시퀀스에 포함된 질의 윈도우 단위로 서브시퀀스와 유사한 후보 서브시퀀스를 검색하고 상기 검색된 후보 서브시퀀스를 다중키를 이용하여 이진 탐색 트리에 삽입하여 정렬하고 상기 이진 탐색 트리에 삽입된 후보 시퀀스들을 포함하는 데이터 시퀀스에 일괄적으로 액세스하여 상기 질의 시퀀스와 유사한 서브시퀀스를 비교하여 유사한 서브시퀀스를 최종적으로 반환하게 된다. 여기서, 중요한 것은 인덱스 검색 결과로부터 전송된 후보 서브시퀀스들을 일괄적으로 상기 이진 탐색 트리에 삽입하여 같은 시퀀스에 속하는 후보 서브시퀀스들을 정렬한 후 후처리과정에서 상기 같은 시퀀스를 한번만 액세스하여 상기 후보 서브시퀀스와 질의 시퀀스를 비교한다는 것이다. 이로써, 종래에서 검색된 후보 서브시퀀스가 전송된 순서대로 매회 액세스함으로써 발생되는 성능저하를 줄일 수 있다.The subsequence matching process according to the present invention is largely composed of three processes: an index searching process, a sorting process, and a post-processing process. In the index retrieval process, candidate subsequences similar to the subsequences are searched by the unit of the query window included in the query sequence, the searched candidate subsequences are inserted into a binary search tree using multiple keys, sorted, and inserted into the binary search tree. The data sequence including the candidate sequences is collectively accessed to compare similar subsequences to the query sequence and finally return similar subsequences. In this case, it is important that the candidate subsequences transmitted from the index search results are collectively inserted into the binary search tree to align candidate subsequences belonging to the same sequence, and then the same subsequence is accessed only once in a post-process. Is to compare the query sequence with As a result, it is possible to reduce performance degradation caused by accessing the candidate subsequence retrieved conventionally every time in the order of transmission.
이하, 도면을 참조하여 본 발명을 보다 상세하게 설명한다.Hereinafter, the present invention will be described in more detail with reference to the drawings.
도 4는 본 발명에 따른 방법을 구현하는 장치의 일실시예를 도시한 구성블럭도이다. 도 4에 도시된 바와 같이, 본 발명에서 효율적인 서브시퀀스 매칭을 구현하기 위한 장치는, 질의 시퀀스 입력부(30), 서브시퀀스 매칭 처리부(40), 저장부(50)로 구성되며 상기 서브시퀀스 매칭 처리부(40)는 인덱스 검색부(41), 정렬부(42) 및 후처리부(43)로 구성된다. 상기 질의 시퀀스 입력부(30) 및 서브시퀀스 매칭 처리부(40)는 바람직하게는 프로그램 실행가능한 컴퓨터로 구현되며 상기 저장부(50)는 바람직하게는 하드디스크로 구현된다.4 is a block diagram showing one embodiment of an apparatus for implementing the method according to the present invention. As shown in FIG. 4, the apparatus for implementing efficient subsequence matching according to the present invention includes a query sequence input unit 30, a subsequence matching processing unit 40, and a storage unit 50, and the subsequence matching processing unit. 40 is composed of an index search unit 41, an alignment unit 42 and a post-processing unit 43. The query sequence input unit 30 and the subsequence matching processing unit 40 are preferably implemented by a program executable computer and the storage unit 50 is preferably implemented by a hard disk.
사용자에 의해 질의 시퀀스 입력부(30)로 입력된 질의 시퀀스는 후단의 서브시퀀스 매칭 처리부(40)로 입력된다. 서브시퀀스 매칭을 위해서는 상기 질의 시퀀스로부터 일정 크기의 윈도우 단위로 분할하여 DFT를 통해 저차원 공간상에 질의 윈도우 점으로 변환한다. 인덱스 검색부(41)는 상기 각각의 질의 윈도우 점에 대하여 허용 범위가 ε/ p1/2이내인 범위 질의를 R-트리에 수행하여 후보 윈도우를 검색한다. 즉, 상기 인덱스 검색부(41)에서는 상기 R-트리를 검색함으로써 저장부(50)에 존재하는 시계열 데이터베이스로부터 질의 시퀀스의 질의 윈도우와 유사한 후보 윈도우를 찾아내는 것이다. 여기서, 주의해야 할 것은 상기 인덱스 검색부(41)는 질의 윈도우 단위로 상기 질의 윈도우와 유사한 윈도우를 인덱스 검색부(41)에서 검색하여 상기 유사한 윈도우를 포함하는 서브시퀀스를 검색한다는 것이다. 이때, 하나의 질의 시퀀스에는 복수개의 질의 윈도우가 존재할 수 있으므로 상기 인덱스 검색부(41)는 하나의 질의 시퀀스와 유사한 서브시퀀스를 검색할 때, 동일한 서브시퀀스를 중복해서 여러번 검색할 경우가 발생한다. 예를 들어, A의 질의 시퀀스를 a1,a2,a3의 질의 윈도우로 분할하고 상기 세 개의 질의 윈도우와 유사한 윈도우를 인덱스 검색부(41)에서 검색하는 경우, a1의 질의 윈도우와 유사한 윈도우 b1과 a2의 질의 윈도우와 유사한 윈도우 b2가 동일한 서브시퀀스에 속하는 경우가 발생할 수도 있다는 것이다. 여기서, 상기 윈도우 b1,b2는 동일한 서브시퀀스에 속한다.The query sequence input by the user to the query sequence input unit 30 is input to a subsequent subsequence matching processing unit 40. For subsequence matching, the query sequence is divided into predetermined window units and transformed into query window points in a low dimensional space through a DFT. The index retrieval section 41 searches the candidate window by performing a range query having an allowable range within ε / p1/2 for the respective query window points to the R-tree. That is, the index searching unit 41 searches for the R-tree to find candidate windows similar to the query windows of the query sequence from the time series database existing in the storage unit 50. It should be noted that the index searching unit 41 searches for a subsequence including the similar window by searching the index searching unit 41 for a window similar to the query window on a query window basis. In this case, since a plurality of query windows may exist in one query sequence, the index search unit 41 may search for the same subsequence multiple times when searching for a subsequence similar to one query sequence. For example, when the query sequence of A is divided into query windows a1, a2, a3, and the index search unit 41 searches for windows similar to the three query windows, the windows b1 and a2 similar to the query windows of a1. It may be the case that a window b2 similar to the query window of s belongs to the same subsequence. Here, the windows b1 and b2 belong to the same subsequence.
결국, 상기 인덱스 검색부(41)는 사용자에 의해 주어지는 질의 시퀀스로부터 분할된 질의 윈도우와 유사한 데이터 윈도우들을 R-트리 인덱스로부터 검색하며 상기 유사성의 판단은 바람직하게는 유클리드 거리 계산방법을 이용한다.As a result, the index retrieval unit 41 retrieves data windows similar to the query windows divided from the query sequence given by the user from the R-tree index, and the determination of the similarity preferably uses a Euclidean distance calculation method.
상기와 같이 검색된 질의 시퀀스와 유사한 서브시퀀스(이하, '후보 서브시퀀스'라 함)들을 후단의 정렬부(42)로 전송한다. 상기 정렬부(42)는 상기 후보 서브시퀀스들을 받아 소정의 기준형식으로 정렬한다. 상기 기준형식은 바람직하게는 <시퀀스ID, 서브시퀀스 오프셋(offset)>의 다중키(multi-attribute key)를 사용한다. 여기서, 상기 시퀀스ID(식별자)는 그 후보 서브시퀀스가 속하는 데이터 시퀀스의 식별자이고 상기 서브시퀀스 오프셋은 그 후보 서브시퀀스에 의해 후보로 설정된 시퀀스ID에서의 서브시퀀스의 시작값을 나타낸다. 상기 서브시퀀스 오프셋 값은 상기 후보 윈도우와 매치되는 질의 윈도우의 위치정보를 이용하여 역으로 계산될 수도 있다.Subsequences (hereinafter, referred to as "candidate subsequences") similar to the searched query sequences are transmitted to the rearrangement unit 42. The sorter 42 receives the candidate subsequences and sorts them in a predetermined reference format. The reference format preferably uses a multi-attribute key of <sequence ID, subsequence offset>. Here, the sequence ID (identifier) is an identifier of a data sequence to which the candidate subsequence belongs, and the subsequence offset indicates a start value of the subsequence at the sequence ID set as a candidate by the candidate subsequence. The subsequence offset value may be calculated inversely using location information of the query window that matches the candidate window.
상기 정렬부(42)에서의 후보 서브시퀀스들의 정렬은 바람직하게는 이진 탐색 트리(binary search tree)를 이용한다. 즉, 상기 정렬부(42)는 상기 인덱스 검색부(41)에서 검색된 각 후보 서브시퀀스들에 대하여 상기 <시퀀스ID, 서브시퀀스 오프셋>을 이진 탐색 트리에 차례로 삽입한다. 상기 이진 탐색 트리는 상기 각 후보 서브시퀀스에 대응하는 시퀀스별로 순서대로 자동 정렬한다. 이때, 동일한 시퀀스ID를 가지는 서로 다른 후보 서브시퀀스가 존재하는 경우도 있다. 예를 들어, A라는 시퀀스에 T1의 서브시퀀스와 T2의 서브시퀀스가 있고 상기 두 개의 서브시퀀스가 모두 상기 후보 서브시퀀스인 경우에 <시퀀스A, 서브시퀀스 T1>와 <시퀀스A, 서브시퀀스 T2>가 이진 탐색 트리에 삽입되고 상기 이진 탐색 트리에서 각 시퀀스별로 정렬되어진다.The sorting of candidate subsequences in the sorting section 42 preferably uses a binary search tree. That is, the sorter 42 sequentially inserts the <sequence ID, subsequence offset> into the binary search tree for each candidate subsequence searched by the index searcher 41. The binary search tree is automatically sorted in order for each sequence corresponding to each candidate subsequence. At this time, different candidate subsequences having the same sequence ID may exist. For example, if the sequence A has a subsequence of T1 and a subsequence of T2 and both of the two subsequences are the candidate subsequences, <Sequence A, Subsequence T1> and <Sequence A, Subsequence T2>. Is inserted into the binary search tree and sorted by each sequence in the binary search tree.
상기와 같이 각 후보 서브시퀀스에 대하여 이진 탐색 트리에서 정렬이 완료되면 후처리부(43)에서는 상기 이진 탐색 트리를 중위 순회(in-order traverse) 방식으로 탐색하여 저장부(50)에 저장된 해당 시퀀스에 액세스한 후, 질의 시퀀스와 상기 정렬된 후보 서브시퀀스를 비교하여 상기 후보 서브시퀀스 중에서 상기 질의 시퀀스와 유사한 것을 판단한다. 상기 유사성 판단은 상술한 바와 같이 유클리드 거리 계산방법을 이용하는 것이 바람직하다. 상기 거리 계산 결과가 허용치 이하인 서브시퀀스들을 최종결과로 반환한다. 상기 중위 순회 방식은 정렬부(42)에 삽입되어 정렬된 시퀀스별로 순서대로 후처리하는 것을 말한다. 즉, 정렬되는 시퀀스ID에 대응하는 시퀀스별로 디스크에 액세스한 후 상기 시퀀스에 포함된 모든 서브시퀀스를 비교하는 것을 말하는 것이다. 예를 들어, A시퀀스에 대한 디스크 액세스를 실행한 후 상기 A시퀀스 내의 모든 후보 서브시퀀스를 질의 시퀀스와 비교한 후, 다른 B,C 등의 시퀀스에 대해서 디스크 액세스를 실행하여 각각의 시퀀스에 포함되는 모든 후보 시퀀스를 비교하는 것이다. 이로써, 상기 A시퀀스를 한번만 액세스하면 상기 A시퀀스 내의 모든 후보 서브시퀀스들을 상기 질의 시퀀스와 비교할 수 있다.After the sorting is completed in the binary search tree for each candidate subsequence as described above, the post-processing unit 43 searches the binary search tree in an in-order traverse manner and stores the binary search tree in the corresponding sequence stored in the storage unit 50. After access, the query sequence is compared with the sorted candidate subsequences to determine similarities among the candidate subsequences. As described above, it is preferable to use the Euclidean distance calculation method as described above. Subsequences whose distance calculation results are less than the allowable value are returned as final results. The median traversal method refers to post-processing in sequence for each sequence inserted into the alignment unit 42. That is, after accessing the disc for each sequence corresponding to the sequence ID to be sorted, it means to compare all the subsequences included in the sequence. For example, after performing the disk access for the A sequence, all candidate subsequences in the A sequence are compared with the query sequence, and then the disk access is performed for the other B, C, etc. to be included in each sequence. All candidate sequences are compared. Thus, accessing the A sequence only once allows all candidate subsequences in the A sequence to be compared with the query sequence.
본 발명의 후처리 최적화 방법에서는 인덱스 검색 결과로 전송되는 후보 서브시퀀스들을 상기 이진 탐색 트리에 삽입하여 저장하는데 같은 시퀀스에 속하는 후보 서브시퀀스들을 소정의 그룹으로 하여 정렬한다. 예를 들어, A,B,C의 후보 서브시퀀스들이 모두 X 시퀀스에 포함된다면 상기 A,B,C 후보 서브시퀀스들을 하나의 그룹으로 구성하여 정렬하는 것이다.In the post-processing optimization method of the present invention, candidate subsequences transmitted as index search results are inserted into the binary search tree and stored. The candidate subsequences belonging to the same sequence are arranged into a predetermined group. For example, if the candidate subsequences of A, B, and C are all included in the X sequence, the A, B, and C candidate subsequences are organized into one group and aligned.
이로써, 각 그룹의 시퀀스에 액세스할 때는 각각의 후보 서브시퀀스가 반환될 때마다 해당 시퀀스를 액세스 할 필요없이, 같은 시퀀스는 한번만 액세스하여 상기 액세스된 시퀀스에 포함된 모든 후보 서브시퀀스들을 연속적으로 비교함으로써 종래의 중복문제를 해결하여 성능상의 문제점을 해결할 수 있는 것이다.Thus, when accessing a sequence of each group, the same sequence is accessed only once, without having to access the sequence each time each candidate subsequence is returned, thereby successively comparing all candidate subsequences contained in the accessed sequence. The problem of performance can be solved by solving the conventional redundancy problem.
이하, 본 발명에 따른 서브시퀀스 매칭의 후처리 과정을 도 5 및 도 6을 참조하여 보다 상세하게 설명한다. 본 발명에서의 기술요지는 서브시퀀스 매칭을 위한 후처리의 최적화 방법에 관한 것이다. 따라서, 인덱스 검색 과정은 기존의 방법을 적용하므로 이하에서는 본 발명에서 제시하는 정렬과정과 후처리 과정을 중심으로 설명한다.Hereinafter, a post-processing process of subsequence matching according to the present invention will be described in more detail with reference to FIGS. 5 and 6. Summary of the Invention The present invention relates to a method of optimizing post-processing for subsequence matching. Therefore, the index retrieval process applies the existing method, and will be described below with reference to the sorting process and the post-processing process.
도 5는 본 발명의 후처리 최적화 방법에 따른 정렬과정을 보이는 플로우차트이다. 먼저, 인덱스 검색과정에서는 질의 시퀀스로부터 분할된 윈도우 단위로 서브시퀀스의 후보 윈도우와 비교하여 유사하다고 판단되는 후보 서브시퀀스를 검색한다. 정렬부(42)에서는 상기와 같이 인덱스 검색의 결과로 반환되는 각 후보 서브시퀀스를 수신하여(S501), 상기 각 후보 서브시퀀스들에 대응하는 <시퀀스ID, 서브시퀀스 오프셋>을 다중키로 하여 이진 탐색 트리에 삽입한다(S502). 예를 들어, 주식 데이터의 경우, 임의의 주식에 대한 질의 시퀀스(X)를 질의 윈도우(Wx) 단위로 분할하여 각 질의 윈도우(Wx) 단위로 이와 유사한 서브시퀀스(이하, 후보 서브시퀀스라 함)들을 순서대로 검색한 결과 A회사의 주식에 대한 데이터 시퀀스의 두 번째 서브시퀀스, B회사의 주식에 대한 데이터 시퀀스의 첫 번째 서브시퀀스 및 상기 A회사 주식에 대한 상기 데이터 시퀀스의 네 번째 서브시퀀스와 유사하다고 간주되면 상기한 다중키로 <A회사, 두 번째 서브시퀀스>, <B회사, 첫 번째 서브시퀀스>, <A회사, 네 번째 서브시퀀스>를 이진 탐색 트리에 삽입한다.5 is a flowchart showing the alignment process according to the post-processing optimization method of the present invention. First, in the index retrieval process, candidate subsequences that are determined to be similar are searched by comparing the candidate windows of the subsequences in units of windows divided from the query sequence. The sorter 42 receives each candidate subsequence returned as a result of the index search as described above (S501), and searches for a binary by using <sequence ID, subsequence offset> corresponding to each candidate subsequence as a multi-key. It is inserted into the tree (S502). For example, in the case of stock data, a query sequence (X) for any stock is divided into query window (Wx) units and similar subsequences (hereinafter, referred to as candidate subsequences) in each query window (Wx) units. Search results in order, similar to the second subsequence of the data sequence for Company A's stock, the first subsequence of the data sequence for Company B's stock, and the fourth subsequence of the data sequence for Company A's stock. In this case, <A company, the second subsequence>, <B company, the first subsequence>, <Company A, the fourth subsequence> are inserted into the binary search tree.
계속하여, 상기 이진 탐색 트리에 삽입하면서 동일한 다중키값이 이미 상기 이진 탐색 트리에 존재하는지 판단한다(S503). 상기 단계(S503)에서 존재하는 것으로 판단되면 상기 다중키값을 상기 이진 탐색 트리에 삽입하지 않고 무시하고 다음으로 진행한다(S504). 예를 들어, 도 3에서 k개의 후보 윈도우들은 모두 같은 <시퀀스ID, 서브시퀀스 오프셋>의 다중키 값을 가지게 되므로 단 한번만 이진 탐색 트리에 삽입된다. 이는 같은 시퀀스에 속하는 서브시퀀스의 중복 삽입을 방지하기 위한 것이다. 이로써, 후처리에서 동일한 서브시퀀스의 중복 비교는 발생하지 않지 않는다. 상기 이진 탐색 트리 내에 삽입하는 과정은 인덱스 검색의 결과로부터 후보 서브시퀀스가 전송될 때마다 실행된다.Subsequently, it is determined whether the same multi-key value already exists in the binary search tree while being inserted into the binary search tree (S503). If it is determined in step S503 that the multi-key value is not inserted into the binary search tree and ignored, the process proceeds to step S504. For example, in FIG. 3, the k candidate windows are all inserted into the binary search tree only once because they have multiple key values of the same <sequence ID and subsequence offset>. This is to prevent duplicate insertion of subsequences belonging to the same sequence. Thus, no duplicate comparison of the same subsequence occurs in the post processing. The insertion into the binary search tree is executed each time a candidate subsequence is transmitted from the result of the index search.
그러나, 상기 단계(S503)에서 상기 동일한 다중키값이 존재하지 않는 것으로 판단되면 상기 다중키값을 상기 이진 탐색 트리에 삽입한다(S505). 이와 같이 삽입된 각 다중키값은 시퀀스별로 정렬된다(S506). 상기 시퀀스에 속하는 모든 후보 서브시퀀스들이 상기 이진 탐색 트리에 삽입됨으로써 이들은 <시퀀스ID, 서브시퀀스 오프셋>의 순서로 정렬되며 또한, 시퀀스ID별로 차례로 정렬된다. 상기 정렬은 소정의 기준으로 정렬될 수 있으며 특정한 방법에 한정되는 것이 아니다. 상기 예에서 정렬방식에 대한 일실시예를 들면, <A회사, 두 번째 서브시퀀스>, <A회사, 네 번째 서브시퀀스>, <B회사, 첫 번째 서브시퀀스>와 같이 바람직하게는 동일한 시퀀스ID별로 정렬된다. 이로써, 정렬부(42)에서의 과정은 종료된다.However, if it is determined in step S503 that the same multiple key value does not exist, the multiple key value is inserted into the binary search tree (S505). Each multi-key value inserted in this way is sorted by sequence (S506). All candidate subsequences belonging to the sequence are inserted into the binary search tree so that they are sorted in order of <sequence ID, subsequence offset>, and also in sequence by sequence ID. The alignment may be arranged on a predetermined basis and is not limited to a specific method. In the above example, one embodiment of the sorting method is preferably the same sequence ID as <Company A, Second Subsequence>, <Company A, Fourth Subsequence>, <Company B, First Subsequence>. Sorted by. By this, the process in the alignment part 42 is complete | finished.
도 6은 본 발명에 따른 후처리 최적화 방법의 후처리과정을 보이는 플로우차트이다.6 is a flowchart showing a post-processing process of the post-processing optimization method according to the present invention.
먼저, 상기한 이진 탐색 트리를 중위 순회방식으로 탐색하여 차례로 전송되는 <시퀀스ID, 서브시퀀스 오프셋>을 수신한다(S601). 상기 각 시퀀스ID에 대응하는 시퀀스를 디스크에 액세스하여 읽어들인다(S602). 여기서, 중요한 것은 종래에서와 같이 서브시퀀스가 입력되는 순서대로 즉시 디스크를 액세스하지 않고 본 발명에서는 상기 이진 탐색 트리에서 시퀀스ID 별로 그룹화하여 정렬되어 있으므로 상기 단계(S602)에서는 상기 읽어들일 대상의 시퀀스의 디스크에 한번만 액세스하여 상기 시퀀스에 포함된 서브시퀀스들을 모두 읽어들일 수 있다. 이것은 상기 이진 탐색 트리에서 중위 순회 방식을 통해 실행가능하다. 이때는 단 한번의 시퀀스 액세스가 이루어지며 상기 한번의 액세스 동안 상기 시퀀스에 포함되는 모든 서브시퀀스들을 비교할 수 있게 된다. 다시 말하면, <시퀀스ID, 서브시퀀스 오프셋>의 순서로 후보 시퀀스들을 액세스한다는 것이다.First, the binary search tree is searched in the median traversal method, and received <sequence ID and subsequence offset> are sequentially transmitted (S601). The sequence corresponding to each sequence ID is read by accessing the disk (S602). It is important to note that in the present invention, since the discs are not immediately accessed in the order in which the subsequences are input, as in the prior art, they are grouped and sorted by sequence ID in the binary search tree. The subsequence included in the sequence can be read by accessing the disc only once. This is feasible via a median traversal scheme in the binary search tree. In this case, only one sequence access is made and all subsequences included in the sequence can be compared during the single access. In other words, candidate sequences are accessed in the order of <sequence ID, subsequence offset>.
상기 중위 순회방식은 동일한 시퀀스를 갖는 서브시퀀스를 한꺼번에 일괄 처리하고 다음 시퀀스를 처리하는 것을 말한다. 이는 하나의 시퀀스ID에 여러개의 서브시퀀스 오프셋이 정렬된 경우 상기 하나의 시퀀스에 대해 디스크에 한번만 액세스하여 상기 모든 서브시퀀스를 연속적으로 비교하는 것이다.The median traversal method refers to batch processing of subsequences having the same sequence at once and processing the next sequence. This means that when several subsequence offsets are arranged in one sequence ID, all the subsequences are continuously compared by accessing the disc only once for the one sequence.
이로써, 상기 단계(S602)에서는 같은 시퀀스에 속하는 후보 서브시퀀스들의 경우에는 상기 같은 시퀀스의 디스크를 한번만 액세스하면 되고 상기와 같이 한번의 액세스 동안에 상기 후보 서브시퀀스들은 연속적으로 비교된다.Thus, in step S602, in the case of candidate subsequences belonging to the same sequence, the disc of the same sequence needs to be accessed only once, and the candidate subsequences are continuously compared during one access as described above.
계속하여, 상기 시퀀스 내의 서브시퀀스 오프셋에서 시작되는 서브시퀀스를 확인하고(S603), 상기 확인된 서브시퀀스와 질의 시퀀스의 유클리드 거리가 유사 허용치 ε이내인지 판단한다(S604). 상기 유사성 판단 방법시 상기 유클리드 거리 계산방법을 사용하고 있으나 이에 한정하지는 않는다. 또한, 본 발명에서는 상기 확인된 서브시퀀스와 질의 시퀀스는 한번만 비교한다. 즉, 동일한 복수개의 후보 서브시퀀스가 존재할 경우 상기 복수개의 후보 서브시퀀스 중에서 하나의 후보 서브시퀀스와 상기 질의 시퀀스만 비교한다. 이로써, 중복 비교를 방지할 수 있다.Subsequently, the subsequence starting from the subsequence offset in the sequence is checked (S603), and it is determined whether the Euclidean distance between the identified subsequence and the query sequence is within the similar allowance ε (S604). The similarity determination method uses the Euclidean distance calculation method, but is not limited thereto. Also, in the present invention, the identified subsequence and the query sequence are compared only once. That is, when the same plurality of candidate subsequences exist, only one candidate subsequence and the query sequence among the plurality of candidate subsequences are compared. Thereby, duplication comparison can be prevented.
상기 단계(S604)의 판단결과 ε이내인 것으로 판단되면 상기 서브시퀀스를 질의 결과로 반환하고(S605), 상기 단계(S604)의 판단결과 ε이내가 아닌 것으로 판단되면 착오채택으로 간주한다(S606). 이로써, 후처리 과정을 종료된다.If the determination result of the step (S604) is determined to be within ε, the subsequence is returned as a query result (S605), and if it is determined that the determination result of the step (S604) is not within ε, it is regarded as a mistaken adoption (S606). . This completes the post-processing process.
상기한 바와 같이 상기 후처리 과정에서는 인덱스 검색 결과로부터 반환되는 후보 서브시퀀스들을 즉시 질의 시퀀스와 비교하여 처리하는 종래와는 달리, 상기 후보 서브시퀀스들을 소정의 다중키로 정렬한 후 한꺼번에 디스크에 액세스하여 질의 시퀀스와 비교한 후 처리하도록 한다.As described above, unlike the conventional process in which candidate subsequences returned from an index search result are immediately compared with a query sequence and processed in the post-processing process, the candidate subsequences are sorted by a predetermined multi-key, and then the disk is accessed at once. Compare with the sequence before processing.
본 발명의 상세한 설명 및 도면에는 주식에 대한 데이터 시퀀스에 한정하여 서브시퀀스 매칭의 정렬방법과 후처리방법이 개시되어 있지만, 본 발명은 그 응용되는 분야별로 다양하게 제작될 수 있다. 상기와 같은 주식에 대한 데이터 시퀀스라는 특정 분야는 단지 본 발명의 설명하기 위한 바람직한 일례로서 본 발명의 권리범위를 한정하는 것은 아니다. 따라서, 본 발명의 권리의 범위는 상기한 상세한 설명에 의해 결정되는 것이 아니라 첨부한 청구범위에 결정되어야만 할 것이다.In the detailed description and drawings of the present invention, the method of sorting and post-processing subsequence matching is limited to data sequences of stocks. However, the present invention may be variously manufactured according to its application. This particular field of data sequence for stocks is merely a preferred example of the invention and does not limit the scope of the invention. Therefore, the scope of the present invention should be determined by the appended claims rather than by the foregoing description.
본 발명에 따르면, 인덱스 검색 결과로부터 전송되는 후보 서브시퀀스에 대응하는 시퀀스에 대해 <시퀀스ID, 서브시퀀스 오프셋>을 다중키로 하여 이진 탐색 트리에 삽입하여 정렬하고 상기 이진 탐색 트리의 중위 순회를 수행한 결과로 반환되는 순서대로 후처리를 수행함으로써, 상기 후보 서브시퀀스를 포함하는 각 시퀀스는 디스크로부터 "단 한번만" 액세스되므로 컴퓨터의 성능이 향상된다.According to the present invention, a sequence corresponding to a candidate subsequence transmitted from an index search result is inserted into a binary search tree by using <sequence ID, subsequence offset> as a multi-key and sorted, and an intermediate traversal of the binary search tree is performed. By performing post-processing in the order in which they are returned, each sequence containing the candidate subsequences is accessed "only once" from the disk, thereby improving computer performance.
또한, 상기 이진 탐색 트리 생성시 같은 시퀀스에 속하는 중복된 서브시퀀스들은 미리 제거하여 후처리에서 동일한 서브시퀀스의 중복 비교의 문제가 발생되지 않는다.In addition, when generating the binary search tree, duplicate subsequences belonging to the same sequence are removed in advance so that a problem of overlapping comparison of the same subsequence does not occur in post-processing.
나아가, 반드시 필요한 디스크 액세스와 서브시퀀스 비교를 단 한번만 수행하므로 서브시퀀스 매칭의 후처리 과정에 최적의 방법을 제공하며 이로써, 매우 효과적으로 서브시퀀스 매칭을 수행할 수 있게 된다.Furthermore, since only necessary disk access and subsequence comparison is performed once, it provides an optimal method for the post-processing of subsequence matching, and thus, it is possible to perform subsequence matching very effectively.
도 1은 시퀀스를 윈도우로 분할하는 예시도를 도시한 것이다.1 shows an exemplary diagram of dividing a sequence into windows.
도 2는 일반적으로 R-트리를 이용한 서브시퀀스 매칭의 처리과정을 보이는 일실시예를 나타낸 것이다.Figure 2 shows one embodiment showing the process of subsequence matching using an R-tree in general.
도 3은 질의 시퀀스와 데이터 서브시퀀스의 비교도이다.3 is a comparison of query sequences and data subsequences.
도 4는 본 발명에 따른 방법을 구현하는 장치의 일실시예를 도시한 구성블럭도이다.4 is a block diagram showing one embodiment of an apparatus for implementing the method according to the present invention.
도 5는 본 발명의 후처리 최적화 방법에 따른 정렬과정을 보이는 플로우차트이다.5 is a flowchart showing the alignment process according to the post-processing optimization method of the present invention.
도 6은 본 발명의 후처리 최적화 방법의 후처리과정을 보이는 플로우차트이다.6 is a flowchart showing a post-processing process of the post-processing optimization method of the present invention.
* 도면의 주요 부분에 대한 부호의 설명 * Explanation of symbols on the main parts of the drawings
11,13 : 시퀀스 12 : 슬라이딩 윈도우11,13: Sequence 12: sliding window
14 : 디스조인트 윈도우 21 : R-트리14: disjoint window 21: R-tree
22,32 : 데이터 시퀀스 31 : 후보 서브시퀀스22,32: data sequence 31: candidate subsequence
33 : 질의 시퀀스 30 : 질의 시퀀스 입력부33: query sequence 30: query sequence input unit
40 : 서브시퀀스 매칭 처리부 41 : 인덱스 검색부40: subsequence matching processing unit 41: index searching unit
42 : 정렬부 43 : 후처리부42: alignment unit 43: post-processing unit
50 : 저장부50: storage unit
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR10-2001-0062679AKR100472948B1 (en) | 2001-10-11 | 2001-10-11 | A method for optimizing the post-processing of sub-sequence matching in time-series databases |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR10-2001-0062679AKR100472948B1 (en) | 2001-10-11 | 2001-10-11 | A method for optimizing the post-processing of sub-sequence matching in time-series databases |
| Publication Number | Publication Date |
|---|---|
| KR20030030514A KR20030030514A (en) | 2003-04-18 |
| KR100472948B1true KR100472948B1 (en) | 2005-03-08 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR10-2001-0062679AExpired - Fee RelatedKR100472948B1 (en) | 2001-10-11 | 2001-10-11 | A method for optimizing the post-processing of sub-sequence matching in time-series databases |
| Country | Link |
|---|---|
| KR (1) | KR100472948B1 (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2019147968A1 (en)* | 2018-01-26 | 2019-08-01 | Ge Inspection Technologies, Lp | Real time multi variate time series search |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7654271B2 (en) | 2005-06-02 | 2010-02-02 | The Procter & Gamble Company | Cosmetic applicator |
| US7762269B2 (en) | 2005-06-02 | 2010-07-27 | The Procter & Gamble Company | Cosmetic applicator |
| US8985883B2 (en) | 2007-07-30 | 2015-03-24 | The Procter & Gamble Company | Control surfaces for applicator with moveable applicator head |
| CN110162573B (en)* | 2019-05-05 | 2021-04-30 | 中国银行股份有限公司 | Distributed sequence generation method, device and system |
| KR102451800B1 (en)* | 2021-03-05 | 2022-10-06 | 이화여자대학교 산학협력단 | Music search method and device using inflection point of melody line |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5781906A (en)* | 1996-06-06 | 1998-07-14 | International Business Machines Corporation | System and method for construction of a data structure for indexing multidimensional objects |
| US5779301A (en)* | 1994-04-27 | 1998-07-14 | Aisin Seiki Kabushiki Kaisha | Sun roof device |
| US5930789A (en)* | 1995-05-09 | 1999-07-27 | International Business Machines Corporation | System and method for discovering similar time sequences in databases |
| KR20000033410A (en)* | 1998-11-23 | 2000-06-15 | 이원석 | Image data retrieval method by partial result matrix and flexible attribute tree |
| KR20000032772A (en)* | 1998-11-17 | 2000-06-15 | 정선종 | Space index composition method for similarity search |
| US6226636B1 (en)* | 1998-11-20 | 2001-05-01 | Philips Electronics North America Corp. | System for retrieving images using a database |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5779301A (en)* | 1994-04-27 | 1998-07-14 | Aisin Seiki Kabushiki Kaisha | Sun roof device |
| US5930789A (en)* | 1995-05-09 | 1999-07-27 | International Business Machines Corporation | System and method for discovering similar time sequences in databases |
| US5781906A (en)* | 1996-06-06 | 1998-07-14 | International Business Machines Corporation | System and method for construction of a data structure for indexing multidimensional objects |
| KR20000032772A (en)* | 1998-11-17 | 2000-06-15 | 정선종 | Space index composition method for similarity search |
| US6226636B1 (en)* | 1998-11-20 | 2001-05-01 | Philips Electronics North America Corp. | System for retrieving images using a database |
| KR20000033410A (en)* | 1998-11-23 | 2000-06-15 | 이원석 | Image data retrieval method by partial result matrix and flexible attribute tree |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2019147968A1 (en)* | 2018-01-26 | 2019-08-01 | Ge Inspection Technologies, Lp | Real time multi variate time series search |
| Publication number | Publication date |
|---|---|
| KR20030030514A (en) | 2003-04-18 |
| Publication | Publication Date | Title |
|---|---|---|
| Ganti et al. | Clustering large datasets in arbitrary metric spaces | |
| KR100344530B1 (en) | A Subsequence matching method using duality in constructing windows in time-series databases | |
| US6499033B1 (en) | Database method and apparatus using hierarchical bit vector index structure | |
| Traina Jr et al. | The omni-family of all-purpose access methods: a simple and effective way to make similarity search more efficient | |
| CA2281287C (en) | Method and system for efficiently searching for free space in a table of a relational database having a clustering index | |
| US5265244A (en) | Method and system for facilitating processing of statistical inquires on stored data accessible through a data access structure | |
| US10521441B2 (en) | System and method for approximate searching very large data | |
| US5978794A (en) | Method and system for performing spatial similarity joins on high-dimensional points | |
| US20100106713A1 (en) | Method for performing efficient similarity search | |
| US6266660B1 (en) | Secondary index search | |
| KR20010083096A (en) | Value-instance-connectivity computer-implemented database | |
| Karapiperis et al. | Summarization Algorithms for Record Linkage. | |
| CN118284890A (en) | Method for processing data to be written to a database | |
| KR100472948B1 (en) | A method for optimizing the post-processing of sub-sequence matching in time-series databases | |
| CN115543993A (en) | Data processing method and device, electronic equipment and storage medium | |
| Yagoubi et al. | Radiussketch: massively distributed indexing of time series | |
| KR100472949B1 (en) | A method for searching an index for subsequence matching in time-series databases | |
| Yoon et al. | Trend similarity and prediction in time-series databases | |
| Barg et al. | A fast and versatile path index for querying semi-structured data | |
| Zakrzewicz | Sequential index structure for content-based retrieval | |
| Yoon et al. | Bitmap indexing-based clustering and retrieval of XML documents | |
| Chauhan et al. | Finding similar items using lsh and bloom filter | |
| Kim et al. | Performance bottleneck of subsequence matching in time-series databases: Observation, solution, and performance evaluation | |
| KR20010109945A (en) | RS-tree for k-nearest neighbor queries with non spatial selection predicates and method for using it | |
| Reina et al. | An index structure for fast range search in hamming space |
| Date | Code | Title | Description |
|---|---|---|---|
| A201 | Request for examination | ||
| PA0109 | Patent application | St.27 status event code:A-0-1-A10-A12-nap-PA0109 | |
| PA0201 | Request for examination | St.27 status event code:A-1-2-D10-D11-exm-PA0201 | |
| PN2301 | Change of applicant | St.27 status event code:A-3-3-R10-R13-asn-PN2301 St.27 status event code:A-3-3-R10-R11-asn-PN2301 | |
| PG1501 | Laying open of application | St.27 status event code:A-1-1-Q10-Q12-nap-PG1501 | |
| R17-X000 | Change to representative recorded | St.27 status event code:A-3-3-R10-R17-oth-X000 | |
| D13-X000 | Search requested | St.27 status event code:A-1-2-D10-D13-srh-X000 | |
| D14-X000 | Search report completed | St.27 status event code:A-1-2-D10-D14-srh-X000 | |
| E902 | Notification of reason for refusal | ||
| PE0902 | Notice of grounds for rejection | St.27 status event code:A-1-2-D10-D21-exm-PE0902 | |
| T11-X000 | Administrative time limit extension requested | St.27 status event code:U-3-3-T10-T11-oth-X000 | |
| P11-X000 | Amendment of application requested | St.27 status event code:A-2-2-P10-P11-nap-X000 | |
| P13-X000 | Application amended | St.27 status event code:A-2-2-P10-P13-nap-X000 | |
| E701 | Decision to grant or registration of patent right | ||
| PE0701 | Decision of registration | St.27 status event code:A-1-2-D10-D22-exm-PE0701 | |
| GRNT | Written decision to grant | ||
| PR0701 | Registration of establishment | St.27 status event code:A-2-4-F10-F11-exm-PR0701 | |
| PR1002 | Payment of registration fee | St.27 status event code:A-2-2-U10-U11-oth-PR1002 Fee payment year number:1 | |
| PG1601 | Publication of registration | St.27 status event code:A-4-4-Q10-Q13-nap-PG1601 | |
| PR1001 | Payment of annual fee | St.27 status event code:A-4-4-U10-U11-oth-PR1001 Fee payment year number:4 | |
| FPAY | Annual fee payment | Payment date:20090202 Year of fee payment:5 | |
| PR1001 | Payment of annual fee | St.27 status event code:A-4-4-U10-U11-oth-PR1001 Fee payment year number:5 | |
| PN2301 | Change of applicant | St.27 status event code:A-5-5-R10-R13-asn-PN2301 St.27 status event code:A-5-5-R10-R11-asn-PN2301 | |
| LAPS | Lapse due to unpaid annual fee | ||
| PC1903 | Unpaid annual fee | St.27 status event code:A-4-4-U10-U13-oth-PC1903 Not in force date:20100215 Payment event data comment text:Termination Category : DEFAULT_OF_REGISTRATION_FEE | |
| PC1903 | Unpaid annual fee | St.27 status event code:N-4-6-H10-H13-oth-PC1903 Ip right cessation event data comment text:Termination Category : DEFAULT_OF_REGISTRATION_FEE Not in force date:20100215 | |
| PN2301 | Change of applicant | St.27 status event code:A-5-5-R10-R13-asn-PN2301 St.27 status event code:A-5-5-R10-R11-asn-PN2301 | |
| P22-X000 | Classification modified | St.27 status event code:A-4-4-P10-P22-nap-X000 | |
| P22-X000 | Classification modified | St.27 status event code:A-4-4-P10-P22-nap-X000 |