Recently, great attention has been shown to distributed stream processing systems (DSPSs). In many applications of DSPSs, network communication is the key bottleneck of performance, and hence it is crucial to minimize communication costs. In this dissertation, we address communication-efficient query processing in DSPSs.
An emerging challenge in large-scale DSPSs is to efficiently process multiple continuous aggregation queries, which are one of the most common query types in streaming applications. Since a naive approach that executes each query separately can lead to scalability and efficiency problem, multiple aggregation queries must be processed collectively, rather than separately. In the first part of this dissertation, we propose an efficient method for collectively processing multiple aggregation queries. Running at a local site, our proposed method finds the smallest set of aggregates that need to be sent to the global site in order to correctly answer all the queries and thus, it minimizes the number of required message transmissions. Since our proposed method operates on-the-fly, it can also efficiently handle registration or deregistration of queries at any time. Grounded in linear algebra, we prove that our proposed method is optimal in terms of communication costs.
In sensor networks, which are one of the most popular types of DSPSs, the event detection process can be regarded as a join of two relations, i.e., a sensor table and a condition table, where a condition table is a set of tuples each of which contains condition information about a certain event. When join operations are used for event-detection, it is desirable, if possible, to perform `in-network` joins in order to reduce the communication cost. In the second part of this dissertation, we propose an in-network join algorithm, called $\emph{HIPaG}$. In HIPaG, a condition table is partitioned into several fragments. Those fragments are stored either in paths from the base station (i.e., the global site) to sensor nodes (i.e., local sites), or in groups of nodes each of which are within the broadcast range among each other. By distributing a condition table in this way, a distributed join of a sensor table and a condition table can be effectively performed in the network. The experimental results show that our proposed HIPaG works much better than the existing method.
최근 수년간 분산 스트림 처리 시스템(DSPS)에 대한 관심이 높아져 왔다. DSPS를 사용하는 대부분의 경우 전체 성능이 네트워크 통신비용에 의해 좌우되기 때문에, 통신비용을 줄이는 것이 무엇보다 중요하다고 할 수 있다. 따라서 본 논문에서는 DSPS에서 분산된 연속 질의를 처리하는데 드는 통신비용을 줄이기 위한 방법을 다룬다.
대규모 DSPS에서 최근 관심을 끌고 있는 문제 중의 하나는 다수의 연속 집계 질의를 효율적으로 처리하는 것이다. 연속 집계 질의는 데이터 스트림 관련 응용 분야에서 널리 사용되고 있는 질의 종류 중 하나이다. 다수의 질의가 주어졌을 때 각각의 질의를 개별적으로 처리하는 것은 확장성과 효율성 문제를 야기할 수 있기 때문에, 여러 질의를 한번에 집합적으로 처리할 필요가 있다. 따라서 본 논문의 첫 번째 부분에서는 다수의 집계질의를 집합적으로 처리하기 위한 효율적인 방법을 제안한다. 제안하는 방법은 각 로컬 사이트에서 동작하며, 글로벌 사이트에서 모든 질의에 대한 정확한 결과를 얻기 위해 필요한 최소한의 집계 연산을 식별함으로써 메시지 전송 횟수를 최소화한다. 또한 제안하는 방법은 실행 도중에 질의가 등록되거나 취소될 때에도 이를 효율적으로 처리할 수 있다는 특징이 있다. 본 논문에서는 선형 대수학 지식을 바탕으로 제안하는 방법이 통신비용 관점에서 최적임을 증명한다.
DSPS의 가장 널리 알려진 유형 중 하나인 센서 네트워크에서는, 센서 데이터들을 포함하는 센서 테이블과 이벤트 검출을 위한 조건 정보를 담고 있는 조건 테이블 간의 조인 연산을 통해 이벤트 검출 작업을 수행할 수 있다. 이벤트 검출을 위해 조인 연산을 사용할 경우, 네트워크 내에서 조인 연산을 수행함으로써 통신비용을 크게 줄일 수 있다. 따라서 본 논문의 두 번째 부분에서는 효율적인 네트워크-내 조인 알고리즘인 HIPaG을 제안한다. HIPaG은 조건 테이블을 여러 개의 프레그먼트로 나눈 후에, 이러한 프레그먼트들을 베이스 스테이션에서 각 센서 노드에 이르는 경로 상에 배치하거나, 혹은 서로 방송 범위 안에 있는 센서 노드들의 그룹 내에 배치시킴으로써, 센서 테이블과 조건 테이블 간의 조인 연산을 네트워크 내에서 효과적으로 수행한다. 실험 결과는 제안하는 방법이 기존 방법보다 훨씬 더 성능이 좋다는 것을 보여준다.
