10306775
Piggyback Statistics Collection for Query Optimization: Towards a Self-Maintaining Database Management System
A database management system (DBMS) performs query optimization based on statistical information about data in the underlying database. Out-of-date statistics may lead to inefficient query processing in the system. The existing utility method, which collects statistics in batch mode, suffers from drawbacks such as heavy administrative burden, high system load and tardy updates. In this paper, we study approaches to performing statistical analysis on the fly during query execution, taking advantage of data already resident in main memory. We propose a framework for on-the-fly statistics collection, which we term piggybacking, and analyze the tradeoffs of piggybacking various statistics collection techniques on top of query execution plans. We present a multiple-granularity interleaving algorithm to integrate a set of piggyback operations with an execution plan, and show how the algorithm can be incorporated into an existing query optimizer. Our experiments demonstrate that useful statistics can be obtained via the piggyback method with a small overhead.
6977187
Global Query Optimization Based on Multistate Cost Models for a Dynamic Multidatabase System
Global query optimization in a multidatabase system (MDBS) is a challenging issue since some local optimization information such as local cost models may not be available at the global level due to local autonomy. It becomes even more difficult when dynamic environmental factors are taken into consideration. In our previous work, a qualitative approach was suggested to build so-called multistate cost models to capture the performance behavior of a dynamic multidatabase environment. It has been shown that a multistate cost model can give a good cost estimate for a query run in any contention state in the dynamic environment. In this paper, we present a technique to perform query optimization based on multistate cost models for a dynamic MDBS. Two relevant algorithms are proposed. The first one selects a set of representative system environmental states for generating an execution plan with multiple versions for a given query at compile time, while the second one efficiently determines the best version to invoke for the query at run time. Experiments demonstrate that the proposed technique is quite promising for performing global query optimization in a dynamic MDBS. Compared with related work on dynamic query optimization, our approach has an advantage of avoiding the high overhead for modifying or re-generating an execution plan for a query based on dynamic run-time information.
42927182
Exploiting common subqueries for complex query optimization
As database technology is applied to more and more application areas, user queries on a database become more and more complex. Existing query optimization techniques were not developed for dealing with complex queries and may suffer from some serious problem such as intolerably long optimization time and poor optimizing results. To tackle this challenge, we introduce a new technique to improve the quality of complex query optimization in this paper. The key idea is to exploit the common subqueries that often appear in a complex query and reuse the optimization work done for each common subquery. An algorithm to identify common subqueries efficiently and generate a high-quality execution plan for a given complex query is proposed. The complexity of the algorithm is analyzed. Experiments demonstrate that this proposed polynomial-time technique is quite promising in optimizing complex queries for a database management system.
5120838
Multiple-granularity interleaving for piggyback query processing
Piggyback query processing is a new technique, described in [24], intended to perform additional useful computation (e.g., database statistics collection) during normal query processing, taking full advantage of data resident in main memory. Different types of benecial piggybacking have been identifed and studied, but how to efficiently integrate piggyback operations with a given user query is still an open issue. In this paper, we propose a technique of multiple-granularity interleaving to efficiently integrate multiple piggyback operations with a given query at different levels of data granularity. We introduce an algebraic notation to capture the main characteristics of data flows in a database management system (DBMS), facilitating the study of piggybacking and enabling the automated integration of piggyback operations and user queries in a DBMS supporting the piggyback method. Various integration techniques are introduced to facilitate multiple-granularity interleaving including merging shared work, augmenting user queries, and downgrading piggyback operations. A set of transformations and heuristics are suggested that preserve the semantics of a user query, while efficiently interleaving the operations. Our preliminary experiments indicate that interleaving at proper levels of data granularity is key to the efficient implementation of the piggyback method.
9544892
OBJ-NET: An Object Oriented System Design Tool
Computer-based Systems are used in a wide range of complex systems like automobile assembly lines, power plants, etc. These systems consist of heterogeneous subsystems having a multitude of interactions with other subsystems and environments. Designing software for such systems is a difficult task due to the inherent complexity both at conceptual and implementation levels. When developing a large system, the constituent subsystems may be developed separately. Those subsystems may work well on their own, but may fail to work together with other subsystems and fail to respond to interfacing events. This paper presents OBJ-NET, an object oriented system design tool, which provides a suitable framework for the specification and simulation of complex dynamic systems. The theoretical basis of OBJ-NET is from Category Theory and Petri Nets. OBJ-NET helps users to integrate complex systems by modeling a system as a hierarchy of components. It accepts the flow of control from one set of objects to another and simulates the flow of control among the various components of the system. This will allow a user to validate the correctedness of design and interactively change the design to refine the working of the system. This paper describes the various components of OBJ-NET in detail and illustrates the application of OBJ-NET using, as a working example, the specification and simulation of an Automotive Dashboard System.
27173883
Query optimization using fuzzy set theory for multidatabase systems
One of the challenges for global query optimization in a multidatabase system (MDBS) is that some local optimization information may not be accurately known at the global level because of local autonomy. In this paper, we introduce a fuzzy query optimization approach that is based on fuzzy set theory, introduced by Zadeh in the 1960s, to tackle the challenge. We describe the problem of fuzzy query optimization and compare the fuzzy optimization approach with the traditional (crisp) optimization approach. We show that the fuzzy approach has a better chance to find a good execution strategy for a query than the crisp approach in an MDBS environment, but the complexity of the former may grow exponentially as the complexity of the later. To reduce the complexity, we use a weighted k-approximate fuzzy value to approximate every fuzzy value during fuzzy query optimization. It is proven that the improved fuzzy approach has the same order of complexity as the crisp approach.
2629654
Period Optimization for Hard Real-time Distributed Automotive Systems
The complexity and physical distribution of modern active-safety automotive applications requires the use of distributed architectures. These architectures consist of multiple electronic control units (ECUs) connected with standardized buses. The most common configuration features periodic activation of tasks and messages coupled with run-time priority-based scheduling. The correct deployment of applications on such architectures requires end-to- end latency deadlines to be met. This is challenging since deadlines must be enforced across a set of ECUs and buses, each of which supports multiple functionality. The need for accommodating legacy tasks and messages further complicates the scenario. In this work, we automatically assign task and message periods for distributed automotive systems. This is accomplished by leveraging schedulability analysis within a convex optimization framework to simultaneously assign periods and satisfy end-to-end latency constraints. Our approach is applied to an industrial case study as well as an example taken from the literature and is shown to be both effective and efficient.
1583464
Multimodal fusion using learned text concepts for image categorization
Conventional image categorization techniques primarily rely on low-level visual cues. In this paper, we describe a multimodal fusion scheme which improves the image classification accuracy by incorporating the information derived from the embedded texts detected in the image under classification. Specific to each image category, a text concept is first learned from a set of labeled texts in images of the target category using Multiple Instance Learning [1]. For an image under classification which contains multiple detected text lines, we calculate a weighted Euclidian distance between each text line and the learned text concept of the target category. Subsequently, the minimum distance, along with low-level visual cues, are jointly used as the features for SVM-based classification. Experiments on a challenging image database demonstrate that the proposed fusion framework achieves a higher accuracy than the state-of-art methods for image classification.
3022232
SAT sweeping with local observability don't-cares
SAT sweeping is a method for simplifying an AND/inverter graph (AIG) by systematically merging graph vertices from the inputs towards the outputs using a combination of structural hashing, simulation, and SAT queries. Due to its robustness and efficiency, SAT sweeping provides a solid algorithm for Boolean reasoning in functional verification and logic synthesis. In previous work, SAT sweeping merges two vertices only if they are functionally equivalent. In this paper we present a significant extension of the SAT-sweeping algorithm that exploits local observability don't-cares (ODCs) to increase the number of vertices merged. We use a novel technique to bound the use of ODCs and thus the computational effort to find them, while still finding a large fraction of them. Our reported results based on a set of industrial benchmark circuits demonstrate that ODC-based SAT sweeping results in significantly more graph simplification with great benefit for Boolean reasoning with a moderate increase in computational effort
9839662
JPEG encoding on the Intel MXP5800: a platform-based design case study
Multimedia systems are becoming increasingly complex and concurrent. The platform-based design (PBD) methodology (Keutzer et al., 2000) tackles these issues by recommending the use of formal models, carefully defined abstraction layers and the separation of concerns. Models of computation (Lee and Sangiovanni-Vincentelli, 1998) (MoCs) can be used within this methodology to enable specialized synthesis and verification techniques. In this paper, these concepts are leveraged in an industrial case study: the JPEG encoder application deployed on the Intel MXP5800 imaging processor. The modeling is carried out in the Metropolis (Balarin et al., 2003) design framework. We show that the system-level model using our chosen model of computation allows performance estimation within 5% of the actual implementation. Moreover, the chosen MoC is amenable to automation, which enables future synthesis techniques.
31373005
Long-Term Temporal Features for Conversational Speech Recognition
The automatic transcription of conversational speech, both from telephone and in-person interactions, is still an extremely challenging task. Our efforts to recognize speech from meetings is likely to benefit from any advances we achieve with conversational telephone speech, a topic of considerable focus for our research. Towards both of these ends, we have developed, in collaboration with our colleagues at SRI and IDIAP, techniques to incorporate long-term (~500 ms) temporal information using multi-layered perceptrons (MLPs). Much of this work is based on prior achievements in recent years at the former lab of Hynek Hermansky at the Oregon Graduate Institute (OGI), where the TempoRAl Pattern (TRAP) approach was developed. The contribution here is to present experiments showing: 1) that simply widening acoustic context by using more frames of full band speech energies as input to the MLP is suboptimal compared to a more constrained two-stage approach that first focuses on long-term temporal patterns in each critical band separately and then combines them, 2) that the best two-stage approach studied utilizes hidden activation values of MLPs trained on the log critical band energies (LCBEs) of 51 consecutive frames, and 3) that combining the best two-stage approach with conventional short-term features significantly reduces word error rates on the 2001 NIST Hub-5 conversational telephone speech (CTS) evaluation set with models trained using the Switchboard Corpus.