Found 357 results.
Listing from newest to oldest
TR-CS-2012-01
On the Viability of Compression for Reducing the Overheads of Checkpoint/Restart-based Fault Tolerance
Dewan Ibtesham, Dorian Arnold, Patrick G. Bridges, Kurt B. Ferreira, and Ron
Brightwell
The increasing size and complexity of high performance computing (HPC) systems have lead to major concerns over fault frequencies and the mechanisms necessary to tolerate these faults. Previous studies have shown that state-of-the-field checkpoint/restart mechanisms will not scale sufficiently for future generation systems. Therefore, optimizations that reduce checkpoint overheads are necessary to keep checkpoint/restart mechanisms effective. In this work, we demonstrate that checkpoint data compression is a feasible mechanism for reducing checkpoint commit latency and storage overheads. Leveraging a simple model for checkpoint compression viability, we show: (1) checkpoint data compression is feasible for many types of scientific applications expected to run on extreme scale systems; (2) checkpoint compression viability scales with checkpoint size; (3) user-level versus system-level checkpoints bears little impact on checkpoint compression viability; and (4) checkpoint compression viability scales with application process count. Lastly, we describe the impact checkpoint compression might have on projected extreme scale systems.
TR-CS-2011-02
Exploiting Task Relatedness for Multitask Learning of Bayesian Network
Structures
Diane Oyen and Terran Lane
We address the problem of learning Bayesian networks for a collection of unsupervised tasks when limited data is available and a metric of the relatedness of tasks is given. We exploit this valuable information about task-relatedness to learn more robust structures for each task than those learned with a standard multitask learning algorithm. Our approach is the first network structure learning algorithm that addresses zero-data learning; where no training data is available for a task, but data for related tasks and information about how the tasks are related is given. This paper describes our Task Relationship Aware Multitask (TRAM) algorithm for learning Bayesian networks. The inputs to the algorithm are task-specific sets of data and an undirected graph representing a metric of task-relatedness. TRAM regularizes over the task-relatedness graph to output a network for each task, each of which is biased toward the structures of related tasks. We empirically compare, using synthetic and neuroimaging data, TRAM with three baseline methods and show that task-relatedness knowledge impacts all learning methods. Only TRAM effectively uses this knowledge to learn more robust structures.
TR-CS-2011-01
Physical Evolutionary Computation
Eric Schulte and David H. Ackley
Although evolutionary computation (EC) is an "embarrassingly parallel"
process, it is often deployed on essentially serial machines, and even
its parallel implementations typically retain the globally
synchronized and regimented style typical of serial computation. We
explore a radical 'physical evolutionary computation' (PEC)
hardware/software framework that is based on real time and real space
rather than an abstract sequence of events--for example, the mutation
rate is specified in Hertz. PEC supports massive and reconfigurable
parallelism, using a prototype hardware 'tile' that begins
evolutionary computation within three seconds of applying
power. Although each tile is a simple computer by today's standards,
tiles can be plugged together into a wide variety of size and shape
computing grids--even while the computation is running.
We present our initial explorations with this framework, defining
mechanisms for representing and sharing problems, and mapping between
computational spaces and physical ones. We discuss advantages of
PEC--such as extremely robust operation--as well as its challenges, and
touch on some unexpected, and potentially useful, level-crossing
interactions that can be explored when the embedding of the
computational within the physical is made real.
TR-CS-2010-08
Exploiting Task Relatedness to Learn Multiple Bayesian Network Structures
Diane Oyen and Terran Lane
We address the problem of learning multiple Bayesian network structures for experimental data where the experimental conditions define relationships among datasets. A metric of the relatedness of datasets, or tasks, can be described which contains valuable information that we exploit to learn more robust structures for each task. We represent the task-relatedness with an undirected graph. Our method uses a regularization framework over this task-relatedness graph to learn Bayesian network structures for each task that are smoothed toward the structures of related tasks. Experiments on synthetic data and real fMRI experiment data show that this method learns structures which are close to ground truth, when available, and which generalize to holdout data better than an existing multitask learning method, learning networks independently, and learning one global network for all tasks.
TR-CS-2010-07
Leaving Timing Channel Fingerprints in Hidden Service Log Files
Bilal Shebaro, Fernando Perez-Gonzalez, and Jedidiah R. Crandall
Hidden services are anonymously hosted services that can be accessed
over an anonymity network, such as Tor. While most hidden services
are legitimate, some host illegal content. There has been a fair
amount of research on locating hidden services, but an open problem is
to prove that a physical machine, once confiscated, was in fact the
machine that had been hosting the illegal content. In this paper we
assume that the hidden service logs requests with some timestamp, and
give experimental results for leaving an identifiable fingerprint in
this log file as a timing channel that can be recovered from the
timestamps. In 60 minutes, we are able to leave a 36-bit fingerprint
that can be reliably recovered.
The main challenges are the packet delays caused by the anonymity
network that requests are sent over and the existing traffic in the
log from the actual clients accessing the service. We give data to
characterize these noise sources and then describe an implementation
of timing-channel fingerprinting for an Apache web-server based hidden
service on the Tor network, where the fingerprint is an additive
channel that is superencoded with a Reed-Solomon code for reliable
recovery. Finally, we discuss the inherent tradeoffs and possible
approaches to making the fingerprint more stealthy.
TR-CS-2010-06
Enabling rational democratic decision-making with collective belief models and game theoretic analysis
Kshanti Greene, Joe Kniss and George Luger
We introduce a new approach to aggregating the beliefs and preferences of many individuals to form models for democratic decision-making. Traditional social choice functions used to aggregate beliefs and preferences attempt to find a single consensus model, but produce inconsistent results when a stalemate between opposing opinions occurs. Our approach combines the probabilistic beliefs of many individuals using Bayesian decision networks to form collectives such that the aggregate of each collective, or collective belief has rational behavior. We first extract the symbolic preference order used in social choice theory from each individual's quantitative Bayesian beliefs. We then show that if a group of individuals share a preference order, their aggregate will uphold principles of rationality defined by social choice theorists. These groups will form the collectives, from which we can extract the Pareto optimal solutions. By representing the situation competitively as opposed to forcing cooperation, our approach identifies the situations for which no single consensus model exists, and returns a rational set of models and their corresponding solutions. Using an election simulation, we demonstrate that our approach more accurately predicts of the behavior of a large group of decision-makers than a single consensus approach that exhibits unstable behavior.
TR-CS-2010-05
Tracking Address and Control Dependencies for Full-System Information Flow Measurement
Mohammed I. Al-Saleh and Jedidiah R. Crandall
Dynamic information flow tracking (DIFT) works by tagging (or tainting) data and tracking it to measure the information flow throughout the system. Existing DIFT systems have limited support for address and control dependencies, and therefore cannot track information flow within a full system without addressing these very challenging dependencies in an application-specific fashion. A general way to track address and control dependencies will allow DIFT to be applied in a much wider variety of applications than is now possible, ranging from data provenance to behavioral malware analysis.
Tracking address and control dependencies is largely a problem of stability: if these flows of information are tagged then the tainting scheme becomes unstable and soon the entire system becomes tainted, but if they are not tagged then information that should be tainted is not. In this paper, we propose relaxed static stability dynamic information flow tracking as a way to track address and control dependencies in a general fashion without compromising stability of the DIFT system. To the best of our knowledge, the system presented in this paper is the first DIFT system to measure full-system information flow with general support for tracking all address and control dependencies within the system. As a motivating example, in this paper we measure the amount of information flow between tainted sources and the control path of the CPU for a variety of scenarios. Our results demonstrate that tracking address and control dependencies is both: (1) necessary for meaningful measurements of the information flow in a real system, and (2) made possible by a relaxed static stability approach. Besides tracking address and control dependencies, other key research challenges addressed in this paper include how to handle loop constructs and how to prevent memory locations that are written once and read many times from leading to DIFT system instability.
TR-CS-2010-04
Circuit partitions and #P-complete products of inner products
Cristopher Moore and Alexander Russell
We present a simple, natural #P-complete problem. Let G be a directed graph, and let k be a positive integer. We define q(G;k) as follows. At each vertex v, we place a k-dimensional complex vector x_v. We take the product, over all edges (u,v), of the inner product
TR-CS-2010-03
Idle Port Scanning and Non-interference Analysis of Network Protocol Stacks Using Model Checking
Roya Ensafi, Jong Chun Park, Deepak Kapur, and Jedidiah R. Crandall
Idle port scanning uses side-channel attacks to bounce scans off of a "zombie" host to stealthily scan a victim IP address and determine if a port is open or closed, or infer IP-based trust relationships between the zombie and victim. In this paper, we present results from building a transition system model of a network protocol stack for an attacker, victim, and zombie, and testing this model for non-interference properties using model checking. We present two new methods of idle scans in this paper that resulted from our modeling effort, both of which have been verified through implementation. One is based on TCP RST rate limiting and the other on SYN caches. The latter does not require the attacker to send any packets to the victim on the port to be scanned, not even forged packets. This gives the attacker additional capabilities beyond known idle scan techniques, such as the ability to scan ports that are blocked by a firewall or locate hosts on trusted networks, to which the attacker is not able to route packets, and infer their operating system. This is in contrast to the one currently known method of idle scan in the literature, which is based on non-random IPIDs.
For the future design of network protocols, we suggest that a notion of trusted vs. untrusted networks and hosts be made explicit in the protocol stack all the way down to the IP layer. This will enable shared, limited resources to be divided in a way that achieves non-interference and makes idle scans impossible. Using symbolic model checking, we verify that separate RST rate limitations for trusted vs. untrusted hosts achieves non-interference (without the SYN cache). Using bounded model checking we model a split SYN cache structure with separate buffers for trusted and untrusted hosts and prove non-interference to a depth of 1000 transitions. Because each transition is roughly a packet, this means that idle scans are eliminated by the split SYN cache for all practical purposes.
TR-CS-2010-02
Active Learning for Hidden Attributes in Networks
Xiao Ran Yan, Yao Jia Zhu, Jean-Baptiste Rouquier, and Cristopher Moore
In many networks, vertices have hidden attributes that are correlated with the network's topology. For instance, in social networks, people are more likely to be friends if they are demographically similar. In food webs, predators typically eat prey of lower body mass.
We explore a setting in which the network's topology is known, but these attributes are not. If each vertex can be queried, learning the value of its hidden attributes---but only at some cost---then we need an algorithm which chooses which vertex to query next, in order to learn as much as possible about the attributes of the remaining vertices. We assume that the network is generated by a probabilistic model, but we make no assumptions about the assortativity or disassortativity of the network. We then query the vertex with the largest mutual information between its type and that of the others (a well-known approach in active learning) or with the largest average agreement between two independent samples of the Gibbs distribution which agree on its type.
We test these approaches on two networks with known attributes, the Karate Club network and a food web of species in the Weddell Sea. In several cases, we found that the average agreement algorithm performs better than mutual information. The algorithms appear to explore the network intelligently, first querying vertices at the centers of communities, and then querying vertices at the boundaries between communities.
TR-CS-2010-01
Uncovering Hidden Phylogenetic Consensus
Nicholas D. Pattengale, Krister M. Swenson, Bernard M.E. Moret
Many of the steps in phylogenetic reconstruction can be confounded by "rogue" taxa, taxa that cannot be placed with assurance anywhere within the tree -- whose location within the tree, in fact, varies with almost any choice of algorithm or parameters. Phylogenetic consensus methods, in particular, are known to suffer from this problem. In this paper we provide a novel framework in which to define and identify rogue taxa. In this framework, we formulate a bicriterion optimization problem that models the net increase in useful information present in the consensus tree when certain taxa are removed from the input data. We also provide an effective greedy heuristic to identify a subset of rogue taxa and use it in a series of experiments, using both pathological examples described in the literature and a collection of large biological datasets. As the presence of rogue taxa in a set of bootstrap replicates can lead to deceivingly poor support values, we propose a procedure to recompute support values in light of the rogue taxa identified by our algorithm; applying this procedure to our biological datasets caused a large number of edges to change from "unsupported" to "supported" status, indicating that many existing phylogenies should be recomputed and reevaluated to reduce any inaccuracies introduced by rogue taxa.
TR-CS-2009-11
A Replication-based Approach to Parallelizing Protocol Stacks
Donour Sizemore & Patrick G. Bridges
Current multi-core network protocol stack designs use lock-based and scheduler-based approaches to leverage multiple processors. Unfortunately, these approaches limit protocol stack scalability on multi-core systems both for high-bandwidth connections and large numbers of concurrent connections. In this paper, we propose a new approach to parallelizing network protocol stacks based on state replication, as opposed to locking or scheduler-based segregation to dedicated processors. This approach replicates protocol and connection state across processors; each replica is responsible for fully processing only a subset of incoming packets and consistency between these replicas is explicitly managed. This minimizes interprocessor locking and synchronization costs that limit current designs. It also allows for protocol implementations that weaken consistency requirements by using existing protocol-based recovery mechanisms to recover from replica inconsistency. We also describe our approach to implementing this protocol stack architecture and discuss the open research questions this approach raises to network stack and protocol design.
TR-CS-2009-10
Knowledge-Based Probabilistic Reasoning from Expert Systems to Graphical Models
George F. Luger, Chayan Chakrabarti
An important research enterprise for the Artificial Intelligence community since the 1970s has been the design of expert or "knowledge-based" systems. These programs used explicitly encoded human knowledge, often in the form of a production rule system, to solve problems in the areas of diagnostics and prognostics. The earliest research/development program in expert systems was created by Professor Edward Feigenbaum at Stanford University (Buchanan and Shortliff 1984). Because the expert system often addresses problems that are imprecise and not fully proposed, with data sets that are often inexact and unclear, the role of various forms of probabilistic support for reasoning is important.
The 1990s saw radical new approaches to the design of automated reasoning/diagnostic systems. With the creation of graphical models, the explicit pieces of human knowledge (of the expert system) were encoded into causal networks, sometimes referred to as Bayesian belief networks (BBNs). The reasoning supporting these networks, based on two simplifying assumptions (that reasoning could not be cyclic and that the causality supporting a child state would be expressed in the links between it and its parent states) made BBN reasoning quite manageable computationally. In recent years the use of graphical models has replaced the traditional expert system, especially in situations where reasoning was diagnostic and prognostic, i.e., extending from concrete situations to the best explanations for their occurrence. This type reasoning is often termed abductive.
In this chapter we first (Section 1) present the technology supporting the traditional knowledge-based expert system, including the production system for reasoning with rules. Next (Section 2), we discuss Bayesian inference, and the adoption of simplifying techniques such as the Stanford Certainty Factor Algebra. We then (Section 3) introduce graphical models, including the assumptions supporting the use of Bayesian belief networks (BBN), and present an example of BBN reasoning. We conclude (Section 4) with a brief introduction of a next
generation system for diagnostic reasoning with more expressive forms of the BBN.
TR-CS-2009-09
Palacios and Kitten: High Performance Operating Systems For Scalable Virtualized and Native Supercomputing
John Lange, Kevin Pedretti, Trammell Hudson, Peter Dinda, Zheng Cui, Lei Xia, Patrick Bridges, Steven Jaconette, Mike Levenhagen, Ron Brightwell, Patrick Widener
Palacios and Kitten are new open source tools that enable applications, whether ported or not, to achieve scalable high performance on large machines. They provide a thin layer over the hardware to support both full-featured virtualized environments and native codebases. Kitten is an OS under development at Sandia that implements a lightweight kernel architecture to provide predictable behavior and increased flexibility on large machines, while also providing Linux binary compatibility. Palacios is a VMM that is under development at Northwestern University and the University of New Mexico. Palacios, which can be embedded into Kitten and other OSes, supports existing, unmodified applications and operating systems by using virtualization that leverages hardware technologies. We describe the design and implementation of both Kitten and Palacios. Our benchmarks show that they provide near native, scalable performance. Palacios and Kitten provide an incremental path to using supercomputer resources that is not performance-compromised.
TR-CS-2009-08
Satisficing the masses: Applying game theory to large-scale,democratic decision problems
Kshanti A. Greene, Joseph M. Kniss, George F. Luger, Carl R. Stern (Management Sciences Inc.)
We present ongoing research on large-scale decision models in which there are many invested individuals. We apply our unique Bayesian belief aggregation approach to decision problems, taking into consideration the beliefs and utilities of each individual. Instead of averaging all beliefs to form a single consensus, our aggregation approach allows divergence in beliefs and utilities to emerge. In decision models this divergence has implications for game theory-enabling the competitive aspects in an apparent cooperative situation to emerge. Current approaches to belief aggregation assume cooperative situations by forming one consensus from diverse beliefs. However, many decision problems have individuals and groups with opposing goals, therefore this forced consensus does not accurately represent the decision problem. By applying our approach to the topical issue of stem cell research using input from many diverse individuals, we analyze the behavior of a decision model including the groups of agreement that emerge. We show how to find the Pareto optimal solutions, which represent the decisions in which no group can do better without another group doing worse. We analyze a range of solutions, from attempting to "please everybody," with the solution that minimizes all emerging group's losses, to optimizing the outcome for a subset of individuals. Our approach has the long-reaching potential to help define policy and analyze the effect of policy change on individuals.
TR-CS-2009-07
Learning Probabilistic Networks of Condition-Specific Response: Digging Deep in Yeast Stationary Phase
Sushmita Roy, Terran Lane, Margaret Werner-Washburne
Condition-specific networks are functional networks of genes describing molecular behavior under different conditions such as environmental stresses, cell types, or tissues. These networks frequently comprise parts that are unique to each condition, and parts that are shared among related conditions. Existing approaches for learning condition-specific networks typically identify either only differences or similarities across conditions. Most of these approaches first learn networks per condition independently, and then identify similarities and differences in a postlearning step. Such approaches have not exploited the shared information across conditions during network learning.
We describe an approach for learning condition-specific networks that simultaneously identifies the shared and unique subgraphs during network learning, rather than as a post-processing step. Our approach learns networks across condition sets, shares data from conditions, and leads to high quality networks capturing biologically meaningful information.
On simulated data from two conditions, our approach outperformed an existing approach of learning networks per condition independently, especially on small training datasets. We further applied our approach to microarray data from two yeast stationary-phase cell populations, quiescent and non-quiescent. Our approach identified several functional interactions that suggest respiration-related processes are shared across the two conditions. We also identified interactions specific to each population including regulation of epigenetic expression in the quiescent population, consistent with known characteristics of these cells. Finally, we found several high confidence cases of combinatorial interaction among single gene deletions that can be experimentally tested using double gene knock-outs, and contribute to our understanding of differentiated cell populations in yeast stationary phase.
TR-CS-2009-06
Conditions for Additional Roots from Maximal-Rank Minors of Macaulay Matrices
Deepak Kapur, Manfred Minimair
Necessary conditions, under which the maximal-rank minors of a (possibly singular) Macaulay matrix of a polynomial system vanish, are analyzed. It is shown that the vanishing of the maximal-rank minors of the Macaulay matrix of a system of parametric polynomials under specialization is a necessary condition for the specialized polynomials to have an additional common root even when the parametric system has common roots without any specialization of parameters. For such a parametric system, its resultant is identically zero. A theorem of independent interest also gives a degree bound from which the Hilbert function of a certain zero-dimensional polynomial system that is not necessarily a complete intersection, as defined by Macaulay in his 1913 paper, becomes constant. These results are not only of theoretical interest, but it extends the class of parametric polynomial systems whose zeros can be analyzed using matrix based resultant formulations. Particularly, the main result has applications in areas where conditions for additional common roots of polynomial systems with generic roots are needed, such as in implicitization of surfaces with base points and in reasoning about geometric objects.
TR-CS-2009-05
Coregulation Analysis via Spectra of a Hypercube
Sergey M. Plis, Vamsi K. Potluru, Sushmita Roy,Terran Lane
Traditional clustering treats data as instances with sets of attributes and commonly uses pairwise criteria. Graphical models, on the other hand, treat the data as random variables (attributes) with respective samples and allow multivariate interaction among these variables. It is common in graphical model learning to sacrifice multivariate interactions for the sake of a detailed (in)dependence structure. We present an alternative approach. We partition random variables into coregulated clusters focusing on arbitrary multivariate relations and ignoring their detailed structure. Multivariate interactions among groups of random variables are hard to compute and even the best estimators are not very fast. To address this, we show that the problem can be cast in the form suitable to the recently proposed framework for smooth function approximation over a hypercube. This formulation allows us to approximate the multiway clustering objective with a few samples, thus providing runtime benefits. We also improve the running time of the original approximation framework, and demonstrate the new clustering framework using a stochastic global search algorithm.
TR-CS-2009-04
Fast Bayesian Network Structure Search Using
Gaussian Processes
Blake Anderson and Terran Lane
In this paper we introduce two novel methods for performing Bayesian network structure search that make use of Gaussian Process regression. Using a relatively small number of samples from the posterior distribution of Bayesian networks, we are able to find an accurate function approximator based on Gaussian Processes. This allows us to remove our dependency on the data during the search and leads to massive speed improvements without sacrificing performance. We use our function approximator in the context of Hill Climbing, a local-score based search algorithm, and in the context of a global optimization technique based on response surfaces. We applied our methods to both synthetic and real data. Results show that we converge to networks of equal score to those found by traditional Hill Climbing, but at a fraction of the total time.
TR-CS-2009-03
Approaches to the Network-Optimal Partition Problem for fMRI Data
Benjamin Yackley, Terran Lane
Although much MRI research has been performed using existing atlases of brain regions, it is possible that these regions, which are anatomically determined, are not the truly optimal way to divide brain activity into parts. The goal of this research is to discover a way to take existing fMRI data and use it as a basis for a clustering method that would divide the brain into functional partitions independent of anatomy. Since Bayesian networks over anatomical regions have been shown to be informative models of brain activity, this paper describes attempts to solve a mathematical problem which is an abstraction of the above goal: to partition a group of variables (the voxels of the MRI data) into clusters such that the optimal Bayesian network given the clustering is as "good" as possible.
TR-CS-2009-02
A Term Rewriting Approach to the Automated Termination Analysis of Imperative Programs
Stephan Falke and Deepak Kapur
An approach based on term rewriting techniques for the automated termination analysis of imperative programs operating on integers is presented. An imperative programs is transformed into rewrite rules with constraints from quantifier-free Presburger arithmetic. Any computation in the imperative program corresponds to a rewrite sequence, and termination of the rewrite system thus implies termination of the imperative program. Termination of the rewrite system is analyzed using a decision procedure for Presburger arithmetic that identifies possible chains of rewrite rules, and automatically generated polynomial interpretations are used to show finiteness of such chains. An implementation of the approach has been evaluated on a large collection of imperative programs, thus demonstrating its effectiveness and practicality.
TR-CS-2009-01
Termination of Context-Sensitive Rewriting with Built-In Numbers and Collection Data Structures
Stephan Falke and Deepak Kapur
Context-sensitive rewriting is a restriction of rewriting that can be used to elegantly model declarative specification and programming languages such as Maude. Furthermore, it can be used to model lazy evaluation in functional languages such as Haskell. Building upon our previous work on an expressive and elegant class of rewrite systems (called CERSs) that contains built-in numbers and supports the use of collection data structures such as sets or multisets, we consider context-sensitive rewriting with CERSs in this paper. This integration results in a natural way for specifying algorithms in the rewriting framework. In order to prove termination of this kind of rewriting automatically, we develop a dependency pair framework for context-sensitive rewriting with CERSs, resulting in a flexible termination method that can be automated effectively. Several powerful termination techniques are developed within this framework. An implementation in the termination prover AProVE has been successfully evaluated on a large collection of examples.
TR-CS-2008-15
Agreeing to disagree: Leveraging consensus and divergence in Bayesian belief aggregation
Kshanti A. Greene and George F. Luger
We present a new approach for combining the beliefs of many individuals using graphical models. Existing Bayesian belief aggregation methods break several theoretical assumptions for Bayesian reasoning. More practically, existing opinion pool functions that compute a single value to represent the belief of all contributors do not represent reality well, especially in cases where there are many diverse opinions. Divergence is a natural result of combining opinions from individuals with different beliefs, backgrounds and experiences. Instead of forming a single consensus value that will average out this diversity, we find clusters of agreement for each probability distribution and propagate the cluster means throughout the network during inference. We utilize a social network that tracks the agreement between individuals and the normalized graph cut algorithm to find emerging groups of consensus in the agreement network. We leverage the agreement that occurs across multiple belief estimates to help reduce the complexity that may arise as the means are propagated throughout a belief network. By monitoring agreement over time we may also expose the variety of backgrounds that will help explain divergence in belief. This paper discusses the approach, background and our motives for ongoing research.
TR-CS-2008-14
Learning structurally consistent undirected probabilistic graphical models
Sushmita Roy, Terran Lane, Margaret Werner-Washburne
In many real-world domains, undirected graphical models such as Markov random fields provide a more natural representation of the dependency structure than directed graphical models. For example, Bayesian networks cannot explicitly capture cyclic dependencies which occur commonly in real-world networks such as in biology. Unfortunately, structure learning of undirected graphs using likelihood-based scores remains difficult because of the intractability of computing the partition function. We describe a new Markov random field structure learning algorithm which is motivated by canonical parameterization of Abbeel et al. We improve on their parameterization by learning per-variable canonical factors, which makes our algorithm suitable for domains with hundreds of nodes. Our algorithm is similar to learning dependency networks, but the learned structure is guaranteed to be consistent, and, therefore represents a consistent joint probability distribution. We compare our algorithm against several algorithms for learning undirected and directed models on simulated and real datasets from the biology domain. Our algorithm frequently outperforms existing algorithms, producing higher-quality structures, suggesting that enforcing consistency during structure learning is beneficial for learning undirected graphs.
TR-CS-2008-13
Using Structured Knowledge Representation for Context-Sensitive Probabilistic Modeling
Nikita A. Sakhanenko, George F. Luger
We propose a context-sensitive probabilistic modeling system (COSMOS) that reasons about a complex, dynamic environment through a series of applications of smaller, knowledge-focused models representing contextually relevant information. COSMOS uses a failure-driven architecture to determine whether a context is supported, and consequently whether the current model remains applicable. The individual models are specified through sets of structured, hierarchically organized probabilistic logic statements using transfer functions that are then mapped into a representation supporting stochastic inferencing. We demonstrate COSMOS using data from a mechanical pump system.
TR-CS-2008-12
Model Failure and Context Switching Using Logic-based Stochastic Models
Nikita A. Sakhanenko, George F. Luger
We define a notion of context that represents invariant, stable-over-time behavior in an environment and we propose an algorithm for detecting context changes in a stream of data. A context change is captured through model failure when a probabilistic model, representing current behavior, is no longer able to fit the newly encountered data. We specify stochastic models using a logic-based probabilistic modeling language and use its learning mechanisms to identify context changes. We also discuss how our algorithm can be incorporated into a failure-driven context-switching probabilistic modeling framework and demonstrate several examples of its application.
TR-CS-2008-11
Efficient Representations for Set-Sharing Analysis
Eric Trias, Jorge Navas, Elena S. Ackley, Stephanie Forrest, Manuel V. Hermenegildo
The Set-Sharing domain has been widely used to infer at
compile-time interesting properties of logic programs such as
occurs-check reduction, automatic parallelization, and finite-tree
analysis. However, performing abstract unification in this domain
requires a closure operation that increases the number of sharing
groups exponentially. Much attention has been given in the literature
to mitigating this key inefficiency in this otherwise very useful
domain. In this paper we present a novel approach to Set-Sharing: we
define a new representation that leverages the complement (or
negative) sharing relationships of the original sharing set, without
loss of accuracy. Intuitively, given an abstract state shv over
the finite set of variables of interest V, its negative
representation is 
V \ shV. Using this encoding
during analysis dramatically reduces the number of elements that need
to be represented in the abstract states and during abstract
unification as the cardinality of the original set grows toward
2|V|. To further compress the number of elements, we express the
set-sharing relationships through a set of ternary strings that
compacts the representation by eliminating redundancies among the
sharing sets. Our experimental evaluation shows that our approach can
compress the number of relationships, reducing significantly the
memory usage and running time of all abstract operations, including
abstract unification.
TR-CS-2008-10
A High-Level Implementation of Non-Deterministic, Unrestricted, Independent And-Parallelism
Amadeo Casas, Manuel Carro, Manuel V. Hermenegildo
The growing popularity of multicore architectures has renewed interest in language-based approaches to the exploitation of parallelism. Logic programming has proved an interesting framework to this end, and there are parallel implementations which have achieved significant speedups, but at the cost of a quite sophisticated low-level machinery. This machinery has been found challenging to code and, specially, to maintain and expand. In this paper, we follow a different approach which adopts a higher level view by raising some of the core components of the implementation to the level of the source language. We briefly present an implementation model for independent and-parallelism which fully supports non-determinism through backtracking and provides extensible solutions for some of the main problems found in previous and-parallel implementations. Our proposal is able to optimize the execution for the case of deterministic programs and to exploit unrestricted and-parallelism, which allows exposing more parallelism among clause literals than fork-join-based proposals. We present performance results for an implementation, including data for benchmarks where and-parallelism is exploited in non-deterministic programs.
TR-CS-2008-09
Predictions And Diagnostics in Experimental Data Using Support Vector Regression
Nikita A. Sakhanenko, George F. Luger, Hanna E. Makaruk, David B. Holtkamp
In this paper we present a novel support vector machine (SVM) based framework for prognosis and diagnosis. We apply the framework to sparse physics data sets, although the method can easily be extended to other domains. Experiments in applied fields, such as experimental physics, are often complicated and expensive. As a result, experimentalists are unable to conduct as many experiments as they would like, leading to very unbalanced data sets that can be dense in one dimension and very sparse in others. Our method predicts the data values along the sparse dimension providing more information to researchers. Often experiments deviate from expectations due to small misalignments in initial parameters. It can be challenging to distinguish these outlier experiments from those where a real underlying process caused the deviation. Our method detects these outlier experiments. We describe our success at prediction and outlier detection and discuss implications for future applications.
TR-CS-2008-08
Sharing Analysis of Arrays, Collections, and Recursive Structures
Mark Marron, Mario Mendez-Lojo, Manuel Hermenegildo, Darko Stefanovic, Deepak Kapur
Precise modeling of the program heap is fundamental for understanding the behavior of a program, and is thus of significant interest for many optimization applications. One of the fundamental properties of the heap that can be used in a range of optimization techniques is the sharing relationships between the elements in an array or collection. If an analysis can determine that the memory locations pointed to by different entries of an array (or collection) are disjoint, then in many cases loops that traverse the array can be vectorized or transformed into a thread-parallel version. This paper introduces several novel sharing properties over the concrete heap and corresponding abstractions to represent them. In conjunction with an existing shape analysis technique, these abstractions allow us to precisely resolve the sharing relations in a wide range of heap structures (arrays, collections, recursive data structures, composite heap structures) in a computationally efficient manner. The effectiveness of the approach is evaluated on a set of challenge problems from the JOlden and SPECjvm98 suites. Sharing information obtained from the analysis is used to achieve substantial thread-level parallel speedups.
TR-CS-2008-07
Bayesian Network Score Approximation using a Metagraph Kernel
Benjamin Yackley, Eduardo Corona, and Terran Lane
Many interesting problems, including Bayesian network structure-search, can be cast in terms of finding the optimum value of a function over the space of graphs. However, this function is often expensive to compute exactly. We here present a method derived from the study of reproducing-kernel Hilbert spaces which takes advantage of the regular structure of the space of all graphs on a fixed number of nodes to obtain approximations to the desired function quickly and with reasonable accuracy. We then test this method on both a small testing set and a real-world Bayesian network; the results suggest that not only is this method reasonably accurate, but that the BDe score itself varies quadratically over the space of all graphs.
TR-CS-2008-06
Using Laplacian Methods, RKHS Smoothing Splines and Bayesian Estimation as a framework for Regression on Graph and Graph Related Domains
Eduardo Corona, Terran Lane, Curtis Storlie, Joshua Neil
We first present an overview of the Laplacian operator, its properties, and the methods that arise from analizing its eigenvalues and eigenfunctions. We mainly draw our material from (BLS00) and (Chu97), trying to combine the linear algebra approach with the more analytic one, which suggests the analogue with the continuous Laplacian Operator on manifolds.
TR-CS-2008-05
Fast Set Sharing using ZBDDs
Mario Mendez-Lojo, Ondrej Lhotak, Manuel V. Hermenegildo
Set sharing is an abstract domain in which each concrete object is represented by the set of local variables from which it might be reachable. It is a useful abstraction to detect parallelism opportunities, since it contains definite information about which variables do not share in memory, i.e., about when the memory regions reachable from those variables are disjoint. Set sharing is a more precise alternative to pair sharing, in which each domain element is a set of all pairs of local variables from which a common object may be reachable. However, the exponential complexity of some set sharing operations has limited its wider application. This work introduces an efficient implementation of the set sharing domain using Zero-supressed Binary Decision Diagrams (ZBDDs). Because ZBDDs were designed to represent sets of combinations (i.e., sets of sets), they naturally represent elements of the set sharing domain.We show how to synthesize the operations needed in the set sharing transfer functions from basic ZBDD operations. For some of the operations, we devise custom ZBDD algorithms that perform better in practice. We also compare our implementation of the abstract domain with an efficient, compact, bitset-based alternative, and show that the ZBDD version scales better in terms of both memory usage and running time.
TR-CS-2008-04
A New Approach to Model-Based Diagnosis Using Probabilistic Logic
Nikita A. Sakhanenko, Roshan R. Rammohan, George F. Luger, Carl R. Stern
We describe a new approach to model construction using transfer function diagrams that are consequently mapped into generalized loopy logic, a first-order, Turing-complete stochastic language. Transfer function diagrams support representation of dynamic systems with interconnected components. We demonstrate how these diagrams provide interfaces to a context-sensitive probabilistic modeling system (COSMOS). As a result, interfaces as well as the notion of context underlying COSMOS are successfully used for model-based diagnosis. This paper describes transfer function diagrams and how they are incorporated into COSMOS. We illustrate our approach with a practical example taken from a "pump system" modeling problem.
TR-CS-2008-03
Proving Termination of Imperative Programs via Term Rewriting
Stephan Falke and Deepak Kapur
This paper adapts techniques from the term rewriting literature in order to show termination of imperative programs operating on numbers. For this, we present a two-stage approach. In the first stage, imperative programs are translated into constrained term rewrite systems operating on numbers, where constraints are quantifier-free formulas of Presburger arithmetic. This way, computations of imperative programs are mimicked by rewrite sequences. In the second stage, termination of constrained term rewrite systems is analyzed by specializing and simplifying the dependency pair framework for normalized equational rewriting with constraints. This approach is highly flexible and allows the use of various termination techniques adapted from the term rewriting literature, including graph-based decompositions and polynomial interpretations. The approach has been used to prove termination of a large collection of imperative programs.
TR-CS-2008-02
Customizable Resource Usage Analysis for Java Bytecode
Jorge Navas, Mario Mendez-Lojo, and Manuel Hermenegildo
Automatic cost analysis of programs has been traditionally studied in terms of a number of concrete, predefined resources such as execution steps, time, or memory. However, the increasing relevance of analysis applications such as static debugging and/or certification of user-level properties (including for mobile code) makes it interesting to develop analyses for resource notions that are actually application-dependent. This may include, for example, bytes sent or received by an application, number of files left open, number of SMSs sent or received, number of accesses to a database, money spent, energy consumption, etc. We present a fully automated analysis for inferring upper bounds on the usage that a Java bytecode program makes of a set of application programmer-definable resources. In our context, a resource is defined by programmer-provided annotations which state the basic consumption that certain program elements make of that resource. From these definitions our analysis derives functions which return an upper bound on the usage that the whole program (and individual blocks) make of that resource for any given set of input data sizes. The analysis proposed is independent of the particular resource. We also present some experimental results from a prototype implementation of the approach covering an ample set of interesting resources.
TR-CS-2008-01
A Filesystem Interface for Sensor Networks
James Horey, Jean-Charles Tournier, Patrick Widener, Arthur B. Maccabe, and Ann Kilzer
Sensor network users currently face enormous challenges, including programming difficulty and the use of unfamiliar, complex interfaces. To date, most usability research with respect to sensor networks have focused on simplifying programming by offering powerful programming abstractions. Unfortunately, such work does little to encourage ordinary users, such as application scientists, to adopt sensor networks. In order to address these issues we have developed a filesystem interface for sensor networks. By treating a sensor network as a standard Unix filesystem, users are able to use familiar tools to interface with sensor networks. This simplifies management and debugging. Similarly, programs originally designed for filesystems, such as file-sharing programs, can be used to extend sensor networks. Finally, users are also able to prototype applications using pre-existing programming environments that interface with the sensor network through the file I/O interface.
TR-CS-2007-22
Operational Termination of Conditional Rewriting with Built-in Numbers and Semantic Data Structures
Stephan Falke and Deepak Kapur
Rewrite systems on free data structures have limited expressive power since semantic data structures like sets or multisets cannot be modeled elegantly. In this work we define a class of rewrite systems that allows the use of semantic data structures. Additionally, built-in natural numbers, including (dis)equality, ordering, and divisibility constraints, are supported. The rewrite mechanism is a combination of normalized equational rewriting with evaluation of conditions and validity checking of instantiated constraints. The framework is highly expressive and allows modeling of algorithms in a natural way.
Termination is one of the most important properties of conditional normalized equational rewriting. For this it is not sufficient to only show well-foundedness of the rewrite relation, but it also has to be ensured that evaluation of the conditions does not loop. The notion of operational termination is a way to capture these properties. In this work we show that it is possible to transform a conditional constrained equational rewrite system into an unconditional one such that termination of the latter implies operational termination of the former. Methods for showing termination of unconditional constrained equational rewrite system are presented in a companion paper.
TR-CS-2007-21
Dependency Pairs for Rewriting with Built-in Numbers and Semantic Data Structures
Stephan Falke and Deepak Kapur
Rewrite systems on free data structures have limited expressive power since semantic data structures like sets or multisets cannot be modeled elegantly. In this work we define a class of rewrite systems that allows the use of semantic data structures. Additionally, built-in natural numbers, including (dis)equality, ordering, and divisibility constraints, are supported. The rewrite mechanism is a combination of normalized equational rewriting with validity checking of instantiated constraints. The framework is highly expressive and allows modeling of algorithms in a natural way.
Termination is one of the most important properties of algorithms. This is true for both functional programs and imperative programs operating on natural numbers, which can be translated into rewrite systems. In this work, the dependency pair framework for proving termination is extended to be applicable to the class of rewrite systems described above, thus obtaining a flexible and powerful method for showing termination that can be automated effectively. We develop various refinements which increase power and efficiency of the method.
TR-CS-2007-20
Machine Learning: Probabilistic
George F. Luger, Nikita A. Sakhanenko, Roshan R. Rammohan, Chayan Chakrabarti
In this chapter we introduce probabilistic concepts and present several important machine learning algorithms influenced by these stochastic methods. At the heart of the chapter lie Bayes' rule and Markov chains. Probabilistic models of machine learning use the Bayesian approach which allows for interpretation of new evidence based on prior knowledge and experience. Similarly, Markov chains describe the probability of a current event as a function of the probabilities of events at previous time steps. We present hidden Markov models and their variants and illustrate the Viterbi algorithm with a speech processing example. Dynamic Bayesian networks, a temporal extension to traditional Bayesian networks, are presented. We also discuss different learning techniques including Markov chain Monte-Carlo and Expectation Maximization algorithms. Finally, we show how probabilistic measures can be used to extend reinforcement learning and Markov decision processes. This chapter is published as chapter 13 in the book "Artificial Intelligence: Structures and Strategies for Complex Problem Solving" by G. F. Luger (Addison-Wesley 2009).
TR-CS-2007-19
Tables: A Table-Based Language Environment for Sensor Networks
James Horey, Eric Nelson, and Arthur B. Maccabe
Intuitive programming environments targetting application specialists and casual users are currently lacking. Current work has either required large investment from users to learn advanced programming techniques or has focused on simplistic and limited tools. This paper introduces Tables, a graphical programming environment that consists of a spreadsheet-inspired interface and a local runtime executing on sensor nodes. Tables emphasizes ease-of-use by reusing spreadsheet abstractions, such as pivot tables and functions, to interactively program the sensor network. By using these familiar tools, users are able to construct complex applications that include local data filtering and collective processing.
We discuss the design and prototype implementation of Tables and demonstrate how to use Tables to create simple environmental monitoring applications and an advanced object-tracking application. We evaluate these applications in terms of ease-of-use and the relative network overhead, measured in simulation, imposed by the Tables environment. Using this evaluation, we show that the Tables programming environment represents a feasible alternative to existing programming systems.
TR-CS-2007-18
A Relational Algebra for Negative Databases
Fernando Esponda, Eric D. Trias, Elena S. Ackley, Stephanie Forrest
A negative database is a representation of all elements not contained in a given database. A negative database can enhance the privacy of sensitive information without resorting to encryption. This can be useful in settings where encryption is too expensive, e.g., some sensor networks, or for applications where searches or other operations on stored data are desired. The original negative database framework supported only authentication queries and operations for modifying data, such as insert and delete. This paper extends that work by defining a set of relational operators for negative representations. For each relational operator, the corresponding negative operator is defined such that the result of the negative operator applied to a negative representation is equivalent to the positive version applied to the positive representation. Algorithms for each relational operator are described and compared to its positive counterpart. This work enhances the practicality of negative databases and expands their range of application.
TR-CS-2007-17
Structured Streams: Data Services for Petascale Science Environments
Patrick M. Widener, Matthew Wolf, Hasan Abbasi, Matthew Barrick, Jay Lofstead,
Jack Pullikottil, Greg Eisenhauer, Ada Gavrilovska, Scott Klasky, Ron Oldfield,
Patrick G. Bridges, Arthur B. Maccabe, Karsten Schwan.
The challenge of meeting the I/O needs of petascale applications is exacerbated by an emerging class of data-intensive HPC applications that requires annotation, reorganization, or even conversion of their data as it moves between HPC computations and data end users or producers. For instance, data visualization can present data at different levels of detail. Further, actions on data are often dynamic, as new end-user requirements introduce data manipulations unforeseen by original application developers. These factors are driving a rich set of requirements for future petascale I/O systems: (1) high levels of performance and therefore, flexibility in how data is extracted from petascale codes; (2) the need to support .on demand. data annotation . metadata creation and management . outside application codes; (3) support for concurrent use of data by multiple applications, like visualization and storage, including associated consistency management and scheduling; and (4) the ability to flexibly access and reorganize physical data storage.
We introduce an end-to-end approach to meeting these requirements: Structured Streams, streams of structured data with which methods for data management can be associated whenever and wherever needed. These methods can execute synchronously or asynchronously with data extraction and streaming, they can run on the petascale machine or on associated machines (such as storage or visualization engines), and they can implement arbitrary data annotations, reorganization, or conversions. The Structured Streaming Data System (SSDS) enables high-performance data movement or manipulation between the compute and service nodes of the petascale machine and between/on service nodes and ancillary machines; it enables the metadata creation and management associated with these movements through specification instead of application coding; and it ensures data consistency in the presence of anticipated or unanticipated data consumers. Two key abstractions implemented in SSDS, I/O graphs and Metabots, provide developers with high-level tools for structuring data movement as dynamically-composed topologies. A lightweight storage system avoids traditional sources of I/O overhead while enforcing protected access to data.
This paper describes the SSDS architecture, motivating its design decisions and intended application uses. The utility of the I/O graph and Metabot abstractions is illustrated with examples from existing HPC codes executing on Linux Infiniband clusters and Cray XT3 supercomputers. Performance claims are supported with experiments benchmarking the underlying software layers of SSDS, as well as application-specific usage scenarios.
TR-CS-2007-16
Towards a High-Level Implementation of Execution Primitives for Unrestricted, Independent And-parallelism
Amadeo Casas, Manuel Carro, and Manuel V. Hermenegildo
Most efficient implementations of parallel logic programming rely on complex low-level machinery which is arguably difficult to implement and modify. We explore an alternative approach aimed at taming that complexity by raising core parts of the implementation to the source language level for the particular case of and-parallelism. We handle a significant portion of the parallel implementation at the Prolog level with the help of a comparatively small number of concurrency-related primitives which take care of lower-level tasks such as locking, thread management, stack set management, etc. The approach does not eliminate altogether modifications to the abstract machine, but it does greatly simplify them and it also facilitates experimenting with different alternatives. We show how this approach allows implementing both restricted and unrestricted (i.e., non fork-join) parallelism. Preliminary experiments show that the performance sacrificed is reasonable, although granularity control is required in some cases. Also, we observe that the availability of unrestricted parallelism contributes to better observed speedups.
TR-CS-2007-15
A Flexible, (C)LP-based Approach to the Analysis of Object-Oriented Programs
Mario Mendez-Lojo, Jorge Navas, and Manuel V. Hermenegildo
Static analyses of object-oriented programs usually rely on intermediate representations that respect the original semantics while having a more uniform and basic syntax. Most of the work involving object-oriented languages and abstract interpretation usually omits the description of that language or just refers to the Control Flow Graph (CFG) it represents. However, this lack of formalization on one hand results in an absence of assurances regarding the correctness of the transformation and on the other it typically strongly couples the analysis to the source language. In this work we present a framework for analysis of object-oriented languages in which in a first phase we transform the input program into a representation based on Horn clauses. This allows on one hand proving the transformation correct attending to a simple condition and on the other being able to apply an existing analyzer for (constraint) logic programming to automatically derive a safe approximation of the semantics of the original program. The approach is flexible in the sense that the first phase decouples the analyzer from most languagedependent features, and correct because the set of Horn clauses returned by the transformation phase safely approximates the standard semantics of the input program. The resulting analysis is also reasonably scalable due to the use of mature, modular (C)LP-based analyzers. The overall approach allows us to report results for medium-sized programs.
TR-CS-2007-14
Annotation Algorithms for Unrestricted Independent And-Parallelism in Logic Programs
Amadeo Casas, Manuel Carro, and Manuel V. Hermenegildo
We present two new algorithms which perform automatic parallelization via source-to-source transformations. The objective is to exploit goal-level, unrestricted independent and-parallelism. The proposed algorithms use as targets new parallel execution primitives which are simpler and more flexible than the well-known &/2 parallel operator. This makes it possible to generate better parallel expressions by exposing more potential parallelism among the literals of a clause than is possible with &/2. The difference between the two algorithms stems from whether the order of the solutions obtained is preserved or not. We also report on a preliminary evaluation of an implementation of our approach. We compare the performance obtained to that of previous annotation algorithms and show that relevant improvements can be obtained.
TR-CS-2007-13
Dominance: Modeling Heap Structures with Sharing
Mark Marron, Rupak Majumdar, Darko Stefanovic, Deepak Kapur
A number of papers have used predicate languages over sets of abstract locations to model the heap (decorating a heap graph with the predicates, or in conjunction with an access path abstraction). In this work we introduce a new predicate, dominance, which is a generalization of aliasing and is used to model how objects are shared in the heap (e.g. do two lists contain the same set of objects?) and how sharing influences the results of destructive updates (e.g. if all the objects in one list are modified does that imply that all the objects in another list are modified?). The dominance relation is introduced in the context of a graph-based heap model but the concept is general and can be incorporated in other frameworks as a high-level primitive.
The motivation for introducing a higher-order predicate to model sharing is based on the success of existing approaches which use connectivity, reachability, and sharing predicates to perform shape analysis using high-level graph-based models. Our approach provides an analysis technique that is efficient and scalable while retaining a high level of accuracy. This is in contrast to proposals in the literature based on using logical languages (usually built on top of first-order predicate logic) which either are highly expressive and very general (resulting in a computationally expensive analysis) or utilize only fragments of the full logic (which reduces the computational cost but results in a much less powerful analysis).
The approach presented in this paper has been implemented and run on a variation of the Jolden benchmarks. The information extracted using the analysis has been used to parallelize these programs with a near optimal speedup for 7 of the 9 benchmarks. The runtimes are small enough to make the analysis practical (a few seconds for each program).
TR-CS-2007-12
Protecting BGP from Invalid Paths
Josh Karlin, Stephanie Forrest and Jennifer Rexford
The Internet's interdomain routing protocol, BGP, is vulnerable to a number of potentially crippling attacks. Many promising cryptography-based solutions have been proposed, but none have been embraced by the necessary communities to garner significant adoption. This is largely due to the difficulty of developing and maintaining the necessary PKI infrastructure and changes to the BGP protocol that the proposed solutions require. Alternative solutions such as anomaly detectors have been unable to provide the same level of security as the cryptographic mechanisms. In this paper we create an anomaly detector and response mechanism capable of automatically stopping the propagation of invalid path attacks, a difficult class of attacks to detect. Our solution provides comparable security to the cryptographic methods and could be readily deployed with a simple software upgrade in participating networks.
TR-CS-2007-11
Worm Versus Alert: Who Wins in a Battle for Control of a
Large-Scale Network?
James Aspnes, Navin Rustagi, and Jared Saia
Consider the following game between a worm and an alert1 over a network of n nodes. Initially, no nodes are infected or alerted and each node in the network is a special detector node independently with small but constant probability. The game starts with a single node becoming infected. In every round thereafter, every infected node sends out a constant number of worms to other nodes in the population, and every alerted node sends out a constant number of alerts. Nodes in the network change state according to the following three rules: 1) If a worm is received by a node that is not a detector and is not alerted, that node becomes infected; 2) If a worm is received by a node that is a detector, that node becomes alerted; 3) If an alert is received by a node that is not infected, that node becomes alerted.
We make two assumptions about this game. First, that an infected node can send worm messages to any other node in the network but, in contrast, an alerted node can send alert messages only through a previously determined, constant degree overlay network. Second, we assume that the infected nodes are intelligent, coordinated and essentially omniscient. In other words, the infected nodes know everything except for which nodes are detectors and the alerted nodes' random coin flips i.e. they know the topology of the overlay network used by the alerts; which nodes are alerted and which are infected at any time; where alerts and worms are being sent; the overall strategy used by the alerted nodes; etc. The alerted nodes are assumed to know nothing about which other nodes are infected or alerted, where alerts or worms are being sent, or the strategy used by the infected nodes.
Specifically, this result holds if d ≥ α and 
,
where α and 
represent the
rate of the spread of the alert and worm respectively; 
is the
probability that a node is a detector node; d is the degree of the
overlay network; and c is the node expansion of the overlay
network. Next, we give empirical results that suggest that our
algorithms for the alert may be useful in current large-scale
networks. Finally, we show that if the overlay network has poor
expansion, in particular if 
, then the worm will likely
infect almost all of the non-detector nodes.
1Specifically, we consider self-certifying alerts[6], which contain short proofs that a security flaw exists and thereby eliminate false alerts.
TR-CS-2007-10
Selecting Bayesian Network Parameterizations for Generating Simulated Data
John Burge, Terran Lane
The correct solution for an unsupervised learning task is never known. Thus, experimental results for such tasks must be validated. This can be done by turning the task into a supervised learning problem by training on simulated data where the correct solution is known and controllable. While this is a common practice, little research is done on generating interesting classes of random data that can be applied to many domains. We present a method to select the parameters of a Bayesian network (BN) which can be used to generate simulated data. Our methods allow the magnitude of correlations among random variables in the data to be precisely controlled. We apply our methods to the validation of BN structure search techniques and demonstrate that by precisely controlling correlations in the simulated data, qualitative differences among structure learning algorithms can be observed.
TR-CS-2007-09
A Context-Partitioned Stochastic Modeling
System with Causally Informed Context
Management and Model Induction
Nikita A. Sakhanenko, Roshan R. Rammohan, George F. Luger, and
Carl R. Stern
We describe a flexible multi-layer architecture for context-sensitive stochastic modeling. The architecture incorporates a high performance stochastic modeling core based on a recursive form of probabilistic logic. On top of this modeling core, causal representations and reasoning direct a long-term incremental learning process that produces a context-partitioned library of stochastic models. The failure-driven learning procedure for expanding and refining the model library employs a combination of abductive inference together with EM model induction to construct new models when current models no longer perform acceptably. The system uses a causal finite state machine representation to control on-line model switching and model adaptation along with embedded learning. Our system is designed to support operational deployment in real-time monitoring, diagnostic, prognostic, and decision support applications. In this paper we describe the basic multi-layer architecture along with new learning algorithms inspired by developmental learning theory.
TR-CS-2007-08
Efficient Context-Sensitive Shape Analysis with Graph Based Heap Models
Mark Marron, Manuel Hermenegildo, Deepak Kapur, and Darko Stefanovic
The performance of heap analysis techniques has a significant impact on their utility in optimization and verification applications. A significant factor affecting analysis performance is how procedure calls are handled. To maximize the accuracy of the analysis it is desirable to perform inter-procedural data flow analysis in a context-sensitive manner. However, re-analyzing a procedure for each calling context can result in the analysis being computationally intractable. To minimize the computational cost of performing context-sensitive dataflow analysis it is critical to minimize the number of times a function body needs to be re-analyzed. The computational cost can be further reduced by minimizing the amount of information that is carried in from the caller scope and thus needs to be processed during the analysis of the callee procedure. This can be accomplished by memoizing the calls as they are analyzed and using project/extend operations to remove portions of the heap model that cannot be affected by the called procedure.
The focus of this paper is the design of project and extend operations for a graph-based abstract heap model. Our interprocedural analysis introduces a novel method for naming cutpoints which is able to accurately model calls with shared data structures, multiple cutpoints, and recursive calls. In conjunction with our heap model (which tracks all heap properties using local information) the project and extend operations are able to substantially reduce the amount of calling context information that is carried into the analysis of the callee body. Our experimental results indicate that the proposed project/extend operations have a substantial positive effect on the memoization of procedure analysis results and on the reduction of the size of the model that the local analysis must deal with. Additionally, the cutpoint naming technique is (in many cases) able to precisely maintain the relations between the callee local variables and the caller local variables in the immediately preceding call frame, which is critical to modeling programs that perform recursive destructive modifications on lists or trees.
TR-CS-2007-07
Dependency Pairs for Rewriting with Non-Free Constructors
Stephan Falke and Deepak Kapur
A method based on dependency pairs for showing termination of functional programs on data structures generated by constructors with relations is proposed. A functional program is specified as an equational rewrite system, where the rewrite system specifies the program and the equations express the relations on the constructors that generate the data structures. Unlike previous approaches, relations on constructors can be collapsing, including idempotency and identity relations. Relations among constructors may be partitioned into two parts: (i) equations that cannot be oriented into terminating rewrite rules, and (ii) equations that can be oriented as terminating rewrite rules, in which case an equivalent convergent system for them is generated. The dependency pair method is extended to normalized rewriting, where constructor-terms in the redex are normalized first. The method has been applied to several examples, including the Calculus of Communicating Systems and the Propositional Sequent Calculus. Various refinements, such as dependency graphs, narrowing, etc., which increase the power of the dependency pair method, are presented for normalized rewriting.
TR-CS-2007-06
A Simulation Framework for Modeling Combinatorial Control in Transcription Regulatory Networks
Sushmita Roy, Terran Lane, Margaret Werner-Washburne
With the increasing availability of genome scale data, a plethora of algorithms are being developed to infer genome scale regulatory networks. However, identifying the appropriate algorithm for a particular inference task is a critical and difficult modeling question. This is because for most real-world data, the true network is rarely known and different algorithms produce different networks, which may be due to assumptions inherrent to the algorithm or the objective the algorithm is designed to optimize. One approach to address this issue is to build artificial, but biologically realistic, gene networks for which the true topology is known. These networks can be sampled to generate data, which can then serve as a testbed to compare a suite of network inference algorithms.
Existing simulation systems either require highly detailed descriptions of network components making the generation of large-scale networks (> 100 nodes) infeasible, or, make simplifications that render the simulated networks very far from true models of gene regulation. We have developed a simulation system that builds a network of genes and proteins and models the rate of transcriptional activity as a non-linear function of a set of transciption factor complexes. Our simulator uses a system of differential equations and interfaces with Copasi, a differential equation solver, to produce steady-state and time-series expression datasets. Overall, our simulator has the following advantages: (i) it can produce expression datasets in an efficient and highthroughput manner, (ii) it is biologically more realistic since it models transcription rate as a function of transcription factor levels rather than gene expression levels, (iii) it incorporates the combinatorial control among different transcription factors, and (iii) it incorporates gene and protein expressions, thus allowing the comparison of algorithms that use different combinations of these data sources.
TR-CS-2007-05
Precise Set Sharing and Nullity Analysis for Java-style Programs
Mario Mendez Lojo, Manuel V. Hermenegildo
Finding useful sharing information between instances in object-oriented programs has been recently the focus of much research. The applications of such static analysis are multiple:by knowing which variables share in memory we can apply conventional compiler optimizations, find coarse-grained parallelism opportunities, or, more importantly,verify certain correctness aspects of programs even in the absence of annotations In this paper we introduce a framework for deriving precise sharing information based on abstract interpretation for a Java-like language. Our analysis achieves precision in various ways. The analysis is multivariant, which allows separating different contexts. We propose a combined Set Sharing + Nullity + Classes domain which captures which instances share and which ones do not or are definitively null, and which uses the classes to refine the static information en inheritance is present. Carrying the domains in a combined way facilitates the interaction among the domains in the presence of mutivariance in the analysis. We show that both the set sharing part of the domain as well as the combined domain provide more accurate information than previous work based on pair sharing domains, at reasonable cost.
TR-CS-2007-04
Managing Dynamic Contexts Using Failure-Driven Stochastic Models
Nikita A. Sakhanenko, George F. Luger, Carl R. Stern
We describe an architecture for representing and managing context shifts that supports dynamic data interpretation. This architecture utilizes two layers of learning and three layers of control for adapting and evolving new stochastic models to accurately represent changing and evolving situations. At the core of this architecture is a form of probabilistic logic used to encode sets of recursive relationships defining Dynamic Bayesian Models. This logic is extended with a syntax for defining contextual restrictions on stochastic Horn clauses. EM parameter learning is used to calibrate models as well as to assess the quality of fit between the model and the data. Model failure, detected as a poor fit between model and data, triggers a model repair mechanism based on causally informed context splitting and context merging. An implementation of this architecture for distributed weather monitoring is currently under development.
TR-CS-2007-03
An Efficient, Parametric Fixpoint Algorithm for Analysis of Java Bytecode
Mario Mendez, Jorge Navas, Manuel Hermenegildo
Abstract interpretation has been widely used for the analysis of object-oriented languages and, in particular, Java source and bytecode. However, while most existing work deals with the problem of finding expressive abstract domains that track accurately the characteristics of a particular concrete property, the underlying fixpoint algorithms have received comparatively less attention.
In fact, many existing (abstract interpretation based--) fixpoint algorithms rely on relatively inefficient techniques for solving inter-procedural call graphs or are specific and tied to particular analyses. We also argue that the design of an efficient fixpoint algorithm is pivotal to supporting the analysis of large programs. In this paper we introduce a novel algorithm for analysis of Java bytecode which includes a number of optimizations in order to reduce the number of iterations. The algorithm is parametric -- in the sense that it is independent of the abstract domain used and it can be applied to different domains as "plug-ins" --, multivariant, and flow-sensitive. Also, is based on a program transformation, prior to the analysis, that results in a highly uniform representation of all the features in the language and therefore simplifies analysis. Detailed descriptions of decompilation solutions are given and discussed with an example. We also provide some performance data from a preliminary implementation of the analysis.
TR-CS-2007-02
Heap Analysis in the Presence of Collection Libraries
Unified Memory Analysis: Analyzing Collections
Mark Marron, Darko Stefanovic, Manuel Hermenegildo, and Deepak Kapur
Memory analysis techniques have become sophisticated enough to model, with a high degree of accuracy, the manipulation of simple memory structures (finite structures, single/double linked lists and trees). However, modern programming languages provide extensive library support including a wide range of generic collection objects that make use of complex internal data structures. While these data structures ensure that the collections are efficient, often these representations cannot be effectively modeled by existing methods (either due to excessive runtime or due to the inability to represent the required information).
This paper presents a method to represent collections using an abstraction of their semantics. The construction of the abstract semantics for the collection objects is done in a manner that allows individual elements in the collections to be identified. Our construction also supports iterators over the collections and is able to model the position of the iterator with respect to the elements in the collection. By ordering the contents of the collection based on the iterator position, the model can represent a notion of progress when iteratively manipulating the contents of a collection. These features allow strong updates to the individual elements in the collection as well as strong updates over the collections themselves.
TR-CS-2007-01
Resource Bounds Analysis
Jorge Navas, Edison Mera, Pedro Lopez-Garcia, and Manuel
Hermenegildo
We present a generic analysis that infers both upper and lower bounds on the usage that a program makes of a set of user-definable resources. The inferred bounds will in general be functions of input data sizes. A resource in our approach is a quite general, user-defined notion which associates a basic cost function with elementary operations. The analysis then derives the related (upper- and lower-bound) cost functions for all procedures in the program. We also present an assertion language which is used to define both such resources and resource-related properties that the system can then check based on the results of the analysis. We have performed some experiments with some concrete resource-related properties such as execution steps, bits sent or received by an application, number of arithmetic operations performed, number of calls to a procedure, number of transactions, etc. presenting the resource usage functions inferred and the times taken to perform the analysis. Applications of our analysis include resource consumption verification and debugging (including for mobile code), resource control in parallel/distributed computing, and resource-oriented specialization.
TR-CS-2006-15
A Platform for Research into Object-Level Trace Generation
James Foucar
An object-level trace, which we will hereafter refer to as a garbage collection trace (GC-trace), enumerates all the events that happen during program execution that affect the heap. Therefore, GC-tracing is an excellent way to examine the behavior of an object-oriented system. Knowing behavior expedites many forms of virtual machine research including garbage collection research. GC-traces were originally generated by the painfully slow brute-force technique. Subsequently, this technique was replaced by the Merlin algorithm which can generate GC-traces at a fraction of the cost of the brute-force algorithm.
Our work introduces a new GC-tracing system. Our system uses the Merlin algorithm within the context of a general shadow heap that is independent of the virtual machine. The shadow heap supports many optimizations to the Merlin algorithm and also supports analysis and verification. We examine the advantages and disadvantages of our approach, the viability of using a C++ library for analysis in conjunction with a Java-in-Java virtual machine, the various costs of integrating our shadow heap with a virtual machine, and the effectiveness of our GC-tracing optimizations. Finally, we compare our GC-tracing system with the GC-tracing system that is currently bundled with JikesRVM.
TR-CS-2006-14
Markov Random Field Modeling of the Spatial Distribution of Proteins on Cell Membranes
Jun Zhang, Stanly L. Steinberg, Bridget S. Wilson, Janet M. Oliver, and Lance R. Williams
Biologists use gold particles visualized by transmission electron microscopy (TEM) to label proteins on the cell membrane. This is done to gain insight into how proteins in a signaling pathway interact. However, due to limitations of applicable gold particle size and shape, typically only two proteins can be labeled at a time. A formidable challenge is to integrate experimental data across multiple experiments where there are from 10 to 100 different proteins of interest and only the positions of two proteins can be observed simultaneously. We propose to use Markov random fields (MRF) to characterize the distribution of proteins on the cell membrane. Markov random fields are a powerful mathematical formalism for modeling correlations between states associated with neighboring sites in spatial lattices. The presence or absence of a protein of a specific type at a point on the cell membrane is a state. Since only two protein types can be observed, i.e., those bound to particles, and the rest cannot be observed, the problem is one of deducing the conditional distribution of a MRF with unobservable (hidden) states. We develop a multiscale MRF model and use mathematical programming techniques to infer the conditional distribution of a MRF for proteins of three types from observations showing the interactions between only two types. Application to artificial data shows that the interactions among three proteins can be reliably estimated. Results on real data are also presented.
TR-CS-2006-13
Design and Implementation of a Baseline port of the Jikes Research Virtual Machine to the IA-64 Architecture
Ravi kiran Gorrepati
Of all 64-bit architectures, IA-64 is the most recent and offers exciting new features for compiler developers. IA-64 gains speed from efficient compilation, which is costly for Java, because the compilation of modules happens dynamically on the virtual machine. Lack of an opensource Java virtual machine for the IA-64 which allows for research on code generation techniques lead us to pursue this work. This work presents a baseline code generator for the IA-64 architecture. This code generator is a part of the Jikes Research Virtual Machine for Java written in Java. To our knowledge, this work presents the first open-source, just-in-time virtual machine for Java on IA-64 architecture.
TR-CS-2006-12
On the Equational Definability of Brouwer-Zadeh Lattices
Matthew Spinks and Robert Veroff
We give an axiomatisation of the variety of Brouwer-Zadeh lattices, suitable for applications to quantum theory.
TR-CS-2006-11
Shock Physics Data Reconstruction Using Support Vector Regression
Nikita A. Sakhanenko, George F. Luger, Hanna E. Makaruk, Joysree B. Aubrey, and David B. Holtkamp
This paper considers a set of shock physics experiments that investigate how materials respond to the extremes of deformation, pressure, and temperature when exposed to shock waves. Due to the complexity and the cost of these tests, the available experimental data set is often very sparse. A support vector machine (SVM) technique for regression is used for data estimation of velocity measurements from the underlying experiments. Because of good generalization performance, the SVM method successfully interpolates the experimental data. The analysis of the resulting velocity surface provides more information on the physical phenomena of the experiment. Additionally, the estimated data can be used to identify outlier data sets, as well as to increase the understanding of the other data from the experiment.
TR-CS-2006-10
Pretty Good BGP: Improving BGP by Cautiously Adopting Routes
Josh Karlin, Stephanie Forrest, and Jennifer Rexford
The Internet's interdomain routing protocol, BGP, is vulnerable to a number of damaging attacks, which often arise from operator misconfiguration. Proposed solutions with strong guarantees require a public-key infrastructure, accurate routing registries, and changes to BGP. While experts debate whether such a large deployment is feasible, networks remain vulnerable to false information injected into BGP. However, BGP routers could avoid selecting and propagating these routes if they were cautious about adopting new reachability information. We describe a protocol-preserving enhancement to BGP, Pretty Good BGP (PGBGP), that slows the dissemination of bogus routes, providing network operators time to respond before problems escalate into a large-scale Internet attack. Simulation results show that realistic deployments of PGBGP could provide 99% of Autonomous Systems with 24 hours to investigate and repair bogus routes without affecting prefix reachability. We also show that without PGBGP, 40% of ASs cannot avoid selecting bogus routes; with PGBGP, this number drops to less than 1%. Finally, we show that PGBGP is incrementally deployable and offers significant security benefits to early adopters and their customers.
TR-CS-2006-09
The Concrete Mathematics of Microfluidic Mixing, Part I
Jennifer Sager, Maxwell Young, and Darko Stefanovic
We analyze mathematically a previously reported class of passive microfluidic mixing networks. The networks produce nonhomogeneous concentrations in the output channel, resulting in diverse concentration profiles. We formally prove that all profiles obtainable with this class of networks can be described as polynomials of degree no higher than the number of input channels less one. We derive explicit formulas for the calculation of resultant output concentration profiles and conversely for the calculation of input concentrations needed to obtain set output profiles.
TR-CS-2006-08
Use of Crossing-State Equivalence Classes for Rapid Relabeling of
Knot-Diagrams Representing 2 1/2 D Scenes
Keith Wiley and Lance R. Williams
In previous research, we demonstrated a sophisticated computer- assisted drawing program called Druid which permits easy construction of 2 1/2 D scenes. A 2 1/2 D scene is a representation of surfaces that is fundamentally two-dimensional, but which also represents the relative depths of those surfaces in the third dimension. This paper greatly improves Druid's efficiency by exploitating a topological constraint on 2 1/2 D scenes which we call a crossing-state equivalence class. This paper describes this constraint and how it is used by Druid.
TR-CS-2006-07
A Syntactic Approach to Combining Functional Notation, Lazy Evaluation, and Higher-Order in LP Systems
Amadeo Casas, Daniel Cabeza, and Manuel V. Hermenegildo
Nondeterminism and partially instantiated data structures give logic programming expressive power beyond that of functional programming. However, functional programming often provides convenient syntactic features, such as having a designated implicit output argument, which allow function call nesting and sometimes results in more compact code. Functional programming also sometimes allows a more direct encoding of lazy evaluation, with its ability to deal with infinite data structures. We present a syntactic functional extension, used in the Ciao system, which can be implemented in ISO-standard Prolog systems and covers function application, predefined evaluable functors, functional definitions, quoting, and lazy evaluation. The extension is also composable with higher-order features and can be combined with other extensions to ISO-Prolog such as constraints. We also highlight the features of the Ciao system which help implementation and present some data on the overhead of using lazy evaluation with respect to eager evaluation.
TR-CS-2006-06
Unified Memory Analysis
Mark Marron, Deepak Kapur, Darko Stefanovic, and Manuel Hermenegildo
The ability to accurately model the state of program memory and how it evolves during program execution is critical to many optimization and verification techniques. Current memory analysis techniques either provide very accurate information but run prohibitively slowly or run in an acceptable time but produce very conservative results. This paper presents an analysis method that is capable of accurately modeling many important program properties (aliasing, shape, logical data structures, sharing of data elements in collections) while maintaining an acceptable level of performance. Using several examples we show how our abstract model is able to provide detailed information on the properties of interest in the concrete domain. We demonstrate that the model is a safe approximation of the concrete heap and outline the required data flow operations. Finally, we show that the asymptotic runtime of this method is polynomial in the size of the abstract heap and that in practice it is efficient enough to be used in an optimizing compiler.
TR-CS-2006-05
NetGen Release Notes, Epsilon Version
(Phylogenetic Network Generation Application)
Monique M. Morin
NetGen is an event-driven simulator that creates phylogenetic histories which include hybrids. The birth-death model typically employed by biologists is extended with a diploid hybridization event. DNA sequences are evolved in conjunction with the typology, enabling hybridization decisions to be based upon hamming distance if desired. NetGen supports variable rate lineages, root sequence specification, outgroup generation and many other options. This document provides an overview of the software, installation and execution instructions, as well as a comprehensive list of input parameters.
TR-CS-2006-04
Implicit Induction Methods and Decision Procedures
Stephan Falke and Deepak Kapur
Decision procedures are widely used in automated reasoning tools in order to reason about data structures. Their scope is typically limited, though, and many conjectures occurring in practical applications fall outside the theory handled by a decision procedure. Typically, reasoning about functions that are defined on those data structures is needed. For this, inductive reasoning has to be employed.
In this work, families of function definitions and conjectures are identified for which inductive validity can be decided using implicit induction methods and decision procedures for an underlying decidable theory. The results significantly extend the results obtained in (Kapur & Subramaniam, 2000), which were obtained using explicit induction schemes. Firstly, we allow performing induction on nonlinear terms, which enables us to decide conjectures like gcd(x, x) = x. Secondly, we allow for mutually recursive function definitions. Thirdly, we allow general terms from the decidable theory on inductive positions, which is needed to decide conjectures such as gcd(2x, 2) = 2. These contributions are crucial for successfully integrating inductive reasoning into decision procedures.
TR-CS-2006-03
A Theoretical and Experimental Evaluation of Augmented Bayesian
Classifiers
Vikas Hamine and Paul Helman
Naive Bayes is a simple Bayesian network classifier with strong independence assumptions among features. This classifier despite its strong independence assumptions, often performs well in practice. It is believed that relaxing the independence assumptions of naive Bayes may improve the performance of the resulting structure. Augmented Bayesian Classifiers relax the independence assumptions of naive Bayes by adding augmenting arcs that obey certain structural restrictions, between features of a naive Bayes classifier. In this paper we present algorithms for learning Augmented Bayesian Classifiers with respect to the Minimum Description Length (MDL) and Bayesian-Dirichlet (BD) metrics. Experimental results on the performance of these algorithms on various datasets selected from the UCI Machine Learning Repository are presented. Finally, a comparison of the learning rates and accuracies of various Augmented Bayesian Classifiers is presented on artificial data. Global connectivity from local geometric constraints for sensor networks with various wireless footprints
TR-CS-2006-02
Global connectivity from local geometric constraints for
sensor networks with various wireless footprints
Raissa D’Souza, David Galvin, Cristopher Moore, and Dana Randall
Adaptive power topology control (APTC) is a local algorithm for constructing a one-parameter family of theta-graphs, where each node increases power until it has a neighbor in every theta sector around it. We show it is possible to use such a local geometric theta-constraint to determine whether full network connectivity is achievable, and consider tradeoffs between assumptions of the wireless footprint and constraints on the boundary nodes. In particular, we show that if the boundary nodes can communicate with neighboring boundary nodes and all interior nodes satisfy a theta_I < pi constraint, we can guarantee connectivity for any arbitrary wireless footprint. If we relax the boundary assumption and instead impose a theta_B < 3pi/2 constraint on the boundary nodes, together with the theta_I < pi constraint on interior nodes, we can guarantee full network connectivity using only a weak-monotonicity footprint assumption. The weakmonotonicity model, introduced herein, is much less restrictive than the disk model of coverage and captures aspects of the spatial correlations inherent in signal propagation and noise. Finally, assuming the idealized disk model of coverage, we show that when theta < pi, APTC constructs graphs that are sparse, and when theta < 2pi/3, the graphs support greedy geometric routing.
TR-CS-2006-01
Efficient top-down set-sharing analysis using cliques
Jorge Navas, Francisco Bueno, and Manuel Hermenegildo
We study the problem of efficient, scalable set-sharing analysis of logic programs. We use the idea of representing sharing information as a pair of abstract substitutions, one of which is a worst-case sharing representation called a clique set, which was previously proposed for the case of inferring pair-sharing. We use the clique-set representation for (1) inferring actual set-sharing information, and (2) analysis within a top-down framework. In particular, we define the new abstract functions required by standard top-down analyses, both for sharing alone and also for the case of including freeness in addition to sharing. We use cliques both as an alternative representation and as widening, defining several widening operators. Our experimental evaluation supports the conclusion that, for inferring set-sharing, as it was the case for inferring pair-sharing, precision losses are limited, while useful efficiency gains are obtained. We also derive useful conclusions regarding the interactions between thresholds, precision, efficiency and cost of widening. At the limit, the clique-set representation allowed analyzing some programs that exceeded memory capacity using classical sharing representations.
TR-CS-2005-44
The Reduction Approach to Decision Procedures
Deepak Kapur and Calogero G. Zarba
Reduction functions reduce the satisfiability of a formula over a complex data structure to the satisfiability of formula over a simpler data structure. It is shown how reduction functions can be used to reduce a formula over lists to a formula over constructors, a formula over arrays to a formula over equality, a formula over sets to a formula over equality, and a formula over multisets to a formula over integer linear arithmetic extended with uninterpreted function symbols. Furthermore, a method for combining reduction functions is presented. Consequently, the satisfiability of a formula over the combination of complex data structures can be reduced to the satisfiability of a formula over the combination of simpler data structures.
TR-CS-2005-43
A survey of configurable operating systems
Jean-Charles Tournier
The need to deal with configurable operating systems is not new and several research projects have tried, and are trying, to deal with this issue. In order to identify the huge number of different configurable operating systems, a survey is therefore needed. Moreover, such a survey should allow to identify the main classes of configurability and to compare operating systems from a configurability point of view. This paper presents an up-to-date survey that includes newest research projects and based on revelant criteria that has been risen when authors started to work on a configurable operating system for high-performance computing.
TR-CS-2005-42
Multiple Kernel Learning for Support Vector Regression
Shibin Qiu and Terran Lane
Kernel support vector (SV) regression has successfully been used for prediction of nonlinear and complicated data. However, like other kernel methods such as support vector machine (SVM) classification, the quality of SV regression depends on proper choice of kernel functions and their parameters. Kernel selection for model selection is conventionally performed through repeated cross validation over a range of kernels and their parameters. Multiple kernel learning arises when a range of kernel parameters need to be tuned within one training process, when different types of kernels are applied simultaneously, or when data are from heterogeneous sources and are characterized with different kernels. Multiple kernel learning can improve the efficiency of kernel selection by automatically evaluate the relative importance of the candidate kernels. Inspired by recent developments in kernel selection for SVM classification, we investigate multiple kernel learning for SV regression. Since more slack variables and constraints are involved in the optimization formulation of SV regression than SVM, we can only follow the general procedures used by SVM but cannot directly use the results derived from SVM. We transform the optimization problems of SV regressions using both epsilon-insensitive loss function and automatic error control into proper forms so that they can be formulated as semidefinite programming (SDP) problems. To avoid the high computational cost of SDP programming, we further formulate multiple kernel SV regression into quadratically constrained quadratic programming optimization problems. Experiments on public and simulated data sets demonstrate that multiple kernel SV regression improves prediction accuracy, reduces the number of support vectors, and helps characterize the propertis of the data.
TR-CS-2005-41
Games, Strategies, and Boolean Formula Manipulation
Ben Andrews
Biomolecular automata based on chemical logic gates can play two-player games of perfect information provided that a legal strategy for the game can be expressed in terms of Boolean formulas. To facilitate the construction of such automata, we developed a formal procedure for the analysis of game strategies, their translation into Boolean formulas, and the manipulation of the resultant formulas into canonical forms determined by the available logic primitives. As a case study in the application of this procedure, we generated strategies for the first player in the game of tic-tac-toe that, by construction, are favorable (do not admit a loss), and we found that many can be translated into Boolean formulas. Moreover, the resultant formulas can be expressed in logic with a fan-in of five, but, apparently, not in simpler logic. Additionally, we studied the combinatorics of strategies and, for the first player in the game of tic-tac-toe, we computed the number of all strategies, about 1.423e124, and the number of favorable strategies, about 2.648e103.
TR-CS-2005-40
Designing a Dynamic Middleware System for Sensor Networks
James Horey and Arthur Maccabe
Kensho is a middleware system for sensor networks that provides a communication and computation transparent view of the sensor network. Kensho is based on the specification of functional groups that support both data sharing and computation. Collective operations can migrate automatically throughout a group to take advantage of new resources without the user's input. This allows new nodes to be added to the network without having to reprogram the network or the new node. We believe that these abstractions provided by the Kensho middleware supports the creation of highly scalable, robust distributed programs.
TR-CS-2005-39
The Design and Testing of a First-Order Logic-Based Stochastic Modeling Language
Daniel J. Pless, Chayan Chakrabarti, Roshan Rammohan, and George F. Luger
We have created a logic-based, Turing-complete language for stochastic modeling. Since the inference scheme for this language is based on a variant of Pearl's loopy belief propagation algorithm, we call it Loopy Logic. Traditional Bayesian networks have limited expressive power, basically constrained to finite domains as in the propositional calculus. Our language contains variables that can capture general classes of situations, events and relationships. A first-order language is also able to reason about potentially infinite classes and situations using constructs such as hidden Markov models(HMMs). Our language uses an Expectation-Maximization (EM) type learning of parameters. This has a natural fit with the Loopy Belief Propagation used for inference since both can be viewed as iterative message passing algorithms. We present the syntax and theoretical foundations for our Loopy Logic language. We then demonstrate three examples of stochastic modeling and diagnosis that explore the representational power of the language. A mechanical fault detection example displays how Loopy Logic can model time-series processes using an HMM variant. A digital circuit example exhibits the probabilistic modeling capabilities, and finally, a parameter fitting example demonstrates the power for learning unknown stochastic values.
TR-CS-2005-38
Multiple Target Tracking with Lazy Background Subtraction and Connected Component Analysis
Robert G. Abbott and Lance R. Williams
Background subtraction, binary morphology, and connected components analysis are the first processing steps in many vision-based tracking applications. Although background subtraction has been the subject of much research, it is typically treated as stand-alone process, dissociated from the subsequent phases of object recognition and tracking. This paper presents a method for decreasing computational cost in visual tracking systems by using track state estimates to direct and constrain image segmentation via background subtraction and connected components analysis. We also present a multiple target tracking application which uses the technique to achieve a large reduction in computation costs.
TR-CS-2005-37
Pretty Good BGP: Protecting BGP by Cautiously Selecting Routes
Josh Karlin, Stephanie Forrest, and Jennifer Rexford
The Border Gateway Protocol (BGP), the Internet's interdomain routing protocol, is vulnerable to a number of damaging attacks. Proposed solutions either (i) rely on a public-key infrastructure and accurate routing registries or (ii) detect attacks only after they have spread throughout the network. However, BGP routers could avoid selecting and propagating malicious routes if they were cautious about adopting new reachability information. We describe an enhancement to BGP, Pretty Good BGP (PGBGP), that slows the dissemination of malicious routes, providing network operators time to respond before the problem escalates into a large-scale Internet attack. Results show that realistic deployments of PGBGP could provide 99% of Autonomous Systems with 24 hours to investigate and repair malicious routes without affecting prefix reachability. The result also show that without PGBGP, 40% of ASs cannot avoid using malicious routes; with PGBGP, this number drops to less than 1%. Finally, we show that PGBGP is incrementally deployable and offers significant security benefits to early adopters and their customers.
TR-CS-2005-36
Scale Invariance in Road Networks
Vamsi Kalapala, Vishal Sanwalani, Aaron Clauset, and Cristopher Moore
We study the topological and geographic structure of the national road networks of the United States, England and Denmark. By transforming these networks into their dual representation, where roads are vertices and an edge connects two vertices if the corresponding roads ever intersect, we show that they exhibit both topological and geographic scale invariance. That is, we empirically show that the degree distribution of the dual is well-characterized by a power law with exponent 2.0 < alpha < 2.5, and that journeys, regardless of their length, have a largely identical structure. To explain these properties, we introduce and analyze a simple fractal model of road placement that reproduces the observed structure, and suggests a connection between the scaling exponent alpha and the fractal dimensions governing the placement of roads and intersections.
TR-CS-2005-35
Infiniband Scalability in Open MPI
Galen M. Shipman, Tim S. Woodall, Rich L. Graham, and Arthur B. Maccabe
Infiniband is becoming an important interconnect technology in high performance computing. Recent efforts in large scale Infiniband deployments are raising scalability questions in the HPC community. Open MPI, a new production grade implementation of the MPI standard, provides several mechanisms to enhance Infiniband scalability. Initial comparisons with MVAPICH, the most widely used Infiniband MPI implementation, show similar performance but with much better scalability characterics. Specifically, small message latency is improved by up to 10% in medium/large jobs and memory usage per host is reduced by as much as 300%. In addition, Open MPI provides predicatable latency that is close to optimal without sacrificing bandwidth performance.
TR-CS-2005-34
A Sublinear-Time Randomized Approximation Scheme for the
Robinson-Foulds Metric
Nicholas D. Pattengale and Bernard M.E. Moret
The Robinson-Foulds (RF) metric is the measure most widely used in comparing phylogenetic trees; it can also be computed in linear time using Day's algorithm. When faced with the need to compare large numbers of large trees, however, even linear time becomes prohibitive. In this paper, we present a randomized approximation scheme that provides, with high probability, a (1+epsilon) approximation of the true RF metric for all pairs of trees in a given collection. Our approach is to use a sublinear-space embedding of the trees, combined with an application of the Johnson-Lindenstrauss lemma to approximate vector norms very rapidly. We discuss the consequences of various parameter choices (in the embedding and in the approximation requirements). We also implemented our algorithm as a Java class that can easily be combined with popular packages such as Mesquite; in consequence, we present experimental results illustrating the precision and running-time tradeoffs as well as demonstrating the speed of our approach.
TR-CS-2005-33
Representation of Interwoven Surfaces in 2 1/2D Drawing
Keith Wiley and Lance R. Williams
The state-of-the-art in computer drawing programs is based on a number of concepts that are over two decades old. One such concept is the use of layers for ordering the surfaces in a 2 1/2D drawing from top to bottom. A 2 1/2D drawing is a drawing that depicts surfaces in a fundamentally two-dimensional way, but also represents the relative depths of those surfaces in the third dimension. Unfortunately, the current approach based on layers unnecessarily imposes a partial ordering on the depths of the surfaces and prevents the user from creating a large class of potential drawings, e.g., of Celtic knots and interwoven surfaces. In this paper we describe a novel approach which only requires local depth ordering of segments of the boundaries of surfaces in a drawing rather than a global depth relation between entire surfaces. Our program provides an intuitive user interface with a fast learning curve that allows a novice to create complex drawings of interwoven surfaces that would be extremely difficult and time-consuming to create with standard drawing programs.
TR-CS-2005-32
Combining Data Structures with Nonstably Infinite Theories using Many-Sorted Logic
Silvio Ranise, Christophe Ringeissen, and Calogero G. Zarba
Most computer programs store elements of a given nature into container-based data structures such as lists, arrays, sets, and multisets. To verify the correctness of these programs, one needs to combine a theory S modeling the data structure with a theory T modeling the elements. This combination can be achieved using the classic Nelson-Oppen method only if both S and T are stably infinite. The goal of this paper is to relax the stable infiniteness requirement. To achieve this goal, we introduce the notion of polite theories, and we show that natural examples of polite theories include those modeling data structures such as lists, arrays, sets, and multisets. Furthemore, we provide a method that is able to combine a polite theory S with any theory T of the elements, regardless of whether T is stably infinite or not. The results of this paper generalize to many-sorted logic those recently obtained by Tinelli and Zarba concerning the combination of shiny theories with nonstably infinite theories in one-sorted logic.
TR-CS-2005-31
A Tableau-Based Decision Procedure for a Fragment of Graph Theory Involving Reachability and Acyclicity
Domenico Cantone and Calogero G. Zarba
We study the decision problem for the language DGRA (directed graphs with reachability and acyclicity), a quantifier-free fragment of graph theory involving the notions of reachability and acyclicity. We prove that the language DGRA is decidable, and that its decidability problem is NP-complete. We do so by showing that the language enjoys a small model property: If a formula is satisfiable, then it has a model whose cardinality is polynomial in the size of the formula. Moreover, we show how the small model property can be used in order to devise a tableau-based decision procedure for DGRA.
TR-CS-2005-30
Model Selection and Model Complexity: Identifying Truth Within A Space Saturated with Random Models
Paul Helman
A framework for the analysis of model selection issues is presented. The framework separates model selection into two dimensions: the model-complexity dimension and the model-space dimension. The model-complexity dimension pertains to how the complexity of a single model interacts with its scoring by standard evaluation measures. The model-space dimension pertains to the interpretation of the totality of evaluation scores obtained. Central to the analysis is the concept of evaluation coherence, a property which requires that a measure not produce misleading model evaluations. Of particular interest is whether model evaluation measures are misled by model complexity. Several common evaluation measures --- apparent error rate, the BD metric, and MDL scoring --- are analyzed, and each is found to lack complexity coherence. These results are used to consider arguments for and against the Occam razor paradigm as it pertains to overfit avoidance in model selection, and also to provide an abstract analysis of what the literature refers to as oversearch.
TR-CS-2005-29
An Extensible Message-Oriented Offload Model for High-Performance Applications
Patricia Gilfeather and Arthur B. Maccabe
In this paper, we present and verify a new model designed to capture the benefits of protocol offload in the context of high performance computing systems. Other models capture the benefits of offload or the performance of parallel applications. However, the extensible message-oriented offload model (EMO) is the first model to emphasize the performance of the network protocol itself and models it in a message-oriented rather than flow-oriented manner. EMO allows us to consider benefits associated with the reduction in message latency along with benefits associated with reduction in overhead and improvements to throughput.
In order to verify EMO, we use the tool to model a very common offload technique, interrupt coalescing. We discuss the assumptions of our model and show the modeled offload and latency performance of interrupt coalescing and no interrupt coalescing. We then present preliminary results to verify that our model is accurate.
TR-CS-2005-28
The Triton Branch Predictor
Josh Karlin, Darko Stefanovic, and Stephanie Forrest
We describe a new branch predictor that is designed to balance multiple constraints---predicting branch biases versus predicting specific branch instance behavior. Most branch instances only require branch bias information for accurate predictions while a select few require more sophisticated prediction structures. Our predictor uses a cache mechanism to classify branches and dynamically adjust the balance of the predictor. On average, our predictor mispredicts 24% less often than YAGS and 19% less often than a global perceptron predictor with the same bit budget.
TR-CS-2005-27
Distributed Recommender Systems and the Network Topologies that Love Them
Hamilton Link, Jared Saia, Terran Lane, and Randall Laviolette
One approach to distributed recommender systems is to have users sample products at random and randomly query one another for the best item they have found. We have been considering refinements to this approach that take advantage of a communication network; users may share information only with their immediate neighbors, who either by design or by nature may have common interests. In the ``mailing list model,'' users with common interests form cliques, while in the ``word-of-mouth model'' the users are distributed randomly in a scale-free network (SFN). In both models, users tell their neighbors about satisfactory products as they are found. We have found that our distributed recommender systems benefit from the communication network in terms of the number of sampled items, the number of messages sent, and the amount of ``spam'' sent. In the course of developing these results, we have revisited the question of subgraph structure in SFNs and now have a more precise understanding of the character and parameters of random SFN subgraphs than has previously been published. This new result in power-law graphs gives a clearer picture of the resilience of SFNs to random node failures; in fact, their resilience appears to have been overstated in the literature. In the case of the widely-cited ``Internet resilience'' result, high failure rates actually lead to the orphaning of half or more of the surviving nodes and the complete disintegration of the giant component after 90% of the network has failed independently of the size of the network.
TR-CS-2005-26
Machine learning approaches to siRNA efficacy prediction.
Sahar Abubucker
RNA interference (RNAi) is being widely used to study gene expression and gene regulation via selective knockdown of gene expression, which is important for functional genomic studies. RNAi refers to the biological process by which short interfering RNA (siRNA) after incorporation into the RNA induced silencing complex (RISC) degrades complementary messenger RNA (mRNA) sequences. This knockdown of mRNA prevents it from producing amino acid sequences that are responsible for gene expression. Recent studies indicate that all siRNAs do not produce the same knockdown effects. Due to the high cost of synthesizing siRNAs and the extensive effort required to test siRNAs, rational siRNA design---a priori prediction of functionality for specific siRNAs---is a critical task for practical RNAi studies. Therefore, a key component of RNAi applications is the selection of effective siRNA sequences---ones that degrade at least 80% of the targeted mRNA. The goal of siRNA efficacy prediction is to aid in designing siRNA sequences that are highly efficient in degrading target mRNA sequences. Most of the current algorithms use positional features, energy characteristics, thermodynamic properties and secondary structure predictions to predict the knockdown efficacy of siRNAs. In this work, frequently occurring patterns in siRNAs are used to make predictions about their efficacy. Time after transfection is shown to be an important factor in siRNA efficacy prediction---a feature that has been ignored in previous efficacy studies. The relevance of these extracted patterns to previous results and their biological significance are analyzed. Random feature sets are generated and the ability of these sets to predict efficacy are studied and their results discussed. Our algorithm does not require any specialized hardware and consistently performs better than other publicly available efficacy prediction algorithms.
TR-CS-2005-25
A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas
Cristopher Moore, Gabriel Istrate, Demetrios Demopoulos, and Moshe Y. Vardi
We compute the probability of satisfiability of a class of random Horn-SAT formulae, motivated by a connection with the nonemptiness problem of finite tree automata. In particular, when the maximum clause length is three, this model displays a curve in its parameter space along which the probability of satisfiability is discontinuous, ending in a second-order phase transition where it becomes continuous. This is the first case in which a phase transition of this type has been rigorously established for a random constraint satisfaction problem.
TR-CS-2005-24
Dynamic Bayesian Networks: Class Discriminative Structure Search with
an Application to Functional Magnetic Resonance Imaging Data
John Burge
The neuroanatomical behavior and underlying root causes of many mental illnesses are only moderately understood. To further understand these illnesses, the relationships among neuroanatomical regions of interest (ROIs) can be modeled. Neuroscientists have several standardized methods which have yielded much success, however, many of these methods make restrictive assumptions. On the other hand, the machine learning community has developed techniques that do not require many of these assumptions. I propose a method based on dynamic Bayesian networks (DBNs) that is capable of modeling the temporal relationships among ROIs. DBNs are graphical models that explicitly represent statistical correlations among random variables (RVs). Within the fMRI domain, it is not known a priori which ROIs are correlated. Thus, the DBN's structure modeling the ROI interactions must be learned. My research focuses on novel techniques capable of learning the structure of DBNs from a given set of data. First, I observe that under certain circumstances, learning multiple Bayesian networks, one for each possible class of data, is a better approach than the frequently employed method of learning a single BN with a class node. Second, I propose a method for determining which structures are representative of class-discriminating relationships. Third, I propose a structure search heuristic that takes advantage of the relationships among hierarchically related RVs. Finally, I propose to incorporate shrinkage (a statistical technique previously used in machine learning) in the calculation of the DBN's parameters. This proposal also summarizes preliminary work on the classification of functional magnetic resonance imaging data with my proposed scoring function.
TR-CS-2005-23
A Practical Approach to Significance Assessment of siRNA Off-target
Effects in RNA Interference
Wenzhong Zhao and Terran Lane
Detection of potential cross-hybridization (or cross-reaction) between a short oligonucleotide sequence and a longer (unintended) sequence is crucial for many biological applications, such as selecting PCR primers, microarray nucleotide probes or short interfering RNAs (siRNAs). In this paper, we propose a flexible framework for estimating the significance of siRNA off-target effects on untargeted transcripts (messager RNA, or mRNA) in the RNA interference (RNAi) process. The framework can also be extended to other applications with minor changes.
We have developed and implemented a new homology sequence search framework -- siRNA Off-target Search (SOS). SOS uses a hybrid, q-gram based approach, combining two filtering techniques using overlapping and non-overlapping q-grams. Our approach considers three types of imperfect matches based on biological experiments, namely G:U wobbles, mismatches, and bulges. The three main improvements over existing methods are: the introduction of a more general cost model (an affine bulge cost model) for siRNA-mRNA off-target alignment; the use of separate searches for alignments with and without bulges, that enables efficient discovery of potential off-target candidates in the filtration phase; and the use of position-preserving and order-preserving hit-processing techniques, that further improves the filtration efficiency. Overall, SOS achieves better performance, in terms of speed and recall/precision, than BLAST in detecting potential siRNA off-targets.
TR-CS-2005-22
A Framework for Orthology Assignment from Gene Rearrangement Data
Krister M. Swenson and Nicholas D. Pattengale and Bernard M.E. Moret
Gene rearrangements have successfully been used in phylogenetic reconstruction and comparative genomics, but usually under the assumption that all genomes have the same gene content and that no gene is duplicated. While these assumptions allow one to work with organellar genomes, they are too restrictive when comparing nuclear genomes. The main challenge is how to deal with gene families, specifically, how to identify orthologs. While searching for orthologies is a common task in computational biology, it is usually done using sequence data. We approach that problem using gene rearrangement data, provide an optimization framework in which to phrase the problem, and present some preliminary theoretical results.
TR-CS-2005-21
Evaluating EST Clustering with Simulated Data
Ke Ye and Bernard M.E. Moret
Expressed sequence tags (ESTs) provide a rapid and inexpensive approach to gene sequencing, gene discovery, and the characterization of gene regulation and alternate splicings. The first step in using ESTs is to cluster them, that is, to group them according to the gene that produced them. In these applications, clustering performance and quality are the most critical issues. Most efforts in EST clustering have focused on biological data, but such data make assessment of clustering quality and robustness difficult.
In this paper, we use the EST simulator of Hazelhurst and Bergheim, ESTSim, to study experimentally the accuracy and robustness of four different EST clustering tools, ESTate, N2tool, BlastClust, and simple hierarchical agglomerative clustering based on Smith-Waterman similarities, using the Rand index as a measure of clustering quality.
Our results indicate that N2tool consistently dominates BlastClust and that, in turn, ESTate and clustering based on Smith-Waterman similarities greatly outperform N2tool, with the much slower Smith-Waterman-based clustering slightly outperforming ESTate. We also find that, of the various parameters affecting EST generation that can be set in the ESTSim simulator (EST length, indels and substitutions, polymerase decay, stutter, and ligation), polymerase decay has by far the largest effect on the quality of clustering -- a finding that could lead to improved EST and assembly quality through the control of bench procedures.
TR-CS-2005-20
Explicit Multiregister Measurements for Hidden Subgroup Problems; or, Fourier Sampling Strikes Back
Cristopher Moore and Alexander Russell
We present an explicit measurement in the Fourier basis that solves an important case of the Hidden Subgroup Problem, including the case to which Graph Isomorphism reduces. This entangled measurement uses k=log_2 |G| registers, and each of the 2^k subsets of the registers contributes some information.
TR-CS-2005-19
For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets
Cristopher Moore and Alexander Russell
Recently Bacon, Childs and van Dam showed that the ``pretty good measurement'' (PGM) is optimal for the Hidden Subgroup Problem on the dihedral group D_n in the case where the hidden subgroup is chosen uniformly from the n involutions. We show that, for any group and any subgroup H, the PGM is the optimal one-register experiment in the case where the hidden subgroup is a uniformly random conjugate of H. We go on to show that when H forms a Gel'fand pair with its parent group, the PGM is the optimal measurement for any number of registers. This generalizes the case of the dihedral group, and includes a number of other examples of interest.
TR-CS-2005-18
The Symmetric Group Defies Strong Fourier Sampling: Part II
Cristopher Moore and Alexander Russell
Part I of this paper showed that the hidden subgroup problem over the symmetric group---including the special case relevant to Graph Isomorphism---cannot be efficiently solved by strong Fourier sampling, even if one may perform an arbitrary POVM on the coset state. In this paper, we extend these results to entangled measurements. Specifically, we show that the hidden subgroup problem on the symmetric group cannot be solved by any POVM applied to pairs of coset states. In particular, these hidden subgroups cannot be determined by any polynomial number of one- or two-register experiments on coset states.
TR-CS-2005-17
The Symmetric Group Defies Strong Fourier Sampling: Part I
Cristopher Moore, Alexander Russell, and Leonard J. Schulman
We resolve the question of whether Fourier sampling can efficiently solve the hidden subgroup problem. Specifically, we show that the hidden subgroup problem over the symmetric group cannot be efficiently solved by strong Fourier sampling, even if one may perform an arbitrary POVM on the coset state. These results apply to the special case relevant to the Graph Isomorphism problem.
TR-CS-2005-16
Scale Invariance in Global Terrorism
Aaron Clauset, Maxwell Young
Traditional analyses of international terrorism have not sought to explain the emergence of rare but extremely severe events. Using the tools of extremal statistics to analyze the set of terrorist attacks worldwide between 1968 and 2004, as compiled by the National Memorial Institute for the Prevention of Terrorism (MIPT), we find that the relationship between the frequency and severity of terrorist attacks exhibits the "scale-free" property with an exponent of close to two. This property is robust, even when we restrict our analysis to events from a single type of weapon or events within major industrialized nations. We also find that the distribution of event sizes has changed very little over the past 37 years, suggesting that scale invariance is an inherent feature of global terrorism.
TR-CS-2005-15
Cayley-Dixon construction of Resultants of Multi-Univariate Composed Polynomials
Arthur D. Chtcherba, Deepak Kapur, Manfred Minimair
The Cayley-Dixon formulation for multivariate resultants have been shown to be efficient (both experimentally and theoretically) for computing resultants by simultaneously eliminating many variables from a polynomial system. In this paper, the behavior of Cayley-Dixon resultant construction and the structure of Dixon matrices is analyzed for composed polynomial systems constructed from a multivariate system in which each variable is substituted by a univariate polynomial in a distinct variable. It is shown that Dixon projection operator (multiple of resultant) of the composed system can be expressed as a power of the resultant of the outer polynomial system multiplied by powers of the leading coefficients of the univariate polynomials substituted for variables in the outer system. A new resultant formula is derived for systems where it is known that the Cayley-Dixon construction does not contain extraneous factors. The derivation of the resultant formula for the composed system unifies all the known related results in the literature. Furthermore, it demonstrates that the resultant of a composed system can be effectively calculated by considering only the resultant of the outer system. Since the complexity of resultant computation is typically determined by the degree (and support) of the polynomial system, resultants of a composed system can be computed much faster by focusing only on the outer system.
TR-CS-2005-14
Making Chord Robust to Byzantine Attacks
Amos Fiat, Jared Saia, Maxwell Young
Chord is a distributed hash table (DHT) that requires only O(log n) links per node and performs searches with latency and message cost O(log n), where n is the number of peers in the network. Chord assumes all nodes behave according to protocol. We give a variant of Chord which, for any fixed \epsilon_{0}>0, is resilient to (1/4-\epsilon_{0})*z Byzantine nodes joining the network over a time period during which 1) there are always at least z total nodes in the network and 2) the number of correct peers joining and leaving is no more than z^k for some tunable parameter k. We assume there is an omniscient and computationally unbounded adversary controlling the Byzantine peers and that the IP-addresses of all the Byzantine peers and the locations where they join the network are carefully selected by this adversary.
Our notion of resilience is rather strong in that we not only guarantee that searches can be performed but also that we can enforce any set of ``proper behavior'' such as contributing new material, etc. In comparison to Chord, the resources required by this new variant are only a polylogarithmic factor greater in communication, messaging, and linking costs.
TR-CS-2005-13
A First-Order Stochastic Prognostic System for the Diagnosis of Helicoptor Rotor Systems for the US Navy.
Chayan Chakrabarti, Roshan Rammohan and George F. Luger
We have created a diagnostic system for the US Navy to use in the analysis of the running health of helicopter rotor systems. Although our system is not yet deployed for real-time in-flight diagnosis, we have successfully analyzed the data sets of actual helicopter rotor failures supplied by the US Navy. We discuss both critical techniques supporting the design of our stochastic diagnostic system as well as issues related to full deployment.
Our diagnostic system, called DBAYES, is composed of a logic-based, first-order, and Turing-complete set of software tools for stochastic modeling. We use this language for modeling time-series data supplied by sensors on the mechanical system. The inference scheme for these software tools is based on a variant of Pearl's loopy belief propagation algorithm. Our language contains variables that can capture general classes of situations, events, and relationships. A Turing-complete language is able to reason about potentially infinite classes and situations, similar to the analysis of Dynamic Bayesian Networks. Since the inference algorithm is based on a variant of loopy belief propagation, the language includes the Expectation Maximization type learning of parameters in the modeled domain. In this paper we briefly present the theoretical foundations for our first-order stochastic language and then demonstrate time-series modeling and learning in the context of fault diagnosis.
TR-CS-2005-12
A First-Order Stochastic Modeling Language for Diagnosis
Chayan Chakrabarti and George F. Luger
We have created a logic-based, first-order, and Turing-complete set of software tools for stochastic modeling. Because the inference scheme for this language is based on a variant of Pearl's loopy belief propagation algorithm, we call it Loopy Logic. Traditional Bayesian belief networks have limited expressive power, basically constrained to that of atomic elements as in the propositional calculus. Our language contains variables that can capture general classes of situations, events, and relationships. A Turing-complete language is able to reason about potentially infinite classes and situations, with a Dynamic Bayesian Network. Since the inference algorithm for Loopy Logic is based on a variant of loopy belief propagation, the language includes an Expectation Maximization-type learning of parameters in the modeling domain. In this paper we briefly present the theoretical foundations for our loopy-logic language and then demonstrate several examples of stochastic modeling and diagnosis.
TR-CS-2005-11
Comparison of Garbage Collectors Operating in a Large Address Space
Sergiy Kyrylkov and Darko Stefanovic
We analyze the performance of several copying garbage collection algorithms in a large address space offered by modern architectures. In particular, we describe the design and implementation of the RealOF garbage collector, an algorithm explicitly designed to exploit the features of 64-bit environments. This collector maintains a correspondence between object age and object placement in the address space of the heap. It allocates and copies objects within designated regions of memory called zones and performs garbage collection incrementally by collecting one or more ranges of memory called windows. The windows are managed so as to collect middle-aged objects, rather than almost always collecting young objects, as with a generational collector. The address-ordered heap allows us to use the same inexpensive write barrier that works for generational collectors. We show that for server applications this algorithm improves throughput and reduces heap size requirements over the best-throughput generational copying algorithms such as the Appel-style generational collector.
TR-CS-2005-10
Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively
Haixia Jia, Cristopher Moore, and Doug Strain
To test incomplete search algorithms for constraint satisfaction problems such as 3-SAT, we need a source of hard, but satisfiable, benchmark instances. A simple way to do this is to choose a random truth assignment A, and then choose clauses randomly from among those satisfied by A. However, this method tends to produce easy problems, since the majority of literals point toward the ``hidden'' assignment A. Last year, Achlioptas, Jia and Moore proposed a problem generator that cancels this effect by hiding both A and its complement. While the resulting formulas appear to be just as hard for DPLL algorithms as random 3-SAT formulas with no hidden assignment, they can be solved by WalkSAT in only polynomial time.
Here we propose a new method to cancel the attraction to A, by choosing a clause with t > 0 literals satisfied by A with probability proportional to q^t for some q < 1. By varying q, we can generate formulas whose variables have no bias, i.e., which are equally likely to be true or false; we can even cause the formula to ``deceptively'' point away from A. We present theoretical and experimental results suggesting that these formulas are exponentially hard both for DPLL algorithms and for incomplete algorithms such as WalkSAT.
TR-CS-2005-09
FINDMODEL: A tool to select the best-fit model of nucleotide substitution
Tao, N., Bruno, W.J., Abfalterer, W., Moret, B.M.E., Leitner, T., and Kuiken, C.
Choosing a model of sequence evolution is a crucial step when using DNA sequence data to reconstruct phylogenies: using a mismatched model will reduce accuracy and may lead to erroneous conclusions. FINDMODEL is a web-based tool for selecting a model of DNA (nucleotide) evolution; it is designed to be easy to use by researchers who do some sequencing and may not have access to phylogenetic packages. FINDMODEL can analyze 28 models or a restricted subset of 12 models. It creates a guide tree using Weighbor, optimizes branch lengths, calculates the likelihood for every chosen model (using baseml from the PAML package), and computes the Akaike information criterion (AIC). The model with the smallest AIC score is considered to be the best-fit model. Because of server limitations, the FINDMODEL web server processes inputs above a certain size in non-interactive mode, sending an email to the user when it has analyzed that user's data and providing a down-loadable file with the results. To test the performance of FINDMODEL, we generated simulated DNA sequences with Seq-Gen under four different models of nucleotide substitution of different complexity and compared the inferred model with the true model. We used 17 different configurations, with 5 instances for each set of parameter values. FINDMODEL returned the correct model for 75% of our test instances and also returned the correct model, but with variable site-specific rates instead of homogeneous rates for another 8%. Moreover, on all tests where FINDMODEL did not return the correct model, the normalized AIC error between the correct and the predicted models was below 0.002 (and the actual AIC difference was below 7).
TR-CS-2005-08
Inferring Ancestral Chloroplast Genomes with Duplications
Liying Cui, Jijun Tang, Bernard M. E. Moret, and Claude dePamphilis
Motivation: Genome evolution is shaped not only by nucleotide substitutions but also by structural changes including gene and genome duplications, insertions and deletions, and gene-order rearrangements. Reconstruction of phylogeny based on gene-order changes has been limited to cases where equal gene content or few deletions can be assumed. Since conserved duplicated regions are present in many genomes, the inference of duplication is needed in ancestral genome reconstruction.
Results: We apply GRAPPA-IR, a modified GRAPPA algorithm,to reconstruct ancestral chloroplast genomes containing duplicated genes. A test of GRAPPA-IR using six divergent chloroplast genomes from land plants and green algae recovers the phylogeny congruent with prior studies, while analyses that do not consider the duplications fail to obtain the accepted topology. The ancestral genome structure suggests that genome rearrangement in chloroplasts is probably limited by inverted repeats with a conserved core region. In addition, the boundaries of inverted repeats are hot spots for gene duplications or deletions.
TR-CS-2005-07
Towards practical biomolecular computers using microfluidic deoxyribozyme logic gate networks
Joseph Farfel and Darko Stefanovic
We propose a new way of implementing a biomolecular computer in the laboratory, using deoxyribozyme logic gates inside a microfluidic reaction chamber. We build upon our previous work, which simulated the operation of a deoxyribozyme-based flip-flop and oscillator in a continuous stirred-tank reactor (CSTR); unfortunately, using these logic gates in a laboratory-size CSTR is too expensive because the reagent volume is too large. For a realistic microfluidic design, the properties of microfluidic flow and mixing have to be taken into account. We describe the differences between a macrofluidic system such as the CSTR and the microfluidic setting. Liquid in a microfluidic setting exhibits laminar flow, and is more difficult to mix than in the CSTR. We use a rotary mixer, and examine how it operates so that we may properly model it. We discuss the details of our mixer simulation, including our diffusion model. We discuss why having discrete phases of influx/efflux (``charging'') and mixing is necessary, and how it changes the kinetics of the system. We then show the result of simulating both a flip-flop and an oscillator inside our rotary mixing chamber, and discuss the differences in results from the CSTR simulation.
TR-CS-2005-06
Designing Nucleotide Sequences for Computation: A Survey of Constraints
Jennifer Sager and Darko Stefanovic
We survey the biochemical constraints useful for the design of DNA code words for DNA computation. We define the DNA/RNA Code Constraint problem and cover biochemistry topics relevant to DNA libraries. We examine which biochemical constraints are best suited for DNA word design.
TR-CS-2005-05
Consensus methods using phylogenetic databases
Mahesh M. Kulkarni and Bernard M.E. Moret
Motivation: Consensus methods summarize the information from many phylogenetic trees into one tree. With the increasing use of phylogenies throughout the life sciences and with the advent of the Tree of Life project, however, the output of tree reconstruction programs must be stored for future reference, in which case post-tree analyses such as consensus should be run from the database. We set out to determine whether such analyses can be run at a reasonable cost; we chose consensus because of its general applicability and because it creates a severe demand on the database by requiring examination of every edge of every tree.
Methodology: We preprocess the data (the collections of trees) to create a new table in the database in order to support consensus computations; to support the preprocessing step, we extend the PhyloDB schema proposed by Nakhleh et al. For each of the three main consensus methods (strict, majority, and greedy consensus), we compare the PhyloDB-based computation with the computation performed on trees stored in main memory using the Phylip consensus programs. We used a large selection of datasets of varying sizes (up to 1,000 trees of up to 1,500 taxa each) and of varying degrees of commonality. Preprocessing and storing the data in an organized manner in a database is expensive: we only tallied the cost of computing the consensus from the trees stored in the database, as a researcher might do long after the original trees were generated.
Results: The computations from the database are very practical: they often run faster, and never run more than five times slower, than the computations in main memory using Phylip. The additional storage costs are easily handled by any database system, while the preprocessing costs remain reasonable (several hours for our largest datasets). Thus suitable preprocessing of phylogenetic data allows post-tree analyses to be run directly from the database at much the same cost as current memory-resident analyses.
TR-CS-2005-04
On the Bias of Traceroute Sampling, or, Power-law Degree Distributions in Regular Graphs
Dimitris Achlioptas, Aaron Clauset, David Kempe, and Cristopher Moore
Understanding the structure of the Internet graph is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining its graph structure is a surprisingly difficult task, as edges cannot be explicitly queried. Instead, empirical studies rely on traceroutes to build what are essentially single-source, all-destinations, shortest-path trees. These trees only sample a fraction of the network's edges, and a recent paper by Lakhina et al. found empirically that the resuting sample is intrinsically biased. For instance, the observed degree distribution under traceroute sampling exhibits a power law even when the underlying degree distribution is Poisson.
In this paper, we study the bias of traceroute sampling systematically, and, for a very general class of underlying degree distributions, calculate the likely observed distributions explicitly. To do this, we use a continuous-time realization of the process of exposing the BFS tree of a random graph with a given degree distribution, calculate the expected degree distribution of the tree, and show that it is sharply concentrated. As example applications of our machinery, we show how traceroute sampling finds power-law degree distributions in both delta-regular and Poisson-distributed random graphs. Thus, our work puts the observations of Lakhina et al. on a rigorous footing, and extends them to nearly arbitrary degree distributions.
TR-CS-2005-03
Finding local community structure in networks
Aaron Clauset
Although the inference of global community structure in networks has recently become a topic of great interest in the physics community, all such algorithms require that the graph be completely known. Here, we define both a measure of local community structure and an algorithm that infers the hierarchy of communities that enclose a given vertex by exploring the graph one vertex at a time. This algorithm runs in time O(d*k^2) for general graphs when d is the mean degree and k is the number of vertices to be explored. For graphs where exploring a new vertex is time-consuming, the running time is linear, O(k). We show that on computer-generated graphs this technique compares favorably to algorithms that require global knowledge. We also use this algorithm to extract meaningful local clustering information in the large recommender network of an online retailer and show the existence of mesoscopic structure.
TR-CS-2005-02
Quartet methods for phylogeny reconstruction from gene orders
Tao Liu, Jijun Tang, and Bernard M.E. Moret
Phylogenetic reconstruction from gene-rearrangement data has attracted increasing attention from biologists and computer scientists. Methods used in reconstruction include distance-based methods, parsimony methods using sequence-based encodings, and direct optimization. The latter, pioneered by Sankoff and extended by us with the software suite GRAPPA, is the most accurate approach; however, its exhaustive approach means that it can be applied only to small datasets of fewer than 15 taxa. While we have successfully scaled it up to 1,000 genomes by integrating it with a disk-covering method (DCM-GRAPPA), the recursive decomposition may need many levels of recursion to handle datasets with 1,000 or more genomes. We thus investigated quartet-based approaches, which directly decompose the datasets into subsets of four taxa each; such approaches have been well studied for sequence data, but not for gene-rearrangement data. We give an optimization algorithm for the NP-hard problem of computing optimal trees for each quartet, present a variation of the dyadic method (using heuristics to choose suitable short quartets), and use both in simulation studies. We find that our quartet-based method can handle more genomes than the base version of GRAPPA, thus enabling us to reduce the number of levels of recursion in DCM-GRAPPA, but is more sensitive to the rate of evolution, with error rates rapidly increasing when saturation is approached.
TR-CS-2005-01
A Study of Garbage Collection With a Large Address Space for Server Applications
Sergiy Kyrylkov and Darko Stefanovic
We analyze the performance of several copying garbage collection algorithms in a large address space offered by modern architectures. In particular, we describe the design and implementation of the RealOF garbage collector, an algorithm explicitly designed to exploit the features of 64-bit environments. This collector maintains a correspondence between object age and object placement in the address space of the heap. It allocates and copies objects within designated regions of memory called zones and performs garbage collection incrementally by collecting one or more ranges of memory called windows. The address-ordered heap allows us to use the same inexpensive write barrier that works for traditional generational collectors. We show that for server applications this algorithm improves throughput and reduces heap size requirements over the best-throughput generational copying algorithms such as the Appel-style generational collector.
TR-CS-2004-35
Finding community structure in very large networks
Aaron Clauset, M. E. J. Newman, and Cristopher Moore
The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O(m d log n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with m ~ n and d ~ log n, in which case our algorithm runs in essentially linear time, O(n log^2 n). As an example of the application of this algorithm we use it to analyze a network of items for sale on the web-site of a large online retailer, items in the network being linked if they are frequently purchased by the same buyer. The network has more than 400,000 vertices and 2 million edges. We show that our algorithm can extract meaningful communities from this network, revealing large-scale patterns present in the purchasing habits of customers.
TR-CS-2004-34
Computational Challenges from the Tree of Life
B.M.E. Moret
A phylogeny is a reconstruction of the evolutionary history of a group of organisms. Phylogenies are used throughout the life sciences, as they offer a structure around which to organize the knowledge and data accumulated by researchers. Computational phylogenetics has been a rich area for algorithm design over the last 15 years. The biology community has embarked on an enormously ambitious project, the assembly of the Tree of Life---the phylogeny of all organisms on this planet. This project presents a true computational grand challenge: current phylogenetic methods can barely handle a few hundred organisms, yet the Tree of Life has an estimated 10--100 million organisms. Thus, while data collection and cataloguing is one of the major tasks, algorithm design and engineering is a crucial enabling component of the project. In this paper, I briefly introduce the principles of phylogenetic analysis, then discuss the computational challenges posed by the Tree of Life project, from the design and validation of computationally useful models of evolution to the actual computation and assessment of the Tree of Life itself.
TR-CS-2004-33
Building the components for a biomolecular computer
Clint Morgan, Darko Stefanovic, Cristopher Moore and Milan N. Stojanovic
We propose a new method for amorphous bio-compatible computing using deoxyribozyme logic gates in which oligonucleotides act as enzymes on other oligonucleotides, yielding oligonucleotide products. Moreover, these reactions can be controlled by inputs that are also oligonucleotides. We interpret these reactions as logic gates, and the concentrations of chemical species as signals. Since these reactions are homogeneous, i.e., they use oligonucleotides as both inputs and outputs, we can compose them to construct complex logic circuits. Thus, our system for chemical computation offers functionality similar to conventional electronic circuits with the potential for deployment inside of living cells. Previously, this technology was demonstrated in closed-system batch reactions, which limited its computational ability to simple feed-forward circuits. In this work, we go beyond closed systems, and show how to use thermodynamically open reactors to build biomolecular circuits with feedback. The behavior of an open chemical system is determined both by its chemical reaction network and by the influx and efflux of chemical species. This motivates a change in design process from that used with closed systems. Rather than focusing solely on the stoichiometry of the chemical reactions, we must carefully examine their kinetics. Systems of differential equations and the theory of dynamical systems become the appropriate tools for designing and analyzing such systems. Using these tools, we present an inverter. Next, by introducing feedback into the reaction network, we construct devices with a sense of state. We show how a combination of analytical approximation techniques and numerical methods allows us to tune the dynamics of these systems. We demonstrate a flip-flop which exhibits behavior similar to the RS flip-flop of electronic computation. It has two states in which the concentration of one oligonucleotide is high and the other is low or vice versa. We describe how to control the state of the flip-flop by varying the concentration of the substrates. Moreover, there are large regions of parameter space in which this behavior is robust, and we show how to tune the influx rates as a function of the chemical reaction rates in a way that ensures bistability.
TR-CS-2004-32
Efficient RNAi-Based Gene Family Knockdown via Set Cover Optimization
Wenzhong Zhao, M. Leigh Fanning and Terran Lane
RNA interference (RNAi) is a recently discovered genetic immune system with widespread therapeutic and genomic applications. In this paper, we address the problem of selecting an efficient set of initiator molecules (siRNAs) for RNAi-based gene family knockdown experiments. Our goal is to select a minimal set of siRNAs that (a) cover a targeted gene family or a specified subset of it, (b) do not cover any untargeted genes, and (c) are individually highly effective at inducing knockdown. We show that the problem of minimizing the number of siRNAs required to knock down a family of genes is NP-Hard via a reduction to the set cover problem. We also give a formal statement of a generalization of the basic problem that incorporates additional biological constraints and optimality criteria. We modify the classical branch-and-bound algorithm to include some of these biological criteria. We find that, in many typical cases, these constraints reduce the search space enough that we are able to compute exact minimal siRNA covers within reasonable time. For larger cases, we propose a probabilistic greedy algorithm for finding minimal siRNA covers efficiently. Our computational results on real biological data show that the probabilistic greedy algorithm produces siRNA covers as good as the branch-and-bound algorithm in most cases. Both algorithms return minimal siRNA covers with high predicted probability that the selected siRNAs will be effective at inducing knockdown. We also examine the role of "off-target" interactions - the constraint of avoiding covering untargeted genes can, in some cases, substantially increase the complexity of the resulting solution. Overall, however, we find that in many common cases, our approach significantly reduces the number of siRNAs required in gene family knockdown experiments, as compared to knocking down genes independently.
TR-CS-2004-31
On Algorithms for Choosing a Random Peer
Valerie King, Scott Lewis and Jared Saia
In this paper, we study the problem of choosing a peer uniformly at random from the set of all peers in a distributed hash table(DHT). We present two new algorithms to solve this problem and show that these algorithms have good theoretical and empirical properties.
TR-CS-2004-30
Linear Programming for Phylogenetic Reconstruction Based on Gene Rearrangements
Jijun Tang and Bernard M.E. Moret
Phylogenetic reconstruction from gene rearrangements has attracted increasing attention from biologists and computer scientists over the last few years. Methods used in reconstruction include distance-based methods, parsimony methods using sequence-based encodings, and direct optimization. The latter, pioneered by Sankoff and extended by us with the software suite GRAPPA, is the most accurate approach, but has been limited to small genomes because the running time of its scoring algorithm grows exponentially with the number of genes in the genome. We report here on a new method to compute a tight lower bound on the score of a given tree, using a set of linear constraints generated through selective applications of the triangle inequality. Our method generates an integer linear program with a carefully limited number of constraints, rapidly solves its relaxed version, and uses the result to provide a tight lower bound. Since this bound is very close to the optimal tree score, it can be used directly as a selection criterion, thereby enabling us to bypass entirely the expensive scoring procedure. We have implemented this method within our GRAPPA software and run several series of experiments on both biological and simulated datasets to assess its accuracy. Our results show that using the bound as a selection criterion yields excellent trees, with error rates below 5% up to very large evolutionary distances, consistently beating the baseline Neighbor-Joining. Our new method enables us to extend the range of applicability of the direct optimization method to chromosomes of size comparable to those of bacteria, as well as to datasets with complex combinations of evolutionary events.
TR-CS-2004-29
A Sequential Monte Carlo Sampling Approach for Cell Population
Deconvolution from Microarray Data
Sushmita Roy, Terran Lane, Chris Allen, Anthony D. Aragon, and
Margaret Werner-Washburne
Microarray analyses assume that gene expressions are measured from synchronous, homogeneous cell populations. In reality, the measured gene expression is produced by a mixture of populations in different stages of the cellular life cycle. Hence, it is important to estimate the proportions of cells in different stages and to incorporate this information in the analysis of gene expression, clusters, or function. In this paper we propose a novel unsupervised learning approach that models biological processes, such as the cell-cycle, as a hidden state-space model and uses a particle-filter based approach for estimating model parameters. Our approach finds a maximum a posteriori (MAP)estimate of the cell proportions given the gene expression and an estimate of the stage dependant gene expression. Evaluation of statistical validity of our approach using randomized data tests reveals that our model captures true temporal dynamics of the data. We have applied our approach to model the yeast cell-cycle and extracted profiles of the population dynamics for different stages of the cell-cycle. Our results are in agreement with biological knowledge and reproducible in multiple runs of our algorithm, suggesting that our approach is capable of extracting biologically meaningful and statistically significant information. Finally, the stage dependant gene expression can be used to determine clusters of active genes on a per-stage basis.
TR-CS-2004-28
Bayesian Classification of FMRI Data: Evidence for Altered Neural Networks in Dementia
John Burge, Vincent P. Clark, Terran Lane, Hamilton Link and Shibin Qiu
The alterations in functional relationships among brain regions associated with senile dementia are not well understood. We present a machine learning technique using dynamic Bayesian networks (DBNs) that extracts causal relationships from functional magnetic resonance imaging (fMRI) data. Based on these relationships, we build neural-anatomical networks that are used to classify patient data as belonging to healthy or demented subjects. Visual-motor reaction time task data from healthy young, healthy elderly, and demented elderly patients (Buckner et al. 2000) was obtained through the fMRI Data Center. To reduce the extremely large volume of data acquired and the high level of noise inherent in fMRI data, we averaged data over neuroanatomical regions of interest. The DBNs were able to correctly discriminate young vs. elderly subjects with 80% accuracy, and demented vs. healthy elderly subjects with 73% accuracy. In addition, the DBNs identified causal neural networks present in 93% of the healthy elderly studied. The classification efficacy of the DBN was similar to two other widely used machine learning classification techniques: support vector machines (SVMs) and Gaussian nave Bayesian networks (GNBNs), with the important advantage that the DBNs provides candidate neural anatomical networks associated with dementia. Networks found in demented but not healthy elderly patients included substantial involvement of the amygdala, which may be related to the anxiety and agitation associated with dementia. DBNs may ultimately provide a biomarker for dementia in its early stages, and may be helpful for the diagnosis and treatment of other CNS disorders.
TR-CS-2004-27
Parallel Euler tour and Post Ordering for Parallel Tree Accumulations:
An implementation technical report
Sinan Al-Saffar and David Bader
Tree accumulation is the process of aggregating data placed in tree nodes according to their tree structure. The aggregation can be a simple arithmetic operation or a more complex function. This is similar to arithmetic expression evaluation except there is one operation to be performed on the entire tree and is thus implied and internal nodes do not contain arithmetic operations. We have written a program to implement accumulations on tree data structures in parallel. We developed and tested our code on a fourteen-processor Sun SMP and implemented parallelism using the threaded SIMPLE library. We report our results and describe our work in this report. To implement tree accumulation and generally other algorithms in parallel one requires input to be arranged and preprocessed in a certain way, for example a tree needs to be supplied in a post ordering or preordering of its nodes. These operations are as important as the main task one is addressing since if they are not done efficiently, they become bottle-necks for performance. Some authors wave their hand and assume a certain property exists in the data after a "preprocessing step". We address these aspects in this report in detail. We demonstrate how to obtain the Euler tour of a tree in parallel and how to use this tour to obtain the post order of the tree nodes in parallel. We then show how to perform parallel tree accumulations also in parallel using this obtained post ordering.
TR-CS-2004-26
Distance correction for large pairwise genomic distances
J. Tang and B.M.E. Moret
Phylogenetic reconstruction from gene-order data has attracted attention from both biologists and computer scientists over the last few years. Our software suite, GRAPPA and its extension DCM-GRAPPA, has been applied with excellent results to datasets (real and simulated) of up to a thousand organellar genomes and should scale up to even larger datasets. However, scaling it up from the small organellar genomes (with a hundred or so genes) to larger genomes such as bacterial genomes (with several thousand genes) or eukaryotic genomes (with tens of thousands of genes) remains a problem, in terms of both running time and accuracy. The cost of the basic optimization loop grows exponentially with the genomic distance -- and distances are much larger among the widely varying bacterial and eukaryotic genomes than among the highly stable organellar ones. Even with the smaller genomes, the presence of large pairwise evolutionary distances creates a two-sided problem: edit distances will seriously underestimate the evolutionary distance and distance corrections will introduce the risk of serious overestimates. In a computation based on the use of lower bounds to eliminate much of the search space, underestimates lead to loose bounds and poor pruning and thus to excessive running times, while overestimates may lead to the elimination of the best solutions and thus to excessive errors. This problem due to large pairwise distances has been studied in sequence-based phylogenetic reconstruction; the proposed solution has been some form of limit on the largest possible values produced in the process of correction. One particular approach, the so-called "fix-factor," has proved very successful. In this paper, we present an adaptation of the fix-factor technique to gene-order data. Experiments on both biological and simulated datasets suggest that, using our fix-factor adaptation, the pruning rate can be dramatically increased without sacrificing accuracy.
TR-CS-2004-25
Advances in Phylogeny Reconstruction from Gene Order and Content Data
Bernard M.E. Moret and Tandy Warnow
Genomes can be viewed in terms of their gene content and the order in which the genes appear along each chromosome. Evolutionary events that affect the gene order or content are ``rare genomic events" (rarer than events that affect the composition of the nucleotide sequences) and have been advocated by systematists for inferring deep evolutionary histories. This chapter surveys recent developments in the reconstruction of phylogenies from gene order and content, focusing on their performance under various stochastic models of evolution. Because such methods are currently quite restricted in the type of data they can analyze, we also present current research aimed at handling the full range of whole-genome data.
TR-CS-2004-24
Properties of Compatibility and Consensus Sets of Phylogenetic Trees
Tanya Y. Berger-Wolf
One of the fundamental problems in phylogeny reconstruction is combining a set of trees into one ``representative'' tree. There are exist numerous methods for that purpose that combine trees over the same taxa (consensus) or different taxa (supertree) sets. However, many limitations and shortcomings of these methods have been pointed out. In this paper, we state various desirable properties of ``representative'' trees and the impact of considering sets of trees to represent the input. We analyze the sets of compatibility trees and several consensus sets and show which of the properties are satisfied. Specifically, one of the desired properties is the output-polynomial enumeration of the set itself.
TR-CS-2004-23
Why Mapping the Internet is Hard
Aaron Clauset and Cristopher Moore
Despite great effort spent measuring topological features of large networks like the Internet, it was recently argued that sampling based on taking paths through the network (e.g., traceroutes) introduces a fundamental bias in the observed degree distribution. We examine this bias analytically and experimentally. For classic random graphs with mean degree c, we show analytically that traceroute sampling gives an observed degree distribution P(k) ~ k^{-1} for k < c, even though the underlying degree distribution is Poisson. For graphs whose degree distributions have power-law tails P(k) ~ k^{-alpha}, the accuracy of traceroute sampling is highly sensitive to the population of low-degree vertices. In particular, when the graph has a large excess (i.e., many more edges than vertices), traceroute sampling can significantly misestimate alpha.
TR-CS-2004-22
How much backtracking does it take to color random graphs?
Rigorous results on heavy tails
Haixia Jia and Cristopher Moore
For many backtracking search algorithms, the running time has been found experimentally to have a heavy-tailed distribution, in which it is often much greater than its median. We analyze two natural variants of the Davis-Putnam-Logemann-Loveland (DPLL) algorithm for Graph 3-Coloring on sparse random graphs of average degree c. Let P_c(b) be the probability that DPLL backtracks b times. First, we calculate analytically the probability P_c(0) that these algorithms find a 3-coloring with no backtracking at all, and show that it goes to zero faster than any analytic function as c -> c^* = 3.847... Then we show that even in the ``easy'' regime 1 < c < c^* where P_c(0) > 0 --- including just above the degree c=1 where the giant component first appears --- the expected number of backtrackings is exponentially large with positive probability. To our knowledge this is the first rigorous proof that the running time of a natural backtracking algorithm has a heavy tail for graph coloring.
TR-CS-2004-21
From spin glasses to hard satisfiable formulas
Haixia Jia, Cris Moore, and Bart Selman
We introduce a highly structured family of hard satisfiable 3-SAT formulas corresponding to an ordered spin-glass model from statistical physics. This model has provably ``glassy'' behavior; that is, it has many local optima with large energy barriers between them, so that local search algorithms get stuck and have difficulty finding the true ground state, i.e., the unique satisfying assignment. We test the hardness of our formulas with two Davis-Putnam solvers, SatZ and zChaff, the recently introduced Survey Propagation (SP), and two local search algorithms, WalkSAT and Record-to-Record Travel (RRT). We compare our formulas to random 3-XOR-SAT formulas and to two other generators of hard satisfiable instances, the minimum disagreement parity formulas of Crawford et al., and Hirsch's hgen. For the complete solvers the running time of our formulas grows exponentially in sqrt{n}, and exceeds that of random 3-XOR-SAT formulas for small problem sizes. SP is unable to solve our formulas with as few as 25 variables. For WalkSAT, our formulas appear to be harder than any other known generator of satisfiable instances. Finally, our formulas can be solved efficiently by RRT but only if the parameter d is tuned to the height of the barriers between local minima, and we use this parameter to measure the barrier heights in random 3-XOR-SAT formulas as well.
TR-CS-2004-20
Counting Connected Graphs and Hypergraphs via the Probabilistic Method
Amin Coja-Oghlan, Cristopher Moore and Vishal Sanwalani
It is exponentially unlikely that a sparse random graph or hypergraph is connected, but such graphs occur commonly as the giant components of larger random graphs. This simple observation allows us to estimate the number of connected graphs, and more generally the number of connected d-uniform hypergraphs, on n vertices with m=O(n) edges. We also estimate the probability that a binomial random hypergraph H_d(n,p) is connected, and determine the expected number of edges of H_d(n,p) conditioned on its being connected. This generalizes prior work of Bender, Canfield, and McKay on the number of connected graphs; however, our approach relies on elementary probabilistic methods, extending an approach of O'Connell, rather than using powerful tools from enumerative combinatorics, such as generating functions and complex analysis. We also estimate the probability for each t that, given k=O(n) balls in n bins, every bin is occupied by at least t balls.
TR-CS-2004-19
The Chromatic Number of Random Regular Graphs
Dimitris Achlioptas and Cristopher Moore
Given any integer d >= 3, let k be the smallest integer such that d < 2k log k. We prove that with high probability the chromatic number of a random d-regular graph is k, k+1, or k+2, and that if (2k-1) log k < d < 2k log k then the chromatic number is either k+1 or k+2.
TR-CS-2004-18
Enhancing Privacy through Negative Representations of Data
Fernando Esponda, Stephanie Forrest and Paul Helman
The paper introduces the concept of a negative database, in which a set of records DB is represented by its complement set. That is, all the records not in DB are represented, and DB itself is not explicitly stored. After introducing the concept, several results are given regarding the feasibility of such a scheme and its potential for enhancing privacy. It is shown that a database consisting of n, l-bit records can be represented negatively using only O(ln) records. It is also shown that membership queries for DB can be processed against the negative representation in time no worse than linear in its size and that reconstructing the database DB represented by a negative database NDB given as input is an NP-hard problem when time complexity is measured as a function of the size of NDB.
TR-CS-2004-17
Toward a Topological Theory of Relational Reinforcement Learning
for Navigation Tasks
Terran Lane and Andrew Wilson
We examine application of relational learning methods to reinforcement learning in spatial navigation tasks. Specifically, we consider a goal-seeking agent with noisy control actions embedded in an environment with strong topological structure. While formally a Markov decision process (MDP), this task possesses special structure derived from the underlying topology that can be exploited to speed learning. We describe relational policies for such environments that are relocatable by virtue of being parameterized solely in terms of the relations (distance and direction) between the agent's current state and the goal state. We demonstrate that this formulation yields significant learning improvements in completely homogeneous environments for which exact policy relocation is possible. We also examine the effects of non-homogeneities such as walls or obstacles and show that their effects can be neglected if they fall outside of a closed-form envelope surrounding the optimal path between the agent and the goal. To our knowledge, this is the first closed-form result for the structure of an envelope in an MDP. We demonstrate that relational reinforcement learning in an environment that obeys the envelope constraints also yields substantial learning performance improvements.
TR-CS-2004-16
A Decision-Theoretic, Semi-Supervised Model for Intrusion Detection
Terran Lane
In this paper, we develop a model of intrusion detection based on semi-supervised learning. This model attempts to fuse misuse detection with anomaly detection and to exploit strengths of both. In the process of developing this model, we examine different cost functions for the IDS domain and identify two key assumptions that are often implicitly employed in the IDS literature. We demonstrate that relaxing these assumptions requires a decision-theoretic control maker based on the partially observable Markov decision process (POMDP) framework. This insight opens up a novel space of IDS models and allows precise quantification of the computational expense of optimal decision making for specific IDS variants (e.g., additional data sources) and cost functions. While decision-making for many POMDPs is formally intractable, recognizing the equivalence of the IDS problem to solution of a POMDP makes available the wide variety of exact and approximate learning techniques developed for POMDPs. We demonstrate the performance of the simplest of these models (for which optimal decision-making is tractable) on a previously studied user-level IDS problem, showing that, at the lower limit, our semi-supervised learning model is equivalent to a pure anomaly detection system, but that our model is also capable of exploiting increasing degrees of intermittently labeled data. When such intermittently labeled data is available, our system performs strongly compared to a number of current, pure anomaly detection systems.
TR-CS-2004-15
Approximating the True Evolutionary Distance Between Two Genomes
Krister M. Swenson, Mark Marron, Joel V. Earnest-DeYoung, and Bernard M.E. Moret
As more and more genomes are sequenced, evolutionary biologists are becoming increasingly interested in evolution at the level of whole genomes, in scenarios in which the genome evolves through insertions, deletions, and movements of genes along its chromosomes. In the mathematical model pioneered by Sankoff and others, a unichromosomal genome is represented by a signed permutation of a multiset of genes; Hannenhalli and Pevzner showed that the edit distance between two signed permutations of the same set can be computed in polynomial time when all operations are inversions. El-Mabrouk extended that result to allow deletions and a limited form of insertions (which forbids duplications); in turn we extended it to compute a nearly optimal edit sequence between an arbitrary genome and the identity permutation. In this paper we extend and improve our previous work to handle duplications as well as insertions and present an algorithm for computing true evolutionary distances (as opposed to the less useful edit distances) in a framework involving insertions, duplications, deletions, and inversions. We present experimental results showing that our algorithm produces very good estimates of the true evolutionary distance up to a (high) threshold of saturation; indeed, the distances thus produced are good enough to enable a simple neighbor-joining procedure to reconstruct our test trees with high accuracy.
TR-CS-2004-14
Reversing Gene Erosion--Reconstructing Ancestral Bacterial Genomes
from Gene-Content and Order Data
Joel V. Earnest-DeYoung, Emmanuelle Lerat, Bernard M.E. Moret
In the last few years, it has become routine to use gene-order data to reconstruct phylogenies, both in terms of edge distances (parsimonious sequences of operations that transform one end point of the edge into the other) and in terms of genomes at internal nodes, on small, duplication-free genomes. Current gene-order methods break down, though, when the genomes contain more than a few hundred genes, possess high copy numbers of duplicated genes, or create edge lengths in the tree of over one hundred operations. We have constructed a series of heuristics that allow us to overcome these obstacles and reconstruct edges distances and genomes at internal nodes for groups of larger, more complex genomes. We present results from the analysis of a group of thirteen modern gamma-proteobacteria, as well as from simulated datasets.
TR-CS-2004-13
Logic-Based First-Order Stochastic Language that Learns
Roshan Rammohan, Chayan Chakrabarti, Dan Pless, Kshanti Greene and
George Luger
We have created a logic-based, first-order, and Turing-complete set of software tools for stochastic modeling. Because the inference scheme for this language is based on a variant of Pearl's loopy belief propagation algorithm, we call it Loopy Logic. Traditional Bayesian belief networks have limited expressive power, basically constrained to that of atomic elements as in the propositional calculus. A language contains variables that can capture general classes of situations, events, and relationships. A Turing-complete language is able to reason about potentially infinite classes and situations.
Since the inference algorithm for Loopy Logic is based on a variant of loopy belief propagation, the language includes an Expectation Maximization-type learning of parameters in the modeling domain. In this paper we present the theoretical foundations for our loopy-logic language and then demonstrate several examples using the Loopy Logic system for stochastic modeling and diagnosis.
TR-CS-2004-12
Parallel Kernel Computation for High Dimensional Data and Its Application to
fMRI Image Classification
Shibin Qiu and Terran Lane
Kernel method is frequently used for support vector machine classification and regression prediction. Kernel computation for high dimensional data demands heavy computing power. To shorten the computing time, we study the performance issues of parallel kernel computation. We design the parallel algorithms and apply them to the classification of fMRI images, which have extreme high dimensionality. We first formulate the kernel calculation through linear algebraic manipulation so that the operations can be performed in parallel with minimum communication cost. We then implement the algorithms on a cluster of computing workstations using MPI. Finally, we experiment with the fMRI data to study the speedups and communication behaviors.
TR-CS-2004-11
Learning Optimal Augmented Bayes Networks
Vikas Hamine and Paul Helman
Naive Bayes is a simple Bayesian classifier with strong independence assumptions among the attributes. This classifier, desipte its strong independence assumptions, often performs well in practice. It is believed that relaxing the independence assumptions of a naive Bayes classifier may improve the classification accuracy of the resulting structure. While finding an optimal unconstrained Bayesian Network (for most any reasonable scoring measure) is an NP-hard problem, it is possible to learn in polynomial time optimal networks obeying various structural restrictions. Several authors have examined the possibilities of adding augmenting arcs between attributes of a Naive Bayes classifier. Friedman, Geiger and Goldszmidt define the TAN structure in which the augmenting arcs form a tree on the attributes, and present a polynomial time algorithm that learns an optimal TAN with respect to MDL score. Keogh and Pazzani define Augmented Bayes Networks in which the augmenting arcs form a forest on the attributes (a collection of trees, hence a relaxation of the stuctural restriction of TAN), and present heuristic search methods for learning good, though not optimal, augmenting arc sets. The authors, however, evaluate the learned structure only in terms of observed misclassification error and not against a scoring metric, such as MDL. In this paper, we present a simple, polynomial time greedy algorithm for learning an optimal Augmented Bayes Network with respect to MDL score.
TR-CS-2004-10
Reconstructing Phylogenies from Gene-Content and Gene-Order Data
Bernard M.E. Moret, Jijun Tang, and Tandy Warnow
Gene-order data has been used successfully to reconstruct organellar phylogenies; it offers low error rates, the potential to reach farther back in time than through DNA sequences (because genome-level events are much rarer than DNA point mutations), and relative immunity from the so-called gene-tree vs. species-tree problem (caused by the fact that the evolutionary history of specific genes is not isomorphic to that of the organism as a whole). It has also provided deep mathematical and algorithmic results dealing with permutations and shortest sequences of operations on these permutations. Recent developments include generalizations to handle insertions, duplications, and deletions, scaling to large numbers of organisms, and, to a lesser extent, to larger genomes; and the first Bayesian approach to the reconstruction problem. We survey the state-of-the-art in using such data for phylogenetic reconstruction, focusing on recent work by our group that has enabled us to handle arbitrary insertions, duplications, and deletions of genes, as well as inversions of gene subsequences. We conclude with a list of research questions (mathematical, algorithmic, and biological) that will need to be addressed in order to realize the full potential of this type of data.
TR-CS-2004-09
Choosing a Random Peer
Valerie King and Jared Saia
Abstract: We present the first fully distributed algorithm which chooses a peer uniformly at random from the set of all peers in a distributed hash table(DHT). Our algorithm has latency O(log n) and sends O(log n) message in expectation for a standard DHT like Chord~cite{chord01}. Our motivation for studying this problem is threefold: to enable data collection by statistically rigorous sampling methods; to provide support for randomized, distributed algorithms over peer-to-peer networks; and to support the creation and maintenance of random links, and thereby offer a simple means of improving fault-tolerance.
TR-CS-2004-08
Adaptive Radio: Achieving Consensus Using Negative Preferences
Dennis L. Chao, Justin Balthrop, and Stephanie Forrest
We introduce the use of negative preferences to produce solutions that are acceptable to a group of users. Using negative preference profiling, a system determines which solutions are unsatisfactory to individual users, and it is assumed that the remaining solutions are satisfactory. To satisfy all members of the group, the system can propose solutions that are not unsatisfactory to any of the group's members. This approach can find a large set of solutions that are acceptable to a group and simplify user profiling. To demonstrate these benefits, we implemented Adaptive Radio, a system that selects music to play in a shared environment. Rather than attempting to play the songs that users want to hear, the system avoids playing songs that they do not want to hear. Negative preferences can potentially be applied to other domains, such as information filtering, intelligent environments, and collaborative design.
TR-CS-2004-07
Rec-I-DCM3: A Fast Algorithmic Technique for Reconstructing Large
Phylogenetic Trees
U. Roshan, B.M.E. Moret, T.L. Williams, and T. Warnow
Estimations of phylogenetic trees are most commonly obtained through the use of heuristics for maximum parsimony (MP), an NP-hard problem. Although apparently good heuristics have been devised, even they fail to produce good solutions in reasonable time for large datasets -- today's limit is unknown, but is probably less than 1,000 sequences. In this paper we present a promising new divide-and-conquer technique, Recursive-Iterative-DCM3 (Rec-I-DCM3). This new method belongs to our family of Disk-Covering Methods (DCMs); it operates by iteratively dividing the input set of sequences into smaller overlapping subproblems, solving them using some base method (e.g., neighbor-joining, heuristic MP, heuristic ML, etc.), and then merging these subtrees into a single phylogenetic tree. Thus Rec-I-DCM3 is designed to boost the performance of its base method. Our new method is composed of a new DCM, which we call DCM3, but uses recursion and iteration as well. The result is a booster that can produce dramatic improvements for standard heuristics, as well as substantial improvements over the very best methods (which are harder to improve). We demonstrate the power of this new DCM on ten large biological datasets ranging from 1,322 to 13,921 sequences.
TR-CS-2004-06
Quality Measures for Phylogenetic Networks
L. Nakhleh, A. Clement, T. Warnow, C.R. Linder, and B.M.E. Moret
Phylogenies---the evolutionary histories of groups of organisms---are one of the most widely used tools throughout the life sciences, as well as objects of research within systematics, evolutionary biology, epidemiology, etc. Almost every tool devised to date to reconstruct phylogenies produces phylogenetic trees; yet it is widely understood and accepted that trees oversimplify the evolutionary histories of many groups of organisms, most prominently bacteria (because of lateral transfer of genes between different species) and plants (because of hybrid speciation). In order to develop a comparable toolkit of algorithms to reconstruct and analyze phylogenetic networks, we must start with measures of quality.
In this paper, we address the quality issue in terms of topological accuracy (the preferred criterion, but one usually limited to simulation studies) and of parsimony scores (a surrogate criterion in widespread use). Parsimony is one of the most widely used and studied criteria for tree reconstruction and evaluation. Hein suggested a straightforward extension of the parsimony criterion to networks. In this paper, we discuss the pros and cons of this extension and study a parameterized version of the network parsimony criterion. In particular, we give a family of polynomial-time algorithms to compute the parsimony score for a special case of phylogenetic networks, which we call k-gt-networks (gt for galled tree, after the terminology of Gusfield). We also introduce and compare three different measures of topological accuracy, each based on a different characterization of the network topology. We establish that all three measures are metrics on the space of k-gt-networks and show that, in spite of different origins, their values are closely related.
Our work is a first step towards bridging the gap between phylogenetic trees and phylogenetic networks. Based on our measures and using the excellent properties of k-gt-networks, reconstruction methods can now be devised, tested, and properly assessed.
TR-CS-2004-05
Phylogenetic Reconstruction from Arbitrary Gene-Order Data
Jijun Tang, Bernard M.E. Moret, Liying Cui, and Claude W. dePamphilis
Phylogenetic reconstruction from gene-order data has attracted attention from both biologists and computer scientists over the last few years. So far, our software suite GRAPPA is the most accurate approach, but it requires that all genomes have identical gene content, with each gene appearing exactly once in each genome. Some progress has been made in handling genomes with unequal gene content, both in terms of computing pairwise genomic distances and in terms of reconstruction. In this paper, we present a new approach for computing the median of three arbitrary genomes and apply it to the reconstruction of phylogenies from arbitrary gene-order data. We implemented these methods within GRAPPA and tested them on simulated datasets under various conditions as well as on a real dataset of chloroplast genomes; we report the results of our simulations and our analysis of the real dataset and compare them to reconstructions made by using neighbor-joining and using the original GRAPPA on the same genomes with equal gene contents. Our new approach is remarkably accurate both in simulations and on the real dataset, in contrast to the distance-based approaches and to reconstructions using the original GRAPPA applied to equalized gene contents.
TR-CS-2004-04
The Relationship Between Maximum Parsimony Scores and
Phylogenetic Tree Topologies
Tiffani L. Williams, Tanya Berger-Wolf, Bernard M.E. Moret, Usman
Roshan, and Tandy Warnow
Heuristics for the NP-hard maximum parsimony (MP) problem constitute the principle mechanism for estimating phylogenies on large datasets (> 100 sequences). Unfortunately, MP heuristics spend an enormous amount of computational time searching for the optimal solution; on large datasets, MP searches may require months or even years to solve optimally. On the other hand, near-optimal phylogenies require less computational time to reach---possibly providing a good approximation of the tree topology (branching order) of the optimal solution.
In this paper, we investigate whether it is necessary to solve MP optimally. Our experiments explore the relationship between solving MP to various degrees of accuracy and the implied improvement in the estimation of the topology of the optimal tree. We show that near-optimal solutions to MP (within a fraction of one percent of optimal) give highly accurate estimations of optimal tree topologies, and can be obtained in a fraction of the time needed to solve to optimality. Moreover, we propose a preliminary stopping rule that halts a phylogenetic search early with a good of approximation of the optimal solution. Large-scale estimations of phylogenetic trees do not require exact solutions to MP. Our results demonstrate that finding good near-optimal solutions quickly is a more fruitful objective for MP heuristics.
TR-CS-2004-03
On a Homomorphism Property of Hoops
R. Veroff and M. Spinks
We present a syntactic proof that equation
e -> (b . c) = (e -> b) . (e -> c)
is satisfied in a hoop A for any idempotent e in A and all b, c in A. The theorem both answers a question and generalizes a result of Ferreirim.
TR-CS-2004-02
Short Equational Bases for Ortholattices: Proofs and Countermodels
W. McCune, R. Padmanabhan, M. A. Rose and R. Veroff
This document contains proofs and countermodels in support of the paper ``Short Equational Bases for Ortholattices'', by the same set of authors. In that paper, short single axioms for ortholattices, orthomodular lattices, and modular ortholattices are presented, all in terms of the Sheffer stroke. The ortholattice axiom is the shortest possible. Other equational bases in terms of the Sheffer stroke and in terms of join, meet, and complement are presented. Computers were used extensively to find candidates, reject candidates, and search for proofs that candidates are single axioms.
TR-CS-2004-01
Short Equational Bases for Ortholattices
W. McCune, R. Padmanabhan, M. A. Rose and R. Veroff
Short single axioms for ortholattices, orthomodular lattices, and modular ortholattices are presented, all in terms of the Sheffer stroke. The ortholattice axiom is the shortest possible. Other equational bases in terms of the Sheffer stroke and in terms of join, meet, and complement are presented. Proofs are omitted but are available in an associated technical report. Computers were used extensively to find candidates, reject candidates, and search for proofs that candidates are single axioms. The notion of computer proof is addressed.
TR-CS-2003-59
Automatic Generation of Polynomial Loop Invariants: Algebraic Foundations
Enric Rodriguez-Carbonell and Deepak Kapur
In [IJCAR03], the authors proposed an abstract framework leading to a generic procedure for automating the discovery of loop invariants. This framework is then instantiated for the language of conjunctions of polynomial equations for expressing loop invariants. This paper presents the algebraic foundation of the approach. By means of algebraic geometry and polynomial ideal theory, it is proved that the procedure for finding invariants terminates if the assignment statements in the loop are solvable -in particular, affine- mappings with positive eigenvalues. This yields a correct and complete algorithm for inferring invariant conjunctions of polynomial equalities. The method has been implemented in Maple using Grobner bases to compute intersection of ideals as well as to eliminate variables. Non-trivial invariants are generated applying this implementation to several examples to illustrate the power of the techniques.
TR-CS-2003-58
Automatically Generating Loop Invariants using Quantifier Elimination
Deepak Kapur
An approach for automatically generating loop invariants using quantifier-elimination is proposed. An invariant of a loop is expressed as a parameterized formula. Parameters in the invariant are discovered by generating constraints on the parameters by ensuring that the formula is indeed an invariant for every cycle-free execution path of the loop. The hypothesis invariant can be successively refined by considering execution paths one by one; heuristics can be developed for determining the order in which the paths are considered. Initialization of program variables as well as the precondition and postcondition of the loop, if available, can be used to further refine the hypothesized invariant. Constraints on parameters generated in this way are solved for possible values of parameters. If no solution is possible, this means that an invariant of the hypothesized form does not exist for the loop. Otherwise, if constraints are solvable, the strongest possible invariant of the hypothesized form can be generated using most general solutions of the constraints. Properties of first-order theories are identified for which constraint solving can be formulated as a quantifier-free elimination problem.
The approach is illustrated using the first-order theory of polynomial equations as well as Presburger arithmetic.
TR-CS-2003-57
Traceroute sampling makes random graphs appear to have power law
degree distributions
Aaron Clauset and Cristopher Moore
The topology of the Internet has typically been measured by sampling traceroutes, which are roughly shortest paths from sources to destinations. The resulting measurements have been used to infer that the Internet's degree distribution is scale-free; however, many of these measurements have relied on sampling traceroutes from a small number of sources. It was recently argued that sampling in this way can introduce a fundamental bias in the degree distribution, for instance, causing random (Erdos-Renyi) graphs to appear to i have power law degree distributions. We explain this phenomenon analytically using differential equations to model the growth of a breadth-first tree in a random graph G(n,p=c/n) of average degree c, and show that sampling from a single source gives an apparent power law degree distribution P(k) ~ 1/k for k < c.
TR-CS-2003-56
An Abstract Interpretation-based Approach to Mobile Code Safety
Elvira Albert, German Puebla, and Manuel Hermenegildo
Recent approaches to mobile code safety, like proof-carrying code, involve associating safety information to programs. The code supplier provides a program and also includes with it a certificate (or proof) whose validity entails compliance with a predefined safety policy. The intended benefit is that the program consumer can locally validate the certificate w.r.t. the ``untrusted'' program by means of a certificate checker---a process which should be much simpler, efficient, and automatic than generating the original proof. We herein introduce a novel approach to mobile code safety which follows a similar scheme, but which is based throughout on the use of abstract interpretation techniques. In our framework the safety policy is specified by using an expressive assertion language defined over abstract domains. We identify a particular slice of the abstract interpretation-based static analysis results which is especially useful as a certificate. We propose an algorithm for checking the validity of the certificate on the consumer side which is itself a very simplified and efficient specialized abstract-interpreter. Our ideas are illustrated through an example implemented in the context of constraint logic programs, using the CiaoPP system. Though further experimentation is still required, we believe the proposed approach is of interest for bringing the automation and expressiveness which is inherent in the abstract interpretation techniques to the area of mobile code safety.
TR-CS-2003-55
Program Development Using Abstract Interpretation
(and The Ciao System Preprocessor)
Manuel V. Hermenegildo, German Puebla,
Francisco Bueno, and Pedro-Lopez-Garcia
The technique of Abstract Interpretation has allowed the development of very sophisticated global program analyses which are at the same time provably correct and practical. We present in a tutorial fashion a novel program development framework which uses abstract interpretation as a fundamental tool. The framework uses modular, incremental abstract interpretation to obtain information about the program. This information is used to validate programs, to detect bugs with respect to partial specifications written using assertions (in the program itself and/or in system libraries), to generate and simplify run-time tests, and to perform high-level program transformations such as multiple abstract specialization, parallelization, and resource usage control, all in a provably correct way. In the case of validation and debugging, the assertions can refer to a variety of program points such as procedure entry, procedure exit, points within procedures, or global computations. The system can reason with much richer information than, for example, traditional types. This includes data structure shape (including pointer sharing), bounds on data structure sizes, and other operational variable instantiation properties, as well as procedure-level properties such as determinacy, termination, non-failure, and bounds on resource consumption (time or space cost). CiaoPP, the preprocessor of the Ciao multi-paradigm programming system, which implements the described functionality, will be used to illustrate the fundamental ideas.
TR-CS-2003-54
Abstract Specialization and its Applications
German Puebla and Manuel Hermenegildo
The aim of program specialization is to optimize programs by exploiting certain knowledge about the context in which the program will execute. There exist many program manipulation techniques which allow specializing the program in different ways. Among them, one of the best known techniques is partial evaluation, often referred to simply as program specialization, which optimizes programs by specializing them for (partially) known input data. In this work we describe abstract specialization, infinite. However, a technique whose main features are: (1) specialization is performed with respect to ``abstract'' values rather than ``concrete'' ones, and (2) abstract interpretation rather than standard interpretation of the program is used in order to propagate information about execution states. multi-variant. on a optimizing received The concept of abstract specialization is at the heart of the specialization system in CiaoPP, the Ciao system preprocessor. In this paper we present a unifying view of the different specialization techniques used in CiaoPP and discuss their potential applications by means of examples. The applications discussed include program parallelization, optimization of dynamic scheduling (concurrency), and integration of partial evaluation techniques.
TR-CS-2003-53
Fast character optimization in parsimony phylogeny reconstruction
Mi Yan and David A. Bader
The problem of finding a phylogeny with maximum parsimony is one of the main problems in computational biology. While it is impossible to search the possible tree space exhaustively for large data sets, most heuristic approaches try to search in the neighborhood of sub-optimal trees. The speed of computing a score for each tree (e.g. tree length or total number of character changes) is as important as the different tree search strategies. Some techniques include short-cuts that have not been proven to be exact, and an incremental character optimization approach by which the speedup gains depends on data sets and is hardly analyzed in theory. This paper describes an exact and fast algorithm to compute tree length and our algorithm can obtain great speedup for any data sets. We discuss the algorithm for Fitch-parsimony, but it can also be applied to Wagner-parsimony.
TR-CS-2003-52
Improving the Compilation of Prolog to C
Using Type and Determinism Information
(Preliminary Results)
J. Morales, M. Carro, and M. Hermenegildo
We describe the current status of and provide preliminary performance results for a compiler of Prolog to C. The compiler is novel in that it is designed to accept different kinds of high-level information (typically obtained via an analysis of the initial Prolog program and expressed in a standardized language of assertions) and use this information to optimize the resulting C code, which is then further processed by an off-the-shelf C compiler. The basic translation process used essentially mimics an unfolding of a C-coded bytecode emulator with respect to the particular bytecode corresponding to the Prolog program. Optimizations are then applied to this unfolded program. This is facilitated by a more flexible design of the bytecode instructions and their lower-level components. This approach allows reusing a sizable amount of the machinery of the bytecode emulator: ancillary pieces of C code, data definitions, memory management routines and areas, etc., as well as mixing bytecode emulated code with natively compiled code in a relatively straightforward way. We report on the performance of programs compiled by the current version of the system, both with and without analysis information.
TR-CS-2003-51
Multivariant Non-Failure Analysis via Standard Abstract Interpretation
F. Bueno, P. Lopez-Garcia, and M. Hermenegildo
Non-failure analysis aims at inferring that calls to the predicates of a program will never fail. This type of information has many applications in functional/logic programming. It is essential for determining lower bounds on the computational cost of calls, useful in the context of program parallelization, instrumental in partial evaluation and other program transformations, and has also been used in query optimization. In this paper, we re-cast the non-failure analysis proposed by Debray et al. as an abstract interpretation, which not only allows to investigate it from a standard and well studied theoretical framework, but has also several practical advantages. It allows us to incorporate non-failure analysis into a standard, generic abstract interpretation engine. The non-failure analysis thus benefits from the fixpoint propagation algorithm, which leads to improved information propagation. Also, the analysis takes advantage of the multi-variance of the generic engine, so that it is now able to infer separate non-failure information for different call patterns for a given predicate in a program. Moreover, the implementation is simpler, and allows to perform non-failure and covering analyses alongside other abstract interpretation based analyses, such as those for modes and types, in the same framework. Finally, besides the precision improvements and the additional simplicity, we also show improvements in efficiency of the analysis from our implementation in the Ciao/CiaoPP multiparadigm programming system.
TR-CS-2003-50
A Tool for Kinematic Error Analysis of Robots/Active Vision Systems
Kanglin Xu and George F. Luger
In this paper a generic kinematic model for robot structure error analysis is built and then is extended to analyze an active vision system. An active vision system is a robot device for controlling the motion of cameras based on visual information. Because the models are derived from the Denavit-Hartenberg transformation matrix, differential changes for the transformation matrix and link parameters, and the fundamental algorithm for estimating depth using stereo cameras, they are generic and can be used for any robot system or for stereo active vision systems. Based on this model, we created a software tool which functions as a C++ class library. The primary advantage of using this tool is that we can estimate the kinematic error at the design stage instead of at the calibration stage, which is more complicated work, especially for an active vision system or a binocular head. Furthermore, we can estimate the robot pose error or depth estimation error given the manufacturing tolerances.
TR-CS-2003-49
A Fast, Parallel Spanning Tree Algorithm for Symmetric Multiprocessors (SMPs)
David A. Bader and Guojing Cong
The ability to provide uniform shared-memory access to a significant number of processors in a single SMP node brings us much closer to the ideal PRAM parallel computer. Many PRAM algorithms can be adapted to SMPs with few modifications. Yet there are few studies that deal with the implementation and performance issues of running PRAM algorithms on SMPs. Our study in this paper focuses on implementing parallel spanning tree algorithms on SMPs. Spanning tree is an important problem in the sense that it is the building block for many other parallel graph algorithms and also because it is representative of a large class of irregular combinatorial problems that have simple and efficient sequential implementations and fast PRAM algorithms, but often have no known efficient parallel implementations. Experimental studies have been conducted on related problems (minimum spanning tree and connected components) using parallel computers, but only achieved reasonable speedup on regular graph topologies that can be implicitly partitioned with good locality features or on very dense graphs with limited numbers of vertices. In this paper we present a new randomized algorithm and implementation with superior performance that \emph{for the first-time} achieves parallel speedup on arbitrary graphs (both regular and irregular topologies) when compared with the best sequential implementation for finding a spanning tree. This new algorithm uses several techniques to give an expected running time that scales linearly with the number $p$ of processors for suitably large inputs (n > p^2). As the spanning tree problem is notoriously hard for any parallel implementation to achieve reasonable speedup, our study may shed new light on implementing PRAM algorithms for shared-memory parallel computers.
The main results of this paper are 1) A new and practical spanning tree algorithm for symmetric multiprocessors that exhibits parallel speedups on graphs with regular and irregular topologies; and 2) An experimental study of parallel spanning tree algorithms that reveals the superior performance of our new approach compared with the previous algorithms.
The source code for these algorithms is freely-available from our web site.
TR-CS-2003-48
A Framework For Measuring Supercomputer Productivity
Marc Snir and David A. Bader
We propose a framework for measuring the productivity of High Performance Computing (HPC) platforms and outline a research program that will lead to the definition of valid productivity metrics for HPC.
TR-CS-2003-47
A Parallel State Assignment Algorithm for Finite State Machines
David A. Bader and Kamesh Madduri
This paper summarizes the design and implementation of a parallel algorithm for state assignment of large Finite State Machines. High performance CAD tools are necessary to overcome the computational complexity involved in the optimization of large sequential circuits. FSMs constitute an important class of logic circuits and state assignment is one of the key steps in combinational logic optimization. The SMP-based parallel algorithm -- based on the sequential program JEDI targeting multilevel logic implementation -- scales nearly linearly with the number of processors for FSMs of varying problem sizes chosen from standard benchmark suites while attaining quality of results comparable to the best sequential algorithms. The source code for our parallel implementation of JEDI is freely-available from our web site.
TR-CS-2003-46
Fast Shared-Memory Algorithms for Computing the Minimum
Spanning Forest of Sparse Graphs
David A. Bader and Guojing Cong
Minimum Spanning Tree (MST) is one of the most studied combinatorial problems with practical applications in VLSI layout, wireless communication, and distributed networks, recent problems in biology and medicine such as cancer detection, medical imaging, and proteomics, and national security and bioterrorism such as detecting the spread of toxins through populations in the case of biological/chemical warfare. Most of the previous attempts for improving the speed of MST using parallel computing are too complicated to implement or perform well only on special graphs with regular structure. In this paper we design and implement four parallel MST algorithms (three variations of Boruvka plus our new approach) for arbitrary sparse graphs that for the first time give speedup when compared with the \emph{best} sequential algorithm. In fact, our algorithms also solve the minimum spanning forest problem. We provide an experimental study of our algorithms on symmetric multiprocessors such as IBM's p690/Regatta and Sun's Enterprise servers. Our new implementation achieves good speedups over a wide range of input graphs with regular and irregular structures, including the graphs used by previous parallel MST studies. For example, on an arbitrary random graph with 1M vertices and 20M edges, we have a speedup of 5 using 8 processors. The source code for these algorithms is freely-available from our web site.
TR-CS-2003-45
A New Parallel Algorithm for Planarity Testing
David A. Bader and Sukanya Sreshta
This paper presents a new parallel algorithm for planarity testing based upon the work of Klein and Reif. Our new approach gives correct answers on instances that provoke false positive and false negative results using Klein and Reif's algorithm. The new algorithm has the same complexity bounds as Klein and Reif's algorithm and runs in O((n log^2 n)/p) time for any number p <= n processors of a Concurrent Read Exclusive Write (CREW) Parallel RAM (PRAM). Implementations of the major steps of this parallel algorithm exist for symmetric multiprocessors and exhibit speedup when compared to the best sequential approach. Thus, this new parallel algorithm for planarity testing lends itself to a high-performance shared-memory implementation.
TR-CS-2003-44
Identifying the Sources of Latency in a Splintered Protocol
Wenbin Zhu, Arthur B. Maccabe and Rolf Riesen
Communication overhead is a critical factor for application performance in cluster computing based on commodity hardware. We propose a general strategy, splintering, to improve the system's performance. In the splintering strategy, previously centralized functionality is broken into pieces, and the pieces are distributed among the processors in a system in way that ensures system integrity and improves performance.
In this paper, we describe our efforts to use splintering to reduce latency. To date, our efforts have not resulted in the improvement that we originally anticipated. In order to identify the sources of latency, we have done a thorough instrumentation of our implementation. Based on our analysis of our measurements, we propose several modifications to the MPI library and the NIC firmware.
TR-CS-2003-43
An algorithm for computing a Grobner basis of a polynomial ideal
over a ring with zero divisors
Deepak Kapur and Yongyang Cai
An algorithm for computing a Grobner basis of an ideal of polynomials whose coefficients are taken from a ring with zero divisors, is presented; such rings include Z_n and Z_n[i], where n is not a prime number. The algorithm is patterned after (1) Buchberger's algorithm for computing a Grobner basis of a polynomial ideal whose coefficients are from a field and (2) its extension developed by Kandri-Rody and Kapur when the coefficients appearing in the polynomials are from a Euclidean domain. The algorithm works as Buchberger's algorithm when a polynomial ideal is over a field and as KandriRody-Kapur's algorithm when a polynomial ideal is over a Euclidean domain. The proposed algorithm and the related technical development are quite different from a general framework of reduction rings proposed by Buchberger in 1984 and generalized later by Stifter to handle reduction rings with zero divisors. These different approaches are contrasted along with the obvious approach where for instance, in the case of Z_n, the algorithm for polynomial ideals over Z could be used by augmenting the original ideal presented by polynomials over Z_n with n (similarly, in the case of Z_n[i], the original ideal is augmented with n and i^2+1).
TR-CS-2003-42
Scalable Byzantine Agreement
Scott Lewis and Jared Saia
This paper gives the first scalable protocol for solving the synchronized Byzantine agreement problem. The protocol is scalable in the sense that for Byzantine agreement over n processors, each processor sends and receives only O(log n) messages in expectation. To the best of our knowledge this is the first result for the Byzantine agreement problem where each processor sends and receives o(n) messages. The protocol uses randomness and is correct with high probability. (In particular, the probability of failure is n^-c for some constant c>0.) It can tolerate any fraction of faulty processors which is strictly less than 1/8. Our result partially answers the following question posed by Kenneth Birman: ``How scalable are the traditional solutions to problems such as Consensus or Byzantine Agreement?''
TR-CS-2003-41
Jikes Research Virtual Machine: Design and Implementation
of a 64-bit PowerPC Port
Sergiy Kyrylkov
This work describes the design and implementation of a 64-bit PowerPC port of the Jikes Research Virtual Machine (Jikes RVM). It explains general design decisions for 64-bit implementations of Java virtual machines, specifically Jikes RVM, along with details of the specific 64-bit PowerPC implementation.
TR-CS-2003-40
A Tool for Monitoring and Recording Heap-Allocated Object Behavior
Qingfeng Duan
A tool, to be used for monitoring and recording the heap-allocated object behavior, is designed, implemented, evaluated, and documented. Object-oriented programming languages, such as Java, require the support of automatic memory management (garbage collection), because of their intensive heap allocation. Modern garbage collection techniques rely on exploiting the object behaviors. These behaviors include the ages, the types, and the sizes of objects, and the references among objects. For example, the Appel generational copying collector and the Older-First collector are built on the basis of the distribution of object ages. To understand these object behaviors and thus be able to improve garbage collection techniques, we need a simulation tool. The tool described here correlates the low-level read-write data accesses with the high-level object characteristics. When an object is allocated, modified, moved, or deallocated, the tool monitors and records this information. By further analyzing this information, one obtains the relevant data to understand the desired object behaviors. The tool consists of three components: IBM's Jikes RVM, Dynamic SimpleScalar, and an off-line Analyzer. Jikes RVM is a Java virtual machine which itself is written in Java; Dynamic SimpleScalar is a machine-level emulator to simulate a PowerPC model running the AIX operating system; and the Analyzer is used to postprocess the results generated by the first two components. To be running, the entire tool maintains a layering of structures: the Java program, Jikes RVM, Dynamic SimpleScalar, and the host machine, in which the Java program resides at the first layer. We evaluate our tool using three SPECjvm98 Java benchmarks. We also illustrate how the tool can be used to analyze the write statistics to the fields of an object with certain class type. In general, this tool could have great significance in garbage collection research, by being able to provide accurate and flexible analyses at the heap-allocated object level.
TR-CS-2003-39
Automatic Generation of Polynomial Loop Invariants for Imperative Programs
Enric Rodriguez Carbonell and Deepak Kapur
A general framework is presented for automating the discovery of loop invariants for imperative programs. Theoretical results about the correctness and completeness of the proposed method are given. More importantly, it is shown how this abstract approach can be used to automatically infer polynomial invariants. The method has been implemented in Maple. Evidence of its practical interest is shown by means of several non-trivial examples, for which the polynomial loop invariants generated are directly applicable for proving correctness by means of a simple verifier.
TR-CS-2003-38
Design and Implementation of SIND, a Dynamic Binary Translator
Trek Palmer
Recent work with dynamic optimization in platform independent, virtual machine based languages such as Java has sparked interest in the possibility of applying similar techniques to arbitrary compiled binary programs. Systems such as Dynamo, DAISY, and FX$!$32 exploit dynamic optimization techniques to improve performance of native or foreign architecture binaries. However, research in this area is complicated by the lack of openly licensed, freely available, and platform-independent experimental frameworks. SIND aims to fill this void by providing an easily-extensible and flexible framework for research and development of applications and techniques of binary translation. Current research focuses are dynamic optimization of running binaries and dynamic security augmentation and integrity assurance.
TR-CS-2003-37
Chromatic Number in Random Scaled Sector Graphs
Josep Diaz, Vishal Sanwalani, Maria Serna, and Paul Spirakis
In the random sector graph model vertices are placed uniformly at random in the unit square. Each vertex i is assigned a sector S_i uniformly at random, of central angle alpha_i, in a circle of radius r_i (with vertex i as the origin). An arc is present from vertex i to any vertex j if j falls in S_i. We study the chromatic number chi(G), directed clique number omega(G), and undirected clique number mc(G) for random scaled sector graphs with n vertices, where each vertex has the same alpha_i=alpha and the same radius r_i=r_n=sqrt(ln(n)/n). We prove that for values alpha < pi, as n goes to infinity with high probability (w.h.p.), chi(G) and mc(G) are Theta(ln n/ln ln n), while omega(G) is O(1), showing a clear difference with the random geometric graph model. For pi < alpha < 2pi w.h.p., chi(G) and mc(G) are Theta(ln n), being the same for random sector and geometric graphs, while omega(G) is Theta(ln n/ln ln n).
TR-CS-2003-36
How Do Networks Become Navigable?
Aaron Clauset and Cristopher Moore
Networks created and maintained by social processes, such as the human friendship network and the World Wide Web, appear to exhibit the property of navigability: namely, not only do short paths exist between any pair of nodes, but such paths can easily be found using only local information. It has been shown that for networks with an underlying metric, algorithms using only local information perform extremely well if there is a power-law distribution of link lengths. However, it is not clear why or how real networks might develop this distribution. In this paper we define a decentralized ``rewiring'' process, inspired by surfers on the Web, in which each surfer attempts to travel from their home page to a random destination, and updates the outgoing link from their home page if this journey takes too long. We show that this process does indeed cause the link length distribution to converge to a power law, achieving a routing time of O(log^2 n) on networks of size n.
We also study finite-size effects on the optimal exponent, and show that it converges polylogarithmically slowly as the lattice size goes to infinity.
TR-CS-2003-35
Genomic Distances under Deletions and Insertions II
Mark Marron and Krister M. Swenson and Bernard M.E. Moret
As more and more genomes are sequenced, evolutionary biologists are becoming increasingly interested in evolution at the level of whole genomes, in scenarios in which the genome evolves through insertions, deletions, and movements of genes along its chromosomes. In the mathematical model pioneered by Sankoff and others, a unichromosomal genome is represented by a signed permutation of a multi-set of genes; Hannenhalli and Pevzner showed that the edit distance between two signed permutations of the same set can be computed in polynomial time when all operations are inversions. El-Mabrouk extended that result to allow deletions (or conversely, a limited form of insertions which forbids duplications). In this paper we extend El-Mabrouk's work to handle duplications as well as insertions and present an alternate framework for computing (near) minimal edit sequences involving insertions, deletions, and inversions. We derive an error bound for our polynomial-time distance computation under various assumptions and present preliminary experimental results that suggest that performance in practice may be excellent, within a few percent of the actual distance.
TR-CS-2003-34
Online Consensus of Phylogenetic Trees
Tanya Y. Berger-Wolf and Tandy J. Warnow
Phylogeny reconstruction heuristics on biological data need to use some criterion for termination, since we cannot recognize when an optimal tree is produced. A good criterion is the lack of change in the final output of the heuristic. Since these heuristics typically produce many top-scoring trees as their result, these trees are combined using a phylogenetic consensus method. Thus, the lack of change in the consensus of the top-scoring trees is a good heuristic termination criterion. To use this criterion, we need to have algorithms that maintain consensus of a sequence of trees on-line, as the new trees are generated by the heuristic. In this paper, we propose and analyze two algorithms for the on-line computation of strict and majority consensus trees. We show that the on-line strict consensus algorithm is time and space-optimal. We propose two implementations of the on-line majority consensus algorithm. One implementation is space-optimal and O(lg n) competitive, while the other is time-optimal. To the best of our knowledge, these are the first on-line algorithms for computing consensus of phylogenetic trees.
TR-CS-2003-33
Sampling Grid Colourings with Fewer Colours
Dimitris Achlioptas, Mike Molloy, Cristopher Moore, and Frank Van Bussel
We provide an optimally mixing Markov chain for 6-colourings of the square grid. Furthermore, this implies that the uniform distribution on the set of such colourings has strong spatial mixing. 4 and 5 are now the only remaining values of k for which it is not known whether there exists a rapidly mixing Markov chain for k-colourings of the square grid.
TR-CS-2003-32
Iterative-DCM3: A Fast Algorithmic Technique for Reconstructing Large
Phylogenetic Trees
U. Roshan, B.M.E. Moret, T.L. Williams, and T. Warnow
Obtaining reliable phylogenetic trees based on the maximum parsimony (MP) criterion is an NP-hard computational problem; although apparently good heuristics have been devised, even they fail to produce good solutions in reasonable time for large datasets -- today's limit appears to be around one thousand leaves. The other prevailing approach, maximum likelihood (ML), is much slower yet. As biologists collect data for an attempt to reconstruct the Tree of Life, with tens of millions of leaves, it becomes imperative that algorithm designers focus on approaches that will scale up well. In this paper, we present a promising new technique, Iterative-DCM3 (I-DCM3), which is as accurate as any other technique known to us and also scales well. I-DCM3 belongs to our family of Disk-Covering Methods (DCMs); it operates by iteratively dividing the input set of sequences into smaller overlapping subproblems, solving them using some base method (e.g., neighbor-joining, MP, ML), and then merging these subtrees into a single, phylogenetic tree. Thus, I-DCM3 is designed to boost the performance of its base method.
We evaluated the performance of I-DCM3 on eight biological datasets of DNA sequences, ranging from 439 to 2,594 sequences. We used the two most popular (and best-performing) MP heuristics -- Tree-Bisection and Reconnection (TBR) and the parsimony ratchet---as base methods. Our results show that: (i) the ratchet is significantly better than TBR; (ii) I-DCM3 boosts the performance of both base methods; and (iii) I-DCM3(ratchet) is better than any of the methods we have tested to date, with the difference in accuracy and speed growing as the size of the dataset grows.
TR-CS-2003-31
An Exact, Linear-Time Algorithm for Computing Genomic Distances
Under Inversions and Deletions
Tao Liu, Bernard M.E. Moret, and David A. Bader
As more genomes are sequenced, it is becoming possible to study evolution at the level of whole genomes, in scenarios in which the genome evolves through insertions, deletions, and movements of genes along its chromosomes. In the mathematic model pioneered by Sankoff and others, a unichromosomal genome is represented by a signed permutation of a multiset of genes. Hannenhalli and Pevzner gave the first polynomial-time algorithm to compute the shortest sequence of inversions that can transform one signed permutation into another, under the assumption that the genomes have exactly one copy of each gene. Later, Bader et al. showed that the length of such a sequence can be computed in linear time. El-Mabrouk extended Hannenhalli and Pevzner's result to allow deletions (or, equivalently, non-duplicating inversions). In this paper we show that the length of a shortest sequence of inversions and deletions can be computed in linear time. In the process, we also refine the characterization of hurdles and safe mergings. Our algorithm is easy to implement and runs with very low overhead: we include the results of computational experiments over a large range of permutation pairs produced through simulated evolution.
TR-CS-2003-30
Controlled Breeding Problem
Tanya Y. Berger-Wolf, Cris Moore, and Jared Saia
We consider the biological problem of designing mating strategies for controlled animal breeding programs. Beginning with a small population of known individual genetics and or their pedigree, the aim of a breeding program is to come up with a mating strategy that creates and maintains certain characteristics (such as maximum genetic diversity) within the population. Typically, these strategies are derived based on extensive stochastic modeling, including computer modeling, based on statistical information about the population (birth rate, death rate, etc.). However, in most cases, especially in conservation biology, it is very hard to determine the population parameters. Additionally, in a small population, or a zoo population, one cannot apply statistical methods to derive or use these parameters. In this paper we propose the first discrete model of the controlled animal breeding problem and analyze two possible objectives: breeding for maximum diversity and breeding a target individual. The strategy design goal in both cases is to minimize the expected number of matings until the breeding objective is achieved. We evaluate several mating heuristics and provide upper and lower bounds for the expected number of matings. While the actual population parameters may vary and can change the actual number of matings for a particular strategy, order of magnitude of the number expected matings and the relative competitiveness of the mating heuristics remains the same. Hence, this first simple discrete model of the animal breeding problem provides a novel viable approach to designing and comparing breeding strategies in captive populations.
TR-CS-2003-29
The Visibility Graph Among Polygonal Obstacles:
a Comparison of Algorithms
John Kitzinger and Bernard Moret
This work examines differences of four approaches in finding the visibility graph of a polygonal region with obstacles defined by simple polygons. The algorithms are (1) trivial (2) Lee's (3) Overmars and Welzl's (4) Ghosh and Mount's. Each has been implemented and tuned. The experimental comparisons are carried out via time measurements against various testcases. Expected asymptotic time bounds have been verified with crossover points between the implementations identified. The two contributions of this thesis have been (a) adapting Overmars and Welzl's algorithm from working only with line segments to working with general simple polygons (b) implementing method (4). According to one of the authors of method (4), this may be the first working implementation. This may be because the algorithm has always been considered a theoretical algorithm with complicated structures and assumed high time constants. During the course of implementing the algorithm, a major bug in the paper was identified and corrected. Also, as a bit of surprise, the run-time constants for this implementation have shown to be not as high as previously thought. In fact, the implementation out-performs the others on even medium-sized input.
Note: in the future, it may be possible to gain access to the source code of the implementations by writing to bejmk@yahoo.com.
TR-CS-2003-28
Object Lifetime Prediction in Java
Hajime Inoue, Darko Stefanovic, and Stephanie Forrest
Accurately predicting the lifetimes of objects in object-oriented and functional languages is important because such predictions can be used to improve memory management performance at run-time. A typical approach to this prediction problem is first to observe object lifetimes by tracing a sample program execution, then to construct a predictor function based on these observations, and finally to test the predictions on reference program executions. Four quantitative measures characterize this approach: coverage, the proportion of objects in the reference program execution for which the predictor function is defined; accuracy, the fraction of predicted lifetimes that are correct; precision, the granularity of the predictions; and size, the size of the predictor itself. These four properties are not independent; for example, increased precision often leads to less coverage and accuracy.
We describe a fully precise prediction method and report experimental results on its performance. By ``fully precise'' we mean that the granularity of predictions is equal to the smallest unit of allocation. We show that for a number of benchmark programs in the Java programming language, fully precise prediction can be achieved, together with high coverage and accuracy. Our results also show that a significant proportion of objects have a measured lifetime of zero, a fact which a dynamic compiler could use to avoid explicit allocation. The method described here is the first to combine high-precision and efficiency in a single lifetime predictor.
TR-CS-2003-27
Splintering TCP to Decrease Small Message Latency in High-Performance
Computing
Breanne Duncan
The adoption of commodity networking protocols and hardware in high-performance computing yields low-cost alternatives to expensive proprietary communications infrastructures. However, commodity protocols do not inherently have the advantages of low overhead, low latency, and offloaded control programs associated with specialty components, such as Myrinet. Many high-performance computing applications depend on the rapid transmission of small messages between processors. Hosts in a high-performance computing environment using gigabit Ethernet and TCP-IP need mechanisms to acknowledge small messages quickly without engaging the operating system. By "splintering" TCP and transferring acknowledgment capabilities to the network interface card (NIC), an application avoids costly interrupts and context switches into the operating system that incur delay. Acknowledgments are sent earlier, allowing the sender to advance its TCP flow control window more frequently. Results from a proof of concept model suggest that small message acknowledgment latency can be reduced by approximately 40% through splintering the TCP stack.
TR-CS-2003-26
An Error Metric for Phylogenetic Networks
C. Randal Linder, Bernard M.E. Moret, Luay Nakhleh, Anneke Padolina,
Jerry Sun, Anna Tholse, Ruth Timme, and Tandy Warnow
Phylogenetic networks model the evolutionary history of sets of organisms when events such as hybridization and lateral gene transfer occur. In spite of their widely acknowledged importance in evolutionary biology, phylogenetic networks have so far been studied mostly for specific datasets. We present a general definition of phylogenetic networks in terms of directed acyclic graphs (DAGs) and a set of conditions. We then characterize when a measure we proposed (PSB'03) is a true metric in terms of these conditions. Our results define a natural class of phylogenetic networks, suitable for several types of nontree evolutionary events, along with a well founded metric for their analysis.
TR-CS-2003-25
Undecidability of Unification over Two Theories of Modular Exponentiation
Deepak Kapur, Paliath Narendran and Lida Wang
(To be presented at UNIF'03, Valencia, Spain, June 2003.)
Modular multiplication and exponentiation are common operations in modern cryptography. Unification problems with respect to some equational theories that these operations satisfy are investigated. Two different but related equational theories in which the (one-sided) distributivity property of exponentiation over multiplication is assumed are analyzed. The unifiability problem is shown to be undecidable for these two theories.
TR-CS-2003-24
An MPI Tool to Measure Application Sensitivity to Variation
in Communication Parameters
Edgar A. Leon, Arthur B. Maccabe and Ron Brightwell
This work describes an apparatus which can be used to vary communication performance parameters for MPI applications, and provides a tool to analyze the impact of communication performance on parallel applications. Our tool is based on Myrinet (along with GM). We use an extension of the LogP model to allow greater flexibility in determining the parameter(s) to which parallel applications may be sensitive. We show that individual communication parameters can be independently controlled within a small percentage error. We also present the results of using our tool on a suite of parallel benchmarks.
TR-CS-2003-23
Towards Robust and Scalable Trust Metrics
Jeremy Avnet and Jared Saia
We describe a distributed and scalable trust metric for networks where transactions occur under a model of preferential attachment. Our trust metric algorithm, which we call expert voting is very simple. For a network over n nodes, the algorithm always considers only the opinions of the first log n nodes to join the network; we call these nodes experts. For any node v, the algorithm evaluates the trustworthiness of v based on the opinions of those experts which have had transactions with v. Empirical results suggest that this simple algorithm is surprisingly robust for large scale networks where transactions occur under a model of preferential attachment. To the best of our knowledge, this is the first algorithm that exploits a model of preferential attachment.
TR-CS-2003-22
Deciding Inductive Validity of Equations
Jurgen Giesl and Deepak Kapur
(To appear in the Proceedings of the International Conference on Automated Dedution (CADE 2003), July 2003, Miami, Florida.)
In CADE 2000, Kapur and Subramaniam defined syntactical classes of equations where inductive validity can be decided automatically. However, these classes are quite restrictive, since defined function symbols with recursive definitions may only appear on one side of the equations. In this paper, we expand the decidable class of equations significantly by allowing both sides of equations to be expressed using defined function symbols. The definitions of these function symbols must satisfy certain restrictions which can be checked mechanically. These results are crucial to increase the applicability of decision procedures for induction.
TR-CS-2003-21
An E-unification Algorithm for Analyzing Protocols that Use
Modular Exponentiation
Deepak Kapur, Paliath Narendran, and Lida Wang
(to appear in the Proceedings of International Conference on Rewriting Techniques and Applications (RTA 2003), June 2003, Valencia, Spain).
Modular multiplication and exponentiation are common operations in modern cryptography. Unification problems with respect to some equational theories that these operations satisfy are investigated. Two different but related equational theories are analyzed. A unification algorithm is given for one of the theories which relies on solving syzygies over multivariate integral polynomials with noncommuting indeterminates. For the other theory, in which the distributivity property of exponentiation over multiplication is assumed, the unifiability problem is shown to be undecidable by adapting a construction developed by one of the authors to reduce Hilbert's 10th problem to the solvability problem for linear equations over semi-rings. A new algorithm for computing strong Groebner bases of right ideals over the polynomial ring Z(x1, ..., xn) is proposed; unlike earlier algorithms proposed by Baader as well as by Madlener and Reinert which work only for right admissible term orderings with the boundedness property, this algorithm works for ANY right admissible term ordering. The algorithms for some of these unification problems are expected to be integrated into Naval Research Lab.'s Protocol Analyzer (NPA), a tool developed by Catherine Meadows, which has been successfully used to analyze cryptographic protocols, particularly emerging standards such as the Internet Engineering Task Force's (IETF) Internet Key Exchange and Group Domain of Interpretation protocols. Techniques from several different fields -- particularly symbolic computation (ideal theory and Groebner basis algorithms) and unification theory --- are thus used to address problems arising in state-based cryptographic protocol analysis.
TR-CS-2003-20
An MPI Tool to Measure Application Sensitivity to Variation in
Communication Parameters
Edgar A. Leon Borja
This work describes an apparatus which can be used to vary communication performance parameters for MPI applications, and provides a tool to analyze the impact of communication performance on parallel applications. Our apparatus is based on Myrinet (along with GM). We use an extension of the LogP model to allow greater flexibility in determining the parameter(s) to which parallel applications may be sensitive. We show that individual communication parameters can be independently controlled within a small percentage error.
We also present preliminary results from applying this tool to a suite of parallel applications that represent a variety of (a) degree of exploitable concurrency, (b) computation to communication ratio and (c) frequency and granularity of inter-processor communications.
TR-CS-2003-19
An Experimental Evaluation of Phylogenetic Consensus Methods
Tanya Y. Berger-Wolf, Tiffani L. Williams, Bernard E. Moret, and Tandy
J. Warnow
A consensus method for phylogenetic trees takes a collection of input trees and returns a single ``representative'' tree. Here, we focus on phylogenetic trees that are derived from the same set of taxa. There are a considerable number of consensus methods to choose from, but little is known about their behavior in practice, especially on large data sets (hundreds of trees and thousands of taxa). In this paper we present the first comprehensive large-scale comparative analysis of several consensus methods. We study the performance and accuracy of strict, majority rule, and greedy consensus techniques as a function of the number of input trees, the size of each source tree, and the degree of conflict among the trees. For all the methods, the accuracy decreased with the number and size of source trees, and the degree of conflict among them. As expected, majority rule improves the accuracy and the degree of resolution over strict consensus. While the greedy approach improves the resolution of the consensus trees, it does so at the expense of accuracy. This study provides the first quantitative measure of the behavior of consensus methods illuminating their shortcomings and necessitating the development of better techniques.
TR-CS-2003-18
Model Checking Reconfigurable Processor Configurations for
Safety Properties
John Cochran, Deepak Kapur, and Darko Stefanovic
Reconfigurable processors pose unique problems for program safety because of their use of computational approaches that are difficult to integrate into traditional program analyses. The combination of proof-carrying code for verification of standard processor machine code and model-checking for array configurations is explored. This combination extends proof-carrying code to provide a context for model checking, but uses standard model checking technology. This approach is shown to be useful in verifying safety properties including the synchronization of memory access by the reconfigurable array and memory access bounds checking.
TR-CS-2003-17
Model-Combining by Conditioning Rule Sets:
Improving on a Signal Classifier for NASA
Kshanti K. Greene, George F. Luger, and Edouard Siregar
We present a methodology for signal classification for NASA's autonomous space systems. Individual "models," described as sets of classifier rules, are used to interpret input signals. The input signals are ubiquitous in nature and frequently occur in space phenomena. Our model-combining method scores rule sets generated from multiple training sets on their ability to classify input signals. High scoring rule sets represent the input signals better and have more weight when classifying subsequent input signals. Our model-combining method doubled classification accuracy compared to classifying without the model-combining method.
TR-CS-2003-16
Generic Quantum Fourier Transforms
Cristopher Moore, Daniel Rockmore, and Alexander Russell
The quantum Fourier transform (QFT) is the principal algorithmic tool underlying most efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by ``quantizing'' the separation of variables technique that has been so successful in the study of classical Fourier transform computations. Specifically, this framework applies the existence of computable Bratteli diagrams, adapted factorizations, and Gel'fand-Tsetlin bases to offer efficient quantum circuits for the QFT over a wide variety a finite Abelian and non-Abelian groups, including all group families for which efficient QFTs are currently known and many new group families. Moreover, the method gives rise to the first subexponential-size quantum circuits for the QFT over the linear groups GL_k(q), SL_k(q), and the finite groups of Lie type, for any fixed prime power q.
TR-CS-2003-15
GUI Environments for Functional Languages
Dan Pless & George Luger
We describe an Integrated Development Environment (IDE) for purely functional programming languages. This environment leverages the properties of such languages to provide software development productivity features that would be difficult or impossible to provide for a language with state. We show how such an environment can enable the construction of regression tests and improve documentation. We also show how other standard tools such as debuggers and profilers can leverage these capabilities.
TR-CS-2003-14
Adaptation and Ruggedness in an Evolvability Landscape
Terry Van Belle and David H. Ackley
Evolutionary algorithms depend on both a within-generation selection process that determines the fitness of individual genomes, and a cross-generation evolvability process that determines how offspring can improve on their ancestors. We introduce a minimal model in which not only selection but also evolvability are genetically controlled, and study its behavior in an environment where peak fitness changes location over evolutionary time. We demonstrate an `evolution of evolvability' model that can improve performance on this problem, compared to fixed evolvability mechanisms as commonly employed in genetic algorithms. We introduce and discuss evolvability landscapes that relate evolvability parameters to long-term population success, and find that the evolvability landscape of our model problem turns out to have some rugged features, in which badly performing points can be found very close to high scoring points. We suggest that a research focus on evolvability may help build better evolutionary algorithms as well as understand their behaviors.
TR-CS-2003-13
Hiding Satisfying Assignments: Two are Better than One
Dimitris Achlioptas, Haixia Jia, and Cristopher Moore
Evaluating incomplete algorithms for constraint satisfaction problems benefits greatly by readily available hard satisfiable instances. A natural attempt to generate such instances in the context of satisfiability is the following: construct a k-SAT instance whose clauses are chosen uniformly at random among those clauses that satisfy some randomly chosen truth assignment A. Unfortunately, instances generated in this manner tend to be relatively easy and can be solved efficiently by practical heuristics. Roughly speaking, as the formula's density increases, A acts as a stronger and stronger attractor. Motivated by recent results on the geometry of the space of satisfying truth assignments for random k-SAT and NAE-k-SAT formulas, we propose a very simple twist on this model, which appears to greatly increase the hardness of the resulting formulas. Namely, in addition to forbidding the clauses violated by the hidden assignment A, we also forbid the clauses violated by its complement, so that both A and -A are satisfying. It appears that under this ``symmetrization'' the effects of the two attractors largely cancel out, making it much harder for an algorithm to ``feel'' (and find) either one. We give theoretical and experimental evidence supporting this assertion.
TR-CS-2003-12
Experiences Constructing a Lightweight SPARC Interpreter for a Dynamic
Binary Translator
Trek Palmer and Darko Stefanovic
Dynamic binary translation is an important area for compiler research, because additional information available at runtime can substantially improve the effectiveness of optimizations. The difficulty lies in creating a system capable of gathering runtime information without slowing down the running executable. Several such systems have been created (Dynamo, DynamoRIO, FX!32, etc.), but their use presents several problems to the researcher. They are either closed or proprietary, and are often tied to a very specific platform. In this paper we discuss the design of a new, open, cross-platform dynamic binary translation system, SIND. Specifically we discuss the design in general terms, and then focus on the specific implementation of a lightweight interpreter for the SPARC architecture. We explore the many issues involved in building a self-bootstrapping, efficient interpreter.
TR-CS-2003-11
Discrete Sensor Placement Problems in Distribution Networks
Tanya Y. Berger-Wolf, William E. Hart, and Jared Saia
We consider the problem of placing sensors in a building or a utility network to monitor the air or water supply. We propose several discrete graph models of the problem and outline possible solutions. We concentrate on minimizing the number of sensors and time to contamination detection. We prove that the problem is NP-hard. We use generalizations and extensions of the various versions of the set cover problem to design approximation algorithms.
TR-CS-2003-10
Randomized instruction set emulation to disrupt binary code injection attacks
Gabriela Barrantes, David H. Ackley, Trek S. Palmer, Dino Dai Zovi,
Stephanie Forrest, Darko Stefanovic
Many remote attacks against computer systems inject binary code into the execution path of a running program, gaining control of the program's behavior. If each defended system or program could use a machine instruction set that was both unique and private, such binary code injection attacks would become extremely difficult if not impossible. A binary-to-binary translator provides an economic and flexible implementation path for realizing that idea. As a proof of concept, we describe a randomized instruction set emulator (RISE) based on the open-source Valgrind x86-to-x86 binary translator. Although currently very slow and memory-intensive, our prototype RISE can indeed disrupt binary code injection attacks against a program without requiring its recompilation, linking, or access to source code. We describe the RISE implementation, give evidence demonstrating that RISE defeats common attacks, consider consequences of the dense x86 instruction set on the method's effects, and discuss limitations of the RISE prototype as well as design tradeoffs and extensions of the underlying idea.
TR-CS-2003-09
Phylogenetic Reconstruction from Gene Rearrangement Data
with Unequal Gene Content
Jijun Tang and Bernard M.E. Moret
Phylogenetic reconstruction from gene rearrangement data has attracted increased attention over the last five years. Existing methods are limited computationally and by the assumption (highly unrealistic in practice) that all genomes have the same gene content. We have recently shown that we can scale our reconstruction tool, GRAPPA, to instances with up to a thousand genomes with no loss of accuracy and at minimal computational cost. Computing genomic distances between two genomes with unequal gene contents has seen much progress recently, but that progress has not yet been reflected in phylogenetic reconstruction methods. In this paper, we present extensions to our GRAPPA approach that can handle limited numbers of duplications (one of the main requirements for analyzing genomic data from organelles) and a few deletions. Although GRAPPA is based on exhaustive search, we show that, in practice, our bounding functions suffice to prune away almost all of the search space (our pruning rates never fall below 99.995%), resulting in high accuracy and fast running times. The range of values within which we have tested our approach encompasses mitochondria and chloroplast organellar genomes, whose phylogenetic analysis is providing new insights on evolution.
TR-CS-2003-08
Genomic Distances under Deletions and Insertions
Mark Marron, Krister M. Swenson, and Bernard M.E. Moret
As more and more genomes are sequenced, evolutionary biologists are becoming increasingly interested in evolution at the level of whole genomes, in scenarios in which the genome evolves through insertions, deletions, and movements of genes along its chromosomes. In the mathematical model pioneered by Sankoff and others, a unichromosomal genome is represented by a signed permutation of a multiset of genes; Hannenhalli and Pevzner showed that the edit distance between two signed permutations of the same set can be computed in polynomial time when all operations are inversions. El-Mabrouk extended that result to allow deletions and a limited form of insertions (which forbids duplications). In this paper we extend El-Mabrouk's work to handle duplications as well as insertions and present an alternate framework for computing (near) minimal edit sequences involving insertions, deletions, and inversions. We derive an error bound for our polynomial-time distance computation under various assumptions and present preliminary experimental results that suggest that performance in practice may be excellent, within a few percent of the actual distance.
TR-CS-2003-07
Automatic Synthesis of Isotropic Textures on Subdivision
Surfaces from Sample Images
Joel Castellanos, Curtis Sirl-Moore, and Lance R. Williams
We describe a fully automatic method of synthesizing isotropic textures on subdivision surfaces from sample images. We restrict ourselves to isotropic textures because only isotropic textures can be automatically generated on an arbitrary surface in the absence of a parametrization. Unlike previous approaches, texture synthesis is accomplished in a coarse-to-fine fashion by constructing both Gaussian and Laplacian pyramid representations of the synthetic texture. The inverse Laplacian pyramid transform is used to generate first approximations to the texture at each level of the associated Gaussian pyramid. These approximations are refined using a modified nearest neighbor search process which preserves the first-order statistics of the sample texture. This search process can be considered to be a sampling procedure for an implicitly defined Markov random field. The resulting texture is generated directly on the subdivision surface. Within the domain of isotropic textures, the proposed method offers improvements in faithful reproduction of a sample's appearance over a wide range of scales.
TR-CS-2003-06
Covering a Set of Points with a Minimum Number of Turns
Michael J. Collins
Given a finite set of points in Euclidean space, we can ask what is the minimum number of times a piecewise-linear path must change direction in order to pass through all of them. We prove some new upper and lower bounds for a restricted version of this problem in which all motion is orthogonal to the coordinate axes.
TR-CS-2003-05
Almost all graphs with average degree 4 are 3-colorable
Dimitris Achlioptas and Cristopher Moore
(Journal version, to appear in the invited issue of the Journal of Computer and System Sciences for selected papers in STOC 2002.)
We analyze a randomized version of the Brelaz heuristic on sparse random graphs. We prove that almost all graphs with average degree d <= 4.03 are 3-colorable and that a constant fraction of all 4-regular graphs are 3-colorable.
TR-CS-2003-04
Scaling Up Accurate Phylogenetic Reconstruction from Gene-Order Data
J. Tang and B.M.E. Moret
Phylogenetic reconstruction from gene-order data has attracted increasing attention from both biologists and computer scientists over the last few years. Methods used in reconstruction include distance-based methods (such as neighbor-joining), parsimony methods using sequence-based encodings, Bayesian approaches, and direct optimization. The latter, pioneered by Sankoff and extended by us with the software suite GRAPPA, is the most accurate approach, but cannot handle more than about 15 genomes. We report here on our successful efforts to scale up direct optimization through a two-step approach: the first step decomposes the dataset into smaller pieces and runs the direct optimization (GRAPPA) on the smaller pieces, while the second step builds a tree from the results obtained on the smaller pieces. We used the sophisticated disk-covering method (DCM) pioneered by Warnow and her group, suitably modified to take into account the computational limitations of GRAPPA. We find that DCM-GRAPPA scales gracefully to at least $1,000$ genomes and retains surprisingly high accuracy throughout the range: in our experiments, the topological error rate rarely exceeded a few percent. Thus, reconstruction based on gene-order data can now be accomplished with high accuracy on datasets of significant size.
TR-CS-2003-03
Performance of Supertree Methods on Various Dataset Decomposition, II
B.M.E. Moret, U. Roshan, T. Warnow, and T.L. Williams
Many phylogenetic reconstruction methods attempt to solve hard optimization problems, such as Maximum Parsimony (MP) and Maximum Likelihood (ML); consequently, these methods are limited severely by the number of taxa that they can handle in a reasonable time frame. A divide-and-conquer strategy, based upon dividing a dataset into overlapping subsets, constructing trees on these subsets, and then merging them into a tree on the full dataset, is one promising approach to overcoming the inherent computational difficulties in large-scale phylogenetic reconstruction. Such a method combines a careful data decomposition with the general approach of supertree methods, which assemble a single large tree from a collection of overlapping subtrees. In this paper, we compare a standard supertree method, matrix parsimony (MRP), to a supertree method (strict consensus merger, or SCM) designed to work in tandem with our dataset decomposition method (a disk-covering method, or DCM), on both random decompositions and DCM-produced decompositions. We examine the performance of these methods with respect to maximum parsimony scores, topological accuracy, and running time. We find that our DCM+SCM method outperforms the others with respect to all these criteria.
TR-CS-2003-02
MAX k-CUT and approximating the chromatic number of random graphs
Amin Coja-Oghlan, Cristopher Moore and Vishal Sanwalani
We consider the MAX k-CUT problem in random graphs G(n,p). First, we estimate the probable weight of a MAX k-CUT using probabilistic counting arguments and by analyzing a simple greedy heuristic. Then, we give an algorithm that approximates MAX k-CUT within expected polynomial time. The approximation ratio tends to 1 as np -> infinity. As an application, we obtain an algorithm for approximating the chromatic number of G(n,p) where 1 <= np <= 0.5 n, within a factor of sqrt(np) in polynomial expected time, thereby answering a question of Krivelevich and Vu, and extending a result of Coja-Oghlan and Taraz. We give similar algorithms for random regular graphs G(n,r). Our main technical result is a bound on the probable value of Frieze and Jerrum's SDP-relaxation of MAX k-CUT, and may be of independent interest.
TR-CS-2003-01
EM Learning of Product Distributions in a First-Order Stochastic
Logic Language
Daniel Pless and George Luger
We describe a new logic-based stochastic modeling language called Loopy Logic. It is an extension of the Bayesian logic programming approach of Kersting and De Raedt [2000]. We specialize the Kersting and De Raedt formalism by suggesting that product distributions are an effective combining rule for Horn clause heads. We use a refinement of Pearl's loopy belief propagation [Pearl, 1998] for the inference algorithm. We also extend the Kersting and De Raedt language by adding learnable distributions. We propose a message passing algorithm based on Expectation Maximization [Dempster et al., 1977] for estimating the learned parameters in the general case of models built in our system. We have also added some additional utilities to our logic language including second order unification and equality predicates.
TR-CS-2002-39
Performance of supertree methods on various dataset decompositions
B.M.E. Moret, U. Roshan, T. Warnow, and T.L. Williams
Most large-scale phylogenetic reconstructions are based upon attempts to solve hard optimization problems, such as maximum parsimony or maximum likelihood. One approach that has been suggested for overcoming the computational difficulties in large-scale phylogenetic reconstruction is a divide-and-conquer strategy: first divide the dataset into overlapping subproblems, then reconstruct trees on the subproblems, and finally combine the subtrees into a tree on the full dataset. In this paper we study several such divide-and-conquer methods, with respect to the maximum parsimony scores they obtain on 8 real datasets. These methods differ in two ways: how they define the overlapping subproblems, and also in how they combine subtrees into a supertree. Our study shows that the division into subproblems has a large impact on the quality of the resulting tree, for both supertree methods, with larger subproblems and greater coverage resulting in improved maximum parsimony scores. We also show that the specific technique used to combine subtrees into a supertree can have a big impact on the resultant maximum parsimony score; in particular, we show that a fast method (the "Strict Consensus Merger") outperforms the Matrix Parsimony method with respect to maximum parsimony scores and running time. We conclude with some suggestions for further research.
TR-CS-2002-38
Security Applications of Dynamic Binary Translation
Dino Dai Zovi
The last 13 years have seen a large number of serious computer security vulnerabilities. Some of the most pernicious of these vulnerabilities have been buffer overflow and format string vulnerabilities in widely used software applications. A number of Internet worms have exploited these vulnerabilities to infect target hosts. The first part of this work introduces a framework for understanding and describing attacks that dynamically inject machine code into a process and the vulnerabilities that enable these attacks. The techniques used in these attacks are described in detail. The second part of this work describes the application of dynamic binary translation, previously a technique primarily for dynamic optimization, to stopping and mitigating these sorts of attacks. The implementations of several known techniques using a dynamic binary translation system are described in detail. Finally, some conclusions about the applicability of dynamic binary translation to computer security are made.
TR-CS-2002-37
A History and Survey of Network Firewalls
Kenneth Ingham and Stephanie Forrest
Firewalls are network devices which enforce an organization's security policy. Since their development, various methods have been used to implement firewalls. These methods filter network traffic at one or more of the seven layers of the ISO network model, most commonly at the application, transport, and network, and data-link levels. In addition, researchers have developed some newer methods, such as protocol normalization and distributed firewalls, which have not yet been widely adopted.
Firewalls involve more than the technology to implement them. Specifying a set of filtering rules, known as a policy, is typically complicated and error-prone. High-level languages have been developed to simplify the task of correctly defining a firewall's policy. Once a policy has been specified, the firewall needs to be tested to determine if it actually implements the policy correctly. Little work exists in the area of firewall theory; however, this article summarizes what exists.
Because some data must be able to pass in and out of a firewall, in order for the protected network to be useful, not all attacks can be stopped by firewalls. Some emerging technologies, such as Virtual Private Networks (VPN) and peer-to-peer networking pose new challenges for firewalls.
TR-CS-2002-36
Towards Provably Safe Reconfigurable Processor Code: A Model Checking and
Proof-Carrying Code Approach
John Cochran
Reconfigurable processors pose unique problems for program safety because they employ two dissimilar computational approaches which are difficult to integrate into one computational model. Approaches to software and hardware safety each fail to cover the entire range of potential safety problems for reconfigurable processors, indicating a need for a new approach. One method of dealing with these difficulties is the combination of model-checking for safety verification of reconfigurable array configurations which behave more like hardware, and proof-carrying code for safety verification of traditional aspects of programs. This approach is investigated for potential safety concerns related to software running on reconfigurable processors. Extensions to Necula's proof-carrying methodology are proposed. The application of the proposed approach is shown to be limited due to inability of traditional model checkers such as NuSMV to handle large numbers. More sophisticated model checkers which use abstraction, modularity and provide support for arithmetic data will have to be employed.
TR-CS-2002-35
The Hidden Subgroup Problem in Affine Groups:
Basis Selection in Fourier Sampling
Cristopher Moore, Daniel Rockmore, Alexander Russell, and Leonard Schulman
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which a subgroup H of a group G must be determined from a quantum state Psi uniformly supported on a left coset of H. These hidden subgroup problems are then solved by Fourier sampling: the quantum Fourier transform of Psi is computed and measured. When the underlying group is non-Abelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement occurs. It has remained open whether the strong standard method is indeed stronger, that is, whether there are hidden subgroups which can be reconstructed via the strong method by not by the weak, or any other known, method.
In this article, we settle this question in the affirmative. We show that hidden subgroups of semidirect products of the form Z_q x Z_p, where q | (p-1) and q = p over polylog(p), can be efficiently determined by the strong standard method. Furthermore, the weak standard method and the ``forgetful'' Abelian method are insufficient for these groups. We also give an information-theoretic solution to the the hidden conjugate problem over the affine groups, which generalizes known results for the dihedral groups. In particular, this gives rise to an information-theoretic solution for the hidden subgroup problem over the Affine groups for a prime p where p-1 has polylog(p) divisors. Finally, we prove a closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.
TR-CS-2002-34
Exact Resultants for Corner-cut Unmixed Multivariate Polynomial
Systems using the Dixon Formulation
Arthur Chtcherba and Deepak Kapur
Structural conditions on the support of a multivariate polynomial system are developed for which the Dixon-based resultant methods compute exact resultants. For cases when this cannot be done, an upper bound on the degree of the extraneous factor in the projection operator can be determined a priori, thus resulting in quick identification of the extraneous factor in the projection operator. (For the bivariate case, the degree of the extraneous factor in a projection operator can be determined a priori.)
The concepts of a corner-cut support and almost corner-cut support of an unmixed polynomial system are introduced. For generic unmixed polynomial systems with corner-cut and almost corner-cut supports, the Dixon based methods can be used to compute their resultants exactly. These structural conditions on supports are based on analyzing how such supports differ from box supports of n-degree systems for which the Dixon formulation is known to compute the resultants exactly. Such an analysis also gives a sharper bound on the complexity of resultant computation using the Dixon formulation in terms of the support and the mixed volume of the Newton polytope of the support.
These results are a direct generalization of the authors' results on bivariate systems including the results of Zhang and Goldman as well as of Chionh for generic unmixed bivariate polynomial systems with corner-cut supports.
TR-CS-2002-33
An Investigation of Phylogenetic Likelihood Methods
Tiffani Williams and Bernard M.E. Moret
We analyze the performance of likelihood-based approaches used to reconstruct phylogenetic trees. Unlike other techniques such as Neighbor-Joining (NJ) and Maximum Parsimony (MP), relatively little is known regarding the behavior of algorithms founded on the principle of likelihood. We study the accuracy, speed, and likelihood scores of four representative likelihood-based methods (fastDNAml, MrBayes, PAUP*, and TREE-PUZZLE) that use either Maximum Likelihood (ML) or Bayesian inference to find the optimal tree. NJ is also studied to provide a baseline comparison. Our simulation study is based on random birth-death trees, which are deviated from ultrametricity, and use the Kimura 2-parameter + Gamma model of sequence evolution. We find that MrBayes (a Bayesian inference approach) consistently outperforms the other methods in terms of accuracy and running time.
TR-CS-2002-32
Solution to a Challenge Problem in HBCK
Robert Veroff
In this note, we present a first-order proof that equation
(((x * y) * y) * x) * x = (((y * x) * x) * y) * y
holds in the quasivariety HBCK.
TR-CS-2002-31
Scaling Up Accurate Phylogenetic Reconstruction from Gene-Order Data
J. Tang, T. Liu, and B.M.E. Moret
Phylogenetic reconstruction from gene-order data has attracted increasing attention from both biologists and computer scientists over the last few years. Methods used in reconstruction include distance-based methods (such as neighbor-joining), parsimony methods using sequence-based encodings, Bayesian approaches, and direct optimization. The latter, pioneered by Sankoff and extended by us with the software suite GRAPPA, is the most accurate approach, but cannot handle more than about 15 genomes. We report here on our successful efforts to scale up the direct approach through a two-step approach: the first step decomposes the dataset into smaller pieces and runs the direct optimization (GRAPPA) on the smaller pieces, while the second step builds a tree from the results obtained on the smaller pieces. We used both a quartet-based approach (the quartet-puzzling method) and the more sophisticated disk-covering method (DCM) pioneered by Warnow. We find that DCM-GRAPPA scales gracefully to 100 genomes and retains surprisingly high accuracy throughout the range: in our experiments, the topological error rate rarely exceeded a few percent. The quartet-based methods perform better than might be expected from their known accuracy on sequence data, but trail far behind DCM-GRAPPA in terms of both speed and accuracy. Overall, our results demonstrate that reconstruction based on gene-order data can now be accomplished with high accuracy on datasets of significant size.
TR-CS-2002-30
An Error Metric for Phylogenetic Networks
B.M.E. Moret, L. Nakhleh, and T. Warnow
Phylogenetic networks model the evolutionary history of sets of organisms when events such as hybridization and lateral gene transfer occur. In spite of their widely acknowledged importance in evolutionary biology, phylogenetic networks have so far been studied mostly for specific datasets. We present a general definition of phylogenetic networks in terms of directed acyclic graphs (DAGs) and a set of conditions. We then characterize when the measure proposed in [NakhlehSun03] is a true metric in terms of these conditions. Our results define a natural class of phylogenetic networks, suitable for several types of nontree evolutionary events, along with a well founded metric for their analysis.
TR-CS-2002-29
A comparison of algorithms and data structures for the box-containment problem
Jingkun Yu and Bernard M.E. Moret
We present the results of a detailed experimental study of the box-containment problem, one of the basic range-searching problems. In its 2-dimensional version, it can be phrased as: given a collection of axis-parallel rectangles in the plane, report all rectangles that are completely contained within an axis-parallel query rectangle. We have implemented, tested, and analyzed a wide range of different approaches to this problem.
TR-CS-2002-28
Double-Negation Elimination in Some Propositional Logics
Michael Beeson, Robert Veroff and Larry Wos
This article answers two questions (posed in the literature), each concerning the guaranteed existence of proofs free of double negation. A proof is free of double negation if none of its deduced steps contains a term of the form n(n(t)) for some term t, where n denotes negation. The first question asks for conditions on the hypotheses that, if satisfied, guarantee the existence of a double-negation-free proof when the conclusion is free of double negation. The second question asks about the existence of an axiom system for classical propositional calculus whose use, for theorems with a conclusion free of double negation, guarantees the existence of a double-negation-free proof. After giving conditions that answer the first question, we answer the second question by focusing on the Lukasiewicz three-axiom system. We then extend our studies to infinite-valued sentential calculus and to intuitionistic logic and generalize the notion of being double-negation free. The double-negation proofs of interest rely exclusively on the inference rule condensed detachment, a rule that combines modus ponens with an appropriately general rule of substitution. The automated reasoning program OTTER played an indispensable role.
TR-CS-2002-27
Constructing Regulatory Networks from Gene Expression Data
Using Association Rule Mining
Jiaye Zhou
Gene expression technology, such as high density DNA Microarray, allows us to monitor gene expression patterns at the genomic level. While this technology promises progress toward the understanding of transcriptional response and regulation, it also introduces the challenge of extracting relevant information from the large datasets generated. As a result, data mining of gene expression data has become an important area of research for biologists. Two classical data mining methods: data classification and clustering have been widely used to analyze gene expression data. These methods are valuable exploratory tools in data mining, but they are limited to placing genes into groups with others that share certain characteristics. While it is important to determine which genes are related, we also need to understand the mechanism of how genes relate and how they regulate one another. These two methods do not provide such insight. This information, however, can be extracted from gene expression data with experiments that are well designed. In this thesis, I consider the use of association rule mining for discovering regulatory relationships among genes from gene expression data. Association rule mining, a relatively new technique in the area of data mining and knowledge discovery, has been the focus of much data mining research in computer science. Association rule mining is a process that identifies links between sets of correlated objects in large datasets. In this thesis, I describe the first application of association rule mining to gene expression data analysis. I develop a strategy for transforming gene expression data to make it suitable for association rule mining, and show how the FP-Growth algorithm for association rule mining can be adapted to apply to the transformed data. I implement, test and evaluate the association rule mining method using real gene expression data that is publicly available. I am able to validate our analysis method by showing that our results are consistent with published results generated by independent analysis methods. Furthermore, this method is able to generate previously unknown biological information, making it a valuable gene expression data analysis tool.
TR-CS-2002-26
Segmentation of Multiple Salient Closed Contours from Real Images
Shyjan Mahamud, Lance R. Williams, Karvel K. Thornber, and Kanglin Xu
Using a saliency measure based on the global property of contour closure, we have developed a method that reliably segments out salient contours bounding unknown objects from real edge images. The measure incorporates the Gestalt principles of proximity and smooth continuity that previous methods have exploited. Unlike previous methods, we incorporate contour closure by finding the eigenvector with largest positive real eigenvalue of a matrix defining a stochastic process which models the distribution of contours passing through edges in the scene. The segmentation algorithm utilizes the saliency measure to identify multiple closed contours by finding strongly-connected components on an induced graph. The determination of strongly-connected components is a direct consequence of the property of closure. We report for the first time, results on large real images for which segmentation takes an average of about 10 secs per object on a general-purpose workstation. The segmentation is made efficient for such large images by exploiting the inherent symmetry in the task.
TR-CS-2002-25
On the 2-colorability of random hypergraphs
Dimitris Achlioptas and Cristopher Moore
A 2-coloring of a hypergraph is a mapping from its vertices to a set of two colors such that no edge is monochromatic. Let H_k(n,m) be a random k-uniform hypergraph on n vertices formed by picking m edges uniformly, independently and with replacement. It is easy to show that if r <= r_c = 2^(k-1) ln 2 - 0.5 ln 2, then with high probability H_k(n,m=rn) is not 2-colorable. We complement this observation by proving that if r <= r_c - 1 then with high probability H_k(n,m=rn) is 2-colorable.
TR-CS-2002-24
MAX-CUT on Sparse Random Graphs
Vamsi Kalapala and Cristopher Moore
Numerous NP-complete combinatorial optimization problems have been studied for random graphs. MAX-CUT, however, seems to have been left out. We prove upper and lower bounds on the size of the largest cut for sparse random graphs of average degree c. While we prove explicit upper and lower bounds valid for general c, we focus on the case where c is large (but still fixed as a function of n) and prove that, with high probability, the largest cut consists of half the edges plus A n sqrt(c) + o(n) edges where, for large c, 0.2659 <= A <= 0.4163.
TR-CS-2002-23
Loopy Logic
Dan Pless and George Luger
In this paper we describe a new logic-based stochastic modeling language. It is an extension of the Bayesian logic programming approach of Kersting and De Raedt. We specialize the Kirsting and De Raedt formalism by suggesting that product distributions are an effective combining rule for Horn clause heads. We use a refinement of Pearl's loopy belief propagation for the inference algorithm. We also extend the Kirsting and De Raedt language by adding learnable distributions. We propose a message passing algorithm based on Expectation Maximization for estimating the learned parameters in the general case of models built in our system. We have also added some additional utilities to our logic language including second order unification and equality predicates.
TR-CS-2002-22
Real-time Shape-from-Silhouette
Daniel E. Small and Lance R. Williams
The computer vision field has undergone a revolution of sorts in the past five years. Moore's law has driven real-time image processing from the domain of dedicated, expensive hardware, to the domain of commercial off-the-shelf computers. This thesis describes our work on the design, analysis and implementation of a Real-Time Shape-from-Silhouette Sensor (RTS^3). The system produces time varying volumetric data at real-time rates (10-30Hz). The data is in the form of binary volumetric images. Until recently, using this technique in a real-time system was impractical due to the computational burden. In this thesis we review the previous work in the field, and derive the mathematics behind camera calibration, silhouette extraction, and shape-from-silhouette. For our sensor implementation, we use four color camera-frame-grabber pairs and a single high-end Pentium III computer. The color cameras were configured to observe a common volume. This hardware uses our RTS^3 software to track volumetric motion. Two types of shape-from-silhouette algorithms were implemented and their relative performance was compared. Lastly, an application of our sensor to the problem of generating synthetic views was explored.
TR-CS-2002-21
Resultants for Unmixed Bivariate Polynomial Systems using the Dixon
formulation
Arthur Chtcherba and Deepak Kapur
A necessary and sufficient condition on the support of a generic unmixed bivariate polynomial system is identified such that for polynomial systems with such support, the Dixon resultant formulation produces their resultants. It is shown that Sylvester-type matrices can also be obtained for such polynomial systems. These results are shown to be a generalization of related results recently reported by Chionh as well as Zhang and Goldman. For a support not satisfying the above condition, the degree of the extraneous factor in the projection operator computed by the Dixon formulation is calculated by analyzing how much the support deviates from a related rectangular support satisfying the condition. The concept of a support interior point of a support is introduced; a generic inclusion of terms corresponding to support interior points in a polynomial system is shown not to affect the degree of the projection operator computed by the Dixon construction.
For generic mixed bivariate systems, "good" Sylvester type matrices can be constructed by solving an optimization problem on their supports. The determinant of such a matrix gives a projection operator with a low degree extraneous factor. The results are illustrated on a variety of examples.
TR-CS-2002-20
Logical Basis for the Automation of Reasoning: Case Studies
Larry Wos, Robert Veroff, and Gail W. Pieper
With the availability of computers in the late 1950s, researchers began to entertain the possibility of automating reasoning. Immediately, two distinctly different approaches were considered as the possible basis for that automation. In one approach, the intention was to study and then emulate people; in the other, the plan was to rely on mathematical logic.
In this chapter, we focus mainly on the latter, for logic has proved to provide an excellent basis for the automation of reasoning.
TR-CS-2002-19
Yet Another Single Law for Lattices
William McCune, R. Padmanabhan, and Robert Veroff
In this note we show that the equational theory of all lattices is defined by the single absorption law
(((y v x) ^ x) v (((z ^ (x v x)) v (u ^ x)) ^ v)) ^ (w v ((s v x) ^ (x v t))) = x.
This identity of length 29 with 8 variables is shorter than previously known such equations defining lattices.
TR-CS-2002-18
A Bayesian Network Classification Methodology for Gene Expression Data
Paul Helman, Robert Veroff, Susan R. Atlas, and Cheryl Willman
We present new techniques for the application of the Bayesian network learning framework to the problem of classifying gene expression data. Our techniques address the complexities of learning Bayesian nets in several ways. First, we focus on classification and demonstrate how this reduces the Bayesian net learning problem to the problem of learning subnetworks consisting of a class label node and its set of parent genes. We then consider two different approaches to identifying parent sets which are supported by current evidence; one approach employs a simple greedy algorithm to search the universe of all genes, and a second approach develops and applies a gene selection algorithm whose results are incorporated as a prior to enable an exhaustive search for parent sets over a restricted universe of genes. Two other significant contributions are the construction of classifiers from multiple, competing Bayesian network hypotheses and algorithmic methods for normalizing and binning gene expression data in the absence of prior expert knowledge. Our classifiers are first developed under a cross validation regimen against two publicly available data sets and then validated on corresponding out-of-sample test sets. The classifiers attain a classification rate in excess of 90% on each of these out-of-sample test sets.
TR-CS-2002-17
Splintering: A Technique for Improving Performance in Commodity TCP-IP
Patricia Gilfeather
In this paper, I describe a new approach to decreasing communication overhead: splintering. Splintering is the process of determining which functionality to extract from the protocol stack and distributing it. While offloading onto the network interface card (NIC) traditionally has either added new work or offloaded the entire protocol stack, my approach is to move some of the communication work onto the NIC. In this way we can retain the advantages of commodity protocols and also gain the efficiences of appropriate offloading onto peripheral devices. I describe my initial experimentation with splintering the de-fragmentation of IP datagrams, and follow this by a description of the approach I will take in splintering the processing for TCP packets.
TR-CS-2002-16
Constructing Sylvester-Type Resultant Matrices
using the Dixon Formulation
Arthur D. Chtcherba and Deepak Kapur
A new method for constructing Sylvester-type resultant matrices for multivariate elimination is proposed. Unlike sparse resultant constructions discussed recently in the literature or the Macaulay resultant construction, the proposed method does not explicitly use the support of a polynomial system in the construction. Instead, a multiplier set for each polynomial is obtained from the Dixon formulation using an arbitrary term for the construction. As shown in [KS96], the generalized Dixon resultant formulation implicitly exploits the sparse structure of the polynomial system. As a result, the proposed construction for Sylvester-type resultant matrices is sparse in the sense that the matrix size is determined by the support structure of the polynomial system, instead of the total degree of the polynomial system.
The proposed construction is a generalization of a related construction proposed by the authors in which the monomial 1 is used [CK00]. It is shown that any monomial (inside or outside the support of a polynomial in the polynomial system) can be used instead insofar as that monomial does not vanish on any of the common zeros of the polynomial system. For generic unmixed polynomial systems (in which every polynomial in the polynomial system has the same support, i.e., the same set of terms), it is shown that the choice of a monomial does not affect the matrix size insofar as it is in the support.
The main advantage of the proposed construction is for mixed polynomial systems. Supports of a mixed polynomial system can be translated so as to have a maximal overlap, and a term is selected from the overlapped subset of translated supports. Determining an appropriate translation vector for each support and a term from overlapped support can be formulated as an optimization problem. It is shown that under certain conditions on the supports of polynomials in a mixed polynomial system, a monomial can be selected leading to a Dixon multiplier matrix of the smallest size, thus implying that the projection operator computed using the proposed construction is either the resultant or has an extraneous factor of minimal degree.
The proposed construction is compared theoretically and empirically, on a number of examples, with other methods for generating Sylvester-type resultant matrices.
TR-CS-2002-15
On the Efficiency and Optimality of Dixon-based Resultant Methods
A. Chtcherba and D. Kapur
Structural conditions on polynomial systems are developed for which the Dixon-based resultant methods often compute exact resultants. For cases when this cannot be done, the degree of the extraneous factor in the projection operator computed using the Dixon-based methods is typically minimal. A method for constructing a resultant matrix based on a combination of Sylvester-dialytic and Dixon methods is proposed. A heuristic for variable ordering for this construction often leading to exact resultants is developed.
TR-CS-2002-14
Older-first Garbage Collection in Practice: Evaluation in a Java Virtual
Machine [preliminary version].
Darko Stefanovic, Matthew Hertz, Stephen M. Blackburn, Kathryn S. McKinley
and J. Eliot B. Moss.
Until recently, the best performing copying garbage collectors used a generational policy which repeatedly collects the very youngest objects, copies any survivors to an older space, and then infrequently collects the older space. A previous study, based on garbage collection simulation, pointed to potential improvements by using an Older-First copying garbage collection algorithm. The Older-First algorithm sweeps a fixed-sized window through the heap from older to younger objects, and avoids copying the very youngest objects which have not yet had sufficient time to die. We describe and examine here an implementation of the Older-First algorithm in the Jikes virtual machine for Java bytecode. This investigation shows Older-First can perform as well as the simulation results suggested, and greatly improves total program performance when compared to using a fixed-size nursery generational collector. We further compare Older-First to an Appel-style flexible-nursery generational collector in which the nursery occupies all of the heap that does not contain older objects. In these comparisons, the flexible-nursery collector is occasionally the better of the two, but on average the Older-First collector performs the best.
Final version will appear in ACM SIGPLAN Workshop on Memory System Performance, Berlin, Germany, June, 2002.
TR-CS-2002-13
COMB: A Portable Benchmark Suite for Assessing MPI Overlap
William Lawry, Christopher Wilson, Arthur. B. Maccabe, and Ron
Brightwell
This paper describes a portable benchmark suite that assesses the ability of cluster networking hardware and software to overlap MPI communication and computation. The Communication Offload MPI-based Benchmark, or COMB, uses two different methods to characterize the ability of messages to make progress concurrently with computational processing on the host processor(s). COMB measures the relationship between overall MPI communication bandwidth and host CPU availability. In this paper, we describe the two different approaches used by the benchmark suite, and we present results from several systems. We demonstrate the utility of the suite by examining the results and comparing and contrasting different systems.
TR-CS-2002-12
Experience in Offloading Protocol Processing to a Programmable NIC
Arthur B. Maccabe, Wenbin Zhu, Jim Otto, and Rolf Riesen
Offloading protocol processing will become an important tool in supporting our efforts to deliver increasing bandwidth to applications. In this paper we describe our experience in offloading protocol processing to a programmable gigabit Ethernet network interface card. For our experiments, we selected a simple RTS-CTS (request to send, clear to send) protocol called RMPP (Reliable Message Passing Protocol). This protocol provides end-to-end flow control and full message retransmit in the case of a lost or corrupt packet. By carefully selecting parts of the protocol for offloading, we were able to improve the bandwidth delivered to MPI applications from approximately 280 Mb per sec to approximately 700 Mb per sec using standard, 1500 byte, Ethernet frames. Using ``jumbo'', 9000 byte, frames the bandwidth improves from approximately 425 Mbs to 840 Mb per sec. Moreover, we were able to show a significant increase in the availability of the host processor.
TR-CS-2002-11
Distributing Application and OS Functionality to Improve Application
Performance
Arthur B. Maccabe, William Lawry, Christopher Wilson, and Rolf Riesen
In this paper we demonstrate that the placement of functionality can have a significant impact on the performance of applications. OS bypass distributes OS policies to the network interface and protocol processing to the application to enhance application performance. We take this notion one step further and consider the distribution of application functionality to the network interface and-or the operating system. We illustrate the advantages of this approach by considering double buffering at the application level, a standard technique used to hide communication latency.
TR-CS-2002-10
Sequence length requirements for phylogenetic methods.
Bernard M.E. Moret (U. New Mexico), Usman Roshan (U. Texas Austin),
and Tandy Warnow (U. Texas Austin)
We study the sequence lengths required by neighbor-joining, greedy parsimony, and a phylogenetic reconstruction method (DCM-NJ+MP) based on disk-covering and the maximum parsimony criterion. We use extensive simulations based on random birth-death trees, with controlled deviations from ultrametricity, to collect data on the scaling of sequence length requirements for each of the three methods as a function of the number of taxa, the rate of evolution on the tree, and the deviation from ultrametricity. Our experiments consistently show that DCM-NJ+MP has lower sequence length requirements than the other two methods when trees of high topological accuracy are desired, although all methods require much longer sequences as the deviation from ultrametricity or the height of the tree grows. Our study has significant implications for large-scale phylogenetic reconstruction (where sequence length requirements are a crucial factor), but also for future performance analyses in phylogenetics (since deviations from ultrametricity are proving pivotal).
TR-CS-2002-09
Towards the Development of Computational Tools for Evaluating
Phylogenetic Network Reconstruction Methods
Luay Nakhleh (University of Texas), Jerry Sun (University of Texas),
Tandy Warnow (University of Texas), C. Randal Linder (University of Texas),
and Bernard M.E. Moret (University of New Mexico)
We report on a suite of algorithms and techniques that together provide a simulation flow for studying the topological accuracy of methods for reconstructing phylogenetic networks. We implemented those algorithms and techniques and used three phylogenetic reconstruction methods for a case study of our tools. We present the results of our experimental studies and analyze the relative performance of these methods. Our results show that the accuracy of Splits, a method aimed at reconstructing phylogenetic networks, suffers significantly when hybridization events occurred during evolution.
TR-CS-2002-08
Transient Cplant
Dennis Lucero
This report describes the motivations, design, and implementation of the ``Transient Cplant'' project. The goal of this project is to improve the availability of Cplant to the research community by facilitating the installation of Cplant system software on a temporary basis. Transient Cplant is a Cplant installation designed to be utilized on an operational supercomputer without de-installing or interfering with the existing cluster operating system. Transient Cplant works on variety of architectures. Transient Cplant provides system transparency, minimal changes, efficiency, and scalability. Transient Cplant meets these goals by utilizing a diskless compute node design, RAM disks, installation scripts, and root filesystem export.
TR-CS-2002-07
Generic Application Intrusion Detection
Hajime Inoue and Stephanie Forrest
We describe an approach to Java anomaly intrusion detection called dynamic sandboxing. By gathering information about applications' behavior usually unavailable to other systems, dynamic sandboxing is able to detect anomalies at the application layer. We show our implementation is both effective and efficient at stopping a backdoor and a virus, and has a low false positive rate.
TR-CS-2002-06
Code Factoring and the Evolution of Evolvability
Terry Van Belle and David H. Ackley
Evolvability can be defined as the capacity of a population to evolve. We show that one advantage of Automatically Defined Functions (ADFs) in genetic programming is their ability to increase the evolvability of a population over time. We observe this evolution of evolvability in experiments using genetic programming to solve a symbolic regression problem that varies in a partially unpredictable manner. When ADFs are part of a tree's architecture, then not only do average populations recover from periodic changes in the fitness function, but that recovery rate itself increases over time, as the trees adopt modular software designs more suited to the changing requirements of their environment.
TR-CS-2002-05
Uniform subtree mutation
Terry Van Belle and David H. Ackley
To appear in EuroGP 2002
The traditional genetic programming crossover and mutation operators have the property that they tend to affect smaller and smaller fractions of a solution tree as the tree grows larger. It is generally thought that this property contributes to the `code bloat' problem, in which evolving solution trees rapidly become unmanageably large, and researchers have investigated alternate operators designed to avoid this effect. We introduce one such operator, called uniform subtree mutation (USM), and investigate its performance---alone and in combination with traditional crossover---on six standard problems. We measure its behavior using both computational effort and size effort, a variation that takes tree size into account. Our tests show that genetic programming using pure USM reduces evolved tree sizes dramatically, compared to crossover, but does impact solution quality somewhat. In some cases, however, a combination of USM and crossover yielded both smaller trees and superior performance, as measured both by size effort and traditional metrics.
TR-CS-2002-04
Inversion Medians Generally Outperform Breakpoint Medians in Phylogeny
Reconstruction from Gene-Order Data
Bernard M.E. Moret, Adam C. Siepel, Jijun Tang, and Tao Liu
Phylogeny reconstruction from gene-order data has attracted much attention over the last few years. The two software packages used for that purpose, BPAnalysis and GRAPPA, both use so-called breakpoint medians in their computations. Breakpoint distance, however, is a heuristic measure of evolution, not directly based on any model of genome rearrangement. We conjectured that phylogeny reconstructions could be improved by using inversion medians, which minimize evolutionary distance under an inversions-only model of genome rearrangement. Recent algorithmic developments have made it possible to compute inversion medians for problems of realistic size.
Our experimental studies unequivocally show that inversion medians are strongly preferable to breakpoint medians in the context of phylogenetic reconstruction from gene-order data. Improvements are most pronounced in the reconstruction of ancestral genomes, but are also evident in the topological accuracy of the reconstruction as well as, surprisingly, in the overall running time. Improvements are strongest for small average distances along tree edges and for evolutionary scenarios with a preponderance of inversion events, but occur in all cases, including evolutionary scenarios with high proportions of transpositions.
TR-CS-2002-03
Detector coverage under the r-contiguous bits matching rule
Fernando Esponda and Stephanie Forrest
Some computer anomaly detection systems inspired by the immune system rely on the r-contiguous bits matching rule, whereby two strings of length l are said to match if they have at least r contiguous bits in common. In this paper, we derive a recurrence relation and its closed form solution for computing the number of strings matched by a single such string called a detector.
TR-CS-2002-02
Defining Self: Positive and Negative Detection
Fernando Esponda and Stephanie Forrest
In this paper we present two anomaly detection schemes based on the same partial matching rule. One focuses on the detection of valid patterns while the other on the detection of invalid patterns, termed positive and negative detection respectively. An analysis of both schemes provides a basis for their comparison, as well as a means to control the generalizations in which they incur.
TR-CS-2002-01
Quantum and stochastic branching programs of bounded width
Farid Ablayev, Cristopher Moore, and Christopher Pollett
We prove upper and lower bounds on the power of quantum and stochastic branching programs of bounded width. We show any NC^1 language can be accepted exactly by a width-2 quantum branching program of polynomial length, in contrast to the classical case where width 5 is necessary unless NC^1=ACC. This separates width-2 quantum programs from width-2 doubly stochastic programs as we show the latter cannot compute the middle bit of multiplication. Finally, we show that bounded-width quantum and stochastic programs can be simulated by classical programs of larger but bounded width, and thus are in NC^1.
TR-CS-2001-38
SIND: A Framework for Binary Translation
Trek Palmer, Dino Dai Zovi, and Darko Stefanovic
Recent work with dynamic optimization in platform independent, virtual machine based languages such as Java has sparked interest in the possibility of applying similar techniques to arbitrary compiled binary programs. Systems such as Dynamo, DAISY, and FX!32 exploit dynamic optimization techniques to improve performance of native or foreign architecture binaries. However, research in this area is complicated by the lack of openly licensed, freely available, and platform-independent experimental frameworks. SIND aims to fill this void by providing a easily-extensible and flexible framework for research and development of applications and techniques of binary translation. Current research focuses are dynamic optimization of running binaries and dynamic security augmentation and integrity assurance.
TR-CS-2001-37
Problem Solving as Model Refinement: Towards a Constructivist Epistemology
George F. Luger, Joseph Lewis, and Carl Stern
In recent years the Artificial Intelligence research group at the University of New Mexico has considered several areas of problem solving in interesting and complex domains. These areas have ranged from the low level explorations of a robot tasked to explore, map, and use a new environment to the development of very sophisticated control algorithms for the optimal use of particle beam accelerators. Although the results of our research have been reflected in computer based problem solvers, such as the robot discovering and mapping out its world, these computational tasks are in many ways similar to expert human performance in similar tasks. In fact, in many important ways our computer-based approach mimics human expert performance in such domains. This paper describes three of these task domains as well as the software algorithms that have achieved competent performance therein. We conclude this paper with some comments on how software models of a domain can elucidate aspects of intellectual performance within that context. Furthermore, we demonstrate how exploratory problem solving along with model refinement algorithms can support a constructivist epistemology.
TR-CS-2001-36
A Complete Analysis of Resultants and Extraneous Factors for
Unmixed Bivariate Polynomial Systems using the Dixon formulation
Arthur Chtcherba and Deepak Kapur
A necessary and sufficient condition on the support of a generic unmixed bivariate polynomial system is identified such that for polynomial systems with such support, the Dixon resultant formulation produces their resultants. It is shown that Sylvester-type matrices can also be obtained for such polynomial systems. These results are shown to be a generalization of related results recently reported by Zhang and Goldman. The concept of the interior of a support is introduced; a generic inclusion of terms corresponding to support interior points in a polynomial system does not affect the nature of the projection operator computed by the Dixon construction. For a support not satisfying the above condition, the degree of the extraneous factor in the projection operator computed by the Dixon formulation is calculated by analyzing how much the support deviates from a related support satisfying the condition.
For generic mixed bivariate systems, "good" Sylvester type matrices can be constructed by solving an optimization problem on their supports. The determinant of such a matrix gives a projection operator with a low degree extraneous factor. The results are illustrated on a variety of examples.
TR-CS-2001-35
New Software for Computational Phylogenetics
B.M.E. Moret, L.-S. Wang, and T. Warnow
A phylogeny is the evolutionary history of a group of organisms; phylogenetics attempts to reconstruct such phylogenies from a variety of data available on these organisms, such as behavior, morphology, metabolic pathways, DNA sequences for certain genes, etc. Such reconstructions are crucial to an understanding of evolution and also provide an important tool in pharmaceutical research. Because of the volume of data, reconstructions are done through software; because of the difficulty of the task (almost all approaches require enormous amounts of computation), accurate reconstructions are only possible today for small groups of organisms. Yet the volume of data available about many contemporary (and some ancestral) organisms increases dramatically every year and biologists are setting their sights on the "Tree of Life" grand challenge: to reconstruct the evolutionary history of all known organisms. In order to face this challenge, new approaches to phylogenetic software are needed, approaches that combine a new level of algorithmic sophistication (so as to scale up to the enormous size of the problem) and the best high-performance tools. In this paper, we illustrate these two components with recent work by our research group: (i) we have devised and refined the disc-covering methodology (a type of divide-and-conquer methodology) for handling large datasets efficiently and improve the accuracy of reconstructions; and (ii) we have produced the GRAPPA software suite (for reconstructing phylogenies from gene-order data) using the best principles of high-performance algorithm engineering and obtained a speedup over the original implementation by six orders of magnitude.
TR-CS-2001-34
Data Mining using Web Spiders
Carol D. Harrison and George F. Luger
As the volume of available information has grown, the field of data mining has become more important for turning data into usable knowledge. This project's contribution to the field is an analysis of the efficacy of data mining algorithms as applied to categorizing web pages with respect to a search term. Search engines were used as a springboard, following links suggested by the search engine to traverse the Web and reach pages that may not be found by the search engine. It is intended to provide a more selective result based on data mining results through second level verification and application of more stringent requirements for internal page consistency. In this project, AQ11 and ID3 were chosen as classic data mining algorithms representative of the inductive learning tradition; their results were compared to results from the Support Vector Machine, a more recent data mining algorithm, for their ability to extract information from Web pages.
TR-CS-2001-33
Uniform Subtree Mutation - (Note: now superseded by TR-CS-2002-05.)
Terry Van Belle and David Ackley
(Note: now superseded by TR-CS-2002-05: The paper link below will take you to that paper.) Description below is that from TR-CS-2002-05:
To appear in EuroGP 2002
The traditional genetic programming crossover and mutation operators have the property that they tend to affect smaller and smaller fractions of a solution tree as the tree grows larger. It is generally thought that this property contributes to the `code bloat' problem, in which evolving solution trees rapidly become unmanageably large, and researchers have investigated alternate operators designed to avoid this effect. We introduce one such operator, called uniform subtree mutation (USM), and investigate its performance---alone and in combination with traditional crossover---on six standard problems. We measure its behavior using both computational effort and size effort, a variation that takes tree size into account. Our tests show that genetic programming using pure USM reduces evolved tree sizes dramatically, compared to crossover, but does impact solution quality somewhat. In some cases, however, a combination of USM and crossover yielded both smaller trees and superior performance, as measured both by size effort and traditional metrics.
TR-CS-2001-32
Almost All Graphs of Degree 4 are 3-Colorable
Dimitris Achlioptas and Cristopher Moore
To appear in Proc. Symposium on the Theory of Computing (STOC) 2002.
The technique of approximating the mean path of Markov chains by differential equations has proved to be a useful tool in analyzing the performance of heuristics on random graph instances. However, only a small family of algorithms can currently be analyzed by this method, due to the need to maintain uniform randomness within the original state space. Here, we significantly expand the range of the differential equation technique, by showing how it can be generalized to handle heuristics that give priority to high- or low- degree vertices. In particular, we focus on 3-coloring and analyze a ``smoothed'' version of the practically successful Brelaz heuristic. This allows to prove that almost all graphs with average degree d are 3-colorable for d <= 4.03, and that almost all 4-regular graphs are 3-colorable. This improves over the previous lower bound of 3.847 on the 3-colorability threshold and gives the first non-trivial result on the colorability of random regular graphs. In fact, our methods can be used to deal with arbitrary sparse degree distributions and in conjunction with general graph algorithms that have a preference for high- or low-degree vertices.
TR-CS-2001-31
Subtree-Counting Loops
Francois Lemieux, Cristopher Moore, and Denis Therien
An important objective of the algebraic theory of languages is to determine the combinatorial properties of the languages recognized by finite groups and semigroups. Finite nilpotent groups have been characterized as those groups that have the ability to count subwords. In this paper, we attempt to generalize this result to finite loops. We introduce the notion of subtree-counting and define subtree-counting loops. We prove a number of algebraic results. In particular, we show that all subtree-counting loops and their multiplication groups are nilpotent. We conclude with several small examples and a number of open questions related to computational complexity.
TR-CS-2001-30
Improved bounding and searching for phylogeny reconstruction from
gene-order data
Bernard M.E. Moret and Jijun Tang
A phylogeny is the evolutionary history of a group of organisms; systematists (and other biologists) attempt to reconstruct this history from various forms of data about contemporary organisms. Phylogeny reconstruction is a crucial step in the understanding of evolution as well as an important tool in biological, pharmaceutical, and medical research. Phylogeny reconstruction from molecular data is very difficult: almost all optimization models give rise to NP-hard (and thus computationally intractable) problems. Yet approximations must be of very high quality in order to avoid outright biological nonsense. Thus many biologists have been willing to run farms of processors for many months in order to analyze just one dataset.
Phylogenies derived from gene order data may prove crucial in answering some fundamental open questions in biomolecular evolution. Yet very few techniques are available for such phylogenetic reconstructions---and all involved NP-hard optimization problems. One method is breakpoint analysis, developed by Blanchette and Sankoff for solving the "breakpoint phylogeny." We had reimplemented their approach to produce the GRAPPA software suite, which ran three orders of magnitude faster thanks to the application of algorithm engineering techniques and, in its parallel version, demonstrated a one-million-fold speedup on a dataset of flowering plants.
We report here on improvements to the bounding and searching techniques used in GRAPPA that have brought on an additional speedup by another two orders of magnitude. Such speedups, while modest from a theoretical standpoint (the exponential behavior is simply pushed back to slightly larger instance sizes), nevertheless have important practical consequences, as they allow research biologists to analyze in a few hours or days data that could not have been analyzed at all just one year ago. Our searching method is of independent interest, as it is applicable to any optimization problem of modest size where lower bounds are expected to be tight.
TR-CS-2001-29
An Algorithm to Find All Sorting Reversals
Adam C. Siepel
The problem of estimating evolutionary distance from differences in gene order has been distilled to the problem of finding the reversal distance between two signed permutations. During the last decade, much progress was made both in computing reversal distance and in finding a minimum sequence of sorting reversals. For most problem instances, however, many minimum sequences of sorting reversals exist; furthermore, obtaining the complete set can be useful in exploring the space of genome rearrangements, in pursuit of solutions to higher-level problems. The problem of finding all minimum sequences of sorting reversals reduces easily to the problem of finding all sorting reversals of one permutation with respect to another. We derive an efficient algorithm to solve this latter problem, and present experimental results indicating that our algorithm performs extremely well in comparison to the best known alternative.
TR-CS-2001-28
Designing a Controller for a Multi-Train Multi-Track System
Deepak Kapur, Victor Winter and Raymond Berg
The use of formal methods for analyzing and synthesizing a controller for a multi-train multi-track railway system is discussed. The research was motivated by a case study involving the Bay Area Rapid Transit (BART) system. The overall goal is to design a train acceleration control function that enables trains to be safely placed but also increases system throughput. The use of a modeling language for specifying safety properties and a control function is illustrated. The program transformation methodology supported in the HATS system is employed to generate an efficient implementation from a high-level specification of a controller. This implementation can then be used to simulate the controller behavior, thus further enhancing confidence in the design. Properties of optimization transformations can be verified using an rewrite-rule based induction theorem prover Rewrite Rule Laboratory (RRL).
Appeared in the Proceedings of ICALP 2001, Satellite Workshop on Algorithmic Methods and Models for Organization of Railways, ATMOS 2001, Crete, Greece. Also in Electronic Notes in Theoretical Computer Science, Vol. 50, No. 1.
TR-CS-2001-27
Improving the Scalability of Massively Parallel
System Performance Tools
Chu J. Jong
Many applications, such as material simulation, climate modeling, and data visualization, require tremendous computing power to process data and to generate a result. Massively Parallel (MP) systems, built with thousands of processor nodes, can meet the needs of these applications. The degree of the collaboration between processes that run on different processor nodes in the MP system determines the use of the aggregate computation power of that MP system. Most MP system vendors claim that their systems achieve high throughput and low latencies; but the figures they present are mostly experimental and only measured under an ideal circumstances. In reality, when an application runs, the effective use of a system depends on the programmer's ability, possibly with help from the compiler, to manage the resources.
Tools that assist in performance monitoring and performance tuning can help programmers identify where and when their programs mismanage resources. Currently, many useful performance tools are available for workstations with a low degree of parallelism. When porting these performance tools to an MP system, however, the effectiveness of the tool diminishes quickly as the number of processors increases to certain amount. Although MP system performance tools help programmers improve the performance of their program, most of them either target at a specific architecture or rely on custom-built hardware to collect performance data. Among all MP system performance tools, very few can handle up to hundreds of processor nodes, and none have been able to accommodate more than a thousand processor nodes. The major problem is that these tools do not scale-up, even to hundreds of processor nodes.
Our proposed research work solves the most important issue, scalability, of the MP system performance tool development. Our focus areas include: how to collect useful data, how to gather the needed data, how to reduce system overheads, how to effectively present results to user, and how to produce a flexible and scalable tool for the MP system users.
TR-CS-2001-26
Genetic Algorithms for Finding Polynomial Orderings
Jurgen Giesl, Fernando Esponda, and Stephanie Forrest
Polynomial orderings are a well-known method to prove termination of term rewriting systems. However, for an automation of this method, the crucial point is to find suitable coefficients by machine. We present a novel approach for solving this problem by applying genetic algorithms.
TR-CS-2001-25
High-Performance Algorithm Engineering for Parallel Computation
David A. Bader, Bernard M.E. Moret, and Peter Sanders
The emerging discipline of algorithm engineering has primarily focussed on transforming pencil-and-paper sequential algorithms into robust, efficient, well tested, and easily used implementations. As parallel computing becomes ubiquitous, we need to extend algorithm engineering techniques to parallel computation. Such an extension adds significant complications. After a short review of algorithm engineering achievements for sequential computing, we review the various complications caused by parallel computing, present some examples of successful efforts, and give a personal view of possible future research.
TR-CS-2001-24
A Rotation and Translation Invariant Discrete Saliency Network
Lance R. Williams and John W. Zweck
We describe a neural network which enhances and completes salient closed contours. Our work is different from all previous work in three important ways. First, like the input provided to V1 by LGN, the input to our computation is isotropic. That is, the input is composed of spots not edges. Second, our network computes a well defined function of the input based on a distribution of closed contours characterized by a random process. Third, even though our computation is implemented in a discrete network, its output is invariant under continuous rotations and translations of the input pattern.
TR-CS-2001-23
The Distribution of Variable-length Phatic Interjectives on the World Wide Web
Dennis Chao and Patrik D'haeseleer
If one uses a commercial internet search engine to search for increasingly long versions of variable-length interjectives on the web (e.g. "whee", "wheee", "wheeee", etc), the number of pages found containing these longer words falls off as a power law. The exponents for the length frequency distributions of different interjectives are not the same, although they may cluster around a few exponents. Surprisingly, the exponents are much larger than the -1 predicted by Zipf's Law. We believe that the restricted domain of variable-length phatic interjectives is an interesting subset of English that can provide an alternative simple model system of word length distributions.
TR-CS-2001-22
Realtime MEG source localization with realistic noise
Sung Chan Jun, Barak A. Pearlmutter, Guido Nolte
Iterative gradient methods like Levenberg-Marquardt (LM) are in widespread use for source localization from electroencephalographic (EEG) and magnetoencephalographic (MEG) signals. Unfortunately LM depends sensitively on the initial guess, particularly (and counter-intuitively) at higher signal-to-noise ratios, necessitating repeated runs. This, combined with LM's high per-step cost, makes its computational burden quite high. To reduce this burden, we trained a multilayer perceptron (MLP) as a real-time localizer. We used an analytical model of quasistatic electromagnetic propagation through the head to map randomly chosen dipoles to sensor activities, and trained an MLP to invert this mapping in the presence of various sorts of noise. With realistic noise, our MLP is about five hundred times faster than n-start-LM with n=4 to match accuracies, while our hybrid MLP-start-LM is about four times more accurate and thirteen times faster than 4-start-LM.
TR-CS-2001-21
Computational Complexity in Physics
Cristopher Moore
This is a brief review article written for the proceedings of the NATO Workshop on Complexity and Large Deviations in Geilo, 2001.
TR-CS-2001-20
Tiling groups for Wang tiles
Cristopher Moore, Ivan Rapaport, and Eric Remila
To appear in SODA 2002
We apply tiling groups and height functions to tilings of regions in the plane by Wang tiles, which are squares with colored boundaries where the colors of shared edges must match. We define a set of tiles as unambiguous if it contains all tiles equivalent to the identity in its tiling group. For all but one set of unambiguous tiles with two colors, we give efficient algorithms that tell whether a given region with colored boundary is tileable, show how to sample random tilings, and how to calculate the number of local moves or ``flips'' required to transform one tiling into another. We also analyze the lattice structure of the set of tilings, and study several examples with three and four colors as well.
TR-CS-2001-19
Inferring phylogenetic relationships using whole genome data:
A case study of photosynthetic organelles and chloroplast genomes
Linda A. Raubeson, Bernard M.E. Moret,
Jijun Tang, Stacia K. Wyman, and Tandy Warnow
We present a case study in the use of a challenging dataset of gene orders to determine deep relationships among photosynthetic organelles. We have conducted an extensive analysis using several techniques that our group has developed for phylogenetic reconstruction from such data. We find that our methods are capable of extracting significant information from an undersampled dataset with relatively few genes---evidence that gene-order data contains a strong phylogenetic signal and that our methods can extract this signal. We also present new and independent evidence to resolve some of the controversies remaining in organellar phylogeny.
TR-CS-2001-18
Fast Phylogenetic Methods for the Analysis of Genome Rearrangement Data:
An Empirical Study
Li-San Wang, Robert K. Jansen, Bernard M.E. Moret, Linda A. Raubeson,
and Tandy Warnow
Evolution operates on whole genomes through mutations that change the order and strandedness of genes within the genomes. Thus analyses of gene order data present new opportunities for discoveries about deep evolutionary events, provided that sufficiently accurate methods can be developed to reconstruct evolutionary trees. In this paper we present a new method of character coding for parsimony-based analysis of genomic rearrangements called MPBE-2, and a new parsimony-based method which we call MPME (based on an encoding of Bryant), both variants of the MPBE method. We then conduct computer simulations to compare this class of methods to distance-based methods (NJ under various distance measures) and other parsimony approaches (MPBE and MPME) for phylogeny reconstruction based on genome rearrangement data. Our empirical results show that parsimony approaches generally have better accuracy than distance-based methods.
TR-CS-2001-17
The Accuracy of Fast Phylogenetic Methods for Large Datasets
Luay Nakhleh, Bernard M.E. Moret, Usman Roshan, Katherine St.~John,
Jerry Sun, and Tandy Warnow
Whole-genome phylogenetic studies require various sources of phylogenetic signals to produce an accurate picture of the evolutionary history of a group of genomes. In particular, sequence-based reconstruction will play an important role, especially in resolving more recent events. But using sequences at the level of whole genomes means working with very large amounts of data---large numbers of sequences---as well as large phylogenetic distances, so that reconstruction methods must be both fast and robust as well as accurate. We study the accuracy, convergence rate, and speed of several fast reconstruction methods: neighbor-joining, Weighbor (a weighted version of neighbor-joining), greedy parsimony, and a new phylogenetic reconstruction method based on disk-covering and parsimony search (DCM-NJ + MP). Our study uses extensive simulations based on random birth-death trees, with controlled deviations from ultrametricity. We find that Weighbor, thanks to its sophisticated handling of probabilities, outperforms other methods for short sequences, while our new method is the best choice for sequence lengths above 100. For very large sequence lengths, all four methods have similar accuracy, so that the speed of neighbor-joining and greedy parsimony makes them the two methods of choice.
TR-CS-2001-16
Introduction to Scientific Visualization
Edward Angel
As the power of computers has increased, scientists and mathematicians are having increasing difficult in interpreting the results of their simulations and computations. In addition, the volume of data that is generated defies our ability to store and interpret our results. Scientific visualization combines the power of the human visual system with the power of modern computer graphics to display large data sets in a fashion that can lead to both understanding and insight. In this presentation, we shall introduce the basic ideas behind this new field. First, we shall discuss the basic notions of modern computer graphics and how computer graphics can be used to display nongeometric data. We then examine two fundamental applications: scalar field visualization and vector field visualization. We will also examine some of the available software systems. Finally, we will examine recent work in scientific visualization on high-performance computers.
TR-CS-2001-15
Fast Visualization of Vector Fields Using Color Mapping
Patricia Crossno, Edward Angel, and David Munich
Many problems in vector-field visualization require processing very large data sets. However, at the same time we want to detect very local very complex phenomena. This paper presents an approach that is completely local, unlike standard methods such as streamlines, and requires almost no computation. Instead it relies on the users' ability to visualize quite complex color patterns in real time. We present two closely related color methods. In the first, we make binary color decisions and use halftoning methods to generate more complex colorings. These images have some loose connections to methods such as LIC but are much faster to derive. The second method maps flow vectors directly into colors, which requires more work but is still a local method. We show that both methods are simple to parallelize. We demonstrate the methods applicability to global climate models.
TR-CS-2001-14
Marching Flow
Edward Angel, David Munich, and Patricia Crossno
Interactive visualization of large flow data sets requires new methods that are fast, can be run in parallel, and are interactive. In this paper we propose a method based on the use of color and local pattern matching. The pattern matching is inspired by the marching cubes algorithm for scalar field visualization. For flow visualization, there are many more patterns, but at least for two-dimensional flow, the number of cases is manageable. For three-dimensional flow, using a subset of the cases can produce informative visualizations. We show results on both data from global ocean circulation models and from artificial data sets.
TR-CS-2001-13
An Object-Oriented Particle System for Simulation and
Visualization
Jun Zhang, Edward Angel, Paul Alsing, and David Munich
Particle systems have been used successfully in applications ranging from simulations of physical phenomena, to creation of special effects in the movie industry, to scientific visualization. One problem encountered in practice is that application programmers usually derive a new code from scratch for each application even though particle systems have a basic object-oriented flavor. In this paper, we demonstrate a simple object- oriented particle system that has been implemented in C++ and applied to a variety of applications including graphical special effects, Lennard-Jones fluid simulation, isosurface extraction, and generation of streamlines from flow simulations. In each case, the code was developed from the basic particle system in a very short time. We shall also show comparisons with non-object-oriented codes that demonstrate that the object- orientation has only a small performance penalty. We shall also demonstrate parallelization of our simulations.
TR-CS-2001-12
Reconstructing Optimal Phylogenetic Trees:
A Challenge in Experimental Algorithmics
Bernard M.E. Moret and Tandy Warnow
Experimental algorithmics has made much progress in the study of basic building blocks for discrete computing: many excellent papers have appeared that compared various priority queues, hash tables, search trees, sorting algorithms, and approximation algorithms for Satisfiability, Binpacking, Graph Coloring, and the Travelling Salesperson problems, just to name a few (for references, see~\cite{moret-shapiro,moret-dimacs}). Its subdiscipline of algorithm engineering likewise has seen great progress in the development of libraries (as exemplified by LEDA), the beginning of a set of software engineering practices for discrete computing, and the refinement of models of computation that take into account today's deep memory hierarchies. We need to extend the scope and benefits of experimental algorithmics and algorithm engineering to applications in the computational sciences.
In this paper, we present on one such application: the reconstruction of evolutionary histories (phylogenies) from molecular data such as DNA sequences. Our presentation is not a survey of past and current work in the area, but rather a discussion of what we see as some of the important challenges in experimental algorithmics that arise from computational phylogenetics. As motivational examples or examples of possible approaches, we briefly discuss two specific uses of algorithm engineering and of experimental algorithmics from our recent research.
TR-CS-2001-11
Automatic Synthesis of Isotropic Textures
on the Sphere from Sample Images Using
the Laplacian Pyramid Transform
Curtis Sirl-Moore and Lance R. Williams
A method for synthesizing a given texture sample directly on the surface of a three-dimensional object is presented. The method combines the Heeger-Bergen texture synthesis algorithm with an implementation of the Laplacian pyramid transform on the sphere. It avoids the problems of distortion and discontinuity inherent in texture mapping by synthesizing texture directly on the object surface. Furthermore, because it is automatic, no artistic skill is required and no ad hoc parameter-tweaking is necessary. Finally, while it takes several iterations to terminate, it is notably inexpensive to compute.
TR-CS-2001-10
Industrial Applications of High-Performance Computing for
Phylogeny Reconstruction
David A. Bader, Bernard M.E. Moret, and Lisa Vawter
Phylogenies (that is, tree-of-life relationships) derived from gene order data may prove crucial in answering some fundamental open questions in biomolecular evolution. Real-world interest is strong in determining these relationships. For example, pharmaceutical companies may use phylogeny reconstruction in drug discovery for finding plants with similar gene production. Health organizations study the evolution and spread of viruses such as HIV to gain understanding of future outbreaks. And governments are interested in aiding the production of foodstuffs like rice, wheat, and corn, by understanding the genetic code. Yet very few techniques are available for such phylogenetic reconstructions. Appropriate tools for analyzing such data may help resolve some difficult phylogenetic reconstruction problems; indeed, this new source of data has been embraced by many biologists in their phylogenetic work.
With the rapid accumulation of whole genome sequences for a wide diversity of taxa, phylogenetic reconstruction based on changes in gene order and gene content is showing promise, particularly for resolving deep (i.e., old) branches. However, reconstruction from gene-order data is even more computationally intensive than reconstruction from sequence data, particularly in groups with large numbers of genes and highly rearranged genomes. We have developed a software suite, GRAPPA, that extends the breakpoint analysis (BPAnalysis) method of Sankoff and Blanchette while running much faster: in a recent analysis of a collection of chloroplast data for species of Campanulaceae on a 512-processor Linux supercluster with Myrinet, we achieved a one-million-fold speedup over BPAnalysis. GRAPPA currently can use either breakpoint or inversion distance (computed exactly) for its computation and runs on single-processor machines as well as parallel and high-performance computers.
TR-CS-2001-09
Counting, Fanout, and the Complexity of Quantum QACC
Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett
Quantum Information and Computation 2(1) (2002) 35-65.
We propose definitions of QAC^0, the quantum analog of the classical class AC^0 of constant-depth circuits with AND and OR gates of arbitrary fan-in, and QACC[q], where Mod_q gates are also allowed. We prove that parity or fanout allows us to construct quantum Mod_q gates in constant depth for any q, so QACC[2] = QACC. More generally, we show that for any q, p>1, Mod_q is equivalent to Mod_p (up to constant depth). This implies that QAC^0 with unbounded fanout gates, denoted QAC_wf^0, is the same as QACC[q] and QACC for all q. Since ACC[p] != ACC[q] whenever p and q are distinct primes, QACC[q] is strictly more powerful than its classical counterpart, as is QAC^0 when fanout is allowed. This adds to the growing list of quantum complexity classes which are provably more powerful than their classical counterparts.
TR-CS-2001-08
Finding an Optimal Inversion Median: Experimental Results
Adam Siepel and Bernard M.E. Moret
We derive a branch-and-bound algorithm to find an optimal inversion median of three signed permutations. We establish fairly tight upper and lower bounds at intermediate points using general geometric properties of the problem that can be exploited because highly efficient algorithms are now available for determining pairwise inversion distance. Our experiments on simulated datasets show that optimal inversion medians can be significantly better than breakpoint medians; they also indicate that our algorithm computes the median in reasonable time for genomes of medium size when the distances are not too large, a common case in phylogeny reconstruction. We also provide evidence that parallel implementations can provide linear speedup and thus enable us to solve most realistic instances.
TR-CS-2001-07
Algorithms and Experiments: The New (and Old) Methodology
Bernard M.E. Moret and Henry D. Shapiro
The last twenty years have seen enormous progress in the design of algorithms, but little of it has been put into practice. Because many recently developed algorithms are hard to characterize theoretically and have large running-time coefficients, the gap between theory and practice has widened over these years. Experimentation is indispensable in the assessment of heuristics for hard problems, in the characterization of asymptotic behavior of complex algorithms, and in the comparison of competing designs for tractable problems. Implementation, although perhaps not rigorous experimentation, was characteristic of early work in algorithms and data structures. Donald Knuth has throughout insisted on testing every algorithm and conducting analyses that can predict behavior on actual data; more recently, Jon Bentley has vividly illustrated the difficulty of implementation and the value of testing. Numerical analysts have long understood the need for standardized test suites to ensure robustness, precision and efficiency of numerical libraries. It is only recently, however, that the algorithms community has shown signs of returning to implementation and testing as an integral part of algorithm development. The emerging disciplines of experimental algorithmics and algorithm engineering have revived and are extending many of the approaches used by computing pioneers such as Floyd and Knuth and are placing on a formal basis many of Bentley's observations.
We reflect on these issues, looking back at the last thirty years of algorithm development and forward to new challenges: designing cache-aware algorithms, algorithms for mixed models of computation, algorithms for external memory, and algorithms for scientific research.
TR-CS-2001-06
Quantum Walks on the Hypercube
Cristopher Moore and Alexander Russell
Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical counterparts. We study two quantum walks on the n-dimensional hypercube, one in discrete time and one in continuous time. In both cases we show that the quantum walk mixes in 0.785 n steps, faster than the O(n log n) steps required by the classical walk. In the continuous-time case, the probability distribution is exactly uniform at this time. More importantly, these walks expose several subtleties in the definition of mixing time for quantum walks. Even though the continuous-time walk has an O(n) instantaneous mixing time at which it is precisely uniform, it never approaches the uniform distribution when the stopping time is chosen randomly as in [AharonovAKV2001]. Our analysis treats interference between terms of different phase more carefully than is necessary for the walk on the cycle; previous general bounds predict an exponential, rather than linear, mixing time for the hypercube.
TR-CS-2001-05
High-Performance Algorithm Engineering for Computational Phylogenetics
Bernard M.E. Moret, David A. Bader, and Tandy Warnow
Phylogeny reconstruction from molecular data poses complex optimization problems: almost all optimization models are NP-hard and thus computationally intractable. Yet approximations must be of very high quality in order to avoid outright biological nonsense. Thus many biologists have been willing to run farms of processors for many months in order to analyze just one dataset. High-performance algorithm engineering offers a battery of tools that can reduce, sometimes spectacularly, the running time of existing phylogenetic algorithms. We present an overview of algorithm engineering techniques, illustrating them with an application to the ``breakpoint analysis'' method of Sankoff et al. which resulted in the GRAPPA software suite. GRAPPA demonstrated a million-fold speedup in running time (on a variety of real and simulated datasets) over the original implementation. We show how algorithmic engineering techniques are directly applicable to a large variety of challenging combinatorial problems in computational biology.
TR-CS-2001-04
Toward General Analysis of Recursive Probability Models
Dan Pless and George Luger
Proc. 17th Conference on Uncertainty in Artificial Intelligence, pp. 429-436
There is increasing interest within the research community in the design and use of recursive probability models. Although there still remains concern about computational complexity costs and the fact that computing exact solutions can be intractable for many nonrecursive models and impossible in the general case for recursive problems, several research groups are actively developing computational techniques for recursive stochastic languages. We have developed an extension to the traditional lambda-calculus as a framework for families of Turing complete stochastic languages. We have also developed a class of exact inference algorithms based on the traditional reductions of the lambda-calculus. We further propose that using the deBruijn notation (a lambda-calculus notation with nameless dummies) supports effective caching in such systems (caching being an essential component of efficient computation). Finally, our extension to the lambda-calculus offers a foundation and general theory for the construction of recursive stochastic modeling languages as well as promise for effective caching and efficient approximation algorithms for inference.
TR-CS-2001-03
Using PRAM Algorithms on a Uniform-Memory-Access Shared-Memory Architecture
David A. Bader,
Ajith K. Illendula, and
Bernard M.E. Moret
The ability to provide uniform shared-memory access to a significant number of processors in a single SMP node brings us much closer to the ideal PRAM parallel computer. In this paper, we develop new techniques for designing a uniform-memory-access shared-memory algorithm from a PRAM algorithm and present the results of an extensive experimental study demonstrating that the resulting programs scale nearly linearly across a significant range of processors (from 1 to 64) and across the entire range of instance sizes tested. This linear speedup with the number of processors is, to our knowledge, the first ever attained in practice for intricate combinatorial problems and stands in sharp contrast to the results obtained on distributed-memory machines (such as mesh- and cluster-based architectures). The example we present in detail here is a graph decomposition algorithm that also requires the computation of a spanning tree; this problem is not only of interest in its own right, but is representative of a large class of irregular combinatorial problems that have simple and efficient sequential implementations and optimal PRAM algorithms, but have no known efficient parallel implementations. Our results thus offer promise for bridging the gap between the theory and practice of shared-memory parallel algorithms.
TR-CS-2001-02
New Approaches for Reconstructing Phylogenies from Gene Order Data
Bernard M.E. Moret,
Li-San Wang, Tandy Warnow, and Stacia K. Wyman
We report on new techniques we have developed for reconstructing phylogenies on whole genomes. Our mathematical techniques include new polynomial-time methods for bounding the inversion length of a candidate tree and new polynomial-time methods for estimating genomic distances which greatly improve the accuracy of neighbor-joining analyses. We demonstrate the power of these techniques through an extensive performance study based upon simulating genome evolution under a wide range of model conditions. Combining these new tools with standard approaches (fast reconstruction with neighbor-joining, exploration of all possible refinements of strict consensus trees, etc.) has allowed us to analyze datasets that were previously considered computationally impractical. In particular, we have conducted a complete phylogenetic analysis of a subset of the Campanulaceae family, confirming various conjectures about the relationships among members of the subset and about the principal mechanism of evolution for their chloroplast genome. We give representative results of the extensive experimentation we conducted on both real and simulated datasets in order to validate and characterize our approaches. We find that our techniques provide very accurate reconstructions of the true tree topology even when the data are generated by processes that include a significant fraction of transpositions and when the data are close to saturation.
TR-CS-2001-01
Decidable Classes of Inductive Theorems
Juergen Giesl and Deepak Kapur
Kapur and Subramaniam in their CADE-2000 paper, defined syntactical classes of equations where inductive validity is decidable. Thus, their validity can be checked without any user interaction and hence, this allows an integration of (a restricted form of) induction in fully automated reasoning tools such as model checkers. However, the results in Kapur and Subramaniam's paper were only restricted to equations. This paper extends the classes of conjectures considered in that paper to a larger class of arbitrary quantifier-free formulas (e.g., conjectures also containing negation, conjunction, disjunction, etc.).
TR-CS-2000-61
Automated Response Using System-Call Delays
Anil Somayaji and Stephanie Forrest
Automated intrusion response is an important unsolved problem in computer security. A system called pH (for process homeostasis) is described which can success fully detect and stop intrusions before the target system is compromised. In its current form, pH monitors every executing process on a computer at the systemcall level, and responds to anomalies by either delaying or aborting system calls. The paper presents the rationale for pH, its design and implementation, and a set of initial experimental results.
TR-CS-2000-60
Architecture for an Artificial Immune System
Steven A. Hofmeyr and Stephanie Forrest
An artificial immune system (ARTIS) is described which incorporates many properties of natural immune systems, including diversity, distributed computation, error tolerance, dynamic learning and adaptation and self-monitoring. ARTIS is a general framework for a distributed adaptive system and could, in principle, be applied to many domains. In this paper, ARTIS is applied to computer security, in the form of a network intrusion detection system called LISYS. LISYS is described and shown to be effective at detecting intrusions, while maintaining low false positive rates. Finally, similarities and differences between ARTIS and Holland's classifier systems are discussed.
TR-CS-2000-59
Modeling the Role of Neutral and Selective Mutations in Cancer
C.C. Maley and S. Forrest
In Artificial Life 7, M. Bedau, J. McCaskill, N. Packard, and S. Rasmussen (eds.). MIT Press, Cambridge, MA. pp. 395-404. No abstract available.
TR-CS-2000-58
Immunology as Information Processing
Stephanie Forrest and Steven A. Hofmeyr
In Design Principles for the Immune System and Other Distributed Autonomous Systems, edited by L.A. Segel and I. Cohen. Santa Fe Institute Studies in the Sciences of Complexity. New York: Oxford University Press (2000). No abstract available.
TR-CS-2000-57
Satisfiability of Systems of Equations over Finite Monoids
Cristopher Moore, Pascal Tesson, and Denis Therien
Submitted to Complexity 2001
We study the computational complexity of determining whether a systems of equations over a fixed finite monoid has a solution. In [GR99], it was shown that in the restricted case of groups the problem is tractable if the group is Abelian and NP-complete otherwise. We prove that in the general case, the problem is in P if the monoid is the direct product of an Abelian group and a commutative idempotent monoid, and is NP-complete if it does not divide such a monoid. In the restricted case where only constants appear on the right-hand side, we show that the problem is in P if the monoid is in the class R_1 join L_1, and that if an aperiodic monoid is outside this class, then it contains a submonoid for which this problem is NP-complete.
Furthermore, interesting connections to the well-studied Constraint Satisfiability Problem are uncovered and exploited.
TR-CS-2000-56
A Deformable Semantic Network as a Tool for Context-Based Ambiguity Resolution
M. Rogati, J. Lewis, and G. Luger
Presented at the 2nd Annual PURSUE Student Conference at UNM, (2000).
Ambiguity resolution is one of the primary challenges in natural language processing. We present a modified semantic network as a tool for performing ambiguity resolution based on context. The mechanisms used in this architecture resemble neurological processes responsible for the phenomenon of priming in humans. Three sentences, representing unique grammatical ambiguities, are placed in different contexts to analyze the behavior of the network. The results indicate that this approach has the potential for further application in problems where adaptation to context, or the surrounding environment, is critical.
TR-CS-2000-55
Emergent Representation in a Robot Control Architecture
A. Claiborne, M. Fricke, L. Lopes, J. Lewis, and G. Luger
Presented at 2nd Annual PURSUE Student Conference at UNM, (2000).
We offer a definition of representation based in dynamical systems. Then we present Madcat, a robotic control architecture that uses emergent representation to develop an internal model coupled to the environment through its behavior. The design is inspired by the Copycat program (Mitchell 1993). We present details of the Madcat architecture, the interface and development tool, and some results. A robot control architecture with these features will behave more robustly and autonomously in changing environments. Further research on vision and motivation will rely on the same design.
TR-CS-2000-54
A Learning Architecture for Intelligent Behavior in a Robot
Joseph Lewis and George Luger
We present a computational architecture for modeling intelligent behavior in a specific problem domain. Ours is a learning architecture that embraces a dynamical, embodied notion of intelligence relying on self-organizing emergent p rocesses. We discuss autopoeitic systems, those systems whose components are engaged in an ongoing process of mutual self-maintenance. We believe autopoeisis to be an essential characte ristic of intelligent systems. Structural coupling, or the capacity of the internal dynamics of an autopoeitic system to adapt to its changing environment, enables the architecture to utilize emergent representations of its environment. This representation makes possible further adaptive behavior. We describe the architecture in detail along with methods of development and training for a specific domain. We use our robot control architecture, Madcat (Lewis & Luger 2000), as an instantiated example of this architecture.
TR-CS-2000-53
Dependency Pairs for Equational Rewriting
Juergen Giesl and Deepak Kapur
The dependency pair technique of Arts and Giesl for termination proofs of term rewrite systems is extended to rewriting modulo equations. Up to now, such an extension was only known in the special case of AC-rewriting. In contrast to that, the proposed technique works for arbitrary non-collapsing equations (satisfying a certain linearity condition). With the proposed approach, it is now possible to perform automated termination proofs for many systems where this was not possible before. In other words, the power of dependency pairs can now also be used for rewriting modulo equations.
TR-CS-2000-52
Verification of Erlang Processes by Dependency Pairs
Juergen Giesl and Thomas Arts
Applicable Algebra in Engineering, Communation and Computing
Erlang is a functional programming language developed by Ericsson Telecom, which is particularly well suited for implementing concurrent processes. In this paper we show how methods from the area of term rewriting are presently used at Ericsson. To verify properties of processes, such a property is transformed into a termination problem of a conditional term rewriting system (CTRS). Subsequently, this termination proof can be performed automatically using dependency pairs.
The paper illustrates how the dependency pair technique can be applied for termination proofs of conditional TRSs. Secondly, we present three refinements of this technique, viz. narrowing, rewriting, and instantiating dependency pairs. These refinements are not only of use in the industrial applications sketched in this paper, but they are generally applicable to arbitrary (C)TRSs. Thus, in this way dependency pairs can be used to prove termination of even more (C)TRSs automatically.
TR-CS-2000-51
Highly accurate reconstruction of phylogenies from gene order data.
Bernard M.E. Moret, Li-San Wang, Tandy Warnow, and Stacia K. Wyman
Reconstructing phylogenetic trees from gene-order data has the potential to help resolve intriguing and biologically significant evolutionary datasets. In this paper, we report on some new techniques designed for estimating the NP-hard problem, Inversion Phylogeny, but that also prove remarkably effective for reconstructing phylogenies under evolutionary models that include transpositions and inverted transpositions. The inversion phylogeny problem arises in analyzing chloroplast and animal mitochondrial datasets in which inversions are believed to account for evolutionary changes. Ours is the first tool that explicitly seeks to solve this problem. Our technique is inspired by Sankoff and Blanchette's algorithmic approach to solving the breakpoint phylogeny, but uses new or improved upper and lower bounds that enable us to search tree space more efficiently. Our upper bounds are obtained by a combination of mathematical derivations on the expected inversion distances, numerical techniques, and algorithmic engineering to improve the performance of our algorithms. The lower bound is a simple but effective bound on the inversion length of a given tree. We validate our approach through extensive experimentation on both real and simulated datasets. We find that our techniques provide very accurate reconstructions of the true tree topology even when the data are generated by processes that include a significant fraction of transpositions and even when the data are close to saturation.
TR-CS-2000-50
Reasoning at Multiple Levels of Abstraction
Robert Veroff
In order to be successful in complex domains involving hierarchies of defined terms, an automated reasoning program must be able to reason effectively at multiple levels of abstraction. At a minimum, this requires appropriate problem representations and good search strategies. Ideally, the reasoning program reasons at high levels of abstraction when possible and appeals to arguments at lower levels of abstraction only as necessary. In this article, we describe our early experiences developing representations and search strategies for an application of automated reasoning to a problem domain from theoretical computer science. We then summarize some of the approaches we are considering to permit the automated reasoning program to reason effectively at multiple levels of abstraction.
TR-CS-2000-49
Closure Induction in a Z-like Language
David A. Duffy and Juergen Giesl
Proceeding of the First International Conference of Z and B Users (ZB 2000) LNCS 1878, pp. 471-490, Springer-Verlag, 2000.
Simply-typed set-theoretic languages such as Z and B are widely used for program and system specifications. The main technique for reasoning about such specifications is induction. However, while partiality is an important concept in these languages, many standard approaches to automating induction proofs rely on the totality of all occurring functions. Reinterpreting the second author's recently proposed induction technique for partial functional programs, we introduce in this paper the new principle of "closure induction" for reasoning about the inductive properties of partial functions in simply-typed set-theoretic languages. In particular, closure induction allows us to prove partial correctness, that is, to prove those instances of conjectures for which designated partial functions are explicitly defined.
TR-CS-2000-48
Context-Moving Transformations for Function Verification
Juergen Giesl
Proceedings of the 9th International Workshop on Logic-based Program Synthesis and Transformation (LOPSTR '99), LNCS 1817, pp. 293-312, Springer-Verlag, 2000.
Several induction theorem provers have been developed which support mechanized verification of functional programs. Unfortunately, a major problem is that they often fail in verifying tail recursive functions (which correspond to imperative programs). However, in practice imperative programs are used almost exclusively.
We present an automatic transformation to tackle this problem. It transforms functions which are hard to verify into functions whose correctness can be shown by the existing provers. In contrast to classical program transformations, the aim of our technique is not to increase efficiency, but to increase verifiability. Therefore, this paper introduces a novel application area for program transformations and it shows that such techniques can in fact solve some of the most urgent current challenge problems in automated verification and induction theorem proving.
TR-CS-2000-47
Equational Termination by Semantic Labelling
Hitoshi Ohsaki, Aart Middeldorp, and Juergen Giesl
Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSL '00), LNCS 1862, pp. 457-471, Springer-Verlag, 2000.
Semantic labelling is a powerful tool for proving termination of term rewrite systems. The usefulness of the extension to equational term rewriting described in (Zantema, 1995) is however rather limited. In this paper we introduce a stronger version of equational semantical labelling, parameterized by three choices: (1) the order on the underlying algebra (partial order vs. quasi-order), (2) the relation between the algebra and the rewrite system (model vs. quasi-model), and (3) the labelling of the function symbols appearing in the equations (forbidden vs. allowed). We present soundness and completeness results for the various instantiations and analyze the relationships between them. Applications of our equational semantic labelling technique include a short proof of the main result of (Ferreira et al, 1998) - the correctness of a version of dummy elimination for AC-rewriting which completely removes the AC-axioms - and an extension of Zantema's distribution elimination technique to the equational setting.
TR-CS-2000-46
Eliminating Dummy Elimination
Juergen Giesl and Aart Middeldorp
Proceedings of the 17th International Conference on Automated Deduction (CADE-17), LNAI 1831, pp. 309-323, Springer-Verlag, 2000
This paper is concerned with methods that automatically prove termination of term rewrite systems. The aim of dummy elimination, a method to prove termination introduced by Ferreira and Zantema, is to transform a given rewrite system into a rewrite system whose termination is easier to prove. We show that dummy elimination is subsumed by the more recent dependency pair method of Arts and Giesl. More precisely, if dummy elimination succeeds in transforming a rewrite system into a so-called simply terminating rewrite system then termination of the given rewrite system can be directly proved by the dependency pair technique. Even stronger, using dummy elimination as a preprocessing step to the dependency pair technique does not have any advantages either. We show that to a large extent these results also hold for the argument filtering transformation of Kusakari et al.
TR-CS-2000-45
Induction Proofs With Partial Functions
Juergen Giesl
To appear in the Journal of Automated Reasoning
In this paper we present a method for automated induction proofs about partial functions. We show that most well-known techniques developed for (explicit) induction theorem proving are unsound when dealing with partial functions. But surprisingly, by slightly restricting the application of these techniques, it is possible to develop a calculus for automated induction proofs with partial functions. In particular, under certain conditions one may even generate induction schemes from the recursions of non-terminating algorithms. The need for such induction schemes and the power of our calculus have been demonstrated on a large collection of non-trivial theorems (including Knuth and Bendix' critical pair lemma). In this way, existing induction theorem provers can be directly extended to partial functions without major changes of their logical framework.
TR-CS-2000-44
Ribbon tile invariants from signed area
Cristopher Moore and Igor Pak
Ribbon tiles are polyominoes consisting of $n$ squares laid out in a path, each step of which goes north or east. Tile invariants were first introduced in [Pak], where a full basis of invariants of ribbon tiles was conjectured. Here we present a complete proof of the conjecture, which works by associating ribbon tiles with a certain polygon in the complex plane, and deriving invariants from the signed area of this polygon.
TR-CS-2000-43
Teleo-Reactive Control for Accelerator Beamline Tuning
William Klein, George Luger, Carl Stern, and Dan Pless
Over the past five years we have designed, built, and tested a portable control architecture for accelerator beamline tuning. To date our software has been tested against software models of accelerators and against actual beamlines at Brookhaven and Argonne National Laboratories. In this paper we briefly describe our object-based, hierarchically organized portable architecture. The main focus of this paper, however, is to describe our extensions to Nilsson's teleo-reactive (TR) planner to make it suitable to handle the complex plan execution tasks of accelerator beamline control. Extensions to Nilsson's original system include the addition of actions for targeted data gathering. We extend the rules of the TR planner with the addition of new types of rules that adjust intermediate goals and that adapt to context changes by loading and unloading rule sets. We give some examples of our own extended teleo-reactive control framework. We conclude by briefly discussing tests of our system in beamline tuning as well as in diagnosing beamline misalignments.
TR-CS-2000-42
A Linear-Time Algorithm for Computing Inversion Distance Between
Signed Permutations with an Experimental Study
David A. Bader, Bernard M.E. Moret, Mi Yan
Hannenhalli and Pevzner gave the first polynomial-time algorithm for computing the inversion distance between two signed permutations, as part of the larger task of determining the shortest sequence of inversions needed to transform one permutation into the other. Their algorithm (restricted to distance calculation) proceeds in two stages: in the first stage, the overlap graph induced by the permutation is decomposed into connected components, then in the second stage certain graph structures (hurdles and others) are identified. Berman and Hannenhalli avoided the explicit computation of the overlap graph and gave an $O(n\alpha (n))$ algorithm, based on a Union-Find structure, to find its connected components, where $\alpha$ is the inverse Ackerman function. Since for all practical purposes $\alpha(n)$ is a constant no larger than four, this algorithm has been the fastest practical algorithm to date. In this paper, we present a new linear-time algorithm for computing the connected components, which is more efficient than that of Berman and Hannenhalli in both theory and practice. Our algorithm uses only a stack and is very easy to implement. We give the results of computational experiments over a large range of permutation pairs produced through simulated evolution; our experiments show a speed-up by a factor of 2 to 5 in the computation of the connected components and by a factor of 1.3 to 2 in the overall distance computation.
TR-CS-2000-41
The Phase Transition in 1-in-k SAT and NAE 3-SAT
Dimitris Achlioptas, Arthur Chtcherba, Gabriel Istrate, and Cristopher Moore
To appear in SODA 2001.
We study random instances of two canonical variations of satisfiability, 1-in-k SAT and Not-All-Equal 3-SAT. Like random k-SAT, these problems have a ``phase transition'' from satisfiability to unsatisfiability as we vary the ratio c of clauses to variables. For 1-in-k SAT we obtain the exact location of the threshold, making this the first NP-complete version of satisfiability for which an exact analysis has been given. We also show that the type of phase transition is the same as for 2-SAT, showing that there is no direct connection between the type of phase transition and computational complexity. For NAE 3-SAT we prove that a (non-uniform) sharp threshold exists and provide upper and lower bounds for its location: 1.514 < c < 2.215. We also perform a numerical experiment, giving an estimate of 2.1.
TR-CS-2000-40
Theorem Proving Support for Hardware Verification
Deepak Kapur
Invited Talk at FTP 2000, Third International Workshop on First-Order Theorem Proving, St. Andrews, Scotland, July 2000
Key reasoning mechanisms found useful and effective in using Rewrite Rule Laboratory (RRL) for automatically verifying properties of arithmetic circuits are reviewed.
TR-CS-2000-39
Orientation, Scale, and Discontinuity as Emergent Properties
of Illusory Contour Shape
Lance R. Williams and Karvel K. Thornber
A recent neural model of illusory contour formation is based on a distribution of natural shapes traced by particles moving with constant speed in directions given by Brownian motions. The input to that model consists of pairs of position and direction constraints and the output consists of the distribution of contours joining all such pairs. In general, these contours will not be closed and their distribution will not be scale-invariant. In this paper, we show how to compute a scale-invariant distribution of closed contours given position constraints alone and use this result to explain a well known illusory contour effect.
TR-CS-2000-38
New results on alternating and non-deterministic
two-dimensional finite-state automata
Jarkko Kari and Cristopher Moore
To appear in STACS 2001.
We resolve several long-standing open questions regarding the power of various types of finite-state automata to recognize ``picture languages,'' i.e. sets of two-dimensional arrays of symbols. We show that the languages recognized by 4-way alternating finite-state automata (AFAs) are incomparable to the so-called tiling recognizable languages. Specifically, we show that the set of acyclic directed graphs is AFA-recognizable but not tiling recognizable, while the set of non-acyclic directed graphs is tiling recognizable but not AFA-recognizable. More generally, the complement of an AFA-recognizable language is tiling recognizable, and therefore the AFA-recognizable languages are not closed under complement. We also show that the set of languages recognized by 4-way NFAs is not closed under complement, and that NFAs are more powerful than DFAs, even for languages over one symbol.
TR-CS-2000-37
Parallel Quantum Computation and Quantum Codes
Cristopher Moore and Martin Nilsson
To appear in SIAM Journal on Computing.
We study the class QNC of efficient parallel quantum circuits, the quantum analog of NC. We exhibit several useful gadgets and prove that various classes of circuits can be parallelized to logarithmic depth, including circuits for encoding and decoding standard quantum error-correcting codes, or more generally any circuit consisting of controlled-not gates, controlled pi-shifts, and Hadamard gates. Finally, while we note the exact quantum Fourier transform can be parallelized to linear depth, we conjecture that neither it nor a simpler ``staircase'' circuit can be parallelized to less than this.
TR-CS-2000-36
A New Object-Oriented Stochastic Modeling Language
Dan Pless, George Luger, and Carl Stern
Third IASTED Conference on Artificial Intelligence and Soft Computing (2000)
A new language and inference algorithm for stochastic modeling is presented. This work refines and generalizes the stochastic functional language originally proposed by Koller, McAllester, and Pfeffer (KMP). The language supports object-oriented representation and recursive functions. It provides a compact representation for a large class of stochastic models including infinite models. It provides the ability to represent general and abstract stochastic relationships and to decompose large models into smaller components. Our work extends the language of KMP by providing object encapsulation and reuse and a new and effective strategy for caching. An exact and complete inference algorithm is presented here that is expected to support efficient inference over important classes of models and queries.
TR-CS-2000-35
One-Dimensional Peg Solitaire, and Duotaire
Cristopher Moore and David Eppstein
MSRI Workshop on Combinatorial Games (2000)
We solve the problem of one-dimensional Peg Solitaire. In particular, we show that the set of configurations that can be reduced to a single peg forms a regular language, and that a linear-time algorithm exists for reducing any configuration to the minimum number of pegs.
We then look at the impartial two-player game, proposed by Ravikumar, where two players take turns making peg moves, and whichever play is left without a move loses. We calculate some simple nim-values and discuss when the game separates into a disjunctive sum of smaller games. In the version where a series of hops can be made in a single move, we show that neither the P-positions nor the N-positions (wins for the previous or next player) are described by a regular or context-free language.
TR-CS-2000-34
Independent Components of Magnetoencephalography,
Part II: Single-trial Response Time Estimation
Akaysha C. Tang, Barak A. Pearlmutter, Dan Phung, and Scott A. Carter
Blind source separation (BSS) decomposes multidimensional magnetoencephalography (MEG) data into a set of components. While many components reflect the activity from known and unknown noise sources, a subset of these separated components correspond to activation of spatially focal neuronal populations (TANG et al 2000). Focusing on the temporal aspects of these separated neuronal sources, we measure the single-trial response times of these neuronal populations. Through the application of BSS to MEG data involving visual, auditory, and somatosensory stimulation, we show that it is possible to non-invasively measure, in humans, the single-trial response times from specific neuronal populations within primary sensory and frontal polysensory areas under a wide range of stimulus and task conditions.
TR-CS-2000-33
Independent Components of Magnetoencephalography,
Part I: Localization
Akaysha C. Tang, Barak A. Pearlmutter, Dan Phung, and Scott A. Carter
Blind source separation (BSS) decomposes a multidimensional time series into a set of components, each with a one-dimensional time course and a fixed spatial distribution. For EEG and MEG, the former corresponds to the simultaneously separated and temporally overlapping signals for continuous non-averaged data; the latter corresponds to the set of attenuations from the sources to the sensors. These sensor projection vectors give information on the spatial locations of the sources. We use standard Neuromag dipole-fitting software to localize BSS-separated components of MEG data collected in several tasks in which visual, auditory, and somatosensory stimuli all play a role. We found that BSS-separated components with stimulus- or motor-locked responses can be localized to physiologically and anatomically meaningful locations within the brain. Combining BSS with more sophisticated source localization algorithms may further improve the precision of source modeling for MEG.
TR-CS-2000-32
An experimental study of the influence of quartet quality and
sequence length on the performance of unweighted quartet-based and
neighbor-joining phylogenetic reconstruction methods
Bernard M.E. Moret, Katherine St. John, Lisa Vawter, and Tandy Warnow
We present the results of a large-scale experimental study of unweighted quartet-based methods (quartet cleaning, quartet puzzling, and a short-quartet method) and the neighbor-joining method for phylogeny reconstruction. Our experiments include a large range of problem sizes, evolutionary rates, and sequence lengths, and are carefully designed to yield statistically robust results despite the size of the sample space, thereby offering a small step toward the development of an experimental methodology and a comprehensive test suite in phylogenetic algorithms. We evaluate the performance of these phylogenetic methods using the standard ``bipartition'' metric (the percentage of edge-induced bipartitions of the taxa shared by the model and the reconstructed trees), as well as by using the quartet-based metric (the percentage of quartet subtrees shared by the model and reconstructed trees). Our experiments confirm theoretical predictions that the convergence rate of unweighted quartet-based methods is quite slow. These experiments also show that the bipartition and quartet-based performance metrics are not well correlated, suggesting that methods based upon attempts to satisfy the maximum number of quartet ``constraints" are likely to have poor accuracy with respect to the standard bipartition metric. Finally, we find that the simple and efficient method of neighbor-joining consistently outperforms unweighted quartet-based methods, as well as the short-quartet method known as DCM-Buneman, across the entire range of parameters in our simulations, in terms of both metrics as well as in terms of running time.
TR-CS-2000-31
Phylogenies from Gene Order Data: A Detailed Study of Breakpoint Analysis
Bernard M.E. Moret, Stacia Wyman, David A. Bader, Tandy Warnow, and Mi Yan
Gene order data and phylogenies derived from them may prove crucial in answering some fundamental open questions in biomolecular evolution. Yet there are very few techniques available for such phylogenetic reconstructions. One method is \emph{breakpoint analysis}, developed by Blanchette and Sankoff \cite{BBS} for reconstructing the ``breakpoint phylogeny.'' Our earlier studies \cite{ismb2000,dcaf} confirmed the usefulness of the breakpoint phylogeny approach, but also found that {\tt BPAnalysis}, the implementation of breakpoint analysis developed by Blanchette and Sankoff, was too slow to use on all but very small datasets. In this paper, we report on a new implementation of breakpoint analysis. Our faster (by two orders of magnitude) and flexible implementation allowed us to conduct studies on the characteristics of breakpoint analysis, in terms of running time, quality, and robustness, as well as to analyze datasets that had been considered out of reach of such approaches until now. We report on these findings and also discuss future steps that our new implementation will enable us to take.
TR-CS-2000-30
Performance Study of Phylogenetic Methods:
(Unweighted) Quartet Methods and Neighbor-Joining
Katherine St. John, Tandy Warnow, Bernard M.E. Moret, and Lisa Vawter
We present the results of a large-scale experimental study of quartet-based methods (quartet cleaning and puzzling) for phylogeny reconstruction. Our experiments include a large range of problem sizes and of evolutionary rates, and were carefully designed to yield statistically robust results despite the size of the sample space. We measure outcomes in terms of numbers of edges of the true tree correctly inferred by each method (true positives). Our results indicate that quartet-based methods are much less accurate than the simple and efficient method of neighbor-joining, particularly for data composed of short- to medium-length sequences. We support our experimental findings by theoretical results that strongly suggest that quartet-cleaning methods are unlikely to yield accurate trees with less than exponentially long sequences. We conclude that a proposed reconstruction method should first be compared to the neighbor-joining method and further studied only if it offers a demonstrable practical advantage.
TR-CS-2000-29
Absolute Convergence: True Trees From Short Sequences
Tandy Warnow, Bernard M.E. Moret, and Katherine St. John
Fast-converging methods for reconstructing phylogenetic trees require that the sequences characterizing the taxa be of only polynomial length, a major asset in practice, since real-life sequences are of bounded length. However, of the half-dozen such methods proposed over the last few years, only two fulfill this condition without requiring knowledge of typically unknown parameters, such as the evolutionary rate(s) used in the model; this additional requirement severely limits the applicability of the methods. We say that methods that need such knowledge demonstrate \emph{relative fast convergence}, since they rely upon an oracle. We focus on the class of methods that do not require such knowledge and thus demonstrate \emph{absolute fast convergence}. We give a very general construction scheme that not only turns any relative fast-converging method into an absolute fast-converging one, but also turns any statistically consistent method that converges from sequences of length $O(e^{O(diam(T))})$ into an absolute fast-converging method.
TR-CS-2000-28
Rewriting, Induction and Decision Procedures:
A Case Study of Presburger Arithmetic
Deepak Kapur
To appear in ``Symbolic-algebraic methods and verification methods -- Theory and Applications,'' Alefeld, Rohn, Rump and Tamamato, Eds. Springer Mathematics, Springer Verlag, NY.
For theorem provers to be effective as well as acceptable for use in applications, it is essential that properties considered trivial and obvious by domain experts are proved automatically without any user guidance. To make theorem provers such as Rewrite Rule Laboratory (RRL), a rewrite-based induction prover, more effective, it is important that decision procedures for well-known data structures and representations frequently used in many application domains be integrated efficiently with rewriting and induction. Using the example of the quantifier-free subtheory of Presburger arithmetic, requirements for integration of rewriting and induction with decision procedures are discussed. It is shown how a decision procedure can be used for generating appropriate instantiations of definitions and lemmas, suggesting induction schemes which exploit semantic information, and speculating intermediate lemmas needed to prove theorems.
Sufficient conditions are identified for deciding a priori, the validity of a family of equational conjectures expressed using function symbols that are recursively defined over the terms of a decidable theory. These conjectures can be decided only using induction. The concept of a theory-based function definition is introduced. Conditions on conjectures and interaction among the definitions of functions appearing in them that guarantee the simplification of each induction subgoal to a formula in the decidable theory are identified. It is shown that the cover set method which implements inductive reasoning in RRL can be used as a decision procedure for such conjectures.
TR-CS-2000-27
Neonatal Exposure to Novel Environment Enhanced Memory During
Early Development and Adulthood
Akaysha C. Tang
The classical neonatal handling procedure has a wide range of effects on the development of the stress response system (MEANEY et al 96) and on spatial learning during adulthood and aging (MEANEY et al 88). Despite the existence of a vast literature, the contribution from various behavioral components that constitute handling remains controversial (DENENBERG99). Focusing on a direct stimulation of the stress response system, we briefly exposed neonatal rats to a novel non-home environment during the first three weeks of life (3 min daily). We modified the classical handling procedure to rule out maternal separation and experimenter handling \protect{\em per se} as confounding factors. We found that this early novelty exposure alone was sufficient to induce enhanced learning and memory performance on both aversive and appetitive, and on spatial and non-spatial learning tasks. The enhanced cognitive functions were observed during both early development and adulthood. These results extend the impact of the neonatal stimulation on learning and memory from senescence to early development and from aversive learning to appetitive learning.
TR-CS-2000-26
A Short Sheffer Axiom for Boolean Algebra
Robert Veroff and William McCune
A short Sheffer stroke identity is shown to be a single axiom for Boolean algebra. The axiom has length 15 and 3 variables. The proof shows that it is equivalent to Sheffer's original 3-basis for the theory. Automated deduction techniques were used to find the proof. The shortest single axiom previously known to us has length 105 and 6 variables.
TR-CS-2000-25
Short 2-Bases for Boolean Algebra in Terms of the Sheffer Stroke
Robert Veroff
In this article, we summarize several new results concerning short 2-bases for Boolean algebra in terms of the Sheffer stroke. Two especially short bases are presented, each consisting of a pair of equations having a total of only six applications of the Sheffer stroke operator. Our proofs of correctness of these new results relied heavily on the use of an automated reasoning program.
TR-CS-2000-24
Rectangles and squares recognized by two-dimensional automata
Jarkko Kari and Cristopher Moore
Submitted to Information and Computation.
We consider sets of rectangles and squares recognized by deterministic and non-deterministic two-dimensional finite-state automata. We show that NFAs are strictly more powerful than DFAs, even for pictures over a one-symbol alphabet. In the process, we show that the picture languages recognized by NFAs are not closed under complement, resolving a long-standing open question. We also show that NFAs can only recognize sets of rectangles from the outside that correspond to simple regular languages. Finally, we show that sets of squares recognized by DFAs can be as sparse as any recursively enumerable set.
TR-CS-2000-23
Upper and lower bounds on continuous-time computation
Manuel Lameiras Campagnolo and Cristopher Moore
To appear in Proc. 2nd International Conference on Unconventional Models of Computation.
We consider various extensions and modifications of Shannon's General Purpose Analog Computer, which is a model of computation by differential equations in continuous time. We show that several classical computation classes have natural analog counterparts, including the primitive recursive functions, the elementary functions, the levels of the Grzegorczyk hierarchy, and the arithmetical and analytical hierarchies.
TR-CS-2000-22
A Constructivist Model of Robot Perception and Performance
Joseph A. Lewis and George F. Luger
Paper to appear in Proceedings of the 22nd Annual Meeting of the Cognitive Science Society subsequent to the conference in August 2000.
We present a new architecture for robot control rooted in notions from Brook's subsumption architecture and extended to include an internal representation which matures as it experiences the world. Our architecture is based on the Copycat program of Mitchell and Hofstadter, a model of fluid representation whose details we discuss. We show how our architecture develops a representation of its environment through a continuing interaction with it. The architecture is founded on a dynamical systems interpretation of representation and demonstrates the importance of "embodiment". It reflects a constructivist epistemology, with the robot designed to utilize its environment in its exploration.
TR-CS-2000-21
Fuzzy Configuration of Matching Runtime Implementation Strategies
Angela Sodan and Vicenc Torra
With applications currently growing in complexity and range, increasing numbers of configuration problems are arising in compilers. Already many software systems offer multiple specialized implementation strategies and substrategies, differing in terms of applicability and\or cost, depending on the application context. Configurations then have to be created from the different strategies available in accordance with the application charateristics, the global optimization objective, and potential constraints on the strategies' combinability. In many cases, this results in a combinatorial, i.e., discrete, optimization problem. Proper solutions for automating the configuration while limiting the complexity of the solution search are still being sought We address here the field of parallel\distributed processing and the configuration of runtime implementation strategies, such as for communication or dynamic load balancing. We present a rule-based approach, integrating fuzzy methodologies for the classification of application characteristics and for gradual selection preference in rules. In this way we exploit available knowledge about the correlation of the problem and solution space, and apply soft computing methods to obtain an approximate, rather than perfect, solution approach, thus helping to limit the configuration complexity. Our approach extends standard fuzzy inference by a multistage organization, and --- with proper organization of rules, characteristics and strategies --- performs hierarchical fuzzy inference.
TR-CS-2000-20
An Empirical Comparison Between BPAnalysis and MPBE on the
Campanulaceae Chloroplast Genome Dataset
Mary E. Cosner, Robert K. Jansen, Bernard M.E. Moret, Linda A. Raubeson,
Li-San Wang, Tandy Warnow, and Stacia Wyman
The breakpoint phylogeny is an optimization problem proposed by Blanchette et al. for reconstructing evolutionary trees from gene order data. These same authors also developed and implemented BPAnalysis, a heuristic method (based on solving many instances of the travelling salesman problem) for estimating the breakpoint phylogeny. We present a new heuristic for estimating the breakpoint phylogeny which, although not polynomial-time, is much faster in practice than BPAnalysis. We use this heuristic to conduct a phylogenetic analysis of the flowering plant family Campanulaceae. We also present and discuss the results of experimentation of this real dataset with three methods: our new method, BPAnalysis, and the neighbor-joining method, using breakpoint distances, inversion distances, and inversion plus transposition distances.
TR-CS-2000-19
A New Fast Heuristic for Computing the Breakpoint Phylogeny and
Experimental Phylogenetic Analyses of Real and Synthetic Data
Mary E. Cosner, Robert K. Jansen, Bernard M.E. Moret, Linda A. Raubeson,
Li-San Wang, Tandy Warnow, and Stacia Wyman
The breakpoint phylogeny is an optimization problem proposed by Blanchette et al. for reconstructing evolutionary trees from gene order data. These same authors also developed and implemented BPAnalysis, a heuristic method (based on solving many instances of the travelling salesman problem) for estimating the breakpoint phylogeny. We present a new heuristic for this purpose; although not polynomial-time, our heuristic is much faster in practice than BPAnalysis. We present and discuss the results of experimentation on synthetic datasets and on the flowering plant family Campanulaceae with three methods: our new method, BPAnalysis, and the neighbor-joining method using several distance estimation techniques. Our preliminary results indicate that, on datasets with slow evolutionary rates and large numbers of genes in comparison with the number of taxa (genomes), all methods recover quite accurate reconstructions of the true evolutionary history (although BPAnalysis is too slow to be practical), but that on datasets where the rate of evolution is high relative to the number of genes, the accuracy of all three methods is poor.
TR-CS-2000-18
Point Set Labeling with Specified Positions
Srinivas Doddi, Madhav V. Marathe, and Bernard M.E. Moret
Motivated by applications in cartography and compuuter graphics, we study a version of the map-labeling problem that we call the k-Positions Map-Labeling Problem: given a set of points in the plane and, for each point, a set of up to k allowable positions, place uniform and noninteresecting labels of maximum size at each point in one of the allowable positions. This version combines an aesthetic criterion and a legibility criterion and comes close to actual practice while generalizing the fixed-point and slider models found in the literature. We then extend our approach to arbitrary positions, obtaining an algorithm that is easy to implement and also dramatically improves the best approximation bounds.
We present a general heuristic which runs in time O(n log n + n log R*), where R* is the size of the optimal label, and which guarantees a fixed-ratio approximation for any regular labels. For circular labels, our technique yields a 3.6-approximation, a dramatic improvement in the case of arbitrary placement over the previous bound of 19.35 given by Strijk and Wolff. Our technique combines several geometric and combinatorial properties, which might be of independent interest.
TR-CS-2000-17
Solving Open Questions and Other Challenge Problems Using Proof Sketches
Robert Veroff
In this article, we describe a set of procedures and strategies for searching for proofs in logical systems based on the inference rule condensed detachment. The procedures and strategies rely on the derivation of proof sketches--sequences of formulas that are used as hints to guide the search for sound proofs. In the simplest case, a proof sketch consists of a subproof--key lemmas to prove, for example--and the proof is completed by filling in the missing steps. In the more general case, a proof sketch consists of a sequence of formulas sufficient to find a proof, but it may include formulas that are not provable in the current theory. We find that even in this more general case, proof sketches can provide valuable guidance in finding sound proofs. Proof sketches have been used successfully for numerous problems coming from a variety of problem areas. We have, for example, used proof sketches to find several new two-axiom systems for Boolean algebra using the Sheffer stroke.
TR-CS-2000-16
Finding Shortest Proofs: An Application of Linked Inference Rules
Robert Veroff
In this article we describe a procedure for systematically searching for shortest proofs in logical systems based on the inference rule condensed detachment. The procedure relies on applications of linked UR-resolution and uses demodulation to categorize derivations. Although the procedure is exhaustive in nature--and therefore realistically is applicable only to relatively small problems--it is shown to overcome the obstacles to finding shortest proofs presented by ordinary resolution-style theorem proving.
TR-CS-2000-15
Axiom Systems for Boolean Algebra Using the Sheffer Stroke
Robert Veroff
In this article, we present several new 2-axiom systems for Boolean algebra using the Sheffer stroke. In each case, we indicate how the given system can be used to derive the system presented by Sheffer in 1913. Our search for proofs relied heavily on the use of an automated reasoning program.
TR-CS-2000-14
The Application of Automated Reasoning to Formal Models of
Combinatorial Optimization
Paul Helman and Robert Veroff
To appear in Applied Mathematics and Computation
Many formalisms have been proposed over the years to capture combinatorial optimization algorithms such as dynamic programming, branch and bound, and greedy. In 1989 Helman presented a common formalism that captures dynamic programming and branch and bound type algorithms. The formalism was later extended to include greedy algorithms. In this paper, we describe the application of automated reasoning techniques to the domain of our model, in particular considering some representational issues and demonstrating that proofs about the model can be obtained by an automated reasoning program. The long-term objective of this research is to develop a methodology for using automated reasoning to establish new results within the theory, including the derivation of new lower bounds and the discovery (and verification) of new combinatorial search strategies.
TR-CS-2000-14
Cryptanalysis of the Frankel-MacKenzie-Yung Shared RSA Key Generation
Protocol
Cheryl Beaver, Michael Collins, Peter Gemmell, Anna Johnston, William
D. Neumann, Richard Schroeppel
In recent years, distributed cryptography has gained in interest and potential for application. The two most popular public key signature algorithms, RSA and DSA, now both have shared key generation and shared signature protocols.
We describe a way in which any one malicious shareholder can learn the private key that is generated by the RSA key generation protocol described by [FMY98].
TR-CS-2000-13
Who Wins Domineering on Rectangular Boards?
Michael Lachmann, Cristopher Moore, and Ivan Rapaport
To appear in MSRI Workshop on Combinatorial Games (2000)
Using mostly elementary considerations, we find out who wins the game of Domineering on all rectangular boards of width 2, 3, 5, and 7. We obtain bounds on other boards as well, and prove the existence of polynomial-time strategies for playing on all boards of width 2, 3, 4, 5, 7, 9, and 11. We also comment briefly on toroidal and cylindrical boards.
TR-CS-2000-12
Equation Satisfiability and Program Satisfiability for Finite Monoids
David Mix Barrington, Pierre McKenzie, Cris Moore, Pascal Tesson, and
Denis Therien
To appear in Proc. 25th Int. Symp. on Mathematical Foundations of Computer Science (2000)
We study the computational complexity of solving equations and of determining the satisfiability of programs over a fixed finite monoid. We partially answer an open problem of [GoldmannR1998] by exhibiting quasi-polynomial time algorithms for a subclass of solvable non-nilpotent groups and relate this question to a natural circuit complexity conjecture.
In the special case when M is aperiodic, we show that PROGRAM SATISFIABILITY is in P when the monoid belongs to the variety DA and is NP-complete otherwise. In contrast, we give an example of an aperiodic outside DA for which EQUATION SATISFIABILITY is computable in polynomial time and discuss the relative complexity of the two problems. We also study the closure properties of classes for which these problems belong to P and the extent to which these fail to form algebraic varieties.
TR-CS-2000-11
Applications on a Multithreaded Architecture:
A Case Study with EARTH-MANNA
Angela Sodan
Multithreading offers benefits with respect to the formulation of irregular dynamic programs and their dynamic scheduling, load balancing and interaction. Furthermore, low-cost communication on distributed-memory machines by remote memory access is provided by some systems for efficient communication. EARTH is one of the few systems which combines both, while most other systems either focus on communication or provide multithreading in shared-memory environments. Dynamic irregular applications are often awkward to parallelize on distributed memory when using SPMD style programming via MPI and show different requirements for formulation. In addition, dynamic irregular applications also may show a fairly tight data coupling. Systems like EARTH are beneficial then, because they specifically support large numbers of small data exchanges by providing short startup times and the tolerance of even small latencies (offering very fine-grain threads). However, static regular applications with tight data coupling are supported, too. On the example of EARTH, this paper investigates the benefits of low-cost communication and multithreading, parallelizing three AI applications with medium to high communication intensity. We present experimental results obtained on the MANNA machine.
TR-CS-2000-10
Extending Decision Procedures with Induction Schemes
Deepak Kapur and M. Subramaniam
Presented at 17th International Conf. on Automated Deduction (CADE), Pittsburgh, June 2000.
Families of function definitions and conjectures based in quantifier-free decidable theories are identified for which inductive validity of conjectures can be decided by the {\it cover set} method, a heuristic implemented in a rewrite-based induction theorem prover {\it Rewrite Rule Laboratory} ({\it RRL}) for mechanizing induction. Conditions characterizing definitions and conjectures are syntactic, and can be easily checked, thus making it possible to determine a priori whether a given conjecture can be decided. The concept of a {\it $\TT$-based} function definition is introduced that consists of a finite set of terminating complete rewrite rules of the form $f(s_1, \cdots, s_m) \rew r$, where $s_1, \cdots, s_m$ are interpreted terms from a decidable theory $\TT$, and $r$ is either an interpreted term or has non-nested recursive calls to $f$ with all other function symbols from $\TT$. Two kinds of conjectures are considered. {\it Simple} conjectures are of the form $f(x_1, \cdots x_m) = t$, where $f$ is $\TT$-based, $x_i$'s are distinct variables, and $t$ is interpreted in $\TT$. {\it Complex} conjectures differ from simple conjectures in their left sides which may contain many function symbols whose definitions are $\TT$-based and the nested order in which these function symbols appear in the left sides have the {\it compatibility property} with their definitions.
The main objective is to ensure that for each induction subgoal generated from a conjecture after selecting an induction scheme, the resulting formula can be simplified so that induction hypothesis(es), whenever needed, is applicable, and the result of this application is a formula in $\TT$. Decidable theories considered are the quantifier-free theory of Presburger arithmetic, congruence closure on ground terms (with or without associative-commutative operators), propositional calculus, and the quantifier-free theory of constructors (mostly, free constructors as in the case of finite lists and finite sequences). A byproduct of the approach is that it can predict the structure of intermediate lemmas needed for automatically deciding this subclass of conjectures. Several examples over lists, numbers and of properties involved in establishing the number-theoretic correctness of arithmetic circuits are given.
TR-CS-2000-09
Applying a Dual-Feature Model to Cost Optimization
Angela Sodan
This paper updates the formalization [So97] of a previously presented model of duality [So98] and exploits it for cost estimation, decomposing cost functions into correlated terms of feature pairs and mimimal multiple-feature groups, combined linearly. The model explains the benefits of hybrid approaches and includes hierarchical nesting. The relevance of the model is motivated from the field of parallel systems and demonstrated on some related examples - but it is more general in nature. The model supports compilation and design by enabling lower-cost optimization approaches to be adopted and the decision space to be properly structured.
TR-CS-2000-08
Euclidean Group Invariant Computation of
Stochastic Completion Fields Using
Shiftable-Twistable Functions
John W. Zweck and Lance R. Williams
We describe a method for computing the likelihood that a completion joining two contour fragments passes through any given position and orientation in the image plane. Like computations in primary visual cortex (and unlike all previous models of contour completion), the output of our computation is invariant under rotations and translations of the input pattern. This is achieved by representing input, output, and intermediate states of the computation in a basis of shiftable-twistable functions.
TR-CS-2000-07
Hard Tiling Problems with Simple Tiles
Cristopher Moore and John Michael Robson
It is well-known that the question of whether a given finite region can be tiled with a given set of tiles is NP-complete. We show that the same is true for the right tromino and square tetromino on the square lattice, or for the right tromino alone. In the process, we show that Monotone 1-in-3 Satisfiability is NP-complete for planar cubic graphs. In higher dimensions, we show NP-completeness for the domino and straight tromino for general regions on the cubic lattice, and for simply-connected regions on the four-dimensional hypercubic lattice.
TR-CS-2000-06
Extracting Sparse Resultant Matrices from Dixon Resultant Formulation
Arthur D. Chtcherba and Deepak Kapur
Presented at Seventh Rhine Workshop on Computer Algebra (RWCA'00), Bregenz, Austria.
The multivariate Dixon resultant formulation has been shown by Kapur and Saxena to implicitly exploit the sparse structure of a polynomial system in computing their resultants (or more precisely, projection operators). It is shown how the construction for generating a Dixon resultant matrix from a polynomial system can be modified to generate instead a sparse resultant matrix. An algorithm for constructing a sparse resultant matrix for a polynomial system is given. Unlike the sparse resultant matrix construction algorithms by Canny and Emiris, the proposed algorithm does not explicitly use the support of the polynomial system in its construction. This algorithm is empirically and theoretically compared with the subdivision and incremental methods by Canny and Emiris.
TR-CS-2000-05
Exact solution of site and bond percolation on small-world networks
Cristopher Moore and M. E. J. Newman
We study percolation on small-world networks, which has been proposed as a simple model of the propagation of disease. The occupation probabilities of sites and bonds correspond to the susceptibility of individuals to the disease and the transmissibility of the disease respectively. We give an exact solution of the model for both site and bond percolation, including the position of the percolation transition at which epidemic behavior sets in, the values of the two critical exponents governing this transition, and the mean and variance of the distribution of cluster sizes (disease outbreaks) below the transition.
TR-CS-2000-04
Epidemics and percolation in small-world networks
Cristopher Moore and M.E.J. Newman
We study some simple models of disease transmission on small-world networks, in which either the probability of infection by a disease or the probability of its transmission is varied, or both. The resulting models display epidemic behavior when the infection or transmission probability rises above the threshold for site or bond percolation on the network, and we give exact solutions for the position of this threshold in a variety of cases. We confirm our analytic results by numerical simulation.
TR-CS-2000-03
Conditions for Exact Resultants using the Dixon Formulation
Arthur D. Chtcherba and Deepak Kapur
Presented at International Symposium on Symbolic and Algebraic Computation (ISSAC-2000), St. Andrews, Scotland, August 6-9, 2000
A structural criteria on multivariate polynomial systems is developed such that the generalized Dixon formulation of multivariate resultants defined by Kapur, Saxena and Yang (ISSAC, 1994) computes the resultant exactly, i.e. no extraneous factors are produced in the resultant computations for such polynomial systems. The concept of a Dixon-exact support is introduced; it is proved that the Dixon resultant formulation produces the exact resultant for generic unmixed systems whose support is Dixon-exact. A geometric operation, called direct-sum, on polytopes is defined that preserves the property of supports being Dixon-exact. Generic n-degree systems for which the Dixon formulation is known to compute exact resultants are shown to be a special case of generic unmixed polynomial systems whose support is Dixon-exact. Multigraded systems introduced by Strumfels and Zelvinsky for which they gave a Sylvester type formula for resultants are also shown to be a special case of generic unmixed polynomial systems whose support is Dixon-exact. Using the techniques discussed in a paper by Kapur and Saxena (ISSAC, 1997), a wide class of polynomial systems can be identified for which the Dixon formulation produces exact resultants.
For the bivariate case, an exhaustive analysis of monomials in a polynomial system is given vis a vis their role in producing extraneous factors in a projection operator computed using the generalized Dixon formulation. Such an analysis is likely to give insights for the general case of elimination of arbitrarily many variables.
TR-CS-2000-02
A New Method for Constructing Sparse Resultant Matrices
Arthur D. Chtcherba and Deepak Kapur
Presented at International Symposium on Symbolic and Algebraic Computation (ISSAC-2000), St. Andrews, Scotland, August 6-9, 2000
A new method for constructing sparse resultant matrices for a multivariate polynomial system is presented. Unlike other sparse resultant matrix construction algorithms discussed in the literature, the proposed method does not explicitly use the support of the polynomial system (i.e., the set of exponent vectors corresponding to the power-products appearing in the polynomials). Instead, the construction implicitly exploits the sparse structure of the polynomial system since it is is based on the classical constructions by Cayley and Dixon for setting up resultant matrices. The complexity of the proposed algorithm is given, and compared with the incremental algorithm developed by Emiris and Canny (1995) as well as the lifting and subdivision based algorithm developed by Canny and Emiris (1996) for constructing sparse resultant matrices. The algorithm has been implemented, and also empirically compared with the incremental and subdivision algorithms, on a suite of examples from diverse application domains.
TR-CS-2000-01
Proving Associative-Commutative Termination Using RPO-compatible Orderings
Deepak Kapur and G. Sivakumar
In Proc. Automated Deduction in Classical and Non-Classical Logics, Springer Verlag LNCS 1761 (LNAI) (R. Caferra and G. Salzer, Eds.), Jan. 2000.
Developing path orderings for associative-commutative (AC) rewrite systems has been quite a challenge at least for a decade. Compatibility with the recursive path ordering (RPO) schemes is desirable, and this property helps in orienting the commonly encountered distributivity axiom as desired. For applications in theorem proving and constraint solving, a total ordering on ground terms involving AC operators is often required. It is shown how the main solutions proposed so far with the desired properties can be viewed as arising from a common framework. A general scheme that works for non-ground (general) terms also is proposed. The proposed definition allows flexibility (using different abstractions) in the way the candidates of a term with respect to an associative-commutative function symbol are compared, thus leading to at least two distinct orderings on terms (from the same precendence relation on funciton symbols).
TR-CS-1999-05
"Spiraling Edge: Fast Surface Reconstruction from Partially Organized
Sample Points", IEEE Visualization 1999
Patricia Crossno and Edward Angel
Many applications produce three-dimensional points that must be further processed to generate a surface. Surface reconstruction algorithms that start with a set of unorganized points are extremely time-consuming. Sometimes, however, points are generated such that there is additional information available to the reconstruction algorithm. We present Spiraling Edge, a specialized algorithm for surface reconstruction that is three orders of magnitude faster than algorithms for the general case. In addition to sample point locations, our algorithm starts with normal information and knowledge of each point's neighbors. Our algorithm produces a localized approximation to the surface by creating a star-shaped triangulation between a point and a subset of its nearest neighbors. This surface patch is extended by locally triangulating each of the points along the edge of the patch. As each edge point is triangulated, it is removed from the edge and new edge points along the patch's edge are inserted in its place. The updated edge spirals out over the surface until the edge encounters a surface boundary and stops growing in that direction, or until the edge reduces to a small hole that is filled by the final triangle.
TR-CS-1999-04
"Visual Debugging of Visualization Software: A Case Study for Particle Systems", IEEE Visualization 1999
Patricia Crossno and Edward Angel
Visualization systems are complex dynamic software systems. Debugging such systems is difficult using conventional debuggers because the programmer must try to imagine the three-dimensional geometry based on a list of positions and attributes. In addition, the programmer must be able to mentally animate changes in those positions and attributes to grasp dynamic behaviors within the algorithm. In this paper we shall show that representing geometry, attributes, and relationships graphically permits visual pattern recognition skills to be applied to the debugging problem. The particular application is a particle system used for isosurface extraction from volumetric data. Coloring particles based on individual attributes is especially helpful when these colorings are viewed as animations over successive iterations in the program. Although we describe a particular application, the types of tools that we discuss can be applied to a variety of problems.
TR-CS-1999-03
"OpenGL for the Mac, Part 2", MacTech January 1999
Ed Angel
In Part 1, we developed the basics of OpenGL and argued that the OpenGL API provides an efficient and easy to use interface for developing three-dimensional graphics applications. However, if an API is to be used for developing serious applications, it must be able to exploit modern graphics hardware. In this article, we shall examine a few of the advanced capabilities of OpenGL.
We shall be concerned with three areas. First, we shall examine how to introduce realistic shading by defining material properties for our objects and adding light sources to the scene. Then we shall consider the mixing of geometric and digital techniques afforded by texture mapping. We shall demonstrate these capabilities through the color cube example that we developed in our first article. We will then survey some of the advanced features of OpenGL, concentrating on three areas: writing client-server programs for networked applications, the use of OpenGL buffers, and the ability to tune performance to available hardware.
TR-CS-1999-02
"OpenGL for the Mac, Part 1", MacTech December 1998
Edward Angel
Graphics has always been one of the strongest points for the Macintosh. Although the Mac has been dominant in the graphic arts community, it has not had the same impact on the 3D CAD community or on those who write graphical applications in high-level languages. For these users, the search for a standard Application Programmer' s Interface (API) has been going on for over 20 years. While official standards efforts have failed to produce an API that is actually used by a large part of the community, an API that had its origin in a particular architecture has become the choice for thousands of graphics programmers on systems ranging from SGIs to PCs to Macs.
This article will provide an introduction to OpenGL We shall give the overall structure of this API and then develop a simple application program. We shall then see the ease with which we can convert our simple program to one that incorporates the dynamic and three-dimensional rendering features that we associate with modern graphics. Along the way, we shall see why this particular API should be of interest to the Mac community. A subsequent article will survey the advanced features supported by OpenGL and how OpenGL can exploit the available hardware.
TR-CS-1999-01
"The Deferred Accumulation Buffer", Journal of Graphics Tools, 4(3) pp 35-46, 1999
Patrick S. McCormick, Charles Hansen, and Edward Angel
A well known disadvantage of using the Z-buffer algorithm for medium-quality rendering is the overhead associated with shading, shadowing, and texturing pixels that do not contribute to the final image. This problem may be avoided by deferring shading calculations until the end of the rendering pipeline. In this paper we review two approaches to deferred shading, discuss how to handle transparency, and then extend these ideas to implement a deferred accumulation buffer.
TR-CS-1990-20
The Architecture of a Network Level Intrusion Detection System
Richard Heady, George Luger, Arthur Maccabe, and Mark Servilla
This paper presents the preliminary architecture of a network level intrusion detection system. The proposed system will monitor base level information in network packets (source, destination, packet size and time), learning the 'normal' patterns and announcing anomalies as they occur. The goal of this research is to determine the applicability of current intrusion detection technology to the detection of network level intrusions. In particular, we are investigating the possibility of using this technology to detect and react to worm programs.
News & Events | People | Academics | Research | Jobs | Companies | Visitors | Computer Facilities | Home
