There are growing researches for processing of continuous queries over a set of data streams from multiple data sources. These are indispensable to ubiquitous streaming applications, such as IP or sensor network monitoring, moving objects trajectory, and many others. These stream applications require real-time, or near real-time response for very high arrival rates. But, system resources may not be available for the run-time state required by numerous queries.
In the first part of this dissertation, we propose a newly improved and practical algorithm for multiple windowed join called AMJoin, which improves the multiple join performance by guaranteeing the detection of join failures in constant time. To achieve this goal, we first design a new data structure called BiHT (Bit-vector Hash Table) and present the overall behavior of AMJoin in detail. In addition, we show various experimental results and their analyses for clarifying its efficiency and practicability.
In the next part of this dissertation, we address the problem of load shedding for continuous multi-way join queries over multiple data streams. When the arrival rates of tuples from data streams exceed the system capacity, a load shedding algorithm drops some subset of input tuples to avoid system overloads. To decide which tuples to drop among the input tuples, most existing load shedding algorithms determine the priority of each input tuple based on the frequency or some historical statistics of its join attribute value, and then drop tuples with the lowest priority.However, those v$\It{value-based }$ algorithms cannot determine the priority of tuples properly in environments where join attribute values are unique and each join attribute value occurs at most once in each data stream. In this dissertation, we propose an load shedding algorithm based on $\It{arrival order patterns}$ for multi-way stream joins in such environments. The proposed load shedding algorithm determines the priority of each tuple based on $\emph{the order of streams}$ in which its join attribute value appears in a given time interval, rather than its join attribute value itself. Consequently, the priority of tuples can be determined effectively even in environments where join attribute values are unique and do not repeat. The experimental results show that the proposed algorithm outperforms the existing algorithms in terms of effectiveness and efficiency.
최근 다중 데이터 소스들로부터 발생되는 데이터 스트림을 지속적인 질의를 통해 처리하는 연구가 활발하게 진행되고 있다. 이들 연구는 유비쿼터스 스트림 응용들에 필수적인 것들로, 인터넷이나 센서 네트워크 혹은 이동 물체 궤적 탐지 등 다양한 분야를 그 예로 들 수 있다. 이러한 스트림 응용체계들은 실시간 혹은 거의 실시간 응답을 요구하며, 매우 큰 입력 데이터를 처리해야 하는 문제를 가지고 있다. 이에 반해, 이들이 요구하는 실행 시 필수 자원 (중앙처리장치, 메모리 등)은 여러 응용들에서 한계를 가지고 있다.
본 논문의 첫 번째 부분에서, 우리는 다중 윈도우 조인 질의를 처리하기 위해 새롭게 향상된 실용적인 알고리즘 (이하 AMJoin)을 제안한다. AMJoin은 상수 시간에 조인 실패의 탐지를 보장함으로써 다중 윈도우 조인의 성능을 향상시킨다. 이 목표를 위해, 우리는 최초로 BiHT (Bit-vector Hash Table)라 불리 우는 데이터 구조를 설계하고, 이를 이용하는 AMJoin 알고리즘을 제시한다. 또한, 우리는 다양한 실험 결과와 분석을 통해 제시된 알고리즘의 효율성과 실용성을 보인다.
본 논문의 두 번째 부분에서, 우리는 데이터의 입력이 체계의 한계 성능을 넘을 경우, 이를 처리하기 위한 새로운 로드세딩 기법을 제시한다. 메모리 오버플로우 상황에서, 체계는 입력 데이터 전체를 처리할 수 없다. 이를 위해 기존의 연구들에서는 입력 튜플의 조인키 값의 출현 빈도나 통계적 누적 값을 이용하여 개략적인 조인 결과를 생성한다. (다시 말해, 현재까지 조인 윈도우에 보관된 조인키 값들의 조인 가능성을 이용하여, 조인 가능성이 낮은 조인키 값을 가진 튜플은 메모리에서 제거함). 하지만, 각 스트림 내에서 키 값이 유일하거나 반복이 없는 경우, 조인키 값은 그들의 스트림에서 한 번 이상 나타나기 어렵다. 따라서, 이러한 응용들에서 기존 로드세딩 기법들은 튜플의 우선순위를 적절하게 결정할 수 없다. 이런 문제점을 개선하기 위해, 우리는 도착순서 기반 로드세딩 알고리즘을 제안한다. 제안된 알고리즘은 튜플의 조인키 값이 아닌, 그 값이 스트림에 나타나는 순서를 로드세딩에 사용한다. 즉, 조인 결과의 정확성을 높이기 위해, 조인 가능성이 낮은 도착순서를 가진 튜플들을 메모리에서 제거한다. 우리는 다양한 실험과 분석으로 통해 새롭게 제안된 기법이 키 값을 고려하는 기존 기법들에 비해 더욱 효과적으로 로드세딩을 수행함을 보인다.
