Data dependency in multiple classifier systems

In this paper, the data dependency of aggregation modules in multiple classifier system is being investigated. We first propose a new categorization scheme, in which combining methods are grouped into data-independent, implicitly data-dependent and explicitly data-dependent. It is argued that data-dependent approaches present the highest potential for improved performance. In this study, we intend to provide a comprehensive investigation of this argument and explore the impact of data dependency on the performance of multiple classifiers. We evaluate this impact based on two criteria, prediction accuracy and stability. In addition, we examine the effect of class imbalance and uneven data distribution on these two criteria. This paper presents the findings of an extensive set of comparative experiments. Based on the findings, it can be concluded that data-dependent aggregation methods are generally more stable and less sensitive to class imbalance. In addition, data-dependent methods exhibited superior or identical generalization ability for most of the data sets.     

Succinctness of pattern-based schema languages for XML

Martens et al. defined a pattern-based specification language equivalent in expressive power to the widely adopted XML Schema definitions (XSDs). This language consists of rules of the form $(r,s)$ where r and s are regular expressions and can be seen as a type-free extension of DTDs with vertical regular expressions. Sets of such rules can be interpreted both in an existential or universal way. In the present paper, we study the succinctness of both semantics w.r.t. each other and w.r.t. the common abstraction of XSDs in terms of single-type extended DTDs. The investigation is carried out relative to three kinds of vertical pattern languages: regular, linear, and strongly linear patterns. We also consider the complexity of the simplification problem for each of the considered pattern-based schemas.     

Extended Regular Expressions: Succinctness and Decidability

Most modern implementations of regular expression engines allow the use of variables (also called backreferences). The resulting extended regular expressions (which, in the literature, are also called practical regular expressions, rewbr, or regex) are able to express non-regular languages. The present paper demonstrates that extended regular-expressions cannot be minimized effectively (neither with respect to length, nor number of variables), and that the tradeoff in size between extended and “classical” regular expressions is not bounded by any recursive function. In addition to this, we prove the undecidability of several decision problems (universality, regularity, and cofiniteness) for extended regular expressions. Furthermore, we show that all these results hold even if the extended regular expressions contain only a single variable.     

Efficient dependency tracking for relevant events in concurrent systems

In a concurrent system with N processes, vector clocks of size N are used for tracking dependencies between the events. Using vectors of size N leads to scalability problems. Moreover, association of components with processes makes vector clocks cumbersome and inefficient for systems with a dynamic number of processes. We present a class of logical clock algorithms, called chain clock, for tracking dependencies between relevant events based on generalizing a process to any chain in the computation poset. Chain clocks are generally able to track dependencies using fewer than N components and also adapt automatically to systems with dynamic number of processes. We compared the performance of Dynamic Chain Clock (DCC) with vector clock for multithreaded programs in Java. With 1 % of total events being relevant events, DCC requires 10 times fewer components than vector clock and the timestamp traces are smaller by a factor of 100. For the same case, although DCC requires shared data structures, it is still 10 times faster than vector clock in our experiments. We also study the class of chain clocks which perform optimally for posets of small width and show that a single algorithm cannot perform optimally for posets of small width as well as large width.This is a revised and extended version of the paper “Efficient Dependency Tracking for Relevant Events in Shared Memory System” which appeared in PODC 2005. Anurag Agarwal received his B.Tech. degree in computer science and engineering from the Indian Institute of Technology, Kanpur in 2003. He is currently a student in the Department of Computer Science at the University of Texas, Austin. His research interests include distributed systems, program verification and security. Vijay K. Garg received his B.Tech. degree in computer science from the Indian Institute of Technology, Kanpur in 1984 and M.S. and Ph.D. degrees in electrical engineering and computer science from the University of California at Berkeley in 1985 and 1988, respectively. He is currently a full professor in the Department of Electrical and Computer Engineering and the director of the Parallel and Distributed Systems Laboratory at the University of Texas, Austin. His research interests are in the areas of distributed systems and discrete event systems. He is the author of the books Concurrent and Distributed Computing in Java (Wiley & Sons, 2004), Elements of Distributed Computing (Wiley & Sons, 2002), Principles of Distributed Systems (Kluwer, 1996) and a co-author of the book Modeling and Control of Logical Discrete Event Systems (Kluwer, 1995). Prof. Garg is also an IEEE Fellow.     

Software rejuvenation in cluster computing systems with dependency between nodes

Software rejuvenation is a preventive and proactive fault management technique that is particularly useful for counteracting the phenomenon of software aging, aimed at cleaning up the system internal state to prevent the occurrence of future failure. The increasing interest in combing software rejuvenation with cluster systems has given rise to a prolific research activity in recent years. However, so far there have been few reports on the dependency between nodes in cluster systems when software rejuvenation is applied. This paper investigates the software rejuvenation policy for cluster computing systems with dependency between nodes, and reconstructs an stochastic reward net model of the software rejuvenation in such cluster systems. Simulation experiments and results reveal that the software rejuvenation strategy can decrease the failure rate and increase the availability of the cluster system. It also shows that the dependency between nodes affects software rejuvenation policy. Based on the theoretic analysis of the software rejuvenation model, a prototype is implemented on the Smart Platform cluster computing system. Performance measurement is carried out on this prototype, and experimental results reveal that software rejuvenation can effectively prevent systems from entering into disabled states, and thereby improving the ability of software fault-tolerance and the availability of cluster computing systems.     

Succinctness of regular expressions with interleaving,intersection and counting

In this paper, we study the succinctness of regular expressions (REs) extended with interleaving, intersection and counting operators. We show that in a translation from REs with interleaving to standard regular expressions a double exponential size increase cannot be avoided. We also consider the complexity of translations to finite automata. We give a tight exponential lower bound on the translation of REs with intersection to NFAs, and, for each of the three classes of REs, we show that in a translation to a DFA a double exponential size increase cannot be avoided. Together with known results, this gives a complete picture of the complexity of translating REs extended with interleaving, intersection or counting into (standard) regular expressions, NFAs, and DFAs.     

An empirical approach to evaluating dependency locality in hierarchically structured software systems

In software development, especially component-based software development, dependency locality states that relevant software components should be at shorter distances than irrelevant components. This principle is used together with modularity and hierarchy to guide the design of large-scale complex software systems. In previous work, dependency locality and its correlation with design quality were studied by statically measuring the interactions between software components. This paper presents an empirical approach to evaluating the hierarchical structure of software systems through mining their revision history. Two metrics, spatial distance and temporal distance, are adapted to measure the dependencies between software components. The correlation of spatial distance and temporal distance between software components represents a factor that influences system design quality. More specially, a well designed system hierarchy should have a significant positive correlation while a non-significant positive correlation or a negative correlation would signify design flaws. In an application of this approach, we use Mantel test to study the dependency locality of six software systems from Apache projects.     

Discernibility matrix simplification with new attribute dependency functions for incomplete information systems

Recently, many researches have been done on attribute dependency degree models. In this work, we bring forward three attribute dependency functions for incomplete information systems and investigate their basic properties in detail. Afterward, we apply the proposed models to twelve data sets from the UCI repository of machine learning databases. Finally, using the proposed functions, we perform the discernibility matrix simplification of incomplete information systems. The experimental results show that our proposed functions are more flexible to calculate the degree of each conditional attribute related to the decision attribute for incomplete information systems.     

Context-sensitive dependency pairs

Termination is one of the most interesting problems when dealing with context-sensitive rewrite systems. Although a good number of techniques for proving termination of context-sensitive rewriting (CSR) have been proposed so far, the adaptation to CSR of the dependency pair approach, one of the most powerful techniques for proving termination of rewriting, took some time and was possible only after introducing some new notions like collapsing dependency pairs, which are specific for CSR. In this paper, we develop the notion of context-sensitive dependency pair (CSDP) and show how to use CSDPs in proofs of termination of CSR. The implementation and practical use of the developed techniques yield a novel and powerful framework which improves the current state-of-the-art of methods for automatically proving termination of CSR.     

Efficient order dependency detection

Order dependencies (ODs) describe a relationship of order between lists of attributes in a relational table. ODs can help to understand the semantics of datasets and the applications producing them. They have applications in the field of query optimization by suggesting query rewrites. Also, the existence of an OD in a table can provide hints on which integrity constraints are valid for the domain of the data at hand. This work is the first to describe the discovery problem for order dependencies in a principled manner by characterizing the search space, developing and proving pruning rules, and presenting the algorithm Order, which finds all order dependencies in a given table. Order traverses the lattice of permutations of attributes in a level-wise bottom-up manner. In a comprehensive evaluation, we show that it is efficient even for various large datasets.     

Sorted dependency insertion grammars

An enhanced generative formalism is proposed based on the combination of two features: contextual derivation (as in Marcus contextual grammars) and sorted dependency structures (as in dependency grammars). The model is related to a variant of restarting automaton with rewriting and deletion. Preliminary results on the generative power as well as closure and decidability properties of the new model are presented.     

Simultaneous path-following and vibration control for uncertain nonlinear flexible mechanical systems without dependency on oscillatory mathematical model

Multibody System Dynamics - In this paper, a novel multiobjective algorithm for simultaneous path-following control (PFC) of multivariable flexible dynamical systems and maintaining...     

Repairing XML functional dependency violations

We study the problem of repairing XML functional dependency violations by making the smallest modifications in terms of repair cost. Our cost model assigns a weight to each leaf node in the XML document, and the cost of a repair is measured by the total weight of the modified nodes. We define an optimum repair as the repair with the minimum cost among all of the repairs. We prove lower and upper bounds for the optimum XML repair problem. We show that, in practice, it is beyond reach to find the optimum repairs; this problem is already NP-complete for a setting with a fixed DTD, a fixed set of functional dependencies, and equal weights for all of the nodes in the XML document. Instead, we provide an efficient two-step heuristic method to repair XML functional dependency violations. First, the initial violations are captured and fixed by leveraging the conflict hypergraph. Second, the remaining conflicts are resolved by modifying the violating nodes and their related nodes called determinants in a way that guarantees no new violations. We implement our method and evaluate it on synthetic and real-life data. The experimental results demonstrate that our algorithm scales well and is effective at improving data quality.     

Automating the dependency pair method

Developing automatable methods for proving termination of term rewrite systems that resist traditional techniques based on simplification orders has become an active research area in the past few years. The dependency pair method of Arts and Giesl is one of the most popular such methods. However, there are several obstacles that hamper its automation. In this paper we present new ideas to overcome these obstacles. We provide ample numerical data supporting our ideas.     

Quantifier elimination by dependency sequents

We consider the problem of existential quantifier elimination for Boolean CNF formulas. We present a new method for solving this problem called derivation of dependency-sequents (DDS). A dependency-sequent (D-sequent) is used to record that a set of variables is redundant under a partial assignment. We introduce the join operation that produces new D-sequents from existing ones. We show that DDS is compositional, i.e., if our input formula is a conjunction of independent formulas, DDS automatically recognizes and exploits this information. We introduce an algorithm based on DDS and present experimental results demonstrating its potential.     

Compressing table data with column dependency

Tables are two-dimensional arrays given in row-major order. Such data have unique features that could be exploited for effective compression. For example, tables often represent database files with rows as records so certain columns or fields in a table may have few distinct values. This means that simply transposing the data can make it compress better. Further, a large source of information redundancy in a table is the correlation among columns representing related types of data. This paper formalizes the notion of column dependency as a way to capture this information redundancy across columns and discusses how to automatically compute and use it to substantially improve table compression.     

Data dependency graphs for Ada programs

A compositional method of constructing data dependency graphs for Ada programs is presented. These graphs are useful in a program development environment for analyzing data dependencies and tracking information flow within a program. Graphs for primitive program statements are combined together to form graphs for larger program units. Composition rules are described for iteration, recursion, exception handling, and tasking, as well as for simpler Ada constructs. The correctness of the construction and the practicality of the technique are discussed