Computer Engineering Commons^™

Regular Expression Synthesis For Blast Two-Hit Filtering, Jordan Bradshaw

Theses and Dissertations

Genomic databases are exhibiting a growth rate that is outpacing Moore's Law, which has made database search algorithms a popular application for use on emerging processor technologies. NCBI BLAST is the standard tool for performing searches against these databases, which operates by transforming each database query into a filter that is subsequently applied to the database. This requires a database scan for every query, fundamentally limiting its performance by I/O bandwidth. In this dissertation we present a functionally-equivalent variation on the NCBI BLAST algorithm that maps more suitably to an FPGA implementation. This variation of the algorithm attempts to reduce …

Efficient Partitioning And Allocation Of Data For Workflow Compositions, Annamaria Victoria Kish

Theses and Dissertations

Our aim is to provide efficient partitioning and allocation of data for web service compositions. Web service compositions are represented as partial order database transactions. We accommodate a variety of transaction types, such as read-only and write-oriented transactions, to support workloads in cloud environments. We introduce an approach that partitions and allocates small units of data, called micropartitions, to multiple database nodes. Each database node stores only the data needed to support a specific workload. Transactions are routed directly to the appropriate data nodes. Our approach guarantees serializability and efficient execution.

In Phase 1, we cluster transactions based on data …

Positioning Commuters And Shoppers Through Sensing And Correlation, Rufeng Meng

Theses and Dissertations

Positioning is a basic and important need in many scenarios of human daily activities. With position information, multifarious services could be vitalized to benefit all kinds of users, from individuals to organizations. Through positioning, people are able to obtain not only geo-location but also time related information. By aggregating position information from individuals, organizations could derive statistical knowledge about group behaviors, such as traffic, business, event, etc.

Although enormous effort has been invested in positioning related academic and industrial work, there are still many holes to be filled. This dissertation proposes solutions to address the need of positioning in people’s …

Nd − Pdpa: N Dimensional Probability Density Profile Analysis, Arjang Fahim

Theses and Dissertations

Proteins are often referred as working molecule of a cell, performing many structural, functional and regulatory processes. Revealing the function of proteins still remains a challenging problem. Advancement in genomics sequence projects produces large protein sequence repository, but due to technical difficulty and cost related to structure determination, the number of identified protein structure is far behind. Novel structures identification are particularly important for a number of reasons: they generate models of similar proteins for comparison; identify evolutionary relationships; further contribute to our understanding of protein function and mechanism; and allow for the fold of other family members to be …

Brand Positioning Map And Analysis Using Web Scraping And Advertisement Analysis, Surya Bhatt

Theses and Dissertations

There’s a significant increase in online consumer forums. When customers set out to buy a product they use these forums to form an opinion. Our research focuses on comparing Brand positioning maps based on consumer reviews. We also analyse the impact of advertisements and expert reviews. Our goal is to show that combining consumer reviews with ads and electronic media will help us analyze the effectiveness of advertising on brand positioning maps. This approach shall also help us in making association graphs for a brand using words of perception/opinion associated with that brand/product. Which may in turn assist companies in …

High-Performance Meta-Genomic Gene Identification, Ibrahim Savran

Theses and Dissertations

Computational Genomics, or Computational Genetics, refers to the use of computational and statistical analysis for understanding the structure and the function of genetic material in organisms. The primary focus of research in computational genomics in the past three decades has been the understanding of genomes and their functional elements by analyzing biological sequence data. The high demand for low-cost sequencing has driven the development of highthroughput sequencing technologies, next-generation sequencing (NGS), that parallelize the sequencing process, producing thousands or millions of sequences concurrently. Moore’s Law is the observation that the number of transistors on integrated circuits doubles approximately every two …

Practical Concurrency Support For Web Service Transactions, Emad Alsuwat

Theses and Dissertations

Traditional database concurrency control methods use locking, timestampordering, and optimistic-ordering to achieve DB consistency. However, these approaches are not suitable for long-running Web Service Compositions (WSCs) due to associated performance degradation. Our hypothesis asserts that, using transactional semantic and ordering information, the execution time of a WSC can be reduced, thus allowing the use of traditional database concurrency control methods while avoiding unacceptable performance degradation. Our solution is based on the following approaches: § We model a WSC as WS-BPEL specification, i.e., a partial order of WS transactions. § We allow some of the WS transactions in the WSC to …

Automatic Loop Tuning And Memory Management For Stencil Computations, Fan Zhang

Theses and Dissertations

The Texas Instruments C66x Digital Signal Processor (DSP) is an embedded processor technology that is targeted at real time signal processing. It is also developed with a high potential to become the new generation of coprocessor technology for high performance embedded computing. Of particular interest is its performance for stencil computations, such as those found in signal processing and computer vision tasks. A stencil is a loop in which the output value is updated at each position of an array by taking a weighted function of its neighbors. Efficiently mapping stencil-based kernels to the C66x device presents two challenges. The …

Automated Scratchpad Mapping And Allocation For Embedded Processors, Yang Gao

Theses and Dissertations

Embedded system-on-chip processors such as the Texas Instruments C66 DSP and the IBM Cell provide the programmer with a software controlled on-chip memory to supplement a traditional but simple two-level cache. By decomposing data sets and their corresponding workload into small subsets that fit within this on-chip memory, the processor can potentially achieve equivalent or better performance, power efficiency, and area efficiency than with its sophisticated cache. However, program controlled on chip memory requires a shift in the responsibility for management and allocation from the hardware to the programmer. Specifically, this requires the explicit mapping of program arrays to specific …

Benefits Of Video Games In Multidisciplinary Scientific Research, Jeremiah Jeffrey Shepherd

Theses and Dissertations

In recent years, computer-based games have been shown to be effective both as a tool for conducting research in a variety of domains and for research on games itself. In this work, we show that implementing games that have a basis in theory and that are combined with the most recent gaming practices result in effective research tools. We demonstrate this via game implementations for three domains. The first implementation is based on new theories in speech pedagogy, and demonstrates the effectiveness of our approach. The second implementation shows that using a game that simulates therapeutic speech practices can aid …

Lost In The Middle Kingdom: Teaching New Languages Using Serious Games And Language Learning Methodologies, Renaldo Justin Doe

Theses and Dissertations

This thesis focuses on the design and development of a serious video game for language learning entitled Lost in the Middle Kingdom. Our game utilizes several language learning methodologies including second language acquisition theory, content-based instruction, and task-based language teaching. This thesis examines previous language learning games and their drawbacks in order to create a more effective experience. Lost in the Middle Kingdom seeks to balance language learning with fun and intuitive gameplay in order to deliver a form of interactive media that is accepted by both the gaming and research communities. Our test data illustrates the strengths and weaknesses …

Growth, Fabrication And Characterization Of Cu2Znsn(SXSe1-X)4 Photovoltaic Absorber And Thin-Film Heterojunction Solar Cells, Sandip Das

Theses and Dissertations

Current thin-film solar cell technologies based on CuIn_xGa1_-xSe₂ (CIGS) and CdTe photo-absorber materials use rare and expensive elements, such as In, Te, Ga, and toxic Cd which severely limit the mass production and deployment of these solar cells. Thus, a major research effort is focused toward the development of new photovoltaic (PV) absorber materials comprising of earth-abundant, low-cost, and environmentally benign constituent elements that can support terawatt (TW)-scale PV generation in the near future and be economically sustainable. Cu-based I₂-II-IV-VI₄ quaternary kesterite compound Cu₂ZnSn(S_xSe_1-x)4 (CZTSS_{e …}

Using Genetic Algorithm To Solve Median Problem And Phylogenetic Inference, Nan Gao

Theses and Dissertations

Genome rearrangement analysis has attracted a lot of attentions in phylogenetic com- putation and comparative genomics. Solving the median problems based on various distance definitions has been a focus as it provides the building blocks for maximum parsimony analysis of phylogeny and ancestral genomes. The Median Problem (MP) has been proved to be NP-hard and although there are several exact or heuristic al- gorithms available, these methods all are difficulty to compute distant three genomes containing high evolution events. Such as current approaches, MGR[1] and GRAPPA [2], are restricted on small collections of genomes and low-resolution gene order data of …

Memory Interface Synthesis For Fpga-Based Computing, Zheming Jin

Theses and Dissertations

This dissertation describes a methodology for the generation of a custom memory interface and associated direct memory access (DMA) controller for FPGA-based kernels that have a regular access pattern. The interface provides explicit support for the following features: (1) memory latency hiding, (2) static access scheduling, and (3) data reuse. The target platform is a multi-FPGA platform, the Convey HC-1, which has an advanced memory system that presents the user logic with three critical design challenges: the memory system itself does not perform caching or prefetching, memory operations are arbitrarily reordered, and the memory performance depends on the access order …

Document Image Analysis Techniques For Handwritten Text Segmentation, Document Image Rectification And Digital Collation, Dhaval Salvi

Theses and Dissertations

Document image analysis comprises all the algorithms and techniques that are utilized to convert an image of a document to a computer readable description. In this work we focus on three such techniques, namely (1) Handwritten text segmentation (2) Document image rectification and (3) Digital Collation.

Offline handwritten text recognition is a very challenging problem. Aside from the large variation of different handwriting styles, neighboring characters within a word are usually connected, and we may need to segment a word into individual characters for accurate character recognition. Many existing methods achieve text segmentation by evaluating the local stroke geometry and …

Research On Approximate Bayesian Computation, Jiting Xu

Theses and Dissertations

This thesis presents the development of a new numerical algorithm for statistical inference problems that require sampling from distributions which are intractable. We propose to develop our sampling algorithm based on a class of Monte Carlo methods, Approximate Bayesian Computation (ABC), which are specifically designed to deal with this type of likelihood-free inference. ABC has become a fundamental tool for the analysis of complex models when the likelihood function is computationally intractable or challenging to mathematically specify. The central theme of our approach is to enhance the current ABC algorithms by exploiting the structure of the mathematical models via derivative …

Vocab4me: A Tool That Provides Vocabulary Recommendations For Publishing Linked Data, Srikar Nadipally

Theses and Dissertations

The web before linked data was a database of html documents. These documents were meant for human consumption and it was hard for machines to make sense of data in html documents. The linked data was introduced with the aim of making the web a global database of data that is machine processable. Linked Data describes a method of publishing structured data so that it can be interlinked and become more useful. Realizing the promise of linked data a lot of people started publishing linked data. But the process of publishing the huge amount of existing data is cumbersome and …

Ghosts Of The Horseshoe: A Mobilization Of A Critical Interactive, Richard Lee Walker

Theses and Dissertations

Critical Interactives (CIs) are designed to harness the voluntary, reality-bending excitement of discovery as afforded by play, but to do so in the context of rules that mobilize procedural rhetoric to instantiate critical awareness. Critical interactives are not just about improving lives through code or education; rather, they establish a methodology for generating more aesthetic and reflective interactive experiences. To grasp more fully the logic underpinning CIs, we need to understand the powerful nature of interactivity and outline how such interactivity involves a notion of ethics, i.e., a way of living, in and through media practice.

Ghosts of the Horseshoe …

Secure And Reliable Wireless Communication Through End-To-End-Based Solution, Hossen Asiful Mustafa

Theses and Dissertations

In the past few decades, network architectures and protocols are often designed to achieve a high throughput and a low latency. Security was rarely considered during the initial design phases. As a result, many network systems are insecure by design. Once they are widely deployed, the inherent vulnerabilities may be difficult to eliminate due to the prohibitive update cost. In this dissertation, we examine such types of vulnerabilities in various networks and design end-to-end-based solutions that allow end systems to address such loopholes.

The end-to-end argument was originally proposed to let end hosts implement application-specific functions rather than letting intermediate …

A Multiagent Approach Towards Solving Complex Problems Of Sociotechnical Systems, Hongying Du

Theses and Dissertations

Complex resource allocation problems arise due to complex human societies and scarce resources to be distributed. Scarce resources could be food, water, and energy. Meanwhile, the size of the problem, the intersection of different areas, and possible global consequences all add to the complexity of the problems, which makes it difficult for humans to solve the problems by themselves.

For all these reasons, humans need technical help to tackle complex problems. Since humans participating in the problems usually own part of the information about the problems, and no one may see the whole picture of the problems, it is natural …

Phylogeny And Ancestral Genome Reconstruction From Gene Order Using Maximum Likelihood And Binary Encoding, Fei Hu

Theses and Dissertations

Over the long history of genome evolution, genes get rearranged under events such as rearrangements, losses, insertions and duplications, which in all change the ordering and content along the genome. Recent progress in genome-scale sequencing renews the challenges in the reconstructions of phylogeny and ancestral genomes with gene-order data. Such problems have been proved so interesting that a large number of algorithms have been developed rigorously over the past few years in attempts to tackle these problems following various principles. However, difficulties and limitations in performance and scalability largely prevent us from analyzing emerging modern whole-genome data, our study presented …

Accuracy, Cost And Performance Trade-Offs For Streaming Set-Wise Floating Point Accumulation On Fpgas, Krishna Kumar Nagar

Theses and Dissertations

The set-wise summation operation is perhaps one of the most fundamental and widely used operations in scientific applications. In these applications, maintaining the accuracy of the summation is also important as floating point operations have inherent errors associated with them. Designing floating-point accumulators presents a unique set of challenges: double-precision addition is usually deeply pipelined and without special micro-architectural or data scheduling techniques, the data hazard that exists. There have been several efforts to design floating point accumulators and accurate summation architecture using different algorithms on FPGAs but these problems have been dealt with separately. In this dissertation, we present …

Improving Robustness And Scalability Of Available Ner Systems, Amber Mckenzie

Theses and Dissertations

The focus of this research is to study and develop techniques to adapt existing NER resources to serve the needs of a broad range of organizations without expert NLP manpower. My methods emphasize usability, robustness and scalability of existing NER systems to ensure maximum functionality to a broad range of organizations. Usability is facilitated by ensuring that the methodologies are compatible with any available open-source NER tagger or data set, thus allowing organizations to choose resources that are easy to deploy and maintain and fit their requirements. One way of making use of available tagged data would be to aggregate …

Computational Analysis And Prediction Of Genome-Wide Protein Targeting Signals And Localization, Jhih-Rong Lin

Theses and Dissertations

Computational prediction of protein subcellular localization can greatly help to elucidate its functions. Despite the existence of dozens of protein localization prediction algorithms, the prediction accuracy and coverage are still low. Several ensemble algorithms have been proposed to improve the prediction performance, which usually include as many as 10 or more individual localization algorithms. However, their performance is still limited by the running complexity and redundancy among individual prediction algorithms. In the first part of the dissertation, we propose a novel method for rational design of minimalist ensemble algorithms for practical genome-wide protein subcellular localization prediction. The algorithm is based …

An Application For Keeping Track Of Food Item Expiration, Rejin Paul James

Theses and Dissertations

Food, honestly, is too precious to waste. Food wastage is a very serious issue prevalent in the world today. American households alone throw out an equivalent of $165 billion worth of food each year. People often forget to consume food they purchased before the expiration date, or sometimes they over-purchase food they can have, then throw them away. Hence, this thesis aims to prevent food wastage with the help of a smart phone application that helps keep track of food item expiration dates and gives you notification alerts when it is about to expire. It implements a barcode scanner for …