BMQ-Processor: A High-Performance Border-Crossing Event Detection Framework for Large-Scale Monitoring Applications

In this paper, we present BMQ-Processor, a high-performance border-crossing event (BCE) detection framework for large-scale monitoring applications. We first characterize a new query semantics, namely, border monitoring query (BMQ), which is useful for BCE detection in many monitoring applications. It monitors the values of data streams and reports them only when data streams cross the borders of its range. We then propose BMQ-Processor to efficiently handle a large number of BMQs over a high volume of data streams. BMQ-Processor efficiently processes BMQs in a shared and incremental manner. It develops and operates over a novel stateful query index, achieving a high level of scalability over continuous data updates. Also, it utilizes the locality embedded in data streams and greatly accelerates successive BMQ evaluations. We present data structures and algorithms to support 1D as well as multidimensional BMQs. We show that the semantics of border monitoring can be extended toward more advanced ones and build region transition monitoring as a sample case. Lastly, we demonstrate excellent processing performance and low storage cost of BMQ-Processor through extensive analysis and experiments.

1 Introduction

Recent advances in mobile computing and embedded device technologies open up new opportunities for various types of advanced monitoring applications, e.g., location-aware [29], [38], context-aware [12], [30], environmental [38], and financial [2], [11] monitoring applications. An important feature of such applications lies in situation awareness; the applications continuously monitor and identify if situations or conditions of interest occur. Services are automatically triggered upon the detection of the registered conditions, e.g., an air conditioner is automatically turned on if the temperature of an office is higher than 28 °C. Much research on active databases and event-based systems has been performed to support such event detection and task automation [16], [17], [20], [26], [43], [48], [50]. The event detection is done through continuous monitoring of numerous data streams generated from various sensors, GPSs, or agents that are widely deployed throughout physical or virtual (computing) environments. Often, such monitoring applications are large scale, spanning a number of people and devices over a wide geographic area. An efficient event detection framework is necessary to effectively support large-scale monitoring applications.