Given an unstructured collection of captioned images of cluttered scenes featuring a variety of objects, our goal is to simultaneously learn the names and appearances of the objects. Only a small fraction of local features within any given image are associated with a particular caption word, and captions may contain irrelevant words not associated with any image object. We propose a novel algorithm that uses the repetition of feature neighborhoods across training images and a measure of correspondence with caption words to learn meaningful feature configurations (representing named objects). We also introduce a graph-based appearance model that captures some of the structure of an object by encoding the spatial relationships among the local visual features. In an iterative procedure we use language (the words) to drive a perceptual grouping process that assembles an appearance model for a named object. We also exploit co-occurrences among appearance models to learn hierarchical appearance models. Results of applying our method to three data sets in a variety of conditions demonstrate that from complex, cluttered, real-world scenes with noisy captions, we can learn both the names and appearances of objects, resulting in a set of models invariant to translation, scale, orientation, occlusion, and minor changes in viewpoint or articulation. These named models, in turn, are used to automatically annotate new, uncaptioned images, thereby facilitating keyword-based image retrieval.

Many large business processes are inherently distributed, spanning multiple organizations, administrative domains, and geographic locations. To support such applications, this thesis develops a flexible and distributed platform to develop, execute, and monitor business processes. The solutions utilize a distributed content-based publish/subscribe overlay that is extended with support for mobile clients and client interest churn. Over this layer, a distributed execution engine uses events to coordinate the execution of the process, and dynamically redeploys activities in the process in order to minimize a user-specified cost function and preserve service level agreements (SLAs). Finally, a management layer allows users to find and automatically compose services available across a distributed set of service registries, and monitor processes for SLA violations. Evaluations show that the distributed execution engine can scale better than alternate architectures, exhibiting over 60% improvements in execution time in one experiment. As well the system can dynamically redeploy processes to reflect changing workload conditions and SLAs, saving up to 90% of the process messaging overhead of a static deployment.

This thesis examines the issue of software evolution from a Requirements Engineering perspective. This perspective is founded on the premise that software evolution is best managed with reference to the requirements of a given software system. In particular, I follow the Requirements Problem approach to software development: the problem of developing software can be characterized as finding a specification that satisfies user requirements, subject to domain constraints. To enable this, I propose a shift from treating requirements as artifacts to treating requirements as design knowledge, embedded in knowledge bases. Most requirements today, when they exist in tangible form at all, are static objects. Such artifacts are quickly out of date and difficult to update. Instead, I propose that requirements be maintained in a knowledge base which supports knowledge-level operations for asserting new knowledge and updating existing knowledge. Consistency checks and entailment of new specifications is done automatically by answering simple queries. Maintaining a requirements knowledge base in parallel with running code means that changes precipitated by evolution are always addressed relative to the ultimate purpose of the system. This thesis begins with empirical studies which establish the nature of the requirements evolution problem. I use an extended case study of payment cards to motivate the following discussion. I begin at an abstract level, by introducing a requirements engineering knowledge base (REKB) using a functional specification. Since it is functional, the specifics of the implementation are left open. I then describe one implementation, using a reason-maintenance system, and show how this implementation can a) solve static requirements problems; b) help stakeholders bring requirements and implementation following a change in the requirements problem; c) propose paraconsistent reasoning to support inconsistency tolerance in the REKB. The end result of my work on the REKB is a tool and approach which can guide software developers and software maintainers in design and decision-making in the context of software evolution.

Guidelines focusing on web interface design allow for the dissemination of complex and multidisciplinary research to communities of practice. Motivated by the desire to better understand how research evidence canbe shared with the web design community, this dissertation investigates the role guidelines play in the design process, the attitudes designers hold regarding guidelines, and whether evidence based guidelines can be consistently interpreted by designers. Guidelines are a potential means to address the knowledge gap between research and practice, yet we do not have a clear understanding of the relationship between research evidence, guideline sets and web design practitioners. In order to better understand how design guidelines are used by designers in the practice of web interface design, four sequential studies were designed; the application of a guideline subset to a design project by 16 students, the assessment of ten health information websites by eight designers using a guideline subset, a web based survey of 116 designers, and interviews with 20 designers. The studies reveal that guideline use is dependent on the perceived trustworthiness of the guideline, its source and the alignment between guideline advice and designer experience. The first two studies found that guidelines are inconsistently interpreted. One third of the guidelines used in the second study were interpreted differently by participants, an inconsistency which represents a critical problem in guideline use. Findings showed no difference in the characteristics of guidelines which were consistently interpreted and those for which interpretation was the most inconsistent. Further, research evidence was not a factor in guideline use, less than half the designers are aware of evidence-based guideline sets, and guidelines are predominantly used as memory aids. Ultimately alternatives to guidelines, such as checklists or pattern libraries, may yield the best results in our efforts to share research knowledge with communities of practice.

The PR-tree data structure is introduced to characterize the sets of path-tree models of path graphs. We further characterize the sets of directed path-tree models of directed path graphs with a slightly restricted form of the PR-tree called the Strong PR-tree. Additionally, via PR-trees and Strong PR-trees, we characterize path graphs and directed path graphs by their Split Decompositions. Two distinct approaches (Split Decomposition and Reduction) are presented to construct a PR-tree that captures the path-tree models of a given graph G = (V, E) with n = |V| and m = |E|. An implementation of the split decomposition approach is presented which runs in O(nm) time. Similarly, an implementation of the reduction approach is presented which runs in O(A(n + m)nm) time (where A(s) is the inverse of Ackermann’s function arising from Union-Find [40]). Also, from a PR-tree, an algorithm to construct a corresponding Strong PR-tree is given which runs in O(n + m) time. The sizes of the PR-trees and Strong PR-trees produced by these approaches are O(n + m) with respect to the given graph. Furthermore, we demonstrate that an implicit form of the PR-tree and Strong PR-tree can be represented in O(n) space.

Molecular docking is a computational tool commonly applied in drug discovery projects and fundamental biological studies of protein-ligand interactions. Traditionally, molecular docking is used to address one of three following questions: (i) given a ligand molecule and a protein receptor, predict the binding mode (pose) of the ligand within the context of a receptor, (ii) screen a collection of small-molecules against a receptor and rank ligands by their likelihood of being active, and (iii) given a ligand molecule and a target receptor, predict the binding affinity of the two. Here, we focus on the first two questions, namely ranking and pose prediction. Currently, state-of-the-art docking algorithms predict poses within 2A of the native pose in a rate lower than ∼60% and in many cases, below 40%. In ranking, their ability to identify active ligands is inconsistent and generally suffers from high false-positive rate. In this thesis we present novel algorithms to enhance the ability of molecular docking to address these two questions. These algorithms do not substitute traditional docking but rather being applied on top of them to provide synergistic effect. Our algorithms improve pose predictions by 0.5-1.0A and ranking order for 23% of the targets in gold-standard benchmarks. As importantly, the algorithms improve the consistence of the posing and ranking predictions over diverse sets of targets and screening libraries. In addition to the posing and ranking, we present the pharmacophore concept. A pharmacophore is an ensemble of physiochemical descriptors associated with a biological target that elucidates common interaction patterns of ligands with that target. We introduce a novel pharmacophore inference algorithm and demonstrate its utilization in molecular docking. This thesis is outlined as follow. First we introduce the molecular docking approach for pose prediction and ranking. Second, we discuss the pharmacophore concept and present algorithms for pharmacophore inference. Third, we demonstrate the utilization of pharmacophores for pose prediction by re-scoring candidate poses generated by docking algorithms. Finally, we present algorithms to improve ranking by reducing bias in scoring functions employed by docking algorithms.

Although integrity constraints are the primary means for enforcing data integrity, there are cases in which they are not defined or are not strictly enforced. This leads to inconsistencies in the data, causing poor data quality. In this thesis, we leverage the power of constraints to improve data quality. To ensure that the data conforms to the intended application domain semantics, we develop two algorithms focusing on constraint discovery. The first algorithm discovers a class of conditional constraints, which hold over a subset of the relation, under specific conditional values. The second algorithm discovers attribute domain constraints, which bind specific values to the attributes of a relation for a given domain. These two types of constraints have been shown to be useful for data cleaning. In practice, weak enforcement of constraints often occurs for performance reasons. This leads to inconsistencies between the data and the set of defined constraints. To resolve this inconsistency, we must determine whether it is the constraints or the data that is incorrect, and then make the necessary corrections. We develop a repair model that considers repairs to the data and repairs to the constraints on an equal footing. We present repair algorithms that find the necessary repairs to bring the data and the constraints back to a consistent state. Finally, we study the efficiency and quality of our techniques. We show that our constraint discovery algorithms find meaningful constraints with good precision and recall. We also show that our repair algorithms resolve many inconsistencies with high quality repairs, and propose repairs that previous algorithms did not consider.

Dynamic provisioning of server boxes to applications entails an inherent performance-power trade-off for the service provider, a trade-off that has not been studied in detail. The optimal number of replicas to be dynamically provisioned to an application is ultimately the configuration that results in the highest revenue. The service provider should thus dynamically provision resources for an application only as long as the resulting reward from hosting more clients exceeds its operational costs for power and cooling. We introduce a novel cost-aware dynamic provisioning approach for the database tier of a dynamic content site. Our approach employs Support Vector Machine regression for learning a dynamically adaptive system model. We leverage this lightweight on-line learning approach for two cost-aware dynamic provisioning techniques. The first is a temperature-aware scheme which avoids temperature hot-spots within the set of provisioned machines, and hence reduces cooling costs. The second is a more general cost-aware provisioning technique using a utility function expressing monetary costs for both performance and power.

Wearable computing systems have been researched and developed for several decades. With the advent of the head-mounted display, augmented and mediated reality systems became an important example of wearable computing. However, due to certain factors such as computational constraints, cost, obtrusiveness, practicality, and social acceptance, mediated reality systems have been leveraged in only very specific application domains and have yet to see mainstream adoption. This dissertation describes the research and development of a real-time mediated reality platform developed for modern mobile devices to provide a more reasonable transition in overcoming the mainstream adoption barrier of mediated reality systems. In particular, an outdoor navigational application that provides contextually-relevant information about a user’s surroundings is developed using the platform as a proof-of-concept for evaluation. In addition, the server infrastructure required to support the application is discussed, as well as the evaluation of a hybrid orientation tracking approach using sensors and computer vision.

Wearable computing systems have been researched and developed for several decades. With the advent of the head-mounted display, augmented and mediated reality systems became an important example of wearable computing. However, due to certain factors such as computational constraints, cost, obtrusiveness, practicality, and social acceptance, mediated reality systems have been leveraged in only very specific application domains and have yet to see mainstream adoption. This dissertation describes the research and development of a real-time mediated reality platform developed for modern mobile devices to provide a more reasonable transition in overcoming the mainstream adoption barrier of mediated reality systems. In particular, an outdoor navigational application that provides contextually-relevant information about a user’s surroundings is developed using the platform as a proof-of-concept for evaluation. In addition, the server infrastructure required to support the application is discussed, as well as the evaluation of a hybrid orientation tracking approach using sensors and computer vision.