Nonthreshold-Based Event Detection for 3D Environment Monitoring in Sensor Networks

Event detection is a crucial task for wireless sensor network applications, especially environment monitoring. Existing approaches for event detection are mainly based on some predefined threshold values, and thus are often inaccurate and incapable of capturing complex events. For example, in coal mine monitoring scenarios, gas leakage or water osmosis can hardly be described by the overrun of specified attribute thresholds, but some complex pattern in the full-scale view of the environmental data. To address this issue, we propose a non-threshold based approach for the real 3D sensor monitoring environment. We employ energy-efficient methods to collect a time series of data maps from the sensor network and detect complex events through matching the gathered data to spatio-temporal data patterns. Finally, we conduct trace driven simulations to prove the efficacy and efficiency of this approach on detecting events of complex phenomena from real-life records.     

Hierarchical visual event pattern mining and its applications

In this paper, we propose a hierarchical visual event pattern mining approach and utilize the patterns to address the key problems in video mining and understanding field. We classify events into primitive events (PEs) and compound events (CEs), where PEs are the units of CEs, and CEs serve as smooth priors and rules for PEs. We first propose a tensor-based video representation and Joint Matrix Factorization (JMF) for unsupervised primitive event categorization. Then we apply frequent pattern mining techniques to discover compound event pattern structures. After that, we utilize the two kinds of event patterns to address the applications of event recognition and anomaly detection. First we extend the Sequential Monte Carlo (SMC) method to recognition of live, sequential visual events. To accomplish this task we present a scheme that alternatively recognizes primitive and compound events in one framework. Then, we categorize the anomalies into abnormal events (never seen events) and abnormal contexts (rule breakers), and the two kinds of anomalies are detected simultaneously by embedding a deviation criterion into the SMC framework. Extensive experiments have been conducted which demonstrate that the proposed approach is effective as compared to other major approaches.     

RFID数据流上多目标复杂事件检测

已有的RFID复杂事件处理技术主要关注于单个RFID对象的复杂事件检测和优化技术.实际上,很多RFID应用中往往需要同时检测多个同类型关联目标的复杂事件序列.研究了多个关联的RFID对象的复杂事件处理问题.通过扩展的事件语言和算子的语义以支持同类型多个RFID目标复杂事件查询的定义.通过模式的变换规则,将RFID应用中存在的各种非线性多目标复杂事件模式转换成线性模式,以便各种多目标模式在一个统一的框架下检测.提出了基于自动机NFA\\-{b2}的多目标复杂事件检测模型和多目标复杂事件检测算法.通过在多目标检测算法中使用关键节点下压和同位置约束置后优化策略,大大减少了单个类型上无用实例的数目和不同类型间模式匹配的搜索空间.与SASE算法的实验比较表明算法的正确性和高效性.     

Rule-based inference and decomposition for distributed in-network processing in wireless sensor networks

Wireless sensor networks are application specific and necessitate the development of specific network and information processing architectures that can meet the requirements of the applications involved. A common type of application for wireless sensor networks is the event-driven reactive application, which requires reactive actions to be taken in response to events. In such applications, the interest is in the higher-level information described by complex event patterns, not in the raw sensory data of individual nodes. Although the central processing of information produces the most accurate results, it is not an energy-efficient method because it requires a continuous flow of raw sensor readings over the network. As communication operations are the most expensive in terms of energy usage, the distributed processing of information is indispensable for viable deployments of applications in wireless sensor networks. This method not only helps in reducing the total amount of packets transmitted in the network and the total energy consumed by the sensor nodes, but also produces scalable and fault-tolerant networks. For this purpose, we present two schemes that distribute information processing to appropriate nodes in the network. These schemes use reactive rules, which express relations between event patterns and actions, in order to capture reactive behavior. We also share the results of the performance of our algorithms and the simulations based on our approach that show the success of our methods in decreasing network traffic while still realizing the desired functionality.     

Discovering hybrid temporal patterns from sequences consisting of point- and interval-based events

Previous sequential pattern mining studies have dealt with either point-based event sequences or interval-based event sequences. In some applications, however, event sequences may contain both point-based and interval-based events. These sequences are called hybrid event sequences. Since the relationships among both kinds of events are more diversiform, the information obtained by discovering patterns from these events is more informative. In this study we introduce a hybrid temporal pattern mining problem and develop an algorithm to discover hybrid temporal patterns from hybrid event sequences. We carry out an experiment using both synthetic and real stock price data to compare our algorithm with the traditional algorithms designed exclusively for mining point-based patterns or interval-based patterns. The experimental results indicate that the efficiency of our algorithm is satisfactory. In addition, the experiment also shows that the predicting power of hybrid temporal patterns is higher than that of point-based or interval-based patterns.     

Complex RFID event processing

Advances of sensor and radio frequency identification (RFID) technology provide significant new power for humans to sense, understand and manage the world. RFID provides fast data collection with precise identification of objects with unique IDs without line of sight, thus it can be used for identifying, locating, tracking and monitoring physical objects. Despite these benefits, RFID poses many challenges for data processing and management: (i) RFID observations have implicit meanings, which have to be transformed and aggregated into semantic data represented in their data models; and (ii) RFID data are temporal, streaming, and in high volume, and have to be processed on the fly. Thus, a general RFID data processing framework is needed to automate the transformation of physical RFID observations into the virtual counterparts in the virtual world linked to business applications. In this paper, we take an event-oriented approach to process RFID data, by devising RFID application logic into complex events. We then formalize the specification and semantics of RFID events and rules. We discover that RFID events are highly temporal constrained, and include non-spontaneous events, and develop an RFID event detection engine that can effectively process complex RFID events. The declarative event-based approach greatly simplifies the work of RFID data processing, and can significantly reduce the cost of RFID data integration. This work was done by F. Wang while working at Siemens Corporate Research. This work was done by S. Liu while visiting Siemens Corporate Research.     

Hierarchical querying scheme of human motions for smart home environment

With the recent development of ubiquitous technologies, many new applications have been emerging for smart home implementation. Usually, such applications are based on diverse sensors. One fundamental operation in the applications is to find out semantically meaningful events or activities from huge sensor data stream. Usually, such event or activity is represented by a salient sequence pattern. Among the diverse research issues, detecting salient sequence patterns of human motions from image sensor data stream has received much attention for security and surveillance purposes. In the case of detecting human motions from image sensor data, finding and matching their salient sequence patterns could become more complicated since semantically same motions could show diverse variations such as different motion time. Based on this observation, in this paper, we propose a new querying and answering scheme for continuous sensor data stream to detect abnormal human motions. More specifically, we first present a new hierarchical querying scheme to consider variable length of semantically same human motions. Secondly, we present an indexing scheme to efficiently find semantically meaningful motion sequences in the sensor data stream. Thirdly, we present Dynamic Group Warping algorithm to effectively filter out unnecessary human motions. Through extensive experiments, we show that our proposed method achieves outstanding performance.     

面向RFID数据处理的复杂事件模式匹配方法

RFID数据具有不确定性,复杂事件处理技术将RFID数据看作不同类型的事件,从事件流中检测符合特定匹配模式的复杂事件。概率事件流分为多项概率事件流和单项概率事件流;针对多项概率事件流,提出NFA-MMG模式匹配方法,亦即使用多个有向无环图结合自动机实现模式匹配。针对单项概率事件流,提出NFA-Tree模式匹配方法,亦即使用匹配树结合自动机实现模式匹配;并提出改进的NFA-Tree方法,即基于概率阈值进行过滤,提高结果过滤效率。实验结果验证了上述模式匹配方法的性能优势。     

Max-Margin Early Event Detectors

The need for early detection of temporal events from sequential data arises in a wide spectrum of applications ranging from human-robot interaction to video security. While temporal event detection has been extensively studied, early detection is a relatively unexplored problem. This paper proposes a maximum-margin framework for training temporal event detectors to recognize partial events, enabling early detection. Our method is based on Structured Output SVM, but extends it to accommodate sequential data. Experiments on datasets of varying complexity, for detecting facial expressions, hand gestures, and human activities, demonstrate the benefits of our approach.     

Toward Managing Uncertain Spatial Information for Situational Awareness Applications

Situational awareness (SA) applications monitor the real world and the entities therein to support tasks such as rapid decision-making, reasoning, and analysis. Raw input about unfolding events may arrive from variety of sources in the form of sensor data, video streams, human observations, and so on, from which events of interest are extracted. Location is one of the most important attributes of events, useful for a variety of SA tasks. In this article, we consider the problem of reaching situation awareness from textual input. We propose an approach to probabilistically model and represent (potentially uncertain) event locations described by human reporters in the form of free text. We analyze several types of spatial queries of interest in SA applications. We design techniques to store and index the models, to support the efficient processing of queries. Our extensive experimental evaluation over real and synthetic datasets demonstrates the effectiveness and efficiency of our approaches.     

Signature Detection and Matching for Document Image Retrieval

As one of the most pervasive methods of individual identification and document authentication, signatures present convincing evidence and provide an important form of indexing for effective document image processing and retrieval in a broad range of applications. However, detection and segmentation of free-form objects such as signatures from clustered background is currently an open document analysis problem. In this paper, we focus on two fundamental problems in signature-based document image retrieval. First, we propose a novel multiscale approach to jointly detecting and segmenting signatures from document images. Rather than focusing on local features that typically have large variations, our approach captures the structural saliency using a signature production model and computes the dynamic curvature of 2D contour fragments over multiple scales. This detection framework is general and computationally tractable. Second, we treat the problem of signature retrieval in the unconstrained setting of translation, scale, and rotation invariant nonrigid shape matching. We propose two novel measures of shape dissimilarity based on anisotropic scaling and registration residual error and present a supervised learning framework for combining complementary shape information from different dissimilarity metrics using LDA. We quantitatively study state-of-the-art shape representations, shape matching algorithms, measures of dissimilarity, and the use of multiple instances as query in document image retrieval. We further demonstrate our matching techniques in offline signature verification. Extensive experiments using large real-world collections of English and Arabic machine-printed and handwritten documents demonstrate the excellent performance of our approaches.     

An Efficient Method for Cleaning Dirty-Events over Uncertain Data in WSNs

Event detection in wireless sensor networks (WSNs) has attracted much attention due to its importance in many applications. The erroneous abnormal data generated during event detection are prone to lead to false detection results. Therefore, in order to improve the reliability of event detection, we propose a dirty-event cleaning method based on spatio-temporal correlations among sensor data. Unlike traditional fault-tolerant approaches, our method takes into account the inherent uncertainty of sensor measurements and focuses on the type of directional events. A probabilitybased mapping scheme is introduced, which maps uncertain sensor data into binary data. Moreover, we give formulated definitions of transient dirty-event (TDE) and permanent dirty-event (PDE), which are cleaned by a novel fuzzy method and a collaborative cleaning scheme, respectively. Extensive experimental results show the effectiveness of our dirty-event cleaning method.     

A scalable algorithm for extraction and clustering of event-related pictures

The event detection problem, which is closely related to clustering, has gained a lot of attentions within event detection for textual documents. However, although image clustering is a problem that has been treated extensively in both Content-Based Image Retrieval (CBIR) and Text-Based Image Retrieval (TBIR) systems, event detection within image management is a relatively new area. Having this in mind, we propose a novel approach for event extraction and clustering of images, taking into account textual annotations, time and geographical positions. Our goal is to develop a clustering method based on the fact that an image may belong to an event cluster. Here, we stress the necessity of having an event clustering and cluster extraction algorithm that are both scalable and allow online applications. To achieve this, we extend a well-known clustering algorithm called Suffix Tree Clustering (STC), originally developed to cluster text documents using document snippets. The idea is that we consider an image along with its annotation as a document. Further, we extend it to also include time and geographical position so that we can capture the contextual information from each image during the clustering process. This has appeared to be particularly useful on images gathered from online photo-sharing applications such as Flickr. Hence, our STC-based approach is aimed at dealing with the challenges induced by capturing contextual information from Flickr images and extracting related events. We evaluate our algorithm using different annotated datasets mainly gathered from Flickr. As part of this evaluation we investigate the effects of using different parameters, such as time and space granularities, and compare these effects. In addition, we evaluate the performance of our algorithm with respect to mining events from image collections. Our experimental results clearly demonstrate the effectiveness of our STC-based algorithm in extracting and clustering events.     

Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture

Due to the huge size of patterns to be searched,multiple pattern searching remains a challenge to several newly-arising applications like network intrusion detection.In this paper,we present an attempt to design efficient multiple pattern searching algorithms on multi-core architectures.We observe an important feature which indicates that the multiple pattern matching time mainly depends on the number and minimal length of patterns.The multi-core algorithm proposed in this paper leverages this feature to decompose pattern set so that the parallel execution time is minimized.We formulate the problem as an optimal decomposition and scheduling of a pattern set,then propose a heuristic algorithm,which takes advantage of dynamic programming and greedy algorithmic techniques,to solve the optimization problem.Experimental results suggest that our decomposition approach can increase the searching speed by more than 200% on a 4-core AMD Barcelona system.     

Correlating burst events on streaming stock market data

We address the problem of monitoring and identification of correlated burst patterns in multi-stream time series databases. We follow a two-step methodology: first we identify the burst sections in our data and subsequently we store them for easy retrieval in an efficient in-memory index. The burst detection scheme imposes a variable threshold on the examined data and takes advantage of the skewed distribution that is typically encountered in many applications. The detected bursts are compacted into burst intervals and stored in an interval index. The index facilitates the identification of correlated bursts by performing very efficient overlap operations on the stored burst regions. We present the merits of the proposed indexing scheme through a thorough analysis of its complexity. We also manifest the real-time response of our burst indexing technique, and demonstrate the usefulness of the approach for correlating surprising volume trading events using historical stock data of the NY stock exchange. While the focus of this work is on financial data, the proposed methods and data-structures can find applications for anomaly or novelty detection in telecommunication, network traffic and medical data.     

High utility pattern mining over data streams with sliding window technique

Processing changeable data streams in real time is one of the most important issues in the data mining field due to its broad applications such as retail market analysis, wireless sensor networks, and stock market prediction. In addition, it is an interesting and challenging problem to deal with the stream data since not only the data have unbounded, continuous, and high speed characteristics but also their environments have limited resources. High utility pattern mining, meanwhile, is one of the essential research topics in pattern mining to overcome major drawbacks of the traditional framework for frequent pattern mining that takes only binary databases and identical item importance into consideration. This approach conducts mining processes by reflecting characteristics of real world databases, non-binary quantities and relative importance of items. Although relevant algorithms were proposed for finding high utility patterns in stream environments, they suffer from a level-wise candidate generation-and-test and a large number of candidates by their overestimation techniques. As a result, they consume a huge amount of execution time, which is a significant performance issue since a rapid process is necessary in stream data analysis. In this paper, we propose an algorithm for mining high utility patterns from resource-limited environments through efficient processing of data streams in order to solve the problems of the overestimation-based methods. To improve mining performance with fewer candidates and search space than the previous ones, we develop two techniques for reducing overestimated utilities. Moreover, we suggest a tree-based data structure to maintain information of stream data and high utility patterns. The proposed tree is restructured by our updating method with decreased overestimation utilities to keep up-to-date stream information whenever the current window slides. Our approach also has an important effect on expert and intelligent systems in that it can provide users with more meaningful information than traditional analysis methods by reflecting the characteristics of real world non-binary databases in stream environments and emphasizing on recent data. Comprehensive experimental results show that our algorithm outperforms the existing sliding window-based one in terms of runtime efficiency and scalability.     

地铁列车环境中多依赖复杂事件处理研究

针对多源海量实时数据的复杂事件检测中，原始事件流的分流处理存在事件检测准确率低及效率慢的问题，提出一种基于事件树的复杂事件检测方法。首先给出事件依赖关系的明确定义，然后根据原子事件间存在的多依赖关系生成原子事件树，以事件树为节点构造依赖事件树链表，提升复杂事件处理引擎的有效检测次数，使得事件检测的匹配效率得到提升。同时该方法减少了事件检测过程的内存消耗，提高了事件检测的吞吐量。仿真实验与案例研究证明了提出方法在海量数据处理上的优异性及可行性。     

Foundations for Streaming Model Transformations by Complex Event Processing

Streaming model transformations represent a novel class of transformations to manipulate models whose elements are continuously produced or modified in high volume and with rapid rate of change. Executing streaming transformations requires efficient techniques to recognize activated transformation rules over a live model and a potentially infinite stream of events. In this paper, we propose foundations of streaming model transformations by innovatively integrating incremental model query, complex event processing (CEP) and reactive (event-driven) transformation techniques. Complex event processing allows to identify relevant patterns and sequences of events over an event stream. Our approach enables event streams to include model change events which are automatically and continuously populated by incremental model queries. Furthermore, a reactive rule engine carries out transformations on identified complex event patterns. We provide an integrated domain-specific language with precise semantics for capturing complex event patterns and streaming transformations together with an execution engine, all of which is now part of the Viatra reactive transformation framework. We demonstrate the feasibility of our approach with two case studies: one in an advanced model engineering workflow; and one in the context of on-the-fly gesture recognition.     

普适计算中复合事件检测的研究与挑战

普适计算环境中,传感器设备的大规模使用产生了数量巨大、错综复杂的原子事件,而现实中的许多应用却更注重复合事件的检测,例如:健康护理、监督设施管理、环境/安全监控等,因此如何从这些底层的原子事件中抽取人们感兴趣的、有用的复合事件就变得越来越重要。目前,针对复合事件检测有大量的研究,其内容各有侧重。有的重视时间因素,特别强调时间段的重要性;有的研究分布式数据源中的复合事件检测;近期有人提出了不确定性数据上的复合事件检测。由于复合事件检测日益重要,对复合事件检测研究中存在的挑战性问题进行了分析,从事件类型、时间因素和数据的精确程度3个方面归纳总结了复合事件检测现有的研究成果,并指出了未来的发展方向。