서지주요정보
Adaptive eager-lazy hybrid evaluation of event patterns for low latency = 빠른 지연 시간을 위한 이벤트 패턴의 적응형 Eager-Lazy 하이브리드 평가
서명 / 저자 Adaptive eager-lazy hybrid evaluation of event patterns for low latency = 빠른 지연 시간을 위한 이벤트 패턴의 적응형 Eager-Lazy 하이브리드 평가 / Ilyeop Yi.
저자명 Yi, Ilyeop ; 이일엽
발행사항 [대전 : 한국과학기술원, 2016].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8029880

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 16029

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

Event pattern detection refers to identifying combinations of events matched to a user-specified query event pattern from a real-time event stream. Major applications of event pattern detection include fraud detection, anomaly detection, outlier detection, and intrusion detection. Latency, which is defined as the time elapsed between the arrival of the last event of an event combination matched to a query event pattern and the point at which the system identifies the event combination matched, is an important measure of the performance of an event pattern detection system. Existing methods can be classified into the eager evaluation method and the lazy evaluation method depending on when each event arrival is evaluated. These methods have advantages and disadvantages in terms of latency depending on the event arrival rate. The eager evaluation method evaluates all events immediately when they arrive while the lazy evaluation method defers evaluations of arriving events and later evaluates them in batch. The latency of the eager evaluation method is lower when the event arrival rate is slow while that of the lazy evaluation method, where optimization techniques can be used for batch processing, is lower when the event arrival rate is fast. In this paper, we propose a hybrid eager-lazy evaluation method that combines the advantages of both methods. For each event type, the hybrid method, which we call APAM (Adaptive Partitioning-And-Merging), determines which method to use: eager or lazy. It improves latency by using the eager evaluation method for more event types when the event arrival rate is slower and by using the lazy evaluation method for more event types when the event arrival rate is faster. That is, event types are partitioned into an eager evaluation group and a lazy evaluation group. We also propose a formal cost model to estimate the latency and propose a method of finding the optimal partition based on the cost model. Finally, we show through experiments that our method can improve the latency by up to 361.48 times over the eager evaluation method and 27.94 times over the lazy evaluation method using a synthetic and real-world data set.

이벤트 패턴 탐지는 시스템에 도착하는 이벤트 스트림으로부터 사용자가 명시한 질의 이벤트 패턴에 매치되는 이벤트들의 조합들을 찾는 문제이며, 주요한 응용으로는 사기 탐지, 이상 탐지, 예외 탐지, 침입 탐지 등이 있다. 지연 시간 (질의 이벤트 패턴에 매치되는 한 이벤트 조합의 마지막 이벤트가 도착한 이후부터 시스템이 이 이벤트 조합이 매치됨을 탐지하기까지 걸린 시간) 은 이벤트 패턴 탐지 시스템의 성능을 나타내는 중요한 척도이다. 기존 방법들은 도착한 이벤트를 처리하는 시점에 따라 이거 평가 방법 및 레이지 평가 방법으로 분류할 수 있다. 이들 방법들은 이벤트 도착 속도에 따라 지연 시간 측면에서 장/단점이 존재한다. 이거 평가 방법은 도착한 이벤트를 즉시 처리하는 방법이고, 레이지 평가 방법은 도착한 이벤트들의 처리를 연기한 후 일괄 처리하는 방법이다. 이벤트 도착 속도가 비교적 느린 경우에는 이거 평가 방법의 지연 시간이 더 빠른 반면, 이벤트 도착 속도가 빨라질 경우에는 이벤트들을 일괄 처리함에 따라 최적화 기법을 활용할 수 있는 레이지 평가 방법의 지연 시간이 더 빠르다. 본 논문에서는 기존 두 방법들의 장점을 활용하는 하이브리드 이거-레이지 평가 방법을 제안한다. 제안하는 하이브리드 방법 (이하, APAM) 에서는 이벤트 타입에 따라 그 타입의 이벤트들을 처리하기 위해 사용할 방법을 결정한다: 이거 또는 레이지. 따라서, 이벤트 도착 속도가 느려지는 경우에는 더 많은 수의 이벤트 타입들에 대해 이거 평가 방법을 사용하고, 이벤트 도착 속도가 빨라지는 경우에는 더 많은 수의 이벤트 타입들에 대해 레이지 평가 방법을 사용함으로써 지연 시간을 향상시킬 수 있다. 즉, 이벤트 타입들은 두 그룹 (이거 평가 그룹 및 레이지 평가 그룹) 으로 분할된다. 또한, 지연 시간을 추정하기 위한 포멀한 비용 모델을 정의하고, 이를 기반으로 최적 분할을 찾는 방법을 제안한다. 마지막으로, 합성 및 실제 데이터 집합을 사용한 실험을 통해 제안하는 방법이 이거 평가 방법보다 최대 361.48배, 레이지 평가 방법보다 최대 27.94배 지연 시간을 향상시킬 수 있음을 보인다.

서지기타정보

서지기타정보
청구기호 {DCS 16029
형태사항 iv, 43 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 이일엽
지도교수의 영문표기 : Kyu-Young Whang
지도교수의 한글표기 : 황규영
공동지도교수의 영문표기 : Jae-Gil Lee
공동지도교수의 한글표기 : 이재길
학위논문 학위논문(박사) - 한국과학기술원 : 전산학부,
서지주기 References : p. 36-38
주제 Complex event processing
Event pattern detection
Latency
Optimization
Hybrid
컴플렉스 이벤트 처리
이벤트 패턴 탐지
지연 시간
최적화
하이브리드
QR CODE qr code