<p>High-throughput structure determination based on solution nuclear magnetic resonance (NMR) spectroscopy plays an important role in structural genomics. Unfortunately, current NMR structure determination is still limited by the lengthy time required to process and analyze the experimental data. A major bottleneck in protein structure determination via NMR is the interpretation of NMR data, including the assignment of chemical shifts and nuclear Overhauser effect (NOE) restraints from NMR spectra. The development of automated and efficient procedures for analyzing NMR data and assigning experimental restraints will thereby enable high-throughput protein structure determination and advance structural proteomics research. In this dissertation, we present the following novel algorithms for automating NMR assignment and protein structure determination. First, we develop a novel high-resolution structure determination algorithm that starts with a global fold calculated from the exact and analytic solutions to the residual dipolar coupling (RDC) equations. Our high-resolution structure determination protocol has been applied to solve the NMR structures of the FF Domain 2 of human transcription elongation factor CA150 (RNA polymerase II C-terminal domain interacting protein), which have been deposited into the Protein Data Bank. Second, we propose an automated side-chain resonance and NOE assignment algorithm that does not require any explicit through-bond experiment to facilitate side-chain resonance assignment, such as HCCH-TOCSY. Third, we present a Bayesian approach to determine protein side-chain rotamer conformations by integrating the likelihood function derived from unassigned NOE data, with prior information (i.e., empirical molecular mechanics energies) about the protein structures. Fourth, we develop a loop backbone structure determination algorithm that exploits the global orientational restraints from sparse RDCs and computes an ensemble of loop conformations that not only close the gap between two end residues but also satisfy the NMR data restraints. Finally, to facilitate NMR structure determination for large proteins, we develop a novel algorithm for predicting the Ha chemical shifts by exploiting the dependencies between chemical shifts of different backbone atoms and integrating the attainable structural information. All the algorithms developed in this dissertation have been tested on experimental NMR data with collaborators in Dr. Pei Zhou's and our labs. The promising results demonstrate that our algorithms can be successfully applied to high-quality protein structure determination. Since our algorithms reduce the time required in NMR assignment, it can accelerate the protein structure determination process.</p> / Dissertation

<p> Designers often use a series of sketches to explain how their design goes through different states or modes to achieve its intended function. Instructors find that learning how to create such explanations is a difficult problem for engineering students, thus giving the impetus to create a design coach which allows students to practice explaining their designs and give feedback on said explanations. Given the complexity and wide scope of engineering design sketches, creating this design coach is a challenging AI problem. When communicating with sketches, humans act multi-modally, using language to clarify what would often be ambiguous or crude drawings. Because these drawings can be ambiguous even to human viewers, and because engineering design encompasses a very large space of possible drawings, traditional sketch recognition techniques, such as trained classifiers, will not work. This dissertation describes a coaching system for engineering design, CogSketch Design Coach. The claims are that (1) descriptions of mechanisms, specified multi-modally using sketches and restricted natural language must be understood via qualitative reasoning, and (2) the validity and clarity of an explanation of a mechanical design can be evaluated using a combination of design teleology and qualitative reasoning. These claims are supported by a set of evaluations of the system on sketched explanations. </p><p> The work results in the following contributions: (1) new extensions to qualitative mechanics, a qualitative model of physics reasoning, for use with sketched input, (2) two new algorithms for identifying spatial mechanical relationships, (3) two new algorithms for generating items for critique of engineering design explanations, and (4) a teleology for describing and critiquing explanations of engineering designs. Through a classroom intervention in a first year engineering design course the work resulted in (5) a corpus of 240 multi-modal explanations and (6) data on a phenomenon we describe as <i> sketching anxiety.</i> These contributions form a set of resources for building new engineering design tools like CogSketch Design Coach and provide insight into future challenges for AI and intelligent coaching systems for classroom settings.</p>

<p> Large software projects contain significant code duplication, mainly due to copying and pasting code. Many techniques have been developed to identify similar code to enable applications such as refactoring, detecting bugs, and detecting illicit code reuse. Because source code is often unavailable, especially for third-party software, finding similar code in binaries becomes particularly important. Unfortunately, binaries present challenges that make it difficult to detect similar code, such as overcoming the lack of high-level information and piercing the veil of compiler optimizations. Due to these difficulties, we are yet to have practical techniques and tools for binary similarity detection. </p><p> This dissertation presents novel research that tackles these challenges toward realizing practical binary similarity detection. The central focus of the work is on automatically extracting syntactic and semantic signatures directly from the binaries. This dissertation presents a family of related algorithms, frameworks and tools for extracting these signatures. The two main tools presented are a binary clone detection tool for syntactic similarity and S<p style="font-variant: small-caps">LEUTH</p>, a tool that detects software license violations using hybrid semantic and syntactic signatures. Although software license violations are common, they often remain undetected due to challenges inherent in binary similarity detection. Examples of software license violations include code a programmer wrote for an ex-employer or open source software licensed under copy-left (such as the Linux kernel reused in a closed source router). Each presented algorithm or tool is practical, automatically finding fine-grained similarity with high precision. </p><p> This dissertation also introduces a general, mixed binary interpretation framework and its accompanying implementation for realizing the aforementioned work.</p>

Immersive virtual environments (IVEs) have many applications in the real world, especially with the development of commodity level displays like the Oculus Rift. For these applications to be successful, IVEs must have enough fidelity so that people can behave similarly in a virtual world to the real world. The research here compares peoples performance in virtual environments in order to that in the real world to evaluate the fidelity of virtual environments. We started from a distance perception task. Distance perception is fundamental in the real world. In this task, we manipulated the presence or absence of a self-avatar. However, our results were unable to find any effect of a self-avatar on distance estimation. Rather, we found that scanning and training significantly improved performance on distance perception. We next studied affordance judgments, where body scale might be important. Our results showed that a self-avatar provides critical information during affordance judgments, and that requiring people to perform an action make peoples performance closer to real world behavior. These results are important because they demonstrate circumstances in which a self-avatar improves the fidelity of a virtual environment.

Resource management of large scale clusters is traditionally done manually. Servers are usually over-provisioned to meet the peak demand of workload. It is widely known that manual provisioning is error-prone and inefficient. These problems can be addressed by the use of autonomic clusters that manage their own resources. In those clusters, server nodes are dynamically allocated based on the system performance goals. In this thesis, we develop heuristic algorithms for the dynamic provisioning of a cluster that executes batch jobs with a shared completion deadline. <br /><br /> External factors that may affect the decision to use servers during a certain time period are modeled as a time-varying cost function. The provisioning goal is ensure that all jobs are completed on time while minimizing the total cost of server usage. Five resource provisioning heuristic algorithms which adapt to changing workload are presented. The merit of these heuristics is evaluated by simulation. In our simulation, the job arrival rate is time-dependent which captures the typical job profile of a batch environment. Our results show that heuristics that take into consideration the cost function perform better than the others.

This thesis presents techniques for accurately computing a number of fundamental operations on approximate polynomials. The general goal is to determine nearby polynomials which have a non-trivial result for the operation. We proceed by first translating each of the polynomial operations to a particular structured matrix system, constructed to represent dependencies in the polynomial coefficients. Perturbing this matrix system to a nearby system of reduced rank yields the nearby polynomials that have a non-trivial result. The translation from polynomial operation to matrix system permits the use of emerging methods for solving sophisticated least squares problems. These methods introduce the required dependencies in the system in a structured way, ensuring a certain minimization is met. This minimization ensures the determined polynomials are close to the original input. We present translations for the following operations on approximate polynomials: <ul> <li>Division</li> <li>Greatest Common Divisor (GCD)</li> <li>Bivariate Factorization</li> <li>Decomposition</li> </ul> The Least Squares problems considered include classical Least Squares (LS), Total Least Squares (TLS) and Structured Total Least Squares (STLS). In particular, we make use of some recent developments in formulation of STLS, to perturb the matrix system, while maintaining the structure of the original matrix. This allows reconstruction of the resulting polynomials without applying any heuristics or iterative refinements, and guarantees a result for the operation with zero residual. Underlying the methods for the LS, TLS and STLS problems are varying uses of the Singular Value Decomposition (SVD). This decomposition is also a vital tool for deter- mining appropriate matrix rank, and we spend some time establishing the accuracy of the SVD. We present an algorithm for <i>relatively accurate</i> SVD recently introduced in [8], then used to solve LS and TLS problems. The result is confidence in the use of LS and TLS for the polynomial operations, to provide a fair contrast with STLS. The SVD is also used to provide the starting point for our STLS algorithm, with the prescribed guaranteed accuracy. Finally, we present a generalized implementation of the Riemannian SVD (RiSVD), which can be applied on any structured matrix to determine the result for STLS. This has the advantage of being applicable to all of our polynomial operations, with the penalty of decreased efficiency. We also include a novel, yet naive, improvement that relies on ran- domization to increase the efficiency, by converting a rectangular system to one that is square. The results for each of the polynomial operations are presented in detail, and the benefits of each of the Least Squares solutions are considered. We also present distance bounds that confirm our solutions are within an acceptable tolerance.

Client applications submit streams of relational queries to database servers. For simple requests, inter-process communication costs account for a significant portion of user-perceived latency. This trend increases with faster processors, larger memory sizes, and improved database execution algorithms, and this trend is not significantly offset by improvements in communication bandwidth. Caching and prefetching are well studied approaches to reducing user-perceived latency. Caching is useful in many applications, but it does not help if future requests rarely match previous requests. Prefetching can help in this situation, but only if we are able to predict future requests. This prediction is complicated in the case of relational queries by the presence of request parameters: a prefetching algorithm must predict not only a query that will be executed in the future, but also the actual parameter values that will be supplied. We have found that, for many applications, the streams of submitted queries contain patterns that can be used to predict future requests. Further, there are correlations between results of earlier requests and actual parameter values used in future requests. We present the Scalpel system, a prototype implementation that detects these patterns of queries and optimizes request streams using context-based predictions of future requests. Scalpel uses its predictions to provide a form of semantic prefetching, which involves combining a predicted series of requests into a single request that can be issued immediately. Scalpel's semantic prefetching reduces not only the latency experienced by the application but also the total cost of query evaluation. We describe how Scalpel learns to predict optimizable request patterns by observing the application's request stream during a training phase. We also describe the types of query pattern rewrites that Scalpel's cost-based optimizer considers. Finally, we present empirical results that show the costs and benefits of Scalpel's optimizations. We have found that even when an application is well suited for its original configuration, it may behave poorly when moving to a new configuration such as a wireless network. The optimizations performed by Scalpel take the current configuration into account, allowing it to select strategies that give good performance in a wider range of configurations.

This thesis applies modern financial option valuation methods to the problem of telecommunication network capacity investment decision timing. In particular, given a cluster of base stations (wireless network with a certain traffic capacity per base station), the objective of this thesis is to determine when it is optimal to increase capacity to each of the base stations of the cluster. Based on several time series taken from the wireless and bandwidth industry, it is argued that capacity usage is the major uncertain component in telecommunications. It is found that price has low volatility when compared to capacity usage. A real options approach is then applied to derive a two dimensional partial integro-differential equation (PIDE) to value investments in telecommunication infrastructure when capacity usage is uncertain and has temporary sudden large variations. This real options PIDE presents several numerical challenges. First, the integral term must be solved accurately and quickly enough such that the general PIDE solution is reasonably accurate. To deal with the integral term, an implicit method is suggested. Proofs of timestepping stability and convergence of a fixed point iteration scheme are presented. The correlation integral is computed using a fast Fourier transform (FFT) method. Techniques are developed to avoid wrap-around effects. This method is tested on option pricing problems where the underlying asset follows a jump diffusion process. Second, the absence of diffusion in one direction of the two dimensional PIDE creates numerical challenges regarding accuracy and timestep selection. A semi-Lagrangian method is presented to alleviate these issues. At each timestep, a set of one dimensional PIDEs is solved and the solution of each PIDE is updated using semi-Lagrangian timestepping. Crank-Nicolson and second order backward differencing timestepping schemes are studied. Monotonicity and stability results are derived. This method is tested on continuously observed Asian options. Finally, a five factor algorithm that captures many of the constraints of the wireless network capacity investment decision timing problem is developed. The upgrade decision for different upgrade decision intervals (e. g. monthly, quarterly, etc. ) is studied, and the effect of a safety level (i. e. the maximum allowed capacity used in practice on a daily basis&mdash;which differs from the theoretical maximum) is investigated.

Wireless infrastructure networks provide high-speed wireless connectivity over a small geographical area. The rapid proliferation of such networks makes their management not only more important but also more difficult. Denser network deployments lead to increased wireless contention and greater opportunities for RF interference, thereby decreasing performance. <br /><br /> In the past, wireless site surveys and simplified wireless propagation models have been used to design and configure wireless systems. However, these techniques have been largely unsuccessful due to the dynamic nature of the wireless medium. More recently, there has been work on dynamically configurable systems that can adapt to changes in the surrounding environment. These systems improve on previous approaches but are still not adequate as their solutions make unrealistic assumptions about the operating environment. Nevertheless, even with these simplified models, the network design and configuration problems are inherently complex and require tradeoffs among competing requirements. <br /><br /> In this thesis, we study a self-management system that can adjust system parameters dynamically. We present a system that does not impose any restrictions on the operating environment, is incrementally deployable, and also backwards compatible. In doing so, we propose, (i) framework for modeling system performance based on utility functions, (ii) novel approach to measuring the utility of a given set of configuration parameters, and (iii) optimization techniques for generating and refining system configurations to maximize utility. Although our utility-function framework is able to capture a variety of optimization metrics, in this study, we focus specifically on maximizing network throughput and minimizing inter-cell interference. Moreover, although many different techniques can be used for optimizing system performance, we focus only on transmit-power control and channel assignment. We evaluate our proposed architecture in simulation and show that our solution is not only feasible, but also provides significant improvements over existing approaches.

<p> A Modular Integrated Syntactic/Semantic XML Data Validation Solution Data integration between disparate systems can be difficult when there are distinct data formats and constraints from a syntactic and semantic perspective. Such differences can be the source of miscommunication that can lead to incorrect data interpretations. What we propose is to leverage XML as means to define not only syntactic constraints, but also semantic constraints. </p><p> XML having been widely adopted across multiple industries, is heavily used as a data protocol. However, commonly used XML parsers have only embedded syntactic validation. In other words, if semantic constraints are needed, these come into play after a parser has validated the XML message. Furthermore, semantic constraints tend to be declared inside the client system, either in the code itself or in some other form of persistent storage such as a database. Our solution to this problem is to integrate the syntactic and semantic validation phases into a single parser. This way, all syntactic and semantic rules can be configured outside the client system. For our purposes, semantic rules are defined as co-constraints. Co-constraints are when the value, presence or absence of an element or attribute is dependent on the value, presence or absence of another element or attribute in the same XML message. Using this same concept, we have also built a parser that, based on co-constraints, can express business constraints that transcend the message definition. Our research provides a reusable modular middleware solution that integrates syntactic and semantic validation. We also demonstrate how the same semantic validating parser can be used to execute business rules triggered by semantic rules. </p><p> Combining semantic and syntactic validation in the same XML parser or interpreter is a powerful solution to quick integration between disparate systems. A key of our proposal is also to have the syntax definition and semantic definitions separate, allowing them to evolve independently. One can imagine how syntax might not change between systems, but the semantic constraints can differ between message consumers.</p>