Computer Sciences Commons^™

Desiderata For A Big Data Language, David Maier

Computer Science Faculty Publications and Presentations

Data management and analytics systems for big data have proliferated, including column stores, array databases, graphanalysis environments and linear-algebra packages. This burgeoning of systems has lead to a surfeit of language and APIs. It is time to consider a new framework that can span these systems and simplify the programming and maintenance of Big Data applications. There are two key goals for such a framework:

Portability: It should be relatively easy to move an application or tool developed on one platform to operate against another. As a corollary, back-end data and analytics services should be swappable in a particular …

Default Rules In Functional Logic Programs, Sergio Antoy, Michael Hanus

Computer Science Faculty Publications and Presentations

In functional logic programs, rules are applicable independently of textual order, i.e., any rule can potentially be used to evaluate an expression. This is similar to logic languages and opposite to functional languages, e.g., Haskell enforces a strict sequential interpretation of rules. However, in some situations it is convenient to express alternatives by means of compact default rules. Although default rules are often used in functional programs, the non-deterministic nature of functional logic programs does not allow to directly transfer this concept from functional to functional logic languages in a meaningful way. In this paper we propose a new concept …

Usage Based Topology For Dcns, Qing Yi, Suresh Singh

Computer Science Faculty Publications and Presentations

Many data center network topologies are designed to provide full bisection bandwidth for tens of thousands of servers in order to achieve high network throughput and server agility. However, the utilization rate of DCNs on average is below 10%, which results in a significant waste of network resources and energy. Many researchers propose consolidating network traffic flows to maximize the set of idle network equipment and switching them to low power mode to save energy. In this paper, we propose using skinnier network topologies to meet performance requirements of realistic loads thus saving not only energy but capital cost as …

Query From Examples: An Iterative, Data-Driven Approach To Query Construction, Hao Li, Chee-Yong Chan, David Maier

Computer Science Faculty Publications and Presentations

In this paper, we propose a new approach, called Query from Examples (QFE), to help non-expert database users construct SQL queries. Our approach, which is designed for users who might be unfamiliar with SQL, only requires that the user is able to determine whether a given output table is the result of his or her intended query on a given input database. To kick-start the construction of a target query Q, the user first provides a pair of inputs: a sample database D and an output table R which is the result of Q on D. As there will be …

A Theory Of Name Resolution, Pierre Néron, Andrew Tolmach, Eelco Visser, Guido Wachsmuth

Computer Science Faculty Publications and Presentations

We describe a language-independent theory for name binding and resolution, suitable for programming languages with complex scoping rules including both lexical scoping and modules. We formulate name resolution as a two-stage problem. First a language-independent scope graph is constructed using language-specific rules from an abstract syntax tree. Then references in the scope graph are resolved to corresponding declarations using a language-independent resolution process. We introduce a resolution calculus as a concise, declarative, and language- independent specification of name resolution. We develop a resolution algorithm that is sound and complete with respect to the calculus. Based on the resolution calculus we …

Demonstrating "Data Near Here": Scientific Data Search, Veronika Margaret Megler, David Maier

Computer Science Faculty Publications and Presentations

Prior work proposed "Data Near Here" (DNH), a data search engine for scientific archives that is modeled on Internet search engines. DNH performs a periodic, asynchronous scan of each dataset in an archive, extracting lightweight features that are combined to form a dataset summary. During a search, DNH assesses the similarity of the search terms to the summary features and returns to the user, at interactive timescales, a ranked list of datasets for further exploration and analysis. We will demonstrate the search capabilities and ancillary metadata-browsing features for an archive of observational oceanographic data. While comparing search terms to complete …

Gaining Policy Insight With A System Dynamics Model Of Pain Medicine Prescribing, Diversion And Abuse, Wayne Wakeland, Alexandra E. Nielsen, Teresa D. Schmidt

Complex Systems Faculty Publications and Presentations

Misuse of pain medicine is a leading cause of accidental deaths in the USA—over 15,000 deaths annually. A system dynamics model was developed and used to study the impact of three types of policy interventions to reduce adverse outcomes. Besides medical usage, the model also includes the diversion of pain medicines and their nonmedical use. Model behavior compared favourably with historical data at multiple points in the system. A prescription drug monitoring program intervention reduced nonmedical overdoses through supply restriction, and an intervention to reduce popularity of nonmedical usage reduced nonmedical overdoses by curtailing demand. A tamper-resistant drug formulation intervention …

Optimizing Data Movement In Hybrid Analytic Systems, Patrick Michael Leyshock

Dissertations and Theses

Hybrid systems for analyzing big data integrate an analytic tool and a dedicated data-management platform, storing data and operating on the data at both components. While hybrid systems have benefits over alternative architectures, in order to be effective, data movement between the two hybrid components must be minimized. Extant hybrid systems either fail to address performance problems stemming from inter-component data movement, or else require the user to explicitly reason about and manage data movement. My work presents the design, implementation, and evaluation of a hybrid analytic system for array-structured data that automatically minimizes data movement between the hybrid components. …

Synthesis Of Irreversible Incompletely Specified Multi-Output Functions To Reversible Eosops Circuits With Pse Gates, Robert Adrian Fiszer

Dissertations and Theses

As quantum computers edge closer to viability, it becomes necessary to create logic synthesis and minimization algorithms that take into account the particular aspects of quantum computers that differentiate them from classical computers. Since quantum computers can be functionally described as reversible computers with superposition and entanglement, both advances in reversible synthesis and increased utilization of superposition and entanglement in quantum algorithms will increase the power of quantum computing.

One necessary component of any practical quantum computer is the computation of irreversible functions. However, very little work has been done on algorithms that synthesize and minimize irreversible functions into a …

The Nax Language: Unifying Functional Programming And Logical Reasoning In A Language Based On Mendler-Style Recursion Schemes And Term-Indexed Types, Ki Yung Ahn

Dissertations and Theses

Two major applications of lambda calculi in computer science are functional programming languages and mechanized reasoning systems (or, proof assistants). According to the Curry--Howard correspondence, it is possible, in principle, to design a unified language based on a typed lambda calculus for both logical reasoning and programming. However, the different requirements of programming languages and reasoning systems make it difficult to design such a unified language that provides both. Programming languages usually extend lambda calculi with programming-friendly features (e.g., recursive datatypes, general recursion) for supporting the flexibility to model various computations, while sacrificing logical consistency. Logical reasoning systems usually extend …

Using Gist Features To Constrain Search In Object Detection, Joanna Browne Solmon

Dissertations and Theses

This thesis investigates the application of GIST features [13] to the problem of object detection in images. Object detection refers to locating instances of a given object category in an image. It is contrasted with object recognition, which simply decides whether an image contains an object, regardless of the object's location in the image.

In much of computer vision literature, object detection uses a "sliding window" approach to finding objects in an image. This requires moving various sizes of windows across an image and running a trained classifier on the visual features of each window. This brute force method can …

Interpretable Machine Learning And Sparse Coding For Computer Vision, Will Landecker

Dissertations and Theses

Machine learning offers many powerful tools for prediction. One of these tools, the binary classifier, is often considered a black box. Although its predictions may be accurate, we might never know why the classifier made a particular prediction. In the first half of this dissertation, I review the state of the art of interpretable methods (methods for explaining why); after noting where the existing methods fall short, I propose a new method for a particular type of black box called additive networks. I offer a proof of trustworthiness for this new method (meaning a proof that my method does not …

Learning Two-Input Linear And Nonlinear Analog Functions With A Simple Chemical System, Peter Banda, Christof Teuscher

Computer Science Faculty Publications and Presentations

The current biochemical information processing systems behave in a predetermined manner because all features are defined during the design phase. To make such unconventional computing systems reusable and programmable for biomedical applications, adaptation, learning, and self-modification baaed on external stimuli would be highly desirable. However, so far, it haa been too challenging to implement these in real or simulated chemistries. In this paper we extend the chemical perceptron, a model previously proposed by the authors, to function as an analog instead of a binary system. The new analog asymmetric signal perceptron learns through feedback and supports MichaelisMenten kinetics. The results …

Advances In Piecewise Smooth Image Reconstruction, Ralf Juengling

Dissertations and Theses

Advances and new insights into algorithms for piecewise smooth image reconstruction are presented. Such algorithms fit a piecewise smooth function to image data without prior knowledge of the number of regions or the location of region boundaries in the best fitting function. This is a difficult model selection problem since the number of parameters of possible solutions varies widely.

The approach followed in this work was proposed by Yvan Leclerc. It uses the Minimum Description Length principle to make the reconstruction problem well-posed: the best fitting function yields the shortest encoding of the image data. In order to derive a …

Towards Constructing Interactive Virtual Worlds, Francis Chang

Dissertations and Theses

Networked virtual reality environments including virtual worlds devoted to entertainment, online socializing and remote collaboration have grown in popularity with the rise of commercially available consumer graphics hardware and the growing ubiquity of the Internet. These virtual worlds are typified by a persistent simulated three-dimensional space that communicates over a computer network, where users interact with the environment and each other through digital avatars. Development of these virtual worlds challenges the limits of the networking infrastructure, 3D streaming graphics techniques, and the distributed computing design of the virtual world systems that manages the simulation. In this dissertation, we explore solutions …

Using Spammers' Computing Resources For Volunteer Computing, Thai Le Quy Bui

Dissertations and Theses

Spammers are continually looking to circumvent counter-measures seeking to slow them down. An immense amount of time and money is currently devoted to hiding spam, but not enough is devoted to effectively preventing it. One approach for preventing spam is to force the spammer's machine to solve a computational problem of varying difficulty before granting access. The idea is that suspicious or problematic requests are given difficult problems to solve while legitimate requests are allowed through with minimal computation. Unfortunately, most systems that employ this model waste the computing resources being used, as they are directed towards solving cryptographic problems …

The Role Of Prototype Learning In Hierarchical Models Of Vision, Michael David Thomure

Dissertations and Theses

I conduct a study of learning in HMAX-like models, which are hierarchical models of visual processing in biological vision systems. Such models compute a new representation for an image based on the similarity of image sub-parts to a number of specific patterns, called prototypes. Despite being a central piece of the overall model, the issue of choosing the best prototypes for a given task is still an open problem. I study this problem, and consider the best way to increase task performance while decreasing the computational costs of the model. This work broadens our understanding of HMAX and related hierarchical …

Damage Spreading In Spatial And Small-World Random Boolean Networks, Qiming Lu, Christof Teuscher

Computer Science Faculty Publications and Presentations

The study of the response of complex dynamical social, biological, or technological networks to external perturbations has numerous applications. Random Boolean networks (RBNs) are commonly used as a simple generic model for certain dynamics of complex systems. Traditionally, RBNs are interconnected randomly and without considering any spatial extension and arrangement of the links and nodes. However, most real-world networks are spatially extended and arranged with regular, power-law, small-world, or other nonrandom connections. Here we explore the RBN network topology between extreme local connections, random small-world, and pure random networks, and study the damage spreading with small perturbations. We find that …

Learning General Features From Images And Audio With Stacked Denoising Autoencoders, Nathaniel H. Nifong

Dissertations and Theses

One of the most impressive qualities of the brain is its neuro-plasticity. The neocortex has roughly the same structure throughout its whole surface, yet it is involved in a variety of different tasks from vision to motor control, and regions which once performed one task can learn to perform another. Machine learning algorithms which aim to be plausible models of the neocortex should also display this plasticity. One such candidate is the stacked denoising autoencoder (SDA). SDA's have shown promising results in the field of machine perception where they have been used to learn abstract features from unlabeled data. In …

A Comparative Study Of Reservoir Computing For Temporal Signal Processing, Alireza Goudarzi, Peter Banda, Matthew R. Lakin, Christof Teuscher, Darko Stefanovic

Computer Science Faculty Publications and Presentations

Reservoir computing (RC) is a novel approach to time series prediction using recurrent neural networks. In RC, an input signal perturbs the intrinsic dynamics of a medium called a reservoir. A readout layer is then trained to reconstruct a target output from the reservoir's state. The multitude of RC architectures and evaluation metrics poses a challenge to both practitioners and theorists who study the task-solving performance and computational power of RC. In addition, in contrast to traditional computation models, the reservoir is a dynamical system in which computation and memory are inseparable, and therefore hard to analyze. Here, we compare …

Guiding Data-Driven Transportation Decisions, Kristin A. Tufte, Basem Elazzabi, Nathan Hall, Morgan Harvey, Kath Knobe, David Maier, Veronika Margaret Megler

Computer Science Faculty Publications and Presentations

Urban transportation professionals are under increasing pressure to perform data-driven decision making and to provide data-driven performance metrics. This pressure comes from sources including the federal government and is driven, in part, by the increased volume and variety of transportation data available. This sudden increase of data is partially a result of improved technology for sensors and mobile devices as well as reduced device and storage costs. However, using this proliferation of data for decisions and performance metrics is proving to be difficult. In this paper, we describe a proposed structure for a system to support data-driven decision making. A …

Dynamic Simulation Of The Effect Of Tamper Resistance On Opioid Misuse Outcomes, Alexandra E. Nielsen, Wayne Wakeland

Complex Systems Faculty Publications and Presentations

The objective of the study was to develop a system dynamics model of the medical use of pharmaceutical opioids, and the associated diversion and nonmedical use of these drugs. The model was used to test the impact of the a tamper resistance intervention in this complex system. The study relied on secondary data obtained from the literature and from other public sources for the period 1995 to 2008. In addition, an expert panel provided recommendations regarding model parameters and model structure. The behavior of the resulting systems-level model compared favorably with reference behavior data. After the base model was tested, …

Using Acl2 To Verify Loop Pipelining In Behavioral Synthesis, Disha Puri, Sandip Ray, Kecheng Hao, Fei Xie

Civil and Environmental Engineering Faculty Publications and Presentations

Behavioral synthesis involves compiling an Electronic System-Level (ESL) design into its RegisterTransfer Level (RTL) implementation. Loop pipelining is one of the most critical and complex transformations employed in behavioral synthesis. Certifying the loop pipelining algorithm is challenging because there is a huge semantic gap between the input sequential design and the output pipelined implementation making it infeasible to verify their equivalence with automated sequential equivalence checking techniques. We discuss our ongoing effort using ACL2 to certify loop pipelining transformation. The completion of the proof is work in progress. However, some of the insights developed so far may already be of …

Search Tool That Utilizes Scientific Metadata Matched Against User-Entered Parameters, Veronika Margaret Megler, David Maier

Computer Science Faculty Publications and Presentations

A method for providing proximate dataset recommendations can begin with the creation of metadata records corresponding to datasets that represent scientific data by a scientific dataset search tool. The metadata records can conform to a standardized structural definition, and may be hierarchical. Values for the data elements of the metadata records can be contained within the datasets. Metadata records with a value that is proximate to a user-entered search parameter can be identified. A proximity score can be calculated for each identified metadata record. The proximity score can express a relevance of the corresponding dataset to the user-entered search parameters. …

Trust-But-Verify: Guaranteeing The Integrity Of User-Generated Content In Online Applications, Akshay Dua

Dissertations and Theses

Online applications that are open to participation lack reliable methods to establish the integrity of user-generated information. Users may unknowingly own compromised devices, or intentionally publish forged information. In these scenarios, applications need some way to determine the "correctness" of autonomously generated information. Towards that end, this thesis presents a "trust-but-verify" approach that enables open online applications to independently verify the information generated by each participant. In addition to enabling independent verification, our framework allows an application to verify less information from more trustworthy users and verify more information from less trustworthy ones. Thus, an application can trade-off performance for …

The Grace Programming Language Draft Specification Version 0.3.53, Andrew P. Black, Kim B. Bruce, James Noble

Computer Science Faculty Publications and Presentations

This is a specification of the Grace Programming Language. This specification is notably incomplete and everything is subject to change. In particular, this version does not address the library, nested static type system, module system, metadata, immutable data and pure methods, and other areas. For discussion and rationale, see http://gracelang.org.

It is designed for use by university students learning programming in CS1 and CS2 classes that are based on object-oriented programming, faculty and teaching assistants developing materials for 1st and 2nd year programming classes, programming researchers needing an object-oriented programming language as a research vehicle, and programming designers in search …

Equivalence Checking For High-Assurance Behavioral Synthesis, Kecheng Hao

Dissertations and Theses

The rapidly increasing complexities of hardware designs are forcing design methodologies and tools to move to the Electronic System Level (ESL), a higher abstraction level with better productivity than the state-of-the-art Register Transfer Level (RTL). Behavioral synthesis, which automatically synthesizes ESL behavioral specifications to RTL implementations, plays a central role in this transition. However, since behavioral synthesis is a complex and error-prone translation process, the lack of designers' confidence in its correctness becomes a major barrier to its wide adoption. Therefore, techniques for establishing equivalence between an ESL specification and its synthesized RTL implementation are critical to bring behavioral synthesis …

Type Classes And Instance Chains: A Relational Approach, John Garrett Morris

Dissertations and Theses

Type classes, first proposed during the design of the Haskell programming language, extend standard type systems to support overloaded functions. Since their introduction, type classes have been used to address a range of problems, from typing ordering and arithmetic operators to describing heterogeneous lists and limited subtyping. However, while type class programming is useful for a variety of practical problems, its wider use is limited by the inexpressiveness and hidden complexity of current mechanisms. We propose two improvements to existing class systems. First, we introduce several novel language features, instance chains and explicit failure, that increase the expressiveness of type …

Guinform: Interactive Fiction For Gui Prototyping, Tesca Fitzgerald

Computer Science Faculty Publications and Presentations

There are many methods of rapidly prototyping a graphical user interface (GUI), the most prominent being paper prototyping and wireframe prototyping. In paper prototyping, the developer creates a physical GUI prototype using simple materials such as paper, pencils, and tabbed cards. Paper prototyping, while easy to implement, leads to unrealistic and awkward user interaction. Wireframe prototyping involves the use of simplified software tools to develop a primitive version of the proposed user interface. This method enables graceful interaction, but requires major implementation e↵ort. I propose a middle ground: a method of rapid, interactive GUI prototyping using Interactive Fiction (IF) tools. …

Based On Repeated Experience, System For Modification Of Expression And Negating Overload From Media And Optimizing Referential Efficiency, Peter R. Badovinatz, Veronika M. Megler

Computer Science Faculty Publications and Presentations

Content items are revealed to a user based on whether they have been previously reviewed by the user. A number of content items are thus received over time. The content items may be discrete content items, or may be portions of a content stream, and may be received over different media. For each content item, it is determined whether the content item was previously reviewed by a user. Where the content item was not previously reviewed, the item is revealed to the user, such as by being displayed or announced to the user. Where the content item was previously reviewed, …