Theory and Algorithms Commons^™

Fast Fourier Transforms Over Prime Fields Of Large Characteristic And Their Implementation On Graphics Processing Units, Davood Mohajerani

Electronic Thesis and Dissertation Repository

Prime field arithmetic plays a central role in computer algebra and supports computation in Galois fields which are essential to coding theory and cryptography algorithms. The prime fields that are used in computer algebra systems, in particular in the implementation of modular methods, are often of small characteristic, that is, based on prime numbers that fit on a machine word. Increasing precision beyond the machine word size can be done via the Chinese Remaindering Theorem or Hensel Lemma. In this thesis, we consider prime fields of large characteristic, typically fitting on n machine words, where n is a power of …

Analysis Of 3d Cone-Beam Ct Image Reconstruction Performance On A Fpga, Devin Held

Electronic Thesis and Dissertation Repository

Efficient and accurate tomographic image reconstruction has been an intensive topic of research due to the increasing everyday usage in areas such as radiology, biology, and materials science. Computed tomography (CT) scans are used to analyze internal structures through capture of x-ray images. Cone-beam CT scans project a cone-shaped x-ray to capture 2D image data from a single focal point, rotating around the object. CT scans are prone to multiple artifacts, including motion blur, streaks, and pixel irregularities, therefore must be run through image reconstruction software to reduce visual artifacts. The most common algorithm used is the Feldkamp, Davis, and …

Spatial Data Mining Analytical Environment For Large Scale Geospatial Data, Zhao Yang

University of New Orleans Theses and Dissertations

Nowadays, many applications are continuously generating large-scale geospatial data. Vehicle GPS tracking data, aerial surveillance drones, LiDAR (Light Detection and Ranging), world-wide spatial networks, and high resolution optical or Synthetic Aperture Radar imagery data all generate a huge amount of geospatial data. However, as data collection increases our ability to process this large-scale geospatial data in a flexible fashion is still limited. We propose a framework for processing and analyzing large-scale geospatial and environmental data using a “Big Data” infrastructure. Existing Big Data solutions do not include a specific mechanism to analyze large-scale geospatial data. In this work, we extend …

Algorithm For Premature Ventricular Contraction Detection From A Subcutaneous Electrocardiogram Signal, Iris Lynn Shelly

Dissertations and Theses

Cardiac arrhythmias occur when the normal pattern of electrical signals in the heart breaks down. A premature ventricular contraction (PVC) is a common type of arrhythmia that occurs when a heartbeat originates from an ectopic focus within the ventricles rather than from the sinus node in the right atrium. This and other arrhythmias are often diagnosed with the help of an electrocardiogram, or ECG, which records the electrical activity of the heart using electrodes placed on the skin. In an ECG signal, a PVC is characterized by both timing and morphological differences from a normal sinus beat.

An implantable cardiac …

Massively Parallel Algorithm For Solving The Eikonal Equation On Multiple Accelerator Platforms, Anup Shrestha

Boise State University Theses and Dissertations

The research presented in this thesis investigates parallel implementations of the Fast Sweeping Method (FSM) for Graphics Processing Unit (GPU)-based computational plat forms and proposes a new parallel algorithm for distributed computing platforms with accelerators. Hardware accelerators such as GPUs and co-processors have emerged as general- purpose processors in today’s high performance computing (HPC) platforms, thereby increasing platforms’ performance capabilities. This trend has allowed greater parallelism and substantial acceleration of scientific simulation software. In order to leverage the power of new HPC platforms, scientific applications must be written in specific lower-level programming languages, which used to be platform specific. Newer …

Network Inference Driven Drug Discovery, Gergely Zahoránszky-Kőhalmi, Tudor I. Oprea Md, Phd, Cristian G. Bologa Phd, Subramani Mani Md, Phd, Oleg Ursu Phd

Biomedical Sciences ETDs

The application of rational drug design principles in the era of network-pharmacology requires the investigation of drug-target and target-target interactions in order to design new drugs. The presented research was aimed at developing novel computational methods that enable the efficient analysis of complex biomedical data and to promote the hypothesis generation in the context of translational research. The three chapters of the Dissertation relate to various segments of drug discovery and development process.

The first chapter introduces the integrated predictive drug discovery platform „SmartGraph”. The novel collaborative-filtering based algorithm „Target Based Recommender (TBR)” was developed in the framework of this …

Applications Of Sampling And Estimation On Networks, Fabricio Murai Ferreira

Doctoral Dissertations

Networks or graphs are fundamental abstractions that allow us to study many important real systems, such as the Web, social networks and scientific collaboration. It is impossible to completely understand these systems and answer fundamental questions related to them without considering the way their components are connected, i.e., their topology. However, topology is not the only relevant aspect of networks. Nodes often have information associated with them, which can be regarded as node attributes or labels. An important problem is then how to characterize a network w.r.t. topology and node label distributions. Another important problem is how to design efficient …

Stochastic Network Design: Models And Scalable Algorithms, Xiaojian Wu

Doctoral Dissertations

Many natural and social phenomena occur in networks. Examples include the spread of information, ideas, and opinions through a social network, the propagation of an infectious disease among people, and the spread of species within an interconnected habitat network. The ability to modify a phenomenon towards some desired outcomes has widely recognized benefits to our society and the economy. The outcome of a phenomenon is largely determined by the topology or properties of its underlying network. A decision maker can take management actions to modify a network and, therefore, change the outcome of the phenomenon. A management action is an …

Development Of Anatomical And Functional Magnetic Resonance Imaging Measures Of Alzheimer Disease, Samaneh Kazemifar

Electronic Thesis and Dissertation Repository

Alzheimer disease is considered to be a progressive neurodegenerative condition, clinically characterized by cognitive dysfunction and memory impairments. Incorporating imaging biomarkers in the early diagnosis and monitoring of disease progression is increasingly important in the evaluation of novel treatments. The purpose of the work in this thesis was to develop and evaluate novel structural and functional biomarkers of disease to improve Alzheimer disease diagnosis and treatment monitoring. Our overarching hypothesis is that magnetic resonance imaging methods that sensitively measure brain structure and functional impairment have the potential to identify people with Alzheimer’s disease prior to the onset of cognitive decline. …

A Framework For Hybrid Intrusion Detection Systems, Robert N. Bronte

Master of Science in Information Technology Theses

Web application security is a definite threat to the world’s information technology infrastructure. The Open Web Application Security Project (OWASP), generally defines web application security violations as unauthorized or unintentional exposure, disclosure, or loss of personal information. These breaches occur without the company’s knowledge and it often takes a while before the web application attack is revealed to the public, specifically because the security violations are fixed. Due to the need to protect their reputation, organizations have begun researching solutions to these problems. The most widely accepted solution is the use of an Intrusion Detection System (IDS). Such systems currently …

Algorithms For Glycan Structure Identification With Tandem Mass Spectrometry, Weiping Sun

Electronic Thesis and Dissertation Repository

Glycosylation is a frequently observed post-translational modification (PTM) of proteins. It has been estimated over half of eukaryotic proteins in nature are glycoproteins. Glycoprotein analysis plays a vital role in drug preparation. Thus, characterization of glycans that are linked to proteins has become necessary in glycoproteomics. Mass spectrometry has become an effective analytical technique for glycoproteomics analysis because of its high throughput and sensitivity. The large amount of spectral data collected in a mass spectrometry experiment makes manual interpretation impossible and requires effective computational approaches for automated analysis. Different algorithmic solutions have been proposed to address the challenges in glycoproteomics …

Lattice Boltzmann Methods For Wind Energy Analysis, Stephen Lloyd Wood

Doctoral Dissertations

An estimate of the United States wind potential conducted in 2011 found that the energy available at an altitude of 80 meters is approximately triple the wind energy available 50 meters above ground. In 2012, 43% of all new electricity generation installed in the U.S. (13.1 GW) came from wind power. The majority of this power, 79%, comes from large utility scale turbines that are being manufactured at unprecedented sizes. Existing wind plants operate with a capacity factor of only approximately 30%. Measurements have shown that the turbulent wake of a turbine persists for many rotor diameters, inducing increased vibration …

An Algorithm For The Machine Calculation Of Minimal Paths, Robert Whitinger

Electronic Theses and Dissertations

Problems involving the minimization of functionals date back to antiquity. The mathematics of the calculus of variations has provided a framework for the analytical solution of a limited class of such problems. This paper describes a numerical approximation technique for obtaining machine solutions to minimal path problems. It is shown that this technique is applicable not only to the common case of finding geodesics on parameterized surfaces in R³, but also to the general case of finding minimal functionals on hypersurfaces in Rⁿ associated with an arbitrary metric.

Efficient Inference, Search And Evaluation For Latent Variable Models Of Text With Applications To Information Retrieval And Machine Translation, Kriste Krstovski

Doctoral Dissertations

Latent variable models of text, such as topic models, have been explored in many areas of natural language processing, information retrieval and machine translation to aid tasks such as exploratory data analysis, automated topic clustering and finding similar documents in mono- and multilingual collections. Many additional applications of these models, however, could be enabled by more efficient techniques for processing large datasets. In this thesis, we introduce novel methods that offer efficient inference, search and evaluation for latent variable models of text. We present efficient, online inference for representing documents in several languages in a common topic space and fast …

Wind Farm Wake Modeling And Analysis Of Wake Impacts In A Wind Farm, Yujia Hao

Doctoral Dissertations

More and more wind turbines have been grouped in the same location during the last decades to take the advantage of profitable wind resources and reduced maintenance cost. However wind turbines located in a wind farm are subject to a wind field that is substantially modified compared to the ambient wind field due to wake effects. The wake results in a reduced power production, increased load variation on the waked turbine, and reduced wake farm efficiency. Therefore the wake has long been an important concern for the wind farm installation, maintenance, and control. Thus a wake simulation tool is required. …

Climbing Up Cloud Nine: Performance Enhancement Techniques For Cloud Computing Environments, Mohamed Abusharkh

Electronic Thesis and Dissertation Repository

With the transformation of cloud computing technologies from an attractive trend to a business reality, the need is more pressing than ever for efficient cloud service management tools and techniques. As cloud technologies continue to mature, the service model, resource allocation methodologies, energy efficiency models and general service management schemes are not yet saturated. The burden of making this all tick perfectly falls on cloud providers. Surely, economy of scale revenues and leveraging existing infrastructure and giant workforce are there as positives, but it is far from straightforward operation from that point. Performance and service delivery will still depend on …

Gene Set Enrichment And Projection: A Computational Tool For Knowledge Discovery In Transcriptomes, Karl Douglas Stamm

Dissertations (1934 -)

Explaining the mechanism behind a genetic disease involves two phases, collecting and analyzing data associated to the disease, then interpreting those data in the context of biological systems. The objective of this dissertation was to develop a method of integrating complementary datasets surrounding any single biological process, with the goal of presenting the response to a signal in terms of a set of downstream biological effects. This dissertation specifically tests the hypothesis that computational projection methods overlaid with domain expertise can direct research towards relevant systems-level signals underlying complex genetic disease. To this end, I developed a software algorithm named …

Packet Filter Approach To Detect Denial Of Service Attacks, Essa Yahya M Muharish

Electronic Theses, Projects, and Dissertations

Denial of service attacks (DoS) are a common threat to many online services. These attacks aim to overcome the availability of an online service with massive traffic from multiple sources. By spoofing legitimate users, an attacker floods a target system with a high quantity of packets or connections to crash its network resources, bandwidth, equipment, or servers. Packet filtering methods are the most known way to prevent these attacks via identifying and blocking the spoofed attack from reaching its target. In this project, the extent of the DoS attacks problem and attempts to prevent it are explored. The attacks categories …

Blending Two Automatic Playlist Generation Algorithms, James Curbow

Honors Theses

We blend two existing automatic playlist generation algorithms. One algorithm is built to smoothly transition between a start song and an end song (Start-End). The other infers song similarity based on adjacent occurrences in expertly authored streams (EAS). First, we seek to establish the effectiveness of the Start-End algorithm using the EAS algorithm to determine song similarity, then we propose two playlist generation algorithms of our own: the Unbiased Random Walk (URW) and the Biased Random Walk (BRW). Like the Start-End algorithm, both the URW algorithm and BRW algorithm transition between a start song and an end song; however, issues …

Ant Colony Optimization For Continuous Spaces, Rachel Findley

Computer Science and Computer Engineering Undergraduate Honors Theses

Ant Colony Optimization (ACO) is an optimization algorithm designed to find semi-optimal solutions to Combinatorial Optimization Problems. The challenge of modifying this algorithm to effectively optimize over a continuous domain is one that has been tackled by several researchers. In this paper, ACO has been modified to use several variations of the algorithm for continuous spaces. An aspect of ACO which is crucial to its success when optimizing over a continuous space is choosing the appropriate object (solution component) out of an infinite set to add to the ant's path. This step is highly important in shaping good solutions. Important …

Sparse Feature Learning For Image Analysis In Segmentation, Classification, And Disease Diagnosis., Ehsan Hosseini-Asl

Electronic Theses and Dissertations

The success of machine learning algorithms generally depends on intermediate data representation, called features that disentangle the hidden factors of variation in data. Moreover, machine learning models are required to be generalized, in order to reduce the specificity or bias toward the training dataset. Unsupervised feature learning is useful in taking advantage of large amount of unlabeled data, which is available to capture these variations. However, learned features are required to capture variational patterns in data space. In this dissertation, unsupervised feature learning with sparsity is investigated for sparse and local feature extraction with application to lung segmentation, interpretable deep …

Optimizing Website Design Through The Application Of An Interactive Genetic Algorithm, Elijah Patton Mensch

Senior Projects Spring 2016

The goal of this project was to determine the efficacy and practicality of “optimizing” the design of a webpage through the application of an interactive genetic algorithm. Software was created to display a “population” of mutable designs, collect user feedback as a measure of fitness, and apply genetic operations in an ongoing evolutionary process. By tracking the prevalence of design parameters over multiple generations and evaluating their associated “fitness” values, it was possible to judge the overall performance of the algorithm when applied to this unique problem space.

Enhancements To Hierarchical Pathfinding Algorithms, Xin Li

Electronic Theses and Dissertations

In this thesis we study the problem of pathfinding in static grid-based maps. We apply the approach of abstraction and refinement. We abstract the grid map into a graph representation, and use the classic A* algorithm to search for a path in the abstract space, and then refine it into low-level path.

We started with a 2013 entry program to the Grid-based Path Planning Competition, and implemented several enhancements to experiment with the tradeoff between memory usage and search speed. Our program returns the refined low-level path incrementally, therefore reduces the first-move lag in large maps. We cache the low-level …

Algorithmic Foundations Of Heuristic Search Using Higher-Order Polygon Inequalities, Newton Henry Campbell Jr.

CCE Theses and Dissertations

The shortest path problem in graphs is both a classic combinatorial optimization problem and a practical problem that admits many applications. Techniques for preprocessing a graph are useful for reducing shortest path query times. This dissertation studies the foundations of a class of algorithms that use preprocessed landmark information and the triangle inequality to guide A* search in graphs. A new heuristic is presented for solving shortest path queries that enables the use of higher order polygon inequalities. We demonstrate this capability by leveraging distance information from two landmarks when visiting a vertex as opposed to the common single landmark …

Aspect Mining Using Multiobjective Genetic Clustering Algorithms, David G. Bethelmy

CCE Theses and Dissertations

In legacy software, non-functional concerns tend to cut across the system and manifest themselves as tangled or scattered code. If these crosscutting concerns could be modularized and the system refactored, then the system would become easier to understand, modify, and maintain. Modularized crosscutting concerns are known as aspects and the process of identifying aspect candidates in legacy software is called aspect mining.

One of the techniques used in aspect mining is clustering and there are many clustering algorithms. Current aspect mining clustering algorithms attempt to form clusters by optimizing one objective function. However, the objective function to be optimized tends …

Mutable Class Design Pattern, Nikolay Malitsky

CCE Theses and Dissertations

The dissertation proposes, presents and analyzes a new design pattern, the Mutable Class pattern, to support the processing of large-scale heterogeneous data models with multiple families of algorithms. Handling data-algorithm associations represents an important topic across a variety of application domains. As a result, it has been addressed by multiple approaches, including the Visitor pattern and the aspect-oriented programming (AOP) paradigm. Existing solutions, however, bring additional constraints and issues. For example, the Visitor pattern freezes the class hierarchies of application models and the AOP-based projects, such as Spring AOP, introduce significant overhead for processing large-scale models with fine-grain objects. The …

Automatically Defined Templates For Improved Prediction Of Non-Stationary, Nonlinear Time Series In Genetic Programming, David Moskowitz

CCE Theses and Dissertations

Soft methods of artificial intelligence are often used in the prediction of non-deterministic time series that cannot be modeled using standard econometric methods. These series, such as occur in finance, often undergo changes to their underlying data generation process resulting in inaccurate approximations or requiring additional human judgment and input in the process, hindering the potential for automated solutions.

Genetic programming (GP) is a class of nature-inspired algorithms that aims to evolve a population of computer programs to solve a target problem. GP has been applied to time series prediction in finance and other domains. However, most GP-based approaches to …

Topics On Register Synthesis Problems, Weihua Liu

Theses and Dissertations--Computer Science

Pseudo-random sequences are ubiquitous in modern electronics and information technology. High speed generators of such sequences play essential roles in various engineering applications, such as stream ciphers, radar systems, multiple access systems, and quasi-Monte-Carlo simulation. Given a short prefix of a sequence, it is undesirable to have an efficient algorithm that can synthesize a generator which can predict the whole sequence. Otherwise, a cryptanalytic attack can be launched against the system based on that given sequence.

Linear feedback shift registers (LFSRs) are the most widely studied pseudorandom sequence generators. The LFSR synthesis problem can be solved by the Berlekamp-Massey algorithm, …

Identifying Parameters For Robust Network Growth Using Attachment Kernels: A Case Study On Directed And Undirected Networks, Ahmed F. Abdelzaher

Theses and Dissertations

Network growing mechanisms are used to construct random networks that have structural behaviors similar to existing networks such as genetic networks, in efforts of understanding the evolution of complex topologies. Popular mechanisms, such as preferential attachment, are capable of preserving network features such as the degree distribution. However, little is known about such randomly grown structures regarding robustness to disturbances (e.g., edge deletions). Moreover, preferential attachment does not target optimizing the network's functionality, such as information flow. Here, we consider a network to be optimal if it's natural functionality is relatively high in addition to possessing some degree of robustness …

Evaluating And Improving The Efficiency Of Software And Algorithms For Sequence Data Analysis, Hugh L. Eaves

Theses and Dissertations

With the ever-growing size of sequence data sets, data processing and analysis are an increasingly large portion of the time and money spent on nucleic acid sequencing projects. Correspondingly, the performance of the software and algorithms used to perform that analysis has a direct effect on the time and expense involved. Although the analytical methods are widely varied, certain types of software and algorithms are applicable to a number of areas. Targeting improvements to these common elements has the potential for wide reaching rewards. This dissertation research consisted of several projects to characterize and improve upon the efficiency of several …