Recently, research on the data stream has become of growing importance due to new requirements from advances in network technology, mobile/sensor devices, and emerging ubiquitous environments. Queries over data streams are not one-time queries, which are executed only once against stored data. Instead, they are continuous queries that are registered in advance and run repeatedly over a period of time. In this dissertation, we focus on continuous query processing on a relation data stream and on similar sequence matching continuous query processing.
In the first part of this dissertation, we propose a method that efficiently processes Select-Project-Join(SPJ) continuous queries. Recent data stream systems such as TelegraphCQ have employed the well-known property of duality between data and queries. In these systems, query processing methods are classified into two dual categories, which we call data-initiative and query-initiative, depending on whether query processing is initiated by selecting a data element or by selecting a query. Although the duality property has been widely recognized, previous data stream systems do not fully take advantages of this property since they use the two dual methods independently: data-initiative methods for continuous queries and query-initiative also for one-time queries. We contend that continuous query processing can be better optimized by adopting an approach that integrates the two dual methods. Our primary contribution is based on the observation that spatial join is a powerful tool for achieving this objective. In this dissertation, we first present a new viewpoint of transforming the SPJ continuous query processing problem to a multi-dimensional spatial join problem. We then present a continuous query processing algorithm based on spatial join, which we name Spatial Join CQ. This algorithm processes SPJ continuous queries by finding the pairs of overlapping regions from a set of data elements and a set of queries, both defined as regions in the multi-dimensional space. The algorithm achieves the advantages of the two dual methods simultaneously. We analyze the cost of the algorithm and identify useful properties affecting the performance. We then experimentally show the correctness of the properties. Experimental results also show that the proposed algorithm outperforms earlier algorithms by up to 36 times for simple selection continuous queries and by up to 7 times for sliding window join queries.
In the second part of this dissertation, we propose a new similar sequence matching method that efficiently supports variable-length and variable-tolerance continuous query sequences on time-series data streams. Earlier methods do not support variable lengths or variable tolerances adequately for continuous query sequences if the number of query sequences registered becomes too large to handle in main memory. To support variable-length query sequences, we use the window construction mechanism that divides long sequences into smaller windows for indexing and searching the sequences. To support variable-tolerance query sequences, we present a new notion of intervaled sequences whose individual entries are an interval of real numbers rather than a real number itself. We also propose a new similar sequence matching method based on these notions, and then, formally prove correctness of the method. In the view point of using tolerances, our method is dual to the method in the time-series database. The former uses a tolerance as the range of a region query and the latter as that of an indexed region object. Thus, our method can efficiently support variable-tolerance query sequences by indexing and searching query sequences together with tolerances. In addition, we show that our method has the prematching characteristic, which finds future candidates of similar sequences in advance. Experimental results show that our method outperforms the naive one by up to 127 times and the one proposed by Gao et al. by up to 27 times.
We summarize the contributions of this dissertation as follows. First, by using duality of data and queries, we have proposed a continuous query processing method based on spatial join. This method efficiently handles a large number of SPJ continuous queries on fast data streams. Second, we have proposed a similar sequence matching method that efficiently supports a large number of variable-length and variable-tolerance continuous query sequences. Finally, we have shown, through experiments, that the proposed methods significantly improve the performance compared with those presented in the literature.
최근 들어, 네트웍과 디바이스가 발전하고 유비퀴터스 환경이 일반화됨에 따라 데이터스트림 형태의 데이터를 다루는 연구가 활발히 진행중이다. 데이터스트림에서의 질의는 데이터를 모두 저장해 놓은 상태에서 수행하는 일회성 질의(one-time query) 형태가 아니라 질의를 미리 등록해 놓고 새로 입력된 데이터에 대해서 즉시 혹은 주기적으로 질의를 수행하여 결과를 돌려주는 연속질의{continuous query)의 형태를 가진다. 본 학위논문에서는 기존의 데이터스트림 시스템들에서 주로 다루고 있는 Select-Project-Join(SPJ) 연속질의와 최근 각광받기 시작한 유사 시퀀스 매칭 연속질의에 초점을 두고 연구를 수행한다.
본 학위논문의 첫번째 파트에서는 SPJ 연속질의를 효율적으로 처리하는 방법을 다룬다. TelegraphCQ와 같은 최근의 데이터스트림 시스템들에서는 이미 잘 알려진 데이터와 질의의 이원성 개념을 사용한다. 이러한 시스템들에서는 서로 이원적인 두 가지 질의 처리 방법을 사용하였는데, 우리는 이를 데이터 엘리먼트와 질의 중에서 어느 것을 먼저 선택하고 수행을 시작하느냐에 따라서 데이터-이니셔티브(data-initiative)와 질의-이니셔티브(query-initiative)라 부른다. 이러한 이원성은 이미 널리 알려져 있었지만 기존의 데이터스트림 시스템에서는 이러한 이원적인 두 가지 방법을 각각 사용함으로써 즉, 데이터-이니셔티브 방법은 연속질의 처리에만 그리고 질의-이니셔티브 방법은 일회성 질의 처리에만 사용함으로써 이 성질의 이점을 충분히 살리지 못했다. 본 학위논문에서는 이러한 이원적인 두 가지를 통합하는 방법을 채택함으로써 연속질의 처리를 보다 최적화 할 수 있다는 것에 착안한다. 본 논문의 주요한 공헌은 공간조인이 이러한 목표를 달성할 수 있는 유용한 툴이라는 관찰에 기반한다. 본 논문에서는 먼저 SPJ 연속질의 처리 문제를 다차원 공간에서의 공간조인 문제로 변환하는 새로운 관점을 제시한다. 그리고, 공간조인 기반 연속질의 처리 알고리즘인 Spatial Join CQ를 제안한다. Spatial Join CQ는 다차원 공간상에 영역으로 표현된 데이터 엘리먼트들의 집합과 질의들의 집합으로부터 서로 겹치는 쌍을 찾음으로써 연속질의를 처리한다. 제안하는 알고리즘은 대칭적인(symmetric) 연산인 공간조인을 사용하여 겹치는 영역들을 찾아냄으로써 서로 이원적인 두 가지 질의 처리 방법의 효과를 동시에 얻는다. 성능평가 결과, 제시하는 알고리즘은 기존의 방법에 비해서 단순 선택 연속질의는 최대 36배, 슬라이딩 윈도우 조인 연속질의는 최대 7배의 성능 향상을 보였다.
본 학위논문의 두 번째 파트에서는 유사 시퀀스 매칭 연속질의를 효율적으로 처리하는 방법을 다룬다. 즉, 데이터스트림에서 가변 길이 연속질의 시퀀스와 가변 허용치를 지원하는 새로운 유사 시퀀스 매칭 연속질의 처리 방법을 제안한다. 기존 연구에서는 대량의 연속질의 시퀀스가 등록되어서 메인메모리에서 모두 관리할 수 없는 환경에서는 가변 길이 시퀀스 및 가변 허용치를 제대로 지원하지 못하였다. 본 논문에서는 가변 길이 질의 시퀀스를 지원하기 위하여 긴 시퀀스를 여러 개의 작은 윈도우로 나누어 색인하고 검색하는 윈도우 구성법(window construction mechanism)을 사용한다. 그리고, 가변 허용치 질의 시퀀스를 지원하기 위하여 실수 구간을 엔트리로 하는 새로운 개념의 시퀀스인 구간화된 시퀀스intervaled sequence) 개념을 제안한다. 또한, 구간화된 시퀀스와 윈도우 구성법을 기반으로 새로운 유사 시퀀스 매칭 방법을 제안하고, 이 방법이 유사 시퀀스 매칭을 정확하게 수행할 수 있음을 증명한다. 이러한 방법은 허용치를 사용하는 관점에 있어서 기존의 시계열 데이터베이스에서의 유사 시퀀스 매칭 방법과 이원적인 관계에 있다. 즉, 전자는 영역질의의 범위로 허용치를 사용하였던 반면 후자는 색인하는 영역 객체의 범위로 허용치를 사용한다. 이 방법은 질의 시퀀스와 허용치를 함께 색인하고 검색할 수 있도록 함으로써 가변 허용치 질의 시퀀스를 효율적으로 지원한다. 다음으로, 제안한 방법이 미래 시점의 후보 시퀀스를 미리 판별하는 선매칭(prematching) 성질을 가짐을 보인다. 실험 결과, 제안한 방법은 단순 접근법에 비해 최대 127배, 기존 연구에 비해 최대 27배 성능을 향상시킨 것으로 나타났다.
요약하면, 본 학위논문에서는 먼저 데이터와 질의의 이원성을 사용하여 다차원 공간조인으로 연속질의를 처리함으로써 빠른 속도로 입력되는 데이터스트림에 대해서 대량의 SPJ 연속질의를 효율적으로 수행할 수 있는 방법을 제안하였다. 다음으로, 기존 데이터베이스에서의 유사 시퀀스 매칭 방법과 이원적인 방법을 사용함으로써 가변 길이 연속질의 시퀀스와 가변 허용치를 효율적으로 지원하는 유사 시퀀스 매칭 연속질의 처리 방법을 제안하였다. 마지막으로, 실험을 통하여 기존의 방법에 비해서 성능을 크게 향상시키는 것을 보임으로써 제안하는 방법의 우수성을 입증하였다.
