다중 윈도우 조인을 위한 튜플의 도착 순서에 기반한 효과적인 부하 감소 기법 Effective Load Shedding for Multi-Way windowed Joins Based on the Arrival Order of Tuples on Data Streams원문보기
최근 다중 데이터 스트림에 대한 연속 질의 처리에 관한 연구가 활발하게 진행되고 있다. 데이터 스트림에서 튜플들의 도착 속도가 폭증하여 시스템의 메모리 용량을 초과하는 경우, 일부 튜플을 버림으로써 시스템이 과부하 상태가 되지 않도록 하는 기법을 부하 감소(load shedding)라 한다. 본 논문에서는 다중 데이터 스트림에 대한 다중 윈도우 조인을 위한 효과적인 부하 감소 기법을 제안한다. 기존의 부하 감소 기법들은 버릴 튜플을 선택하기 위해 튜플들의 조인 키 값을 이용하여 각 튜플이 생성할 조인 결자 개수(생산성)를 예측하고, 생산성이 최소가 되는 튜플을 버린다. 그러나 이러한 방법들은 조인 키 값이 다시 나타나지 않거나, 조인 키 값의 분포가 일정하게 유지되지 않는 경우 튜플들의 생산성을 올바르게 예측하기 어렵다. 본 논문은 이러한 경우를 위해 튜플들의 조인 키 값 대신, 튜플의 데이터 스트림에 대한 도착 순서를 사용하여 튜플들의 생산성을 예측하는 방법을 사용한다. 제안하는 방법은 조인 키 값으로 튜플들의 생산성을 예측하가 어려운 상황에서 튜플의 도착 순서를 통해 각 튜플의 생산성을 효과적으로 예측할 수 있도록 해준다. 다양한 실험과 분석을 통해 제안하는 새로운 부하 감소 기법이 기존 기법에 비해 더욱 효과적이고 효율적으로 부하를 감소시킬 수 있음을 보인다.
최근 다중 데이터 스트림에 대한 연속 질의 처리에 관한 연구가 활발하게 진행되고 있다. 데이터 스트림에서 튜플들의 도착 속도가 폭증하여 시스템의 메모리 용량을 초과하는 경우, 일부 튜플을 버림으로써 시스템이 과부하 상태가 되지 않도록 하는 기법을 부하 감소(load shedding)라 한다. 본 논문에서는 다중 데이터 스트림에 대한 다중 윈도우 조인을 위한 효과적인 부하 감소 기법을 제안한다. 기존의 부하 감소 기법들은 버릴 튜플을 선택하기 위해 튜플들의 조인 키 값을 이용하여 각 튜플이 생성할 조인 결자 개수(생산성)를 예측하고, 생산성이 최소가 되는 튜플을 버린다. 그러나 이러한 방법들은 조인 키 값이 다시 나타나지 않거나, 조인 키 값의 분포가 일정하게 유지되지 않는 경우 튜플들의 생산성을 올바르게 예측하기 어렵다. 본 논문은 이러한 경우를 위해 튜플들의 조인 키 값 대신, 튜플의 데이터 스트림에 대한 도착 순서를 사용하여 튜플들의 생산성을 예측하는 방법을 사용한다. 제안하는 방법은 조인 키 값으로 튜플들의 생산성을 예측하가 어려운 상황에서 튜플의 도착 순서를 통해 각 튜플의 생산성을 효과적으로 예측할 수 있도록 해준다. 다양한 실험과 분석을 통해 제안하는 새로운 부하 감소 기법이 기존 기법에 비해 더욱 효과적이고 효율적으로 부하를 감소시킬 수 있음을 보인다.
Recently, there has been a growing interest in the processing of continuous queries over multiple data streams. When the arrival rates of tuples exceed the memory capacity of the system, a load shedding technique is used to avoid the system becoming overloaded by dropping some subset of input tuples...
Recently, there has been a growing interest in the processing of continuous queries over multiple data streams. When the arrival rates of tuples exceed the memory capacity of the system, a load shedding technique is used to avoid the system becoming overloaded by dropping some subset of input tuples. In this paper, we propose an effective load shedding algorithm for multi-way windowed joins over multiple data streams. Most previous load shedding algorithms estimate the productivity of each tuple, i.e., the number of join output tuples produced by the tuple, based on its "join attribute value" and drop tuples with the lowest productivity. However, the productivity of a tuple cannot be accurately estimated from its join attribute value when the join attribute values are unique and do not repeat, or the distribution of the join attribute values changes over time. For these cases, we estimate the productivity of a tuple based on its "arrival order" on data streams, rather than its join attribute value. The proposed method can effectively estimate the productivity of a tuple even when the productivity of a tuple cannot be accurately estimated from its join attribute value. Through extensive experiments and analysis, we show that our proposed method outperforms the previous methods in terms of effectiveness and efficiency.
Recently, there has been a growing interest in the processing of continuous queries over multiple data streams. When the arrival rates of tuples exceed the memory capacity of the system, a load shedding technique is used to avoid the system becoming overloaded by dropping some subset of input tuples. In this paper, we propose an effective load shedding algorithm for multi-way windowed joins over multiple data streams. Most previous load shedding algorithms estimate the productivity of each tuple, i.e., the number of join output tuples produced by the tuple, based on its "join attribute value" and drop tuples with the lowest productivity. However, the productivity of a tuple cannot be accurately estimated from its join attribute value when the join attribute values are unique and do not repeat, or the distribution of the join attribute values changes over time. For these cases, we estimate the productivity of a tuple based on its "arrival order" on data streams, rather than its join attribute value. The proposed method can effectively estimate the productivity of a tuple even when the productivity of a tuple cannot be accurately estimated from its join attribute value. Through extensive experiments and analysis, we show that our proposed method outperforms the previous methods in terms of effectiveness and efficiency.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서 우리는 다중 윈도우 조인 질의를 위한 효과적인 부하감소 알고리즘을 제안한다. 스트림의 윈도우에 할당된 메모리가 가득 찼을 때, 이 스트림에 새로운튜플이 도착된다면(윈도우 시간 경과로 인한 자연 도태튜플이 없는 경우), 우리는 신규 튜플을 저장하기 위해새로운 메모리가 필요하다.
본 논문에서 우리는 다중 윈도우 조인에서 도착순서 패턴을 가진 경우에 효과적으로 부하감소를 수행할 수 있는 새로운 알고리즘을 제안했다. 제안하는 알고리즘은 실세계 응용들에서 자연발생적으로 생기는 튜플들의 도착순서의 패턴을 이용하여 부하감소를 수행한다.
본 논문에서 우리는 튜플이 스트림의 윈도우에 최초로 도착하는 순서에 기준을 두는 새로운 부하감소 알고리즘을 제안한다. 조인 질의에서 데이터 스트림의 개수가 n이라고 하자.
[9]은 메모리 부하감소를 위해 출현빈도를 기준으로 하는 부하감소 기법을 제안했다. 이 논문에서는 튜플 £의생산성은 현재 조인 윈도우들에서 자신의 윈도우를 제외한 나머지 것들에서 I의 조인키 값과 동일한 튜플들의곱으로 표현된다. 또한, 속도 향상을 위해 전체 스트림은 스캔하지 않고 한계 에러 범위 내에서 스케치 기법을 사용한다[6].
3개의 네트워크 라우터가 있다고 하자. 이 중 라우터 Ri, R2, 晶를 지나는 패스의 패킷 사용량을 모니터링 한다고 하자. 각 라우터는 튜플을 발생시키고, 각 튜플은 라우터를 통과하는 패킷의 정보를 가지고 있다.
가설 설정
(2) 결과 기준 알고리즘: 입력 튜플에 대해 그 튜플이 과거에 생성했던 결과 튜플의 개수를 누적하여 우선순위를 표현. (3) 무작위 기준 알고리즘: 입력 튜플을 제외한 나머지튜플들에서 무작위로 부하감소를 수행함. 또한, 세 개의알고리즘은 3장에서 설명한 AMJoin의 프레임워크를 적용하며, 부하감소의 우선순위를 결정하는 부분만 다르게적용한다.
…X 또한, 吼를 의 윈도우라고 한다. 각 I仍 는 $에 나타나는 튜플들을 저장하고 있으며, 튜플의 개수 혹은 발생시간에 따라 제약조건예를 들어 튜플 100 개 혹은 1시간)을 가지고 있으며, 편의상 지정된 크기의 메모리 공간이 할당된다고 가정한다. 그림 1은 논문에서 사용되는 조인 처리 모델을 보여준다.
각 라우터는 튜플을 발생시키고, 각 튜플은 라우터를 통과하는 패킷의 정보를 가지고 있다. 각 패킷 정보는 패킷 아이디(여기서는 알파벳)로 유일하게 식별된다고 가정한다. 우리는 해당 패스를 지나는 패킷 사용량을 모니터링하기 위해 3-way 조인을 수행한다.
대해서 기술한다. 기본적으로, 우리가 제안하는 방법과 2장 관련연구에서 언급한 기존 방법들은 모두 해시기반 조인을 사용한다고 가정한다. 이경우 부하감소를 위해 가장 많은 비용이 소요되는 부분은 우선순위를 결정하고 유지하는 부분이다.
BiHT와 EPTi (IMMn)는 조인 윈도우 呼i(lMiMn)와 함께 메모리에서 유지된다. 설명의 편의를 위해 모든 조인 키들이 동일하다고 가정하며, 한 개의 해시함수 九를 사용한다고 가정한다. 데이터 스트림 S에서 튜플 가 도착하면, 다음의 조인과정이 연속적으로 실행된다.
제안 방법
이런 관점에서 우리는 MJoin을 개선한 AMJoin[12]을 제안했다. AMJoine BiHT(Bit-vector Hash Table)을 이용하여 입력 튜플의 조인 성공 유무를 상수 시간에 판별함으로써 이들 알고리즘을 발전시켰다.
있는 존재패턴테이블에 대한 예제이다. EPTie Si 에서 발생 가능한 모든 존재패턴(100, 101, 110, 111)을가지고 있으며, 각각의 존재패턴으로 도착한 튜플의 리스트와 그들의 생산성을 실시간으로 수정한다. 그림 4에서 보듯이 EP幻의 튜플 切는 ep로 101'을 가지며 윈도우에 삽입될 당시 윈도우 04에 해당 튜플과 같은 조인키 값을 가지는 튜플이 존재했다는 것을 알 수 있습니다.
그림 6 의 실험에서는 각 스트림에서 유일한 조인키 값(1에서 20, 000)으로 튜플 20, 000개를 생성하고, 각 윈도우에서이중 75%(15,000개)만을 저장할 수 있도록 메모리를 할당하였다. 각 스트림에서 무작위 순으로 튜플이 도착할 때를 'no pattern'으로 실험하고, 도착순서에 시간적인 연관성을 부여했을 때를 'pattern'으로 실험하였다. 여기서, 시간적인 연관성은 스트림이 S1, &, S3, &, S5 순으로 도착하였을 경우, 그렇지 않은 경우보다 높은 조인 성공률을 가지도록 설정한다는 의미이다.
(3) 무작위 기준 알고리즘: 입력 튜플을 제외한 나머지튜플들에서 무작위로 부하감소를 수행함. 또한, 세 개의알고리즘은 3장에서 설명한 AMJoin의 프레임워크를 적용하며, 부하감소의 우선순위를 결정하는 부분만 다르게적용한다. 공통적인 프레임을 적용하는 구체적인 이유는이장에 마지막에 기술하도록 하겠다.
먼저, 우리는 실험을 위해 데이터 생성모듈을 구현했다. 이 모듈은 입력 스트림의 개수, 각 스트림당 튜플의개수, 조인키 값의 범위와 분포 등 다양한 입력 파라메터를 기준으로 가상 데이터를 생성한다.
앞서 기술한 3가지 알고리즘과 우리가 제안한 알고리즘 (EP) 에 대해, 조인키 값이 유일한 경우 (uniform distribution) 에 대해 5-웨이 조인을 수행하였다. 그림 6 의 실험에서는 각 스트림에서 유일한 조인키 값(1에서 20, 000)으로 튜플 20, 000개를 생성하고, 각 윈도우에서이중 75%(15,000개)만을 저장할 수 있도록 메모리를 할당하였다.
즉, 1亿에서는 존재패턴 과 '111'을 가진 튜플이가장 생산성이 높고, 呀에서는 존재패턴과을가진 튜플이 가장 생산성이 높고, 같은 방식으로 W?에서는 존재패턴 '110'과 '011'이 높다. 여기서, R이나 R3 로부터 새로운 튜플이 도착한다면 제안하는 알고리즘은튜플 d를 제거하며, Rz로부터 새로운 튜플이 도착한다면 튜플 c를 제거한다. 하지만, 기존 알고리즘들은 이러한 상황에서 부하감소를 위한 적절한 기준을 제시하기어렵다.
우리가 제안하는 부하감소 알고리즘은 다음 몇 가지관찰을 통해 튜플의 우선순위를 결정하는 새로운 기준을 제시한다. 많은 응용들어}서, 여러 개의 데이터 스트림에 공통적으로 발견되는 객체나 사건들은 그들이 데이터 스트림에서 최초로 나타날 때, 어떤 반복적인 패턴을 보인다.
BiHT를 이용할 경우 발생되는 추가적인 공간 오버헤드는 조인키 값의 범위에 영향을 받으며, 엔트리당 해시주소를 위한 4byte와 비트 벡터를 위한 2byte로 총 6byte가 필요하다. 이에 반하여 제안하는 알고리즘은 BiHT를 필수로 하며 EPT 를 유지하기 위한 메모리 공간과, 각 튜플의 존재 패턴 기록을 위해 주가적인 메모리가 필요하다(예를 들어 5 장의 실험에서 우리는 2bytes의 필드를 각 튜플의 레코드에 추가했다). 공간 복잡도의 경우는 튜플의 개수 와해 시 테이블의 엔트리의 개수에 영향을 받기 때문에 실제 응용 환경에 따라 차이가 있을 수 있다.
이장에서 우리는 제안한 알고리즘의 효과성(정확성과속도)을 입증하기 위해, 존재하는 다양한 알고리즘들과비교를 수행한다. 비교 대상이 되는 알고리즘들은 다음과 같다.
새로운 알고리즘을 제안했다. 제안하는 알고리즘은 실세계 응용들에서 자연발생적으로 생기는 튜플들의 도착순서의 패턴을 이용하여 부하감소를 수행한다. 이는 조인키 값의 분포에 근거하여 튜플의 조인 가능성을 판별하는 기존 알고리즘들이 가지는 한계점을 해결하는데 효과적이다.
제안하는 알고리즘은 입력(1)에서 윈도우 의 메모리가 가득 찼을 경우, 정의 1, 2, 3에 의해서 所에서 가장 생산성이 낮은 존재패턴을 가진 튜플 중에서 가장 오래된 튜플을 제거한다. 그림 5는 3-웨이 조인에서 제안한 부하감소 알고리즘의 실행예제를 보여준다.
번째 비트는 튜플 I와 같은 조인키값을 가지는 튜플이 현재 i번째 스트림의 조인 윈도우에존재하는지를 표현한다. 즉, 각각의 데이터 스트림의 윈도우에 대해, 우리는 같은 존재패턴을 가지는 튜플들을 유지하는 동시에 각 존재패턴의 평균 생산성을 계산한다. 다음으로, 부하감소 상황에서 가장 낮은 생산성을 가지는 존재패턴에 속한 튜플을 제거한다.
먼저, 모든 실험에서 BiHT의 크기는 120Kbyte(6Bytes(엔트리당 해시주소 4bytes와 비트벡터 2bytes)*20, 000(엔트리 개수))로 비교적 작은 공간을 차지하기 때문에 이를 사용하는데 대한 영향이 적다. 출현빈도와 결과 기반 알고리즘은 부하감소를 위해 8Mbytes (8bytes(해시주소 4bytes와 생산성 값 4bytes)*5(스트림개수 )*200, 000(엔트리 개수))를 필요로 하고, 제안하는 알고리즘은 존재패턴테이블을 위해 약 400Kbytes (4bytes(튜플의 리스트를 유지하기 위한 포인터)*100, 000 (전체 튜플의 개수))와 튜플의 존재패턴 기록을 위해 200細3*聽日3业$(존재패턴)*100, 000(전체 튜플의 개수)) 를 합해서 600Kbytes가 필요하다. 여기서, 제안하는 알고리즘이 작은 메모리를 요구하는 이유는 우선순위 큐가 상대적으로 작기 때문이다.
대상 데이터
예제이다. 우리는 이 예제를 만들기 위해 특정 시점에 네 개의 뉴스 사이트를 검색하여 각 사이트에서 다루어지고 있는 메인 뉴스 7개를 발생순서대로 수집하였다. 그림 2에서 각 뉴스들은 키워드로 대표되며, 각각이고유한 생성시간을 가진다.
데이터처리
여기서, 시간적인 연관성은 스트림이 S1, &, S3, &, S5 순으로 도착하였을 경우, 그렇지 않은 경우보다 높은 조인 성공률을 가지도록 설정한다는 의미이다. 또, 그림 7의 실험은 이전 실험의 'pattern' 상황에서 각 윈도우에 할당되는 메모리 공간을 다르게 설정하여 출력되는 결과의 정확성을 비교하였다. 두 가지 실험의 결과에서 보듯이 유일한 조인키 값을 가지는 상황에서 출현빈도와 결과 기준 알고리즘은 무작위로 부하감소를 수행하는 알고리즘과 유사한 정확도를 보이지만, 제안하는 알고리즘 (EP)는 최고 30%의 높은 정확도를 달성할 수 있다.
이론/모형
여러 실험들에서 모든 알고리즘은 수행속도의 개선을 위해 AMJoin의 프레임 워크를 이용하였다. 제안하는 알고리즘을 제외한 나머지 알고리즘은 필수적으로 BiHT 를 사용할 필요가 없다.
우리가 제안하는 부하감소 알고리즘은 해시조인(Hash Join)을 사용하는 AMJoin[12]의 프레임워크(Framework) 를 사용한다. BiHT와 EPTi (IMMn)는 조인 윈도우 呼i(lMiMn)와 함께 메모리에서 유지된다.
성능/효과
창출할 수 있다. (1) 제안하는 알고리즘은 조인키 값의 반복이 거의 없고, 그들이 시간에 따라 다른 분포를나타내는 응용환경에서, 튜플의 조인 생산성을 효과적으로 예측할 수 있다. (2) 제안하는 알고리즘은 키 값의 분포를 고려하는 기존의 알고리즘들 보다 빠르게 부하감소를 수행 할 수 있다.
(1) 제안하는 알고리즘은 조인키 값의 반복이 거의 없고, 그들이 시간에 따라 다른 분포를나타내는 응용환경에서, 튜플의 조인 생산성을 효과적으로 예측할 수 있다. (2) 제안하는 알고리즘은 키 값의 분포를 고려하는 기존의 알고리즘들 보다 빠르게 부하감소를 수행 할 수 있다. 본론에서 다루겠지만, 제안된 알고리즘은 튜플의 우선순위를 유지하기 위해, 조인키 값의범주보다 크기가 작은 존재패턴에 대해 우선순위를 유지하며, 이를 통해 보다 빠르게 우선순위를 결정할 수 있다.
우리는 5개의 스트림을조인하기 위해 각 존재패턴테이블을 위해 16개의 엔트리만을 요할 뿐이다. 결과적으로 기존 알고리즘들이 BiHT를 사용하지 않더라도 AMJoin 프레임워크를 이용하는 제안하는 알고리즘은 더 작은 메모리 공간을 사용한다.
두 가지 실험의 결과에서 보듯이 유일한 조인키 값을 가지는 상황에서 출현빈도와 결과 기준 알고리즘은 무작위로 부하감소를 수행하는 알고리즘과 유사한 정확도를 보이지만, 제안하는 알고리즘 (EP)는 최고 30%의 높은 정확도를 달성할 수 있다. 다시 말해, 제안하는 알고리즘은 스트림의 도착순서가 존재하는 경우, 키 값이 유일한 경우에도 우수한 조인성능을 보임을 알 수 있다.
또한, 그림 9는 그림 8의 'pattern'상황어서 각 윈도우에할당되는 메모리 공간의 차이에 따른 결과를 보여준다. 두 가지 실험에서 제안하는 알고리즘이 우수한 성능을 보이고 있음을 알 수 있다. 여기서, 출현빈도와 결과 기준 알고리즘이 낮은 성능을 보이는 이유는 다음 두 가지에 있다.
또, 그림 7의 실험은 이전 실험의 'pattern' 상황에서 각 윈도우에 할당되는 메모리 공간을 다르게 설정하여 출력되는 결과의 정확성을 비교하였다. 두 가지 실험의 결과에서 보듯이 유일한 조인키 값을 가지는 상황에서 출현빈도와 결과 기준 알고리즘은 무작위로 부하감소를 수행하는 알고리즘과 유사한 정확도를 보이지만, 제안하는 알고리즘 (EP)는 최고 30%의 높은 정확도를 달성할 수 있다. 다시 말해, 제안하는 알고리즘은 스트림의 도착순서가 존재하는 경우, 키 값이 유일한 경우에도 우수한 조인성능을 보임을 알 수 있다.
(2) 제안하는 알고리즘은 키 값의 분포를 고려하는 기존의 알고리즘들 보다 빠르게 부하감소를 수행 할 수 있다. 본론에서 다루겠지만, 제안된 알고리즘은 튜플의 우선순위를 유지하기 위해, 조인키 값의범주보다 크기가 작은 존재패턴에 대해 우선순위를 유지하며, 이를 통해 보다 빠르게 우선순위를 결정할 수 있다. 다중 윈도우 조인은 대용량 데이터 스트림을 대상으로 하기 때문에 빠른 연산은 매우 중요한 고려 대상이다.
즉, 조인키 값이 유일하거나 반복이 없는 경우 혹은 조인키 값에 중복이 있더라도, 스트림 간에 분포가 상이한 경우에도 제안하는 알고리즘은 상대적으로 우수한 성능을 발휘한다. 우리는 다양한 실험과 분석을 통해 제안하는 알고리즘의 효과성을 검증하였다.
이는 조인키 값의 분포에 근거하여 튜플의 조인 가능성을 판별하는 기존 알고리즘들이 가지는 한계점을 해결하는데 효과적이다. 즉, 조인키 값이 유일하거나 반복이 없는 경우 혹은 조인키 값에 중복이 있더라도, 스트림 간에 분포가 상이한 경우에도 제안하는 알고리즘은 상대적으로 우수한 성능을 발휘한다. 우리는 다양한 실험과 분석을 통해 제안하는 알고리즘의 효과성을 검증하였다.
해당 실험에서 조인키 값의 범주는 20, 000개 정도로한정했기 때문에 제안하는 알고리즘과 결과 기준 알고리즘은 거의 차이가 없지만, 출현빈도 기반 알고리즘은비교적 많은 시간이 소요된다. 출현빈도 기반 알고리즘의 경우 튜플이 입력될 때마다 그 출현빈도를 지속적으로 체크하여 우선순위를 조정하기 때문에 다른 알고리즘(제안하는 알고리즘과 결과 기반은 튜플이 조인결과를생성할 때에만 우선순위를 조정함)에 비해 비교적 느리다. 이런 단점을 보완하기 위해 [9]에서는 어느 정도의에러를 감수하고 스케치 기법[6]을 사용하여 출현빈도를계산하였다.
물론, 조인결과를 생산성에 반영하기 위해 모든 EPT를수정하기 때문에 시간 복잡도는 0(*)으로 볼 수 있다. 통상적으로, 여러 응용들에서 조인에 참여하는 스트림의 개수가 많지 않기 때문에 우리가 제안하는 알고리즘의 복잡도는 기존 방법들에 비해 크지 않고, 조인키 값의 범위에 영향을 받지 않는 장점을 가진다.
해당 실험에서 조인키 값의 범주는 20, 000개 정도로한정했기 때문에 제안하는 알고리즘과 결과 기준 알고리즘은 거의 차이가 없지만, 출현빈도 기반 알고리즘은비교적 많은 시간이 소요된다. 출현빈도 기반 알고리즘의 경우 튜플이 입력될 때마다 그 출현빈도를 지속적으로 체크하여 우선순위를 조정하기 때문에 다른 알고리즘(제안하는 알고리즘과 결과 기반은 튜플이 조인결과를생성할 때에만 우선순위를 조정함)에 비해 비교적 느리다.
지속적으로 반복되게 설정하였다. 해당 실험에서는 스트림 간에 조인키 값의 분산에 차이를 두어, 스트림 순(예를 들어 S1, S3, &, & 순으로 앞쪽 스트림의 분산이 작게 설정)으로 같은 조인키 값을 가질 경우, 튜플이 앞쪽 스트림에서 최초로 나타날 경우 조인될 가능성이 높게 설정하였으며. 이러한 패턴을 반복되게 적용하였다.
참고문헌 (13)
A. Das, J. Gehrke and M. Riedewald. Approximate Join Processing over Data Streams. Proceedings of the 2003 ACM SIGMOD international conference on Management of data, San Diego, California, USA, pp.40-51, 2003.
C. Cranor, T. Johnson, O. Spataschek and V. Shkapenyuk. Gigascope: A Stream Database for Network Applications, Proceedings of the ACM SIGMOD International Conference On Management of Data, San Diego, California, USA, pp.647-651, 2003.
J. Gehrke and S. Madden. Query Processing in Sensor Networks. IEEE Pervasive computing, vol.3, no.1, pp.46-55, 2004.
L. Golab and M. T. Ozsu. Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams. Proceedings of the 29th International Conference on Very Large Data Bases, Berlin, Germany, vol.29, pp.500-511, 2003.
M. A. Hammad, W. G. Aref and A. K. Elmagarmid. Stream Window Join: Tracking Moving Objects in Sensor-Network Databases. Proceedings of 15th International Conference on Scientific and Statistical Database Management, Cambridge, Massachusetts, USA, pp.75-84, 2003.
A. Dobra, M. Garofalakis, J. Gehrke, and R. Rastogi. Processing complex aggregate queries over data streams. Proceedings of the 2002 ACM SIGMOD international conference on Management of data, Madison, Wisconsin, USA, pp.61-72, 2002.
B. Gredik, K. Wu, P. S. Yu and L. Liu. A Load Shedding Framework and Optimizations for Mway Windowed Stream Joins. IEEE 23rd International Conference on Data Engineering, pp. 536-545, 2007.
Y. Bai, H. Wang and C. Zaniolo. Load Shedding in Classifying Multi-Source Streaming Data: A Bayes Risk Approach. Proceedings of the Seventh SIAM International Conference on Data Mining, Minneapolis, Minnesota, USA, pp.425-430, 2007.
Y. Law and C. Zaniolo. Load Shedding for Window Joins on Multiple Data Streams. IEEE 23rd International Conference on Data Engineering, pp.674- 683, 2007.
U. Srivastava and J. Widom. Memory-Limited Execution of Windowed Stream Joins. Proceedings of the 30th VLDB Conference, Toronto, Canada, pp.324-335, 2004.
S. D. Viglas, J. F. Naughton and J. Burger. Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources. Proceedings of the 29th International Conference on Very Large Data Bases, Berlin, Germany, vol.29, pp.285-296, 2003.
T. Kwon, H. Kim, M. Kim and J. Son, An Advanced Join Algorithm for Multiple Data Streams Using a Bit-vector Hash Table. IEICE Transaction on Information and Systems, vol.E92-D, no.7, pp.1429-1434, 2009.
H. Yu, EP. Lim and J. Zhang. On In-network Synopsis Join Processing for Sensor Networks. Proceedings of the 7th International Conference on Mobile Data Management, Nara, Japan, pp.32- 39, 2006.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.