Recently, the demand for stream data processing has increased due to advancements in IoT(Internet of Things), social media, and smartphone applications. There is also a big demand for CEP(Complex Event Processing) to find user-defined patterns in multiple stream sources and act on the discovered pattern matchings. However, with the increase in the size of stream data, there is also an increase in the number and complexity of rules involved in the analysis. In order to deal with these complexities, an efficient distributed processing algorithm is necessary. In this paper, we proposed distributed RETE networks based on graph partitioning. The state-of-the art did not show efficient resource distribution and did not consider the network usage for this task. Hence, we converted the distributed RETE network problem into a graph partitioning problem. In solving the graph partitioning problem, we distributed fair resources into each computer and minimized the total network usage in this distributed processing setup. Our results indicate better performances in terms of runtimes, degree of imbalance, and total network usage using three types of real data sets.
최근 사물인터넷(Internet of Things)의 발전, 소셜 미디어 및 모바일 기기의 대중화로 인해 끊임없이 입력되는 스트림 데이터 처리에 대한 수요가 증가하고 있다. 따라서 이러한 스트림 데이터에 대해 정의된 규칙을 빠르게 탐지한 후 대응되는 행동을 수행하는 복합이벤트처리(Complex Event Processing)가 각광받고 있고 특히 입력되는 스트림데이터의 양이 증가하고 탐지해야 하는 규칙의 개수와 복잡도가 증가함에 따라 복합이벤트처리 분산화에 대한 필요성 또한 함께 대두되고 있다. 본 논문에서는 규칙기반 복합이벤트처리의 대표 방법인 RETE 네트워크를 그래프 분할 알고리즘을 이용하여 분산처리하는 방법을 제안한다. 기존의 연구에서는 다양한 계산량을 가지는 규칙들을 효율적으로 분배하지 못했고, 분산처리에 사용된 서버간의 네트워크 전송량 또한 고려하지 못했다. 그러므로 이러한 문제점들을 해결하기 위해 본 논문에서는 RETE 네트워크의 분산을 그래프 분할 문제로 변환하여 해결 하였다. 이를 통해 효율적으로 각 서버에 계산량을 분배하고, 서버간 네트워크 사용량 또한 최소화하였다. 또한 세 종류의 실제 데이터를 사용하여 기존 연구 대비 본 방법이 처리시간, 불균형 정도, 네트워크 사용량 관점에서 우수함을 확인하였다.
