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배 지연 시간을 향상시킬 수 있음을 보인다.
