369741
EXPedite: a system for encoded XML processing
As XML becomes an increasingly popular format for information exchange, the efficient processing of broadcast XML data on a constrained device (for example, a cell phone or a PDA) becomes a critical task. In this paper we present the EXPedite system: a new model of data processing in an information exchange environment, which "migrates" the power of the data-sending server to receivers for efficient processing. It consists of a simple and general encoding scheme for servers, and streaming query processing algorithms on encoded XML stream for data receivers with constrained computing abilities. Experiments show the impressive performance of EXPedite.
5650965
L-Tree: A Dynamic Labeling Structure for Ordered XML Data
With the ever growing use of XML as a data representation format, we see an increasing need for robust, high performance XML database systems While most of the recent work focuses on efficient XML query processing, XML databases also need to support efficient updates To speed up query processing, various labeling schemes have been proposed However, the vast majority of these schemes have poor update performance In this paper, we introduce a dynamic labeling structure for XML data: L-Tree and its order-preserving labeling scheme with O(log n) amortized update cost and O(log n) bits per label L-Tree has good performance on updates without compromising the performance of query processing We present the update algorithm for L-Tree and analyze its complexity.
2511748
QPIAD: Query Processing over Incomplete Autonomous Databases
Incompleteness due to missing attribute values (aka "null values") is very common in autonomous Web databases, on which user accesses are usually supported through mediators. Traditional query processing techniques that focus on the strict soundness of answer tuples often ignore tuples with critical missing attributes, even if they wind up being relevant to a user query. Ideally we would like the mediator to retrieve such relevant uncertain answers and gauge their relevance by accessing their likelihood of being relevant answers to the query. However, the autonomous nature of the databases poses several challenges, such as the restricted access privileges, limited query patterns, and sensitivity of database and network resource consumption in the Web environment. We introduce a novel query rewriting and optimization framework QPIAD that tackles these challenges to retrieve relevant uncertain answers. Our technique involves reformulating the user query based on approximate functional dependencies (AFDs) among the database attributes and ranking these queries using value distributions learned from naive Bayes classifiers. Empirical studies demonstrate the effectiveness of our approach in retrieving relevant uncertain answers with high precision, high recall and manageable cost.
37282807
Testing Web Services Using Progressive Group Testing
This paper proposes progressive group testing techniques to test large number of Web services (WS) available on Internet. At the unit testing level, the WS with the same functionality are tested in group using progressively increasing number of test cases. A small number of WS that scored best will be integrated into the real environment for operational testing. At the integration testing level, many composite services will be constructed and tested by group integration testing. The results of group testing at both unit and integration levels are verified by weighted majority voting mechanisms. The weights are based on the reliability history of the WS under test. A case study is designed and implemented, where the dependency among the test cases in WS is analyzed and used to generate progressive layers of test cases.
3132727
Query Processing over Incomplete Autonomous Databases
Incompleteness due to missing attribute values (aka "null values") is very common in autonomous web databases, on which user accesses are usually supported through mediators. Traditional query processing techniques that focus on the strict soundness of answer tuples often ignore tuples with critical missing attributes, even if they wind up being relevant to a user query. Ideally we would like the mediator to retrieve such possible answers and gauge their relevance by accessing their likelihood of being pertinent answers to the query. The autonomous nature of web databases poses several challenges in realizing this objective. Such challenges include the restricted access privileges imposed on the data, the limited support for query patterns, and the bounded pool of database and network resources in the web environment. We introduce a novel query rewriting and optimization framework QPIAD that tackles these challenges. Our technique involves reformulating the user query based on mined correlations among the database attributes. The reformulated queries are aimed at retrieving the relevant possible answers in addition to the certain answers. QPIAD is able to gauge the relevance of such queries allowing tradeoffs in reducing the costs of database query processing and answer transmission. To support this framework, we develop methods for mining attribute correlations (in terms of Approximate Functional Dependencies), value distributions (in the form of Naive Bayes Classifiers), and selectivity estimates. We present empirical studies to demonstrate that our approach is able to effectively retrieve relevant possible answers with high precision, high recall, and manageable cost.
8136301
Architecture classification for SOA-based applications
The architecture of SOA-based applications is different from traditional software architecture where the architecture is mainly static. The architecture of an SOA-based application is dynamic, i.e., the application may be composed at runtime using existing services. Thus SOA has provided a new direction for software architecture study, where the architecture is determined at runtime and architecture can be dynamically changed at runtime to meet the new software requirements. This paper proposes an architecture classification scheme for SOA-based applications. Using this classification, several well-known SOA-based applications are reviewed including the architectures proposed and adopted by major computer companies and standard organizations. The architecture classification provides a unified way to evaluate a variety of architectures for SOA-based applications
31504377
Mapping DTDs to object-oriented schemas
As a subset of SGML, XML (Extensible Markup Language) is becoming a dominant standard for representing data in the World Wide Web and therefore the efficient treatment of XML data is important for information transfer over a network. One way towards this goal is to integrate database technology into document management and bring the very nature of database systems into this area, such as query processing, efficient management of secondary storage, version and update control, etc. We propose a new method to map DTDs (Document Type Definition) into object-oriented schemas. In this way, any complicated DTD structure can be treated uniformly. That is, using the concepts of classification/generalization and aggregation of the object-oriented model, any complex nested and recursive structure in a DTD as well as multiple appearance of element types can be represented. These issues can not be addressed if we map a DTD into a relational schema.
17642380
Evolutionary Modeling of Ordinary Differential Equations for Dynamic Systems
This paper presents a new idea of modeling one-dimensional dynamic systems by higher-order ordinary differential equation (HODE) models in stead of by the ARMA models used in the traditional time series analysis. Accordingly, based on the idea of hybrid evolutionary modeling, we modify the HEMA algorithm in (Cao et al., 1998a; Cao et al., 1998b) to approach the modeling problem of HODEs for dynamic systems. Two applications of time series are used to demonstrate its effectiveness and advantages.
5374807
Automated Planning and Scheduling using Calculus of Variations in Discrete Space
In this paper, we propose new dominance relations that can speed up significantly the solution process of planning problems formulated as nonlinear constrained dynamic optimization in discrete time and space. We first show that path dominance in dynamic programming cannot be applied when there are general constraints that span across multiple stages, and that node dominance, in the form of Euler-Lagrange conditions developed in optimal control theory in continuous space, cannot be extended to that in discrete space. This paper is the first to propose efficient node-dominance relations, in the form of local saddle-point conditions in each stage of a discrete-space planning problem, for pruning states that will not lead to locally optimal paths. By utilizing these dominance relations, we present efficient search algorithms whose complexity, despite exponential, has a much smaller base as compared to that without using the relations. Finally, we demonstrate the performance of our approach by integrating it in the ASPEN planner and show significant improvements in CPU time and solution quality on some spacecraft scheduling and planning benchmarks.
45104603
A Similarity Search Algorithm to Predict Protein Structures
Accurate prediction of protein structures is very important for many applications such as drug discovery and biotechnology. Building side chains is an essential to get any reliable prediction of the protein structure for any given a protein main chain conformation. Most of the methods that predict side chain conformations use statistically generated data from known protein structures. It is a computationally intractable problem to search suitable side chains from all possible rotamers simultaneously using information of known protein structures. Reducing the number of possibility is a main issue to predict side chain conformation. This paper proposes an enumeration based similarity search algorithm to predict side chain conformations. By introducing “beam search” technique, a significant number of unrelated side chain rotamers can easily be eliminated. As a result, we can search for suitable residue side chains from all possible side chain conformations.
406686
Filtering of shrew DDoS attacks in frequency domain
The shrew distributed denial of service (DDoS) attacks are periodic, bursty, and stealthy in nature. They are also known as reduction of quality (RoQ) attacks. Such attacks could be even more detrimental than the widely known flooding DDoS attacks because they damage the victim servers for a long time without being noticed, thereby denying new visitors to the victim servers, which are mostly e-commerce sites. Thus, in order to minimize the huge monetary losses, there is a pressing need to effectively detect such attacks in real-time. Unfortunately, effective detection of shrew attacks remains an open problem. In this paper, we meet this challenge by proposing a new signal processing approach to identifying and detecting the attacks by examining the frequency-domain characteristics of incoming traffic flows to a server. A major strength of our proposed technique is that its detection time is less than a few seconds. Furthermore, the technique entails simple software or hardware implementations, making it easily deployable in a real-life network environment