Computer Sciences Commons^™

Query-Time Optimization Techniques For Structured Queries In Information Retrieval, Marc-Allen Cartright

Open Access Dissertations

The use of information retrieval (IR) systems is evolving towards larger, more complicated queries. Both the IR industrial and research communities have generated significant evidence indicating that in order to continue improving retrieval effectiveness, increases in retrieval model complexity may be unavoidable. From an operational perspective, this translates into an increasing computational cost to generate the final ranked list in response to a query. Therefore we encounter an increasing tension in the trade-off between retrieval effectiveness (quality of result list) and efficiency (the speed at which the list is generated). This tension creates a strong need for optimization techniques to …

The Security And Privacy Implications Of Energy-Proportional Computing, Shane S. Clark

Open Access Dissertations

The parallel trends of greater energy-efficiency and more aggressive power management are yielding computers that inch closer to energy-proportional computing with every generation. Energy-proportional computing, in which power consumption scales closely with workload, has unintended side effects for security and privacy. Saving energy is an unqualified boon for computer operators, but it is becoming easier to identify computing activities by observing power consumption because an energy-proportional computer reveals more about its workload.

This thesis demonstrates the potential for system-level power analysis---the inference of a computers internal states based on power observation at the "plug." It also examines which hardware components …

Exploring Privacy And Personalization In Information Retrieval Applications, Henry A. Feild

Open Access Dissertations

A growing number of information retrieval applications rely on search behavior aggregated over many users. If aggregated data such as search query reformulations is not handled properly, it can allow users to be identified and their privacy compromised. Besides leveraging aggregate data, it is also common for applications to make use of user-specific behavior in order to provide a personalized experience for users. Unlike aggregate data, privacy is not an issue in individual personalization since users are the only consumers of their own data.

The goal of this work is to explore the effects of personalization and privacy preservation methods …

Semantically Grounded Learning From Unstructured Demonstrations, Scott D. Niekum

Open Access Dissertations

Robots exhibit flexible behavior largely in proportion to their degree of semantic knowledge about the world. Such knowledge is often meticulously hand-coded for a narrow class of tasks, limiting the scope of possible robot competencies. Thus, the primary limiting factor of robot capabilities is often not the physical attributes of the robot, but the limited time and skill of expert programmers. One way to deal with the vast number of situations and environments that robots face outside the laboratory is to provide users with simple methods for programming robots that do not require the skill of an expert.

For this …

Optimizing Linear Queries Under Differential Privacy, Chao Li

Open Access Dissertations

Private data analysis on statistical data has been addressed by many recent literatures. The goal of such analysis is to measure statistical properties of a database without revealing information of individuals who participate in the database. Differential privacy is a rigorous privacy definition that protects individual information using output perturbation: a differentially private algorithm produces statistically indistinguishable outputs no matter whether the database contains a tuple corresponding to an individual or not.

It is straightforward to construct differentially private algorithms for many common tasks and there are published algorithms to support various tasks under differential privacy. However methods to design …

Reconfigurable Technologies For Next Generation Internet And Cluster Computing, Deepak C. Unnikrishnan

Open Access Dissertations

Modern web applications are marked by distinct networking and computing characteristics. As applications evolve, they continue to operate over a large monolithic framework of networking and computing equipment built from general-purpose microprocessors and Application Specific Integrated Circuits (ASICs) that offers few architectural choices. This dissertation presents techniques to diversify the next-generation Internet infrastructure by integrating Field-programmable Gate Arrays (FPGAs), a class of reconfigurable integrated circuits, with general-purpose microprocessor-based techniques. Specifically, our solutions are demonstrated in the context of two applications - network virtualization and distributed cluster computing.

Network virtualization enables the physical network infrastructure to be shared among several …

Transiently Powered Computers, Benjamin Ransford

Open Access Dissertations

Demand for compact, easily deployable, energy-efficient computers has driven the development of general-purpose transiently powered computers (TPCs) that lack both batteries and wired power, operating exclusively on energy harvested from their surroundings.

TPCs' dependence solely on transient, harvested power offers several important design-time benefits. For example, omitting batteries saves board space and weight while obviating the need to make devices physically accessible for maintenance. However, transient power may provide an unpredictable supply of energy that makes operation difficult. A predictable energy supply is a key abstraction underlying most electronic designs. TPCs discard this abstraction in favor of opportunistic computation that …

Elastic Resource Management In Cloud Computing Platforms, Upendra Sharma

Open Access Dissertations

Large scale enterprise applications are known to observe dynamic workload; provisioning correct capacity for these applications remains an important and challenging problem. Predicting high variability fluctuations in workload or the peak workload is difficult; erroneous predictions often lead to under-utilized systems or in some situations cause temporarily outage of an otherwise well provisioned web-site. Consequently, rather than provisioning server capacity to handle infrequent peak workloads, an alternate approach of dynamically provisioning capacity on-the-fly in response to workload fluctuations has become popular.

Cloud platforms are particularly suited for such applications due to their ability to provision capacity when needed and charge …

High-Performance Processing Of Continuous Uncertain Data, Thanh Thi Lac Tran

Open Access Dissertations

Uncertain data has arisen in a growing number of applications such as sensor networks, RFID systems, weather radar networks, and digital sky surveys. The fact that the raw data in these applications is often incomplete, imprecise and even misleading has two implications: (i) the raw data is not suitable for direct querying, (ii) feeding the uncertain data into existing systems produces results of unknown quality.

This thesis presents a system for uncertain data processing that has two key functionalities, (i) capturing and transforming raw noisy data to rich queriable tuples that carry attributes needed for query processing with quantified uncertainty, …

Exploiting Domain Structure In Multiagent Decision-Theoretic Planning And Reasoning, Akshat Kumar

Open Access Dissertations

This thesis focuses on decision-theoretic reasoning and planning problems that arise when a group of collaborative agents are tasked to achieve a goal that requires collective effort. The main contribution of this thesis is the development of effective, scalable and quality-bounded computational approaches for multiagent planning and coordination under uncertainty. This is achieved by a synthesis of techniques from multiple areas of artificial intelligence, machine learning and operations research. Empirically, each algorithmic contribution has been tested rigorously on common benchmark problems and, in many cases, real-world applications from machine learning and operations research literature.

The first part of the thesis …

A Non-Asymptotic Approach To The Analysis Of Communication Networks: From Error Correcting Codes To Network Properties, Ali Eslami

Open Access Dissertations

This dissertation has its focus on two different topics: 1. non-asymptotic analysis of polar codes as a new paradigm in error correcting codes with very promising features, and 2. network properties for wireless networks of practical size. In its first part, we investigate properties of polar codes that can be potentially useful in real-world applications. We start with analyzing the performance of finite-length polar codes over the binary erasure channel (BEC), while assuming belief propagation (BP) as the decoding method. We provide a stopping set analysis for the factor graph of polar codes, where we find the size of the …

Evolving Expert Knowledge Bases: Applications Of Crowdsourcing And Serious Gaming To Advance Knowledge Development For Intelligent Tutoring Systems, Mark Floryan

Open Access Dissertations

This dissertation presents a novel effort to develop ITS technologies that adapt by observing student behavior. In particular, we define an evolving expert knowledge base (EEKB) that structures a domain's information as a set of nodes and the relationships that exist between those nodes. The structure of this model is not the particularly novel aspect of this work, but rather the model's evolving behavior. Past efforts have shown that this model, once created, is useful for providing students with expert feedback as they work within our ITS called Rashi. We present an algorithm that observes groups of students as they …

Reflections On The Fog Of (Cyber) War, Diego Rafael Canabarro, Thiago Borne

National Center for Digital Government

No abstract provided.

Brazil And The Fog Of (Cyber) War, Diego Rafael Canabarro, Thiago Borne

National Center for Digital Government

No abstract provided.

Privacy-Aware Collaboration Among Untrusted Resource Constrained Devices, Andres David Molina-Markham

Open Access Dissertations

Individuals are increasingly encouraged to share private information with service providers. Privacy is relaxed to increase the utility of the data for the provider. This dissertation offers an alternative approach in which raw data stay with individuals and only coarse aggregates are sent to analysts. A challenge is the reliance on constrained devices for data collection. This dissertation demonstrates the practicality of this approach by designing and implementing privacy-aware systems that collect information using low-cost or ultra-low-power microcontrollers. Smart meters can generate certified readings suitable for use in a privacy-preserving system every 10 s using a Texas Instruments MSP430 microcontroller. …

Software Techniques To Reduce The Energy Consumption Of Low-Power Devices At The Limits Of Digital Abstractions, Mastooreh Salajegheh

Open Access Dissertations

My thesis explores the effectiveness of software techniques that bend digital abstractions in order to allow embedded systems to do more with less energy. Recent years have witnessed a proliferation of low-power embedded devices with power ranges of few milliwatts to microwatts. The capabilities and size of the embedded systems continue to improve dramatically; however, improvements in battery density and energy harvesting have failed to mimic a Moore's law. Thus, energy remains a formidable bottleneck for low-power embedded systems.

Instead of trying to create hardware with ideal energy proportionality, my dissertation evaluates how to use unconventional and probabilistic computing that …

Bridging The Gap Between Autonomous Skill Learning And Task-Specific Planning, Shiraj Sen

Open Access Dissertations

Skill acquisition and task specific planning are essential components of any robot system, yet they have long been studied in isolation. This, I contend, is due to the lack of a common representational framework. I present a holistic approach to planning robot behavior, using previously acquired skills to represent control knowledge (and objects) directly, and to use this background knowledge to build plans in the space of control actions.

Actions in this framework are closed-loop controllers constructed from combinations of sensors, effectors, and potential functions. I will show how robots can use reinforcement learning techniques to acquire sensorimotor programs. The …

Accurate And Robust Mechanical Modeling Of Proteins, Naomi Fox

Open Access Dissertations

Through their motion, proteins perform essential functions in the living cell. Although we cannot observe protein motion directly, over 68,000 crystal structures are freely available from the Protein Data Bank. Computational protein rigidity analysis systems leverage this data, building a mechanical model from atoms and pairwise interactions determined from a static 3D structure. The rigid and flexible components of the model are then calculated with a pebble game algorithm, predicting a protein's flexibility with much more computational efficiency than physical simulation. In prior work with rigidity analysis systems, the available modeling options were hard-coded, and evaluation was limited to case …

Multiscale Modeling Of Human Addiction: A Computational Hypothesis For Allostasis And Healing, Yariv Z. Levy

Open Access Dissertations

This dissertation presents a computational multiscale framework for predicting behavioral tendencies related to human addiction. The research encompasses three main contributions. The first contribution presents a formal, heuristic, and exploratory framework to conduct interdisciplinary investigations about the neuropsychological, cognitive, behavioral, and recovery constituents of addiction. The second contribution proposes a computational framework to account for real-life recoveries that are not dependent on pharmaceutical, clinical, and counseling support. This exploration relies upon a combination of current biological beliefs together with unorthodox rehabilitation practices, such as meditation, and proposes a conjecture regarding possible cognitive mechanisms involved in the recovery process. Further elaboration …

Latent Relation Representations For Universal Schemas, Sebastian Riedel, Limin Yao, Andrew Mccallum

Andrew McCallum

No abstract provided.

Relation Extraction With Matrix Factorization And Universal Schemas, Sebastian Riedel, Limin Yao, Andrew Mccallum, Benjamin M. Marlin

Andrew McCallum

Traditional relation extraction predicts relations within some fixed and finite target schema. Machine learning approaches to this task require either manual annotation or, in the case of distant supervision, existing structured sources of the same schema. The need for existing datasets can be avoided by using a universal schema: the union of all involved schemas (surface form predicates as in OpenIE, and relations in the schemas of pre-existing databases). This schema has an almost unlimited set of relations (due to surface forms), and supports integration with existing structured data (through the relation types of existing databases). To populate a database …

Open Scholarship And Peer Review: A Time For Experimentation, David Soergel, Adam Saunders, Andrew Mccallum

Andrew McCallum

Across a wide range of scientific communities, there is growing interest in accelerating and improving the progress of scholarship by making the peer review process more open. Multiple new publication venues and services are arising, especially in the life sciences, but each represents a single point in the multi-dimensional landscape of paper and review access for authors, reviewers and readers. In this paper, we introduce a vocabulary for describing the landscape of choices regarding open access, formal peer review, and public commentary. We argue that the opportunities and pitfalls of open peer review warrant experimentation in these dimensions, and discuss …

Dynamic Knowledge-Base Alignment For Coreference Resolution, Jianping Zheng, Luke Vilnis, Sameer Singh, Jinho D. Choi, Andrew Mccallum

Andrew McCallum

Coreference resolution systems can benefit greatly from inclusion of global con- text, and a number of recent approaches have demonstrated improvements when precomputing an alignment to external knowledge sources. However, since alignment itself is a challenging task and is often noisy, existing systems either align conservatively, resulting in very few links, or combine the attributes of multiple candidates, leading to a conflation of entities. Our approach instead maintains ranked lists of candidate entities that are dynamically merged and reranked during inference. Further, we incorporate a large set of surface string variations for each entity by using anchor texts from the …

Localization And Navigation Of The Cobots Over Long-Term Deployments, Joydeep Biswas, Manuela M. Veloso

Computer Science Department Faculty Publication Series

For the last three years, we have developed and researched multiple collaborative robots, CoBots, which have been autonomously traversing our multi-floor buildings. We pursue the goal of long-term autonomy for indoor service mobile robots as the ability for them to be deployed indefinitely while they perform tasks in an evolving environment. The CoBots include several levels of autonomy, and in this paper we focus on their localization and navigation algorithms. We present the Corrective Gradient Refinement (CGR) algorithm, which refines the proposal distribution of the particle filter used for localization with sensor observations using analytically computed state space derivatives on …