Overload situations, in the presence of resource limitations, in complex event processing (CEP) systems are typically handled using load shedding to maintain a given latency bound. However, load shedding might negatively impact the quality of results (QoR). To minimize the shedding impact on QoR, CEP researchers propose shedding approaches that drop events/internal state with the lowest importances/utilities. In both black-box and white-box shedding approaches, different features are used to predict these utilities. In this work, we propose a novel black-box shedding approach that uses a new set of features to drop events from the input event stream to maintain a given latency bound. Our approach uses a probabilistic model to predict these event utilities. Moreover, our approach uses Zobrist hashing and well-known machine learning models, e.g., decision trees and random forests, to handle the predicted event utilities. Through extensive evaluations on a real-world and several synthetic datasets and a representative set of CEP queries, we show that, in the majority of cases, our load shedding approach outperforms state-of-the-art black-box load shedding approaches, w.r.t. QoR.

Many applications require the processing of event streams from different sources in combination with large amounts of background knowledge. Semantic CEP is a paradigm designed specifically for that. It extends complex event processing (CEP) with RDF support and uses a network of operators to process RDF streams in combination with RDF knowledge bases. Another popular class of systems designed for a similar purpose are the RDF stream processors (RSPs). These are systems that extend SPARQL (the RDF query language) with stream processing capabilities. Semantic CEP and RSPs have similar purposes but focus on different things. The former focuses on scalability and distributed processing while the latter tend to focus on the intricacies of RDF stream processing per se. In this paper we propose the use of RSP engines as building blocks for Semantic CEP. We present an infrastructure, called DSCEP, that allows the encapsulation of existing RSP engines into CEP-like operators so that these can be seamlessly interconnected in a distributed, decentralized operator network. DSCEP handles the hurdles of such interconnection, such as reliable communication, stream aggregation and slicing, event identification and time-stamping, etc., allowing users to concentrate on the queries. We also discuss in the paper how DSCEP can be used to speedup monolithic SPARQL queries by splitting them into parallel subqueries operating over restricted parts of the knowledge base.

Complex event processing (CEP) systems continuously process input event streams to detect patterns. Over time, the input event rate might fluctuate and overshoot the system's capabilities. One way to reduce the overload on the system is to use load shedding. In this paper, we propose a load shedding strategy for CEP systems which drops a portion of the CEP operator's internal state (a.k.a. partial matches) to maintain a given latency bound. The crucial question here is how many and which partial matches to drop so that a given latency bound is maintained while minimizing the degradation in the quality of results. In the stream processing domain, different load shedding strategies have been proposed that mainly depend on the importance of individual tuples. However, as CEP systems perform pattern detection, the importance of events is also influenced by other events in the stream. Our load shedding strategy uses Markov chain and Markov reward process to predict the utility/importance of partial matches to determine the ones to be dropped. In addition, we represent the utility in a way that minimizes the overhead of load shedding. Furthermore, we provide algorithms to decide when to start dropping partial matches and how many partial matches to drop. By extensively evaluating our approach on three real-world datasets and several representative queries, we show that the adverse impact of our load shedding strategy on the quality of results is considerably less than the impact of state-of-the-art load shedding strategies.

We propose two extensions for a state-of-the-art method of rollback-recovery in distributed CEP (complex event processing). In CEP, an operator network is used to search for patterns in events streams. Sometimes these operators fail and lose their state. Rollback-recovery is a method for dealing with such state losses. The type of rollback-recovery we consider is upstream backup, where the state of a failed operator is recovered by replaying to it the input events that led it to that state. These events are kept in upstream operators' memory buffers, which are trimmed continuously as the downstream operator progresses. The first extension we propose saves memory and speeds up recovery by avoiding to store and retransmit unnecessary events. The second extension makes the base method of upstream backup compatible with data-parallel CEP, allowing that the windows into which operators partition their input be processed in parallel. We evaluated the proposed extensions through experiments that showed a significant reduction in memory usage and recovery time at the expense of a negligible processing overhead during normal operation.

Many important real-world applications-such as social networks or distributed data bases-can be modeled as hypergraphs. In such a model, vertices represent entities-such as users or data records-whereas hyperedges model a group membership of the vertices-such as the authorship in a specific topic or the membership of a data record in a specific replicated shard. To optimize such applications, we need an efficient and effective solution to the NP-hard balanced k-way hypergraph partitioning problem. However, existing hypergraph partitioners that scale to very large graphs do not effectively exploit the hy-pergraph structure when performing the partitioning decisions. We propose HYPE, a hypergraph partitionier that exploits the neighborhood relations between vertices in the hypergraph using an efficient implementation of neighborhood expansion. HYPE improves partitioning quality by up to 95% and reduces runtime by up to 39% compared to streaming partitioning.

With the fast adoption of location-enabled devices, Location-based Applications (LBAs) have become widely popular. While LBAs enable highly useful concepts such as geo-social networking, their use also raises serious privacy concerns as it involves sharing of location data with non-trusted third parties. In this respect, we propose an approach that protects the frequently visited locations of users, e.g., a bar, against inferences from long-term monitoring of their location data. Such inferences equate a privacy leak as they reveal a user's personal behavior and interests to possibly malicious non-trusted parties. To this end, we first present a study of a dataset of location check-ins to show the existence of this threat among users of LBAs. We then propose our approach to protect visit-frequency of the users to different locations by distributing their location data among multiple third-party Location Servers. This distribution not only serves to avoid a single point of failure for privacy in our system, it also allows the users to control which LBA accesses what information about them. We also describe a number of possible attacks against our privacy approach and evaluate them on real-data from the check-ins dataset. Our results show that our approach can effectively hide the frequent locations while supporting good quality-of-service for the LBAs.

Complex Event Processing (CEP) systems enable applications to react to live-situations by detecting event patterns (complex events) in data streams. With the increasing number of data sources and the increasing volume at which data is produced, parallelization of event detection is becoming of tremendous importance to limit the time events need to be buffered before they actually can be processed by an event detector - named event processing operator. In this paper, we propose a pattern-sensitive partitioning model for data streams that is capable of achieving a high degree of parallelism for event patterns which formerly could only be consistently detected in a sequential manner or at a low parallelization degree. Moreover, we propose methods to dynamically adapt the parallelization degree to limit the buffering imposed on event detection in the presence of dynamic changes to the workload. Extensive evaluations of the system behavior show that the proposed partitioning model allows for a high degree of parallelism and that the proposed adaptation methods are able to meet the buffering level for event detection under high and dynamic workloads.

Processes in the healthcare domain are characterized by coarsely predefined recurring procedures that are flexibly adapted by the personnel to suite-specific situations. In this setting, a workflow management system that gives guidance and documents the personnel's actions can lead to a higher quality of care, fewer mistakes, and higher efficiency. However, most existing workflow management systems enforce rigid inflexible workflows and rely on direct manual input. Both are inadequate for healthcare processes. In particular, direct manual input is not possible in most cases since (1) it would distract the personnel even in critical situations and (2) it would violate fundamental hygiene principles by requiring disinfected doctors and nurses to touch input devices. The solution could be activity recognition systems that use sensor data (e.g., audio and acceleration data) to infer the current activities by the personnel and provide input to a workflow (e.g., informing it that a certain activity is finished now). However, state-of-the-art activity recognition technologies have difficulties in providing reliable information. We describe a comprehensive framework tailored for flexible human-centric healthcare processes that improves the reliability of activity recognition data. We present a set of mechanisms that exploit the application knowledge encoded in workflows in order to reduce the uncertainty of this data, thus enabling unobtrusive robust healthcare workflows. We evaluate our work based on a real-world case study and show that the robustness of unobtrusive healthcare workflows can be increased to an absolute value of up to 91% (compared to only 12% with a classical workflow system). This is a major breakthrough that paves the way towards future IT-enabled healthcare systems.

As mobile devices have become powerful sensor platforms, new applications have emerged which continuously stream mobile user context (location, activities, etc.). However, energy is a limited resource on battery-equipped mobile devices. Especially frequent transmissions of context updates over energy-expensive wireless channels drain the battery of mobile devices in an uncontrolled manner. It is a fundamental algorithmic challenge to design protocols such that users can control the energy consumption on mobile devices while, at the same time, optimizing the quality of mobile applications. To address this trade-off in the area of context update protocols, we propose a novel protocol that maximizes the context accuracy perceived by a remote consumer while guaranteeing that the consumed energy stays under a given limit. Our update protocol exploits predictions about a user's future behaviour to give priority to the most effective context updates. In our evaluation, we apply our predictive update protocol to a real-world trace of user context and show that the context accuracy is significantly increased compared to an update protocol which operates without predictions under the same energy budget.

Scaling heterogeneous information systems (HIS) to thousands of sources poses particular challenges to source discovery. It requires a powerful formalism for describing the contents of the sources in a concise manner and for formulating compatible queries as well as a suitable structure for indexing and retrieving the source descriptions efficiently.

In this paper we introduce a novel scenario for environmental sensing based on the combination of simple and cheap RFID-based sensors and mobile devices like mobile phones with integrated RFID readers. We envision a system that exploits the availability of these devices to cooperatively read sensors installed in the environment, and transmit the data to a server infrastructure. To achieve quality requirements and efficiency in terms of communication cost and energy consumption, this paper presents several algorithms for coordinating update operations. First, mobile nodes form an ad-hoc network for the cooperative management of requested update times to meet the desired update interval and to avoid redundant sensor reading and collisions during read operations. Second, besides this decentralized coordination algorithm, we also show a complementary algorithm that exploits infrastructure based coordination. By extensive simulations we show that our algorithms allow for autonomous operation and achieve a high quality of sensor updates where nearly 100% of the possible updates are performed. Moreover, the algorithms achieve a very high energy efficiency allowing for several hundred hours of operation assuming a typical battery of a mobile phone.

Space-partitioned Moving Objects Databases (SP-MODs) allow for the scalable, distributed management of large sets of mobile objects' trajectories by partitioning the trajectory data to a network of database servers.

In location-based services, continuous queries are often employed to monitor the locations of mobile objects that are determined by sensing devices like GPS receivers. Due to limited battery resources, it is important for these objects to acquire and report location data only if necessary. We study how these energy- consuming operations can be reduced with a controlled impact on query accuracy of continuous range queries (CRQs). Specifically, we develop uncertainty- aware tolerances, which are user-defined error bounds that provide correctness guarantees, with consideration of different sources of data uncertainty: sensing uncertainty, sampling uncertainty, and communication delay. Novel algorithms are developed to control carefully when an object should acquire and update a location, while satisfying these tolerances. Extensive simulations validate the effectiveness of our methods.

The performance of distributed algorithms in mobile ad hoc networks is strongly influenced by the connectivity of the network. In cases where the connectivity is low, network partitioning occurs. The mobility and the density of network nodes as well as the communication technology are fundamental properties that have a large impact on partitioning. A detailed characterization of this behavior helps to improve the performance of distributed algorithms. In this paper we introduce a set of metrics that characterize partitioning in mobile ad hoc networks. Based on an extensive simulation study we show the impact of node mobility, density and transmission range on the proposed metrics for a wide range of network scenarios.

Data Centric Storage (DCS) is a powerful storage paradigm for wireless ad hoc networks. In mobile ad hoc networks (MANETs), however, the mobility and varying density of nodes may significantly impact the efficiency of data access and the level of data consistency for existing DCS mechanisms. In this paper, we propose an efficient resilience mechanism for data centric storage that supports DCS in mobile environments. We introduce a novel indirection strategy that enables us to distinguish the storage of data at dedicated server nodes from the storage of additional information to locate these servers. Our approach places server location information dynamically in strategic parts of the network based on its current topology. Combining our server location advertisement with any geographic routing protocol, we provide a robust data update and query processing technique for data centric storage in MANETs. We show analytically and by means of experimental evaluations that, despite the additional indirection during packet forwarding, our approach provides superior storage and retrieval performance than the original DCS algorithm even for large amounts of dynamic data.

The proliferation of mobile devices has led to the creation of hoarding algorithms that attempt to mitigate the problems related with disconnected operation or with the operation in areas where bandwidth is either scarce or very expensive. Traditional hoarding approaches use probability access tables to determine what information needs to be sent to the mobile device, but fail to take the structured nature of data into account. In this paper, we present an enhanced hoarding approach for semistructured information that relies on the analysis of graphs to determine the information that needs to be hoarded. We show by means of experimental evaluations on Web pages that our approach outperforms other hoarding algorithms that treat information as the combination of unrelated items.

The use of mobile agent technology has been proposed for various fault-sensitive application areas, including electronic commerce and system management. A prerequisite for the use of mobile agents in these environments is that agents have to be executed reliably, independent of communication and node failures. In this article, we present two approaches improving the level of fault-tolerance in agent execution. The introduction of an itinerary concept allows to specify an agent's travel plan flexibly and provides the agent system with the possibility to postpone the visit of currently unavailable nodes or to choose alternative nodes in case of node failures. The second approach is a recently proposed fault-tolerant protocol to ensure the exactly-once execution of an agent. With this protocol, agents are preformed in stages. Each stage consists of a number of nodes. One of these nodes executes the agent while the others monitor the execution. After a summary of this protocol, we focus on the construction of stages. In particular, we investigate how the number of nodes per stage influences the probability of an agent to be blocked due to failures and which nodes should be selected when forming a stage to minimize the protocol overhead.

To ensure atomicity of transactions in distributed systems so-called 2-phase commit (2PC) protocols have been proposed. The basic assumption of these protocols is that the processing nodes involved in transactions are “sane,” i.e., they only fail with omission failures, and nodes eventually recover from failures. Unfortunately, this assumption is not realistic for so-called Open Distributed Systems (ODSs), in which nodes may have totally different reliability characteristics. In ODSs, nodes can be classified into trusted nodes (e.g., a banking server) and nontrusted nodes (e.g., a home PC requesting a remote banking service). While trusted nodes are assumed to be sane, nontrusted nodes may fail permanently and even cause commission failures to occur. In this paper, we propose a family of 2PC protocols that tolerate any number of omission failures at trusted nodes and any number of commission and omission failures at nontrusted nodes. The proposed protocols ensure that (at least) the trusted nodes participating in a transaction eventually terminate the transaction in a consistent manner. Unlike Byzantine commit protocols, our protocols do not incorporate mechanisms for achieving Byzantine agreement, which has advantages in terms of complexity: Our protocols have the same or only a slightly higher message complexity than traditional 2PC protocols.

The concept of nested transactions offers more decomposable execution units and finer grained control over recovery and concurrency as compared to 'flat' transactions. To exploit these advantages, especially transaction recovery has to be refined and adjusted to the requirements of the control structure.In this paper, we investigate transaction recovery for nested transactions. Therefore, a model for nested transaction is introduced allowing for synchronous and asynchronous transaction invocation as well as single call and conversational interfaces. For the resulting four parameter combinations, the properties and dependencies of transaction recovery are explored if a transaction is 'unit of recovery' and if savepoints within transactions are used to gain finer recovery units.