Search

Data- and model-driven computer simulations are increasingly critical in many application domains. These simulations may track 10s or 100s of parameters, affected by complex inter-dependent dynamic processes. Moreover, decision makers usually need to run large simulation ensembles, containing 1000s of simulations. In this paper, we rely on a tensor-based framework to represent and analyze patterns in large simulation ensemble data sets to obtain a high-level understanding of the dynamic processes implied by a given ensemble of simulations.We, further, note that the inherent sparsity of the simulation ensembles (relative to the space of potential simulations one can run) constitutes a significant problem in discovering these underlying patterns. To address this challenge, we propose a partition-stitch sampling scheme, which divides the parameter space into subspaces to collect several lower modal ensembles, and complement this with a novel Multi-Task Tensor Decomposition (M2TD), technique which helps effectively and efficiently stitch these subensembles back. Experiments showed that, for a given budget of simulations, the proposed structured sampling scheme leads to significantly better overall accuracy relative to traditional sampling approaches, even when the user does not have perfect information to help guide the structured partitioning process.

An XML publish/subscribe system needs to filter a large number of queries over XML streams. Most existing systems only consider filtering the simple XPath statements. In this paper, we focus on filtering of the more complex generalized-tree-pattern (GTP) queries. Our filtering mechanism is based on a novel Tree-of-Path (TOP) encoding scheme, which compactly represents the path matches for the entire document. First, we show that the TOP encodings can be efficiently produced via a shared bottom-up path matching. Second, with the aid of this TOP encoding, we can (1) achieve polynomial time and space complexity for post processing, (2) avoid redundant predicate evaluations, (3) allow an efficient duplicate-free and merge join-based algorithm for merging multiple encoded path matches and (4) simplify the processing of GTP queries. Overall our approach maximizes the sharing opportunity across queries by exploiting the suffix as well as prefix sharing. At the same time, our TOP encodings allow efficient post processing for GTP queries. Extensive performance studies show that our GFilter solution not only achieves significantly better filtering performance than state-of-the-art algorithms, but also is capable of efficiently filtering the more complex GTP queries.

Tensor decomposition operation is the basis for many data analysis tasks from clustering, trend detection, anomaly detection, to correlation analysis. One key problem with tensor decomposition, however, is its computational complexity -- especially for dense data sets, the decomposition process takes exponential time in the number of tensor modes; the process is relatively faster for sparse tensors, but decomposition is still a major bottleneck in many applications. While it is possible to reduce the decomposition time by trading performance with decomposition accuracy, a drop in accuracy may not always be acceptable. In this paper, we first recognize that in many applications, the user may have a focus of interest -- i.e., part of the data for which the user needs high accuracy -- and beyond this area focus, accuracy may not be as critical. Relying on this observation, we propose a novel Personalized Tensor Decomposition(PTD) mechanism for accounting for the user's focus: PTD takes as input one or more areas of focus and performs the decomposition in such a way that, when reconstructed, the accuracy of the tensor is boosted for these areas of focus. We discuss alternative ways PTD can be implemented. Experiments show that PTD helps boost accuracy at the foci of interest, while reducing the overall tensor decomposition time.

The problem of finding interesting tuples in a data set, more commonly known as the skyline problem, has been extensively studied in scenarios where the data is static. More recently, skyline research has moved towards data streaming environments, where tuples arrive/expire in a continuous manner. Several algorithms have been developed to track skyline changes over sliding windows; however, existing methods focus on skyline analysis in which all required skyline attributes belong to a single incoming data stream. This constraint renders current algorithms unsuitable for applications that require a real-time “join” operation to be carried out between multiple incoming data streams, arriving from different sources, before the skyline query can be answered. Based on this motivation, in this paper, we address the problem of computing skyline-window-join (SWJ) queries over pairs of data streams, considering sliding windows that take into account only the most recent tuples. In particular, we propose a Layered Skyline-window-Join (LSJ) operator that (a) partitions the overall process into processing layers and (b) maintains skyline-join results in an incremental manner by continuously monitoring the changes in all layers of the process. We combine the advantages of existing skyline methods (including those that efficiently maintain skyline results over a single stream, and those that compute the skyline of pairs of static data sets) to develop a novel iteration-fabric skyline-window-join processing structure. Using the iteration-fabric, LSJ eliminates redundant work across consecutive windows by leveraging shared data across all iteration layers of the windowed skyline-join processing. To the best of our knowledge, this is the first paper that addresses join-based skyline queries over sliding windows. Extensive experimental evaluations over real and simulated data show that LSJ provides large gains over naive extensions of existing schemes which are not designed to eliminate redundant work across multiple processing layers.

In this paper, we first introduce a tensor-based relational data model and define algebraic operations on this model. We note that, while in traditional relational algebraic systems the join operation tends to be the costliest operation of all, in the tensor-relational framework presented here, tensor decomposition becomes the computationally costliest operation. Therefore, we consider optimization of tensor decomposition operations within a relational algebraic framework. This leads to a highly efficient, effective, and easy-to-parallelize join-by-decomposition approach and a corresponding KL-divergence based optimization strategy. Experimental results provide evidence that minimizing KL-divergence within the proposed join-by-decomposition helps approximate the conventional join-then-decompose scheme well, without the associated time and space costs.

This paper presents a novel data structure, called Event-centric Composable Queue (ECQ), a basic building block of a new scalable composite event monitoring (CEM) framework, SCEMon. In particular, we focus on the scalability issues when large numbers of CEM queries and event sources exist in upcoming CEM environments. To address these challenges effectively, we take an event-centric sharing approach rather than dealing with queries and sources separately. ECQ is a shared queue, which stores incoming event instances of a primitive event class. ECQs are designed to facilitate efficient shared evaluations of multiple queries over very large volumes of event streams from numerous event sources. ECQs are composable and form a single shared network within which multiple queries are simultaneously evaluated. In this paper, we present efficient shared processing techniques operating on top of the proposed shared ECQ network. The performance evaluation shows that the proposed approach achieves a high level of scalability compared to conventional separate processing approaches in large-scale CEM environments.

In XML Data Integration, data/metadata merging and query processing are indispensable. Specifically, merging integrates multiple disparate (heterogeneous and autonomous) input data sources together for further usage, while query processing is one main reason why the data need to be integrated in the first place. Besides, when supported with appropriate user feedback techniques, queries can also provide contexts in which conflicts among the input sources can be interpreted and resolved. The flexibility of XML structure provides opportunities for alleviating some of the difficulties that other less flexible data types face in the presence of uncertainty; yet, this flexibility also introduces new challenges in merging multiple sources and query processing over integrated data. In this chapter, the authors discuss two alternative ways XML data/schema can be integrated: conflict-eliminating (where the result is cleaned from any conflicts that the different sources might have with each other) and conflict-preserving (where the resulting XML data or XML schema captures the alternative interpretations of the data). They also present techniques for query processing over integrated, possibly imprecise, XML data, and cover strategies that can be used for resolving underlying conflicts.

Summarization of hierarchical data and metadata is a fundamental operation in applications in many domains. In particular, similarity search of hierarchical data, such as XML, would benefit greatly from concise and indexable summaries. This is especially true in P2P scenarios, where the search needs to be done in a distributed fashion on multiple peers. This situation requires summaries which are small, yet effective in identifying potential peers that need to be further explored. In this paper, we propose a method, called propagation-vectors for trees (PVT) which constructs very concise and accurate summaries of hierarchical data, such as XML trees. We then show how to use this summary to perform similarity search on summarized data. The proposed summarization scheme relies on a label-propagation mechanism, which constructs an n-dimensional vector from a given tree with n unique data labels. Experimental results have shown that the constructed PVT summaries capture the structure of the input trees very accurately, the representations are highly concise, and that the search based on these summaries are faster than the existing approaches.

Media-rich ubiquitous distributed media processing workflow systems continuously sense users' needs, status, and the context, filter and fuse a multitude of real-time media data, and react by adapting the environment to the user. One challenge facing these systems is that they need to process real-time data arriving continuously from the sensors and data rates and qualities may vary dramatically. Thus, reducing the amount of unqualified data objects that need to be processed within the underlying media processing workflows can enhance the performance significantly. In this paper, we first focus on the prediction of the output qualities at the actuator, especially in the presence of fusion operators in the workflow. We then present quality-aware early object elimination schemes to enable informed resource savings in continuous real-time media processing workflow middleware.

In situ wireless sensor networks, not only have to route sensed data from sources to destinations, but also have to filter and fuse observations to eliminate potentially irrelevant data. If data arrive faster to such fusion nodes than the speed with which they can consume the inputs, this will result in an overflow of input buffers. In this paper, we develop load shedding mechanisms which take into consideration both data quality and expensive nature of fusion operators. In particular, we present quality assessment models for objects and fusion operators and we highlight that such quality assessments may impose partial orders on objects.

Basic message processing tasks, such as well-formedness checking and grammar validation, can be off-loaded from the service providers' own infrastructures. To enable effective off-loading of processing tasks, we introduce the Prefix Automata SyStem - PASS, a middleware architecture which distributively processes XML payloads of Web service SOAP messages during their routing towards Web servers. PASS is based on a network of automata, where PASS-nodes independently but cooperatively process parts of the SOAP message XML payload.

ARIA, ARchitecture for Interactive Arts, is a middleware to process, filter, and fuse sensory inputs and actuate responses in real-time. An ARIA media processing workflow describes how the data sensed through media will be processed and what audio-visual responses will be actuated. Each object streamed between ARIA processing components is subject to transformations, as described by a media workflow graph. The media capture and processing components, such as media filters and fusion operators, are programmable and adaptable; i.e, the delay, size, frequency, and quality/precision characteristics of individual operators can be controlled via a number of parameters. In this paper, we present the underlying model which captures the dynamic nature of the ARIA media processing workflows. This model enables design time verification, optimization, and runtime adaptation.

The capability of extracting critical information from a live video signal and presenting it to end-users in an easy-to-grasp form is essential in many application domains, including GIS, intelligence, surveillance, and manufacturing. We outline on the development of methods and algorithms that are necessary for real-time analysis of video data, both in compressed or uncompressed domains, the generation of visual icons that embody the characteristics of the objects of interest (say enemy craft, main actor, star player, etc.) and presentation of the panoramic spatio-temporal view of the entire scene in the form of video mosaics.

The large scale proliferation of multimedia data necessitates the use of sophisticated techniques for accessing the information based on the content. VideoRoadMap is a new content-based video indexing system for retrieving video clips and images from multimedia databases. The system indexes the audio-visual information using spatio-temporal features and information modeling methods. The proposed system employs adaptive similarity measurements based on the contents of media objects, resulting in more accurate retrievals. Principal component analysis and second order statistical analysis are employed to determine the appropriate combination of weight values in similarity search. In addition, VideoRoadMap includes a powerful multi- faceted querying mechanism which allows queries to be formulated and presented in a variety of modes, including query by example (image and/or video), query by sketch, and query by object motion trajectory.