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.
214792426
TIP: a temporal extension to Informix
Commercial relational database systems today provide only limited temporal support. To address the needs of applications requiring rich temporal data and queries, we have built TIP (Temporal Information Processor), a temporal extension to the Informix database system based on its DataBlade technology. Our TIP DataBlade extends Informix with a rich set of datatypes and routines that facilitate temporal modeling and querying. TIP provides both C and Java libraries for client applications to access a TIP-enabled database, and provides end-users with a GUI interface for querying and browsing temporal data.
2070842
Distributed Network Querying with Bounded Approximate Caching
As networks continue to grow in size and complexity, distributed network monitoring and resource querying are becoming increasingly difficult. Our aim is to design, build, and evaluate a scalable infrastructure for answering queries over distributed measurements, at reduced costs (in terms of both network traffic and query latency) while maintaining required precision. In this infrastructure, each network node owns a set of numerical measurements and actively maintains bounds on these values cached at other nodes. We can answer queries approximately, using bounds from nearby caches to avoid contacting the owners directly. We focus on developing efficient and scalable techniques to place, locate, and manage bounded approximate caches across a large network. We have developed two approaches: One uses a recursive partitioning of the network space to place caches in a static, controlled manner, while the other uses a locality-aware distributed hash table to place caches in a dynamic and decentralized manner. In this paper, we focus on the latter approach. Experiments over a large-scale emulated network show that our techniques are very effective in reducing query costs while generating an acceptable amount of background traffic; they are also able to exploit various forms of locality that are naturally present in queries, and adapt to volatility of measurements.
14448318
On Suspending and Resuming Dataflows
Consider a long-running, resource-intensive query Q running on a database management system (DBMS). Suppose another task T with much higher priority arrives, and we need to process T as quickly as possible and with all available resources. Ideally, the system should suspend the execution of Q, quickly release all resources held by Q, and start T using all resources. Query Q can be resumed once T finishes execution, ideally without losing any significant fraction of the work that Q had done prior to suspend. Beyond supporting mixed-priority DBMS workloads, suspend/resume of queries, or dataflows in general, is important in many other settings: Utility and grid: Dataflows now run frequently on computational utilities and grids composed of autonomous resources. When the owner of resources wants to use them, dataflows running on these resources must release control quickly, and migrate to other resources. Software rejuvenation: Benefits of software rejuvenation, the practice of rebooting enterprise computing systems regularly, are now recognized widely. Reboot is critical when performance degrades due to resource exhaustion caused by resource leaks. Suspend and resume is important in this setting because (1) the challenge of predicting completion times accurately makes it difficult to schedule task completion to match a rejuvenation schedule; (2) when performance degrades, it may not be cost-effective to wait for all dataflows to complete before rebooting.
12872505
Value-Based Notification Conditions in Large-Scale Publish/Subscribe Systems
We address the problem of providing scalable support for subscriptions with personalized value-based notification conditions in wide-area publish/subscribe systems. Notification conditions can be fine-tuned by subscribers, allowing precise and flexible control of when events are delivered to the subscribers. For example, a user may specify that she should be notified if and only if the price of a particular stock moves outside a "radius" around her last notified value. Naive techniques for handling notification conditions are not scalable. It is challenging to share subscription processing and notification dissemination of subscriptions with personalized value-based notification conditions, because two subscriptions may see two completely different sequences of notifications even if they specify the same radius. We develop and experimentally evaluate scalable processing and dissemination techniques for these subscriptions. Our approach uses standard network substrates for notification dissemination, and avoids pushing complex application processing into the network. Compared with other alternatives, our approach generates orders of magnitude lower network traffic, and incurs lower server 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.
46223238
Environmental impact assessment using the evidential reasoning approach
Environmental impact assessment (EIA) problems are often characterised by a large number of identified environmental factors that are qualitative in nature and can only be assessed on the basis of human judgments, which inevitably involve various types of uncertainties such as ignorance and fuzziness. So, EIA problems need to be modelled and analysed using methods that can handle uncertainties. The evidential reasoning (ER) approach provides such a modelling framework and analysis method. In this paper the ER approach will be applied to conduct EIA analysis for the first time. The environmental impact consequences are characterized by a set of assessment grades that are assumed to be collectively exhaustive and mutually exclusive. All assessment information, quantitative or qualitative, complete or incomplete, and precise or imprecise, is modelled using a unified framework of a belief structure. The original ER approach with a recursive ER algorithm will be introduced and a new analytical ER algorithm will be investigated which provides a means for using the ER approach in decision situations where an explicit ER aggregation function is needed such as in optimisation problems. The ER approach will be used to aggregate multiple environmental factors, resulting in an aggregated distributed assessment for each alternative policy. A numerical example and its modified version are studied to illustrate the detailed implementation process of the ER approach and demonstrate its potential applications in EIA.
32059093
A Genetic Algorithm for Physical Mapping Problems
In this paper, we study a genetic algorithm for solving physical mapping problem. First, the physical mapping problem is transferred to an optimization problem by incorporating biological knowledge and limitations into the objective function. Based on the idea of genetic algorithms, the proposed approach integrates Edge Assembly Crossover (EAX) and Inver-over genetic operators to get the optimal solution. We analyze essential components of the proposed approach as well as implementation details. Our approach is then applied to some widely used test sets and simulated data, real data of this problem. Experimental results indicate that the new approach performs efficiently and precisely to solve physical mapping problem.
10779366
An efficient adaptive focused crawler based on ontology learning
The enormous growth of the World Wide Web has made it important to perform resource discovery efficiently. Consequently, several new ideas have been proposed; among them a key technique is focused crawling which is able to crawl particular topical portions of the World Wide Web quickly without having to explore all Web pages. In this paper, we present an intelligent focused crawler algorithm in which we embed ontology to evaluate the page's relevance to the topic. Compared with other algorithms using domain knowledge, our algorithm can evolve the ontology automatically during crawl process. Considering the instinct characteristics of the ontology, propagation has also been imported to accelerate the evolution of the ontology. We applied our approaches in several tasks and provided an empirical evaluation which has shown promising results.
37194320
The evidential reasoning approach for multi-attribute decision analysis under interval uncertainty
Abstract The evidential reasoning (ER) approach is a method for multiple attribute decision analysis (MADA) under uncertainties. It improves the insightfulness and rationality of a decision making process by using a belief decision matrix (BDM) for problem modelling and the Dempster–Shafer (D–S) theory of evidence for attribute aggregation. The D–S theory provides scope and flexibility to deal with interval uncertainties or local ignorance in decision analysis, which is not explored in the original ER approach and will be investigated in this paper. Firstly, interval uncertainty will be defined and modelled in the ER framework. Then, an extended ER algorithm, IER, is derived, which enables the ER approach to deal with interval uncertainty in assessing alternatives on an attribute. It is proved that the original ER algorithm is a special case of the IER algorithm. The latter is demonstrated using numerical examples.
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.