Search

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 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.

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.

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.