2007 technical reports

In this paper we describe a top-down join enumeration algorithm that is optimal with respect to the join graph. We present performance results demonstrating that a combination of optimal enumeration with search strategies such as branch-and-bound yields an algorithm significantly faster than those previously described in the literature. Although our algorithm enumerates the search space top-down, it does not rely on transformations and thus retains much of the architecture of traditional dynamic programming. As such, this work provides a migration path for existing bottom-up optimizers to exploit top-down search without drastically changing to the transformational paradigm.

We introduce a new class of nondeterministic semiautomata: A nondeterministic semiautomaton S is predictable if there exists a positive integer k such that, if S knows the present input a and the next k inputs, then the transition under a is deterministic. Nondeterminism may occur only when the length of the unread input is less than k+1. We develop a comprehensive theory of predictable semiautomata. Using a novel semiautomaton, called the core, we present a test for predictability. We then introduce the predictor semiautomaton, based on a look-ahead semiautomaton, that is essentially deterministic. We describe two ways of using the predictor to simulate a nondeterministic semiautomaton. The first simulation predicts the set of states reachable by every prefix of the input word as long as the prefix is in the language of the semiautomaton. The second simulation is similar, but it stops as soon as it infers that the input word is not in the language of the semiautomaton. Moreover, the membership of a word in the language of a semiautomaton can be decided completely deterministically. Finally, we show that, if a semiautomaton with n states over a one-letter alphabet is k-predictable, k being the smallest such integer, then k is at most n-1, and this bound can be reached. For semiautomata over arbitrary alphabets, k is at most (n²-n)/2, and this bound can be reached for a suitable input alphabet.

Keywords: Automaton, delegator, look-ahead, nondeterminism, predictor, selector, semiautomaton, simulation

This paper introduces an approach to constructing information systems based on enterprise service architectures (ESAs). An ESA model is specified using declarative business process modelling or workflow commands in conjunction with service framework instances where the business process model and the instances are captured in a data structure. A service framework is an outline of different types such as reports, databases, agents, diagrams and maps and an instance is produced by completing a framework's adaptation points. Adaptation points are defined by an adaptation interface specified in a declarative language and presented through forms. The business process or workflow is specified similarly. An automatic transformation is then applied to convert the model into an operational information system. This approach can be viewed as model-driven software development without the necessity of writing code to complete the implementation. Thus, we avoid the symptoms of architectural drift that occur when applications evolve independently from their model. The control structure is declarative and separate, clearly delineating the concerns, thus making it easier to address future anticipated, unanticipated and crosscutting concerns. We have created tools to support this approach, and although many of the tools are general, we have concentrated our efforts on the web because of its pervasive nature. Thus, we have produced the web-based Informatics Development Environment (WIDE) technology, a set of tools and processes used to transform a model based on ESA principles into a web-based information system. We have designed and implemented over 30 operational web-based systems to validate our approach.

We present a new language feature, specified as an extension to Java. The feature is a form of dispatch which includes and subsumes multimethods, but which is not as powerful as general predicate dispatch. It is, however, intended to be more practical and easier to use than the latter. The extension, dubbed OOMatch, allows method parameters to be specified as patterns, which are matched against the arguments to the method call. When matches occur, the method applies; if multiple methods apply, the method with the more specific pattern overrides the others.

The pattern matching is very similar to that found in the "case" constructs of many functional languages (ML, for example), with an important difference: functional languages normally allow pattern matching over variant types (and other primitives such as tuples), while OOMatch allows pattern matching on Java objects. Indeed, the wider goal here is the study of the combination of functional and object-oriented programming paradigms. Of special importance, we ensure that matching can occur while retaining the complete control of class designers to prevent implementation details (such as private variables) from being exposed to clients of the class.

We here present both an informal "tutorial" description of OOMatch, as well as a formal specification of the language, and a proof that the conditions specified guarantee run-time safety.

Uncertainty pervades many domains in our lives. Current real-life applications, e.g., location tracking using GPS devices or cell phones, multimedia feature extraction, and sensor data management, deal with different kinds of uncertainty. Finding the nearest neighbour objects to a given query point is an important query type in these applications.
In this paper, we study the problem of finding objects with the highest marginal probability of being the nearest neighbours to a query object. We adopt a general uncertainty model allowing for data and query uncertainty. Under this model, we define new query semantics, and provide several efficient evaluation algorithms. We analyze the cost factors involved in query evaluation, and present novel techniques to address the trade-offs among these factors. We give multiple extensions to our techniques including handling dependencies among data objects, and answering threshold queries. We conduct an extensive experimental study to evaluate our techniques on both real and synthetic data.

Model checking is a technique for verifying that a finite-state concurrent system is correct with respect to its specification. In bounded model checking (BMC), the system is unfolded until a given depth, and translated into a CNF formula. A SAT solver is then applied to the CNF formula, to find a satisfying assignment. Such a satisfying assignment, if found, demonstrates an error in the model of the concurrent system. Description Logic (DL) is a family of knowledge representation formalisms, for which reasoning is based on tableaux techniques. We show how Description Logic can serve as a natural setting for representing and solving a BMC problem. We formulate a bounded model checking problem as a consistency problem in the DL dialect ALC I . Our formulation results in a compact representation of the model, one that is linear in the size of the model description, and does not involve any unfolding of the model. Experimental results, using the DL reasoner FaCT++, significantly improve on a previous approach that used DL reasoning for model checking.

Abstract: The 3D structure of protein sequence A can be assembled by the substructures corresponding to small segments of A. A sequence segment does not take on all the structural fragments and thus it is desirable to build a short customized structural candidate list for each sequence segment. For each sequence segment, these substructures are its "specific structural alphabet". The smaller these candidate lists are, the faster the protein structure can be constructed; the more accurate these candidate lists are, the more accurate the final protein structure will be. A major obstacle in protein structure prediction is to construct a small set of structural candidates for each segment such that the native structure can be rebuilt from these structural candidates accurately.

Based on integer linear programming and incorporating extra structural information, a software package FragShaver is developed. We have made significant progress in overcoming the abovementioned obstacle:

1. Comparing our package to the Rosetta's fragment selection method, at threshold 1A and structural fragment length 9, the position coverage is improved from 56.4% to 79.1% for $\beta$-sheet, and from 55.5% to 67.9% for loop, while reducing the candidate list size from 25 to 10 simultaneously. By using candidate list size 25, our method improves Rosetta's position coverage of $\beta$-sheet from 56.5% to 89.6% and the position coverage of loop from 55.5% to 78.1%. At 1.5A, we achieve position coverage 96.7%.

2 Applying our method to Kolodny's independent library, our experiment indicates that our method is capable of identifying a small subset of structural candidates for a given sequence segment to achieve the same accuracy as using the whole library, reducing Kolodny's library size from 200 to 25 at the same accuracy.

The distributed denial of service attacks are a major threat on Internet and detecting this kind of attack as far as possible from the victim in order to save resources is a real challenge. We propose a new framework to deal with this problem which is based on Intrusion Prevention System (IPS) deployed on a Internet Service Provider (ISP) level. The key point is to use compressed metrics based on the routing rules in order to extract suspect traffics thanks to a collaboration between routers on the same path and finally confirm an attack by using the IPS on different path but on the same level (number of hops before the potential victim). The main metric we use is the frequency of a rule but we decide to use the entropy too. We are able to detect a change in the traffic and define what rules changes a lot and have a too higher frequency. After the share of the different belief of each IPS is needed to determine the very potential attack before confirm it by computing the packets rate. There are three main advantages of our proposition. The first is that because you select the rules, you can analyze precisely these rules and be sure that there is an attack. The second is that we save a lot of resources (network, CPU and storage) thanks to the choice of the metrics and the selection of rule. Finally because we determine the attack as far as possible the final host can save resources too because the attack traffic is blocked early and congestion can be avoided.

In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the '90s (A.V. Aho) and rigorously in 2003 by Campeanu, Salomaa and Yu, when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. We give a positive answer to this question; and for doing so, we propose a new class of machines - regex automata systems (RAS) - which are equivalent to regex. Among others, these machines provide a consistent and convenient method of implementing regex in practice. We also prove, as a consequence of this closure property, that several anthological languages, such as the mirror language, the language of palindromes and the language of balanced words are not regex languages.

Keywords: Extended Regular Expression, Regex Automata System, Regex

The intersection of large ordered sets is a common problem in the context of the evaluation of boolean queries to a search engine. In this paper we propose several improved algorithms for computing the intersection of sorted arrays, and in particular for searching sorted arrays in the intersection context. We perform an experimental comparison with the algorithms from the previous studies from Demaine, López-Ortiz and Munro [ALENEX 2001], and from Baeza-Yates and Salinger [SPIRE 2005]; in addition, we implement and test the intersection algorithm from Barbay and Kenyon [SODA 2002] and its randomized variant [SAGA 2003].

We consider both the random data-set from Baeza-Yates and Salinger, the Google queries used by Demaine et al., a corpus provided by Google and a larger corpus from the TREC Terabyte 2006 efficiency query stream, along with its own query log. We measure the performance both in terms of the number of comparisons and searches performed, and in terms of the CPU time on two different architectures. Our results confirm or improve the results from both previous studies in their respective context (comparison model on real data and CPU measures on random data), and extend them to new contexts. In particular we show that value-based search algorithms perform well in posting lists in terms of the number of comparisons performed.

XML database systems are expected to handle increasingly complex queries over increasingly large and highly structured XML databases. An important problem that needs to be solved for these systems is how to choose the best set of indexes for a given workload. In this paper, we present an XML Index Advisor that solves this XML index recommendation problem, and has the key characteristic of being tightly coupled with the query optimizer. We rely on the optimizer to enumerate candidate indexes and to estimate the benefit gained from potential index configurations. We expand the set of candidate indexes obtained from the query optimizer to include more general indexes that can be useful for queries other than those in the training workload. To recommended an index configuration, we introduce two new search algorithms. The first algorithm finds the best set of indexes for the specific training workload, and the second algorithm finds a general set of indexes that can benefit the training workload as well as other similar workloads. We have implemented our XML Index Advisor in a prototype version of IBM DB2 9, which supports both relational and XML data, and we experimentally demonstrate the effectiveness of our advisor using this implementation.

(i) we show a stronger lower bound for substring search problem via compression extending results of Demaine and L{\'o}pez-Ortiz (SODA '01);

(ii) improve the results of Gal and Miltersen (ICALP '03) by showing a bound on the redundancy needed by the polynomial evaluation problem that is linear in terms of the information-theoretic minimum storage required by a polynomial.

In this report we study the problem of reconstructing orthogonal polyhedra from a putative vertex set, i.e., we are given a set of points and want to find an orthogonal polyhedron for which this is the set of vertices. We are especially interested in testing whether such a polyhedron is unique. Since this is not the case in general, we focus on orthogonally convex polyhedra, and give an $O(n log n)$ algorithm to find the answer. We then consider the case where the given set of points may be rotated beforehand. For 2D, we prove uniqueness and provide an $O(n log n)$ algorithm to obtain the answer, which can then be used for an $O(n2 log n)$ algorithm in 3D.

Automatic physical database design tools rely on ``what-if'' interfaces to the query optimizer to estimate the execution time of the training query workload under different candidate physical designs. The tools use these what-if interfaces to recommend physical designs that minimize the estimated execution time of the input training workload. Minimizing estimated execution time alone can lead to designs that are not robust to query optimizer errors and workload changes. In particular, if the optimizer makes errors in estimating the execution time of the workload queries, then the recommended physical design may actually degrade the performance of these queries. In this sense, the physical design is risky. Furthermore, if the production queries are slightly different from the training queries, the recommended physical design may not benefit them at all. In this sense, the physical design is not general. We define risk and generality as two new measures aimed at evaluating the robustness of a proposed physical database design, and we show how to extend the objective function being optimized by a generic physical design tool to take these measures into account. We have implemented a physical design advisor in PostqreSQL, and we use it to experimentally demonstrate the usefulness of our approach. We show that our two new metrics result in physical designs that are more robust, which means that the user can implement them with a higher degree of confidence. This is particularly important as we move towards truly zero-administration database systems in which there is not the possibility for a DBA to vet the recommendations of the physical design tool before applying them.

Development and maintenance of implicit invocation systems is not as well understood and supported as the development of explicit invocation systems. The situation is aggravated in systems that allow the composition of functionality developed by different organizations, potentially using different programming languages and methodologies. In this document, we categorize the various ways in which implicit invocation systems can define, bind to, announce, subscribe, and deliver events. We also categorize the architectures and topologies of implicit invocation systems. The purpose of the categorization is to increase the understanding of the type of requirements that these systems impose on software development practices. As the categories are introduced, documented representative invocation systems are discussed in order to illustrate the types of systems that fall under each given category. Our categorization applies to systems as varied as active databases, aspect-oriented applications, and distributed heterogeneous event-based systems.

The main contribution of the paper is to show that an appropriate infrastructure for next-generation ubiquitous and pervasive computing systems can be found in the Jabber open-source community. Jabber, now standardized as XMPP, was originally conceived as an open-source alternative to proprietary instant-messaging systems. Its design, architecture, and implementation provide a rich, extensible, standardized selection of concepts, protocols, servers, components, and clients. We show how Jabber provides an excellent foundation for the implementation of smart spaces, and a robust platform on which to build a ubiquitous-computing ecology, while supporting ambitious research goals in second-generation smart spaces. We also discuss various proof-of-concept prototypes that we have developed to validate our argument. Finally, we demonstrate how Jabber has allowed us to pursue research in pervasive computing without requiring substantial effort in a start-up phase.

In this paper, we begin by showing that naive scheduling approaches can be far from optimal. We then show that although optimal schedules can be found using either linear programming or network flow, these classical approaches are infeasible in CPU- and memory-constrained mobile devices. This motivates our novel hill-climbing approach that exploits problem structure to optimally schedule application messages over multiple NICs assuming perfect knowledge of future connectivity. We prove mathematically that our algorithm is correct.

Detailed performance measurements show that our algorithm finds optimal solutions 10-100 times faster than the simplex method and network flow. We also describe an implementation of our solution in a J2ME-based scheduler that runs on laptops, smartphones and PDAs, demonstrating its effectiveness in a realistic setting.

We motivate the design of the SMS-NIC through a characterization of SMS using workloads consisting of bursts of messages between sender and receiver. This analysis differs from previous SMS studies by focusing on transmission patterns that differ from normal cell phone use. Through this characterization we show that message delay and message loss are affected by the transmission order, the time of day has minimal effect on transmission rate, delay, and loss, and that losses and high delays significantly outweigh the rate or message reordering.