Because of high volumes and unpredictable arrival rates, stream processing systems cannot always keep up with input data streams, resulting in buffer overflow and uncontrolled loss of data. Load shedding and spilling, the two prevalent technologies designed to solve this overflow problem by dropping or flushing data to disk, suffer from serious shortcomings. Dropping data suffers in that partial output is lost forever, while flushing may waste precious resources due to making the strong assumption that flushed data can and will eventually still be processed. In this paper, we propose our solution, INSURE, integrating structure-based drop and flush techniques within one unified framework for XML stream systems. Our INSURE framework provides an optimized fine-grained load reduction solution that achieves high quality result production. First, the fusion candidate lattice models the space of load reduction solutions incorporating both drop and flush decisions, called fusion candidates. Second, our systematic analysis of fusion candidates and their interrelationships in the fusion candidate lattice reveals important relationships, including the monotonicity of their feasibility and profitability properties. Third, based upon this fusion candidate lattice model, a family of optimization strategies for the selection of fusion candidates is designed to successfully maximize the overall result quality. Experimental results demonstrate that INSURE consistently achieves higher quality results compared to the state-of-the-art techniques, yet with negligible overhead.

Autonomous agents deployed or moving on land for the purpose of carrying out coordinated tasks need to have good knowledge of their absolute or relative position. For large formations, it is often impractical to equip each agent with an absolute sensor such as GPS, whereas relative range sensors measuring interagent distances are cheap and commonly available. In this setting, this paper considers the problem of autonomous distributed estimation of the position of each agent in a networked formation using noisy measurements of interagent distances. The underlying geometrical problem has been studied quite extensively in various fields, ranging from molecular biology to robotics, and it is known to lead to a hard nonconvex optimization problem. Centralized algorithms do exist that work reasonably well in finding local or global minimizers for this problem (e.g., semidefinite programming relaxations). Here, we explore a fully decentralized approach for localization from range measurements, and we propose a computational scheme based on a distributed gradient algorithm with Barzilai-Borwein stepsizes. The advantage of this distributed approach is that each agent may autonomously compute its position estimate, exchanging information only with its neighbors, without need of communicating with a central station and without needing complete knowledge of the network structure.

Because of high volumes and unpredictable arrival rates, stream processing systems are not always able to keep up with input data - resulting in buffer overflow and uncontrolled loss of data. To produce eventually complete results, load spilling, which pushes some fractions of data to disks temporarily, is commonly employed in relational stream engines. In this work, we now introduce "structure-based spilling", a spilling technique customized for XML streams by considering the partial spillage of possibly complex XML elements. Such structure-based spilling brings new challenges. When a path is spilled, multiple paths may be affected. We analyze possible spilling effects on the query paths and how to execute the "reduced" query to produce partial results. To select the reduced query that maximizes output quality, we develop three optimization strategies, namely, OptR, OptPrune and ToX. We also examine the clean-up stage to guarantee that an entire result set is eventually generated by producing supplementary results. Our experimental study demonstrates that our proposed solutions consistently achieve higher quality results compared to the state-of-the-art techniques.

This demonstration presents a complex event processing system which focuses on out-of-order handling. State-of-the-art event stream processing technology experiences significant challenges when faced with out-of-order data arrival including huge system latencies, missing results, and incorrect result generation. We propose two out-of-order handling techniques, conservative and aggressive strategies. We will show the efficiency of our techniques and how they can satisfy various QoS requirements of different applications.

Because of the high volume and unpredictable arrival rate, stream processing systems may not always be able to keep up with the input data streams - resulting in buffer overflow and uncontrolled loss of data. Load shedding, the prevalent strategy for solving this overflow problem, has so far only been considered for relational stream processing, but not for XML. Shedding applied to XML stream processing brings new opportunities and challenges due to complex nested nature of XML structures. In this paper, we tackle this unsolved XML shedding problem using a three-pronged approach. First, we develop an XQuery preference model that enables users to specify the relative importance of preserving different subpatterns in the XML result structure. This transforms shedding into the problem of rewriting the user query into shed queries that return approximate query answers with utility as measured by the given user preference model. Second, we develop a cost model to compare the performance of alternate shed queries. Third, we develop two shedding algorithms, OptShed and FastShed. OptShed guarantees to find an optimal solution however at the cost of exponential complexity. FastShed, as confirmed by our experiments, achieves a close-to-optimal result in a wide range of test cases. Finally we describe the in-automaton shedding mechanism for XQuery stream engines. The experiments show that our proposed utility-driven shedding solutions consistently achieve higher utility results compared to the existing relational shedding techniques.