7776820
Scalable continuous query processing by tracking hotspots
This paper considers the problem of scalably processing a large number of continuous queries. We propose a flexible framework with novel data structures and algorithms for group-processing and indexing continuous queries by exploiting potential overlaps in query predicates. Our approach partitions the collection of continuous queries into groups based on the clustering patterns of the query ranges, and then applies specialized processing strategies to those heavily-clustered groups (or hotspots). To maintain the partition dynamically, we present efficient algorithms that maintain a nearly optimal partition in nearly amortized logarithmic time. We show how to use the hotspots to scalably process large numbers of continuous select-join and band-join queries, which are much more challenging than simple range selection queries. Experiments demonstrate that this approach can improve the processing throughput by orders of magnitude. As another application of hotspots, we show how to use them to build a high-quality histogram for intervals in linear time.
7995409
Query suspend and resume
Suppose a long-running analytical query is executing on a database server and has been allocated a large amount of physical memory. A high-priority task comes in and we need to run it immediately with all available resources. We have several choices. We could swap out the old query to disk, but writing out a large execution state may take too much time. Another option is to terminate the old query and restart it after the new task completes, but we would waste all the work already performed by the old query. Yet another alternative is to periodically checkpoint the query during execution, but traditional synchronous checkpointing carries high overhead. In this paper, we advocate a database-centric approach to implementing query suspension and resumption, with negligible execution overhead, bounded suspension cost, and efficient resumption. The basic idea is to let each physical query operator perform lightweight checkpointing according to its own semantics, and coordinate asynchronous checkpoints among operators through a novel contracting mechanism. At the time of suspension, we find an optimized suspend plan for the query, which may involve a combination of dumping current state to disk and going back to previous checkpoints. The plan seeks to minimize the suspend/resume overhead while observing the constraint on suspension time. Our approach requires only small changes to the iterator interface, which we have implemented in the PREDATOR database system. Experiments with our implementation demonstrate significant advantages of our approach over traditional alternatives.
14920261
BOXes: efficient maintenance of order-based labeling for dynamic XML data
Order-based element labeling for tree-structured XML data is an important technique in XML processing. It lies at the core of many fundamental XML operations such as containment join and twig matching. While labeling for static XML documents is well understood, less is known about how to maintain accurate labeling for dynamic XML documents, when elements and subtrees are inserted and deleted. Most existing approaches do not work well for arbitrary update patterns; they either produce unacceptably long labels or incur enormous relabeling costs. We present two novel I/O-efficient data structures, W-BOX and B-BOX that efficiently maintain labeling for large, dynamic XML documents. We show analytically and experimentally that both, despite consuming minimal amounts of storage, gracefully handle arbitrary update patterns without sacrificing lookup efficiency. The two structures together provide a nice tradeoff between update and lookup costs: W-BOX has logarithmic amortized update cost and constant worst-case lookup cost, while B-BOX has constant amortized update cost and logarithmic worst-case lookup cost. We further propose techniques to eliminate the lookup cost for read-heavy workloads.
7182462
On the database/network interface in large-scale publish/subscribe systems
The work performed by a publish/subscribe system can conceptually be divided into subscription processing and notification dissemination. Traditionally, research in the database and networking communities has focused on these aspects in isolation. The interface between the database server and the network is often overlooked by previous research. At one extreme, database servers are directly responsible for notifying individual subscribers; at the other extreme, updates are injected directly into the network, and the network is solely responsible for processing subscriptions and forwarding notifications. These extremes are unsuitable for complex and stateful subscription queries. A primary goal of this paper is to explore the design space between the two extremes, and to devise solutions that incorporate both database-side and network-side considerations in order to reduce the communication and server load and maintain system scalability. Our techniques apply to a broad range of stateful query types, and we present solutions for several of them. Our detailed experiments based on real and synthetic workloads with varying characteristics and link-level network simulation show that by exploiting the query semantics and building an appropriate interface between the database and the network, it is possible to achieve orders-of-magnitude savings in network traffic at low server-side processing cost.
2510058
Constraint chaining: on energy-efficient continuous monitoring in sensor networks
Wireless sensor networks have created new opportunities for data collection in a variety of scenarios, such as environmental and industrial, where we expect data to be temporally and spatially correlated. Researchers may want to continuously collect all sensor data from the network for later analysis. Suppression, both temporal and spatial, provides opportunities for reducing the energy cost of sensor data collection. We demonstrate how both types can be combined for maximal benefit. We frame the problem as one of monitoring node and edge constraints. A monitored node triggers a report if its value changes. A monitored edge triggers a report if the difference between its nodes' values changes. The set of reports collected at the base station is used to derive all node values. We fully exploit the potential of this global inference in our algorithm, CONCH, short for constraint chaining. Constraint chaining builds a network of constraints that are maintained locally, but allow a global view of values to be maintained with minimal cost. Network failure complicates the use of suppression, since either causes an absence of reports. We add enhancements to CONCH to build in redundant constraints and provide a method to interpret the resulting reports in case of uncertainty. Using simulation we experimentally evaluate CONCH's effectiveness against competing schemes in a number of interesting scenarios.
11503542
Monitoring Continuous Band-Join Queries over Dynamic Data
A continuous query is a standing query over a dynamic data set whose query result needs to be constantly updated as new data arrive. We consider the problem of constructing a data structure on a set of continuous band-join queries over two data sets R and S, where each band-join query asks for reporting the set { (r,s)∈ R× S | a≤ r–s≤ b} for some parameters a and b, so that given a data update in R or S, one can quickly identify the subset of continuous queries whose results are affected by the update, and compute changes to these results. 
 
We present the first nontrivial data structure for this problem that simultaneously achieves subquadratic space and sublinear query time. This is achieved by first decomposing the original problem into two independent subproblems, and then carefully designing data structures suitable for each case, by exploiting the particular structure in each subproblem. 
 
A key step in the above construction is a data structure whose performance increases with the degree of clusteredness of the band-joins being indexed. We believe that this structure is of independent interest and should have broad impact in practice. We present the details in [1].
207143686
Estimating The Attribute Weights Through Evidential Reasoning And Mathematical Programming
An approach for estimating attribute weight is proposed, which is addressed to the problem inverse to the aggregation assessment based on a hierarchy of attributes. Evidential reasoning framework is employed since the assessment on some basic attributes may be uncertain and incomplete. As a by-product, a simple formula for evidence combination for our special case is obtained. The weights are estimated based on the preference given by the decision-maker, and represented as intervals. The more abundant preference the decision-maker shows, the clearer the relation among the basic attributes.
342298
Nonlinear information aggregation via evidential reasoning in multiattribute decision analysis under uncertainty
In many decision situations, it is inevitable to deal with both quantitative and qualitative information under uncertainty. Evidence-based reasoning within a multiple criteria decision analysis framework provides an alternative way of handling such information systematically and consistently. In this paper, the evidential reasoning (ER) approach is introduced, which is based on a recursive ER algorithm that, in essence, constitutes a nonlinear information aggregation process. To facilitate the application of the ER approach and as an indispensable part of its development, the nonlinear features of the ER information aggregation process need to be thoroughly investigated and properly understood. This forms the theme of this paper where the nonlinear features are explored by examining typical reasoning patterns in aggregating harmonic, quasi-harmonic, and contradictory decision information. This analytical investigation provides insights into the recursive nature of the ER approach as well as valuable experience that could be useful to other researchers and practitioners interested in developing and applying operation research/artificial intelligence (OR/AI)-based approaches for decision analysis under uncertainty. The analytical study is complemented by the numerical studies of two application examples. The analysis of a quality assessment problem for motor engines is aimed to show the step-by-step process of implementing the ER approach and to illustrate its nonlinear features in a real-life decision situation. The study of a more complex assessment problem in ship design is intended to demonstrate the potential of the ER approach and its supporting software for dealing with general decision problems.
15674460
A two-stage logarithmic goal programming method for generating weights from interval comparison matrices
A two-stage logarithmic goal programming (TLGP) method is proposed to generate weights from interval comparison matrices, which can be either consistent or inconsistent. The first stage is devised to minimize the inconsistency of interval comparison matrices and the second stage is developed to generate priorities under the condition of minimal inconsistency. The weights are assumed to be multiplicative rather than additive. In the case of hierarchical structures, a nonlinear programming method is used to aggregate local interval weights into global interval weights. A simple yet practical preference ranking method is investigated to compare the interval weights of criteria or rank alternatives in a multiplicative aggregation process. The proposed TLGP is also applicable to fuzzy comparison matrices when they are transformed into interval comparison matrices using @a-level sets and the extension principle. Six numerical examples including a group decision analysis problem with a group of comparison matrices, a hierarchical decision problem and a fuzzy decision problem using fuzzy comparison matrix are examined to show the applications of the proposed methods. Comparisons with other existing procedures are made whenever possible.
388734
A statistical signal processing approach to image fusion for concealed weapon detection
A statistical signal processing approach to multisensor image fusion is presented for concealed weapon detection (CWD). This approach is based on an image formation model in which the sensor images are described as the true scene corrupted by additive non-Gaussian distortion. The expectation-maximization (EM) algorithm is used to estimate the model parameters and the fused image. We demonstrate the efficiency of this approach by applying this method to fusion of visual and non-visual images with emphasis on CWD applications.
6709166
Harmonium Models for Semantic Video Representation and Classification
Accurate and efficient video classification demands the fusion of multimodal information and the use of intermediate representations. Combining the two ideas into the same framework, we propose a probabilistic approach for video classification using intermediate semantic representations derived from the multi-modal features. Based on a class of bipartite undirected graphical models named harmonium, our approach represents video data as latent semantic topics derived by jointly modeling the transcript keywords and color-histogram features, and perform classification using these latent topics under a unified framework. We show satisfactory classification performance of our approach on a benchmark dataset, and some interesting insights of the data provided by this approach.