In this dissertation, we discuss two issues on processing window queries over continuous data streams: efficient predicate matching and disorder control. Regarding the first, window queries can be specified with filtering conditions. Given a lot of queries with filtering conditions, a predicate index can be used to help finding candidate queries efficiently whose conditions are satisfied by input events. We propose a predicate indexing method which handles equality and inequality tests separately. Our method uses a hash table for the equality test and a balanced binary search tree for the inequality test. Such a separate structure reduces a height of the search tree and the number of comparisons per tree node, as well as the cost for tree rebalancing. We compare the proposed method with the IBS-tree which is one of the popular indexing methods suitable for data stream processing. Our experimental results show that the proposed method provides better insertion and search performances than the IBS-tree.
Regarding the second, out-of-order tuples may cause inaccurate query results since conventional window operators discard those tuples. To resolve this issue, we propose a method to fix disorder of stream tuples while keeping a percentage of tuple drops within a user-specified bound. The proposed method utilizes tuples` interarrival times and their network delays for estimation, whose parameters reflect real-time stream characteristics properly. Based on two parameters, our method controls the amount of tuple drops adaptively in accordance with fluctuated stream characteristics. We compare our method with an existing method which controls disorder based on the maximum network delay seen in the stream. We show through our experiments that (i) it is hard to control the amount of tuple drops in the existing method, and (ii) the proposed method observes a user-specified drop ratio over data streams whose characteristics are dynamically changed.
본 논문에서는 연속 데이터 스트림에서 윈도우 질의를 처리하는데 필요한 효율적인 프레디킷 매칭 및 비순서 제어에 대해 논의한다. 첫째와 관련하여, 윈도우 질의는 필터 조건을 포함할 수 있다. 필터 조건을 포함한 다수의 질의가 주어졌을 경우, 프레디킷 인덱스를 이용하여 입력 이벤트를 만족하는 조건을 지닌 후보 질의를 효율적으로 찾을 수 있다. 이와 관련하여 본 논문에서는 등호와 부등호 검사를 별도로 수행하는 프레디킷 인덱싱 방법을 제안한다. 제안하는 방법은 등호 검사를 위해 해쉬 테이블을 이용하고 부등호 검사를 위해 균형 이진 검색 트리를 이용한다. 이러한 분리된 구조는 검색 트리의 높이, 트리 노드 당 비교 횟수 및 트리의 재균형을 위한 비용을 줄여준다. 본 논문에서는 데이터 스트림 처리에 적합한 기존 인덱싱 방법 중 하나인 IBS-tree와 제안한 방법을 비교하고, 실험을 통해 제안한 방법이 IBS-tree에 비해 우수한 입력 및 검색 성능을 제공함을 보인다.
다음으로 비순서 처리와 관련하여, 비순서화된 튜플은 부정확한 질의 결과를 야기할 수 있다. 이는 기존의 윈도우 연산자들이 일반적으로 비순서화된 튜플을 제거한다는 사실에 기인한다. 이러한 문제를 해결하기 위해, 본 논문에서는 튜플 제거 비율이 사용자가 정의한 한계를 넘지 않는 범위 내에서 입력 스트림을 순서화하기 위한 방법을 제안한다. 제안하는 방법은 실시간 스트림의 특성을 적절하게 반영할 수 있는 파라미터인 튜플의 도착 시간과 네트워크 지연 값을 추정에 이용한다. 이러한 파라미터를 기반으로, 제안하는 방법은 변화하는 스트림의 특성에 맞게 적응적으로 튜플의 제거량을 조절한다. 본 논문에서는 스트림에서 보여진 최대 네트워크 지연 값을 기반으로 비순서를 제어하는 기존 방법과 제안한 방법을 비교하였다. 그리고 실험을 통해, 기존 방법에서 튜플의 제거량을 제어하기 어려우며, 이에 반해 제안하는 방법은 변화하는 스트림 상에서도 사용자가 명세한 제거율을 명확히 지킨다는 점을 보인다.
