4676671
The Hybrid Digital Tree: A New Indexing Technique for Large String Databases
There is an increasing demand for efficient indexing techniques to support queries on large string databases. In this paper, a hybrid RAM/disk-based index structure, called the Hybrid Digital tree (HD-tree), is proposed. The HD-tree keeps internal nodes in the RAM to minimize the number of disk I/Os, while maintaining leaf nodes on the disk to maximize the capability of the tree for indexing large databases. Experimental results using real data have shown that the HD-tree outperformed the Prefix B-tree for prefix and substring searches. In particular, for distinctive random queries in the experiments, the average number of disk I/Os was reduced by a factor of two to three, while the running time was reduced in an order of magnitude.
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.
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.
15918293
A piggyback method to collect statistics for query optimization in database management systems
A database management system (DBMS) performs query optimization based on statistical information about data in the underlying data-base. Out-of-date statistics may lead to inefficient query processing in the system. Existing solutions to this problem have some drawbacks such as heavy administrative burden, high system load, and tardy updates. To overcome these drawbacks, our new approach, called the piggyback method, is proposed in this paper. The key idea is to piggyback some additional retrievals during the processing of a user query in order to collect more up-to-date statistics. The collected statistics are used to optimize the processing of subsequent queries. To specify the piggybacked queries, basic piggybacking operators are defined in this paper. Using the operators, several types of piggybacking such as vertical, horizontal, mixed vertical and horizontal, and multi-query piggybacking are introduced. Statistics that can be obtained from different access methods by applying piggyback analysis during query processing are also studied. In order to meet users' different requirements for the associated overhead, several piggybacking levels are suggested. Other related issues including initial statistics, piggybacking time, and parallelism are also discussed. Our analysis shows that the piggyback method is promising in improving the quality of query optimization in a DBMS as well as in reducing the user's administrative burden for maintaining an efficient DBMS.
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.
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.
13298742
Using visual features for anti-spam filtering
Unsolicited commercial email (UCE), also known as spam, has been a major problem on the Internet. In the past, researchers have addressed this problem as a text classification or categorization problem. However, as spammers' techniques continue to evolve and the genre of email content becomes more and more diverse, text-based anti-spam approaches alone are no longer sufficient. In this paper, we propose a novel anti-spam system which utilizes visual clues, in addition to text information in the email body, to determine whether a message is spam. We analyze a large collection of spam emails containing images and identify a number of useful visual features for this application. We then propose using one-class support vector machines (SVM) as the underlying base classifier for anti-spam filtering. The experimental results demonstrate that the proposed system can add significant filtering power to the existing text-based anti-spam filters.
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
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.
3281684
Efficient octilinear steiner tree construction based on spanning graphs
Octilinear interconnect is a promising technique to shorten wire lengths. We present two practical heuristic octilinear Steiner tree (OSMT) algorithms in the paper. They are both based on octilinear spanning graphs. The one by edge substitution (OST-E) has a worst case running time of O(nlogn) and similar performance as the batched greedy algorithm[9]. The other one by triangle contraction (OST-T) has a small increase in running time and better performance. Experiments on both industry and random test cases are conducted.
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.