In this thesis, we envision the necessity of a scalable data stream monitoring framework to address the unique challenges of emerging large-scale ubiquitous services, proliferating in the near future (e.g., large-scale urban sensor networks, crowd-aware city business). The emerging ubiquitous services will utilize a bunch of massive data streams continuously generated from a real world. Accordingly, they will be situation-aware; the services proactively detect the occurrences of interested events and trigger proper actions automatically. For this purpose, they commonly rely on real-time monitoring on voluminous data streams. Often, such services are remarkably large-scale, spanning a number of people and devices over a wide geographic area.
To address these challenges, we propose a scalable monitoring framework consisting of $\textsl{BMQ-Processor}$ and $\textsl{Tran-Seq}$, which effectively achieves semantics and processing requirements newly arising in the large-scale, senor-rich ubiquitous services. First, we present BMQ-Processor, a high-performance Border-Crossing Event (BCE) detection framework. A BCE is intuitively represented as a data stream crossing the borders of a user-specified interest range. Many scenarios show that BCE is an important and frequently-used primitive event. To facilitate the specification of massive BCEs, we first characterize a new query semantics, namely, Border Monitoring Query (BMQ). More importantly, we develop a high-performance processing mechanism which operates over a novel $\textsl{stateful query index}$. BMQ-Processor efficiently evaluates a large number of BMQs over voluminous data streams in a shared and incremental manner. In particular, we design BMQ-Processor that supports one- and multi-dimensional BMQs. Lastly, we demonstrate excellent processing performance and low storage cost of BMQ-Processor through extensive experiments and analysis.
Second, we present Tran-Seq, a high-performance BCE composition framework. BCE as a primitive event will form the basis for various useful pattern events. In particular, we take note of the practical importance of Region Transition Event (RTE) which is represented as a pair of consecutive BCEs from the same source within a time constraint. A RTE well represents moving behaviors of human or vehicles, i.e., transition or stay associated with a region. We first characterize Region Transition Monitoring Query (RTMQ) to specify massive RTEs. Then, we develop Tran-Seq (Transition-Sequence) provides efficient RTMQ processing and low storage cost through shared composition and time-constraint checking along with shared data structure. Note that the whole RTMQ processing is basically accelerated through BMQ-Processor since it efficiently generates much lower-rate BCEs by directly operating on the high-rate input data streams.
근 미래에는 대규모 도시센서네트워크, 군중인식 비즈니스와 같은 대규모의 유비쿼터스 서비스가 번성할 것이다. 이렇게 새롭게 떠오르는 유비쿼터스 서비스는 실 세계에서 끊임 없이 생성되는 여러 종류의 대량 데이터 스트림을 활용할 것이다. 따라서, 서비스들은 상황 인식 형이 되어 적극적으로 관심 있는 이벤트를 검출하고 적절한 액션을 자동으로 시작하게 할 것이다. 이를 위해, 그들을 주로 대용량의 데이터 스트림을 실시간 모니터링 하는 것이 필요하다. 종종, 이러한 서비스들은 대규모로 넓은 지역에 걸쳐 많은 수의 사람들과 장치들에 걸쳐서 제공된다.
이러한 문제를 다루기 위해서, 우리는 BMQ-Processor와 Tran-Seq으로 구성된 확장형 모니터링 프레임워크를 제안한다. 이는 대규모의 센서가 많은 유비쿼터스 환경에서 새롭게 떠오르는 의미론적 및 처리론적 요구사항을 다룬다. 첫째, 우리는 고성능으로 경계횡단 이벤트 (BCE)를 검출해내는 BMQ-Processor를 제안한다. BCE는 사용자가 지정한 관심지역의 경계를 횡단하는 데이터 스트림으로 표현된다. 많은 시나리오에서 BCE가 중요하고 자주 사용되는 기본이벤트임을 알 수 있다. 우리는 우선 대량의 BCE를 쉽게 명세하기 위해서 경계관찰질의(BMQ)를 제안한다. 더 중요하게는 상태보존형 질의인덱스 위에서 동작하는 고성능 처리방식을 제안한다. 질의를 인덱싱하여 다수의 질의를 처리하며 데이터 스트림의 서서히 움직이는 특징을 활용하여 연속된 질의인덱싱을 가속화한다. 또한, 일차원 및 다차원의 경계관찰질의의 처리를 지원한다. 실험과 분석을 통해 기존 방식에 비해 훨씬 좋은 처리성능과 낮은 저장비용을 증명한다.
둘째, 우리는 고성능 지역이동이벤트(RTE)를 검출해주는 Tran-Seq을 제안한다. 우리는 RTE의 실용적인 중요성을 주목한다. RTE는 같은 스트림소스로부터 시간제약 안에 온 두 연속적인 BCE로 표현되며 사람이나 자동차 같은 이동체의 이동 및 체류패턴을 잘 표현한다. 우리는 우선 대량의 RTE를 쉽게 명세하기 위해서 지역이동관찰질의(RTMQ)를 제안한다. 나아가 우리는 효율적이고 적은 저장비용으로 RTMQ를 처리하는 Tran-Seq (Transition-Sequence)를 제안한다. 이는 이벤트조합과 시간제약검사를 공유형으로 처리하고 데이터구조도 공유한다. RTMQ 처리는 기본적으로 BMQ-Processor에 의해 가속화된다. 이는 BMQ-Processor가 고속의 데이터 스트림에서 직접적으로 동작하여 좀더 저속의 BCE를 생성하기 때문이다.
