Theory and Algorithms Commons^™

Distributed Incomplete Pattern Matching Via A Novelweighted Bloom Filter, Siyuan Liu, Lei Kang, Lei Chen, Lionel Ni

Research Collection School Of Computing and Information Systems

In this paper, we first propose a very interesting and practical problem, pattern matching in a distributed mobile environment. Pattern matching is a well-known problem and extensive research has been conducted for performing effective and efficient search. However, previous proposed approaches assume that data are centrally stored, which is not the case in a mobile environment (e.g., mobile phone networks), where one person’s pattern could be separately stored in a number of different stations, and such a local pattern is incomplete compared with the global pattern. A simple solution to pattern matching over a mobile environment is to collect all …

Utilization Of Probabilistic Models In Short Read Assembly From Second-Generation Sequencing, Matthew W. Segar

Honors Theses

With the advent of cheaper and faster DNA sequencing technologies, assembly methods have greatly changed. Instead of outputting reads that are thousands of base pairs long, new sequencers parallelize the task by producing read lengths between 35 and 400 base pairs. Reconstructing an organism’s genome from these millions of reads is a computationally expensive task. Our algorithm solves this problem by organizing and indexing the reads using n-grams, which are short, fixed-length DNA sequences of length n. These n-grams are used to efficiently locate putative read joins, thereby eliminating the need to perform an exhaustive search over all possible read …

Wi-Fi Sensing Algorithms Utilizing Zigbee Rf Reciever For Use In Emergency Communications Mesh, Alexander Nelson

Computer Science and Computer Engineering Undergraduate Honors Theses

This thesis introduces the idea of a low-power Wi-Fi sensing wake-up controller for an emergency communications mesh network, progressively developing a prototype system which could be used in a live environment. Wireless network protocols are reviewed, as well as a limited view of cluster analysis, in order to introduce relevant concepts crucial to understanding this thesis. Algorithms for system implementation are developed, and pseudocode, designed to be configurable and platform independent, is given for each. Design goals for the system are identified with potential approaches are defined in order to optimize for each. An example hardware configuration is given, in …

Efficient Algorithm To Construct Phi Function In Vector Space Secret Sharing Scheme And Application Of Secret Sharing Scheme In Visual Cryptography, Sunny Potay

Masters Theses & Specialist Projects

Secret Sharing refers to a method through which a secret key K can be shared among a group of authorized participants, such that when they come together later, they can figure out the secret key K to decrypt the encrypted message. Any group which is not authorized cannot determine the secret key K. Some of the important secret schemes are Shamir Threshold Scheme, Monotone Circuit Scheme, and Brickell Vector Space Scheme. Brikell’s vector space secret sharing construction requires the existence of a function from a set of participant P in to vector space Zdp, where p is a …

Incorporating The Nsf/Tcpp Curriculum Recommendations In A Liberal Arts Setting, Akshaye Dhawan

Mathematics, Computer Science & Statistics Faculty Publications

This paper examines the integration of the NSF/TCPP Core Curriculum Recommendations in a liberal arts undergraduate setting. We examine how parallel and distributed computing concepts can be incorporated across the breadth of the undergraduate curriculum. As a model of such an integration, changes are proposed to Data Structures and Design and Analysis of Algorithms. These changes were implemented in Design and Analysis of Algorithms and the results were compared to previous iterations of that course taught by the same instructor. The student feedback received shows that the introduction of these topics made the course more engaging and conveyed an adequate …

Error Estimation Techniques To Refine Overlapping Aerial Image Mosaic Processes Via Detected Parameters, William Glenn Bond

Dissertations

In this paper, I propose to demonstrate a means of error estimation preprocessing in the assembly of overlapping aerial image mosaics. The mosaic program automatically assembles several hundred aerial images from a data set by aligning them, via image registration using a pattern search method, onto a GIS grid.

The method presented first locates the images from a data set that it predicts will not align well via the mosaic process, then it uses a correlation function, optimized by a modified Hooke and Jeeves algorithm, to provide a more optimal transformation function input to the mosaic program. Using this improved …

Framework Developmant For Construction Safety Visialization, Kishor Shrestha

College of Engineering: Graduate Celebration Programs

Throughout the history of the construction industry, many fatalities and injuries have occurred in construction sites. One of the major causes of accidents is unsafe site conditions: basically, this is due to inadequate supervision. To improve upon the traditional supervision approach, this study proposes a 'Framework Development for Construction Safety Visualization' approach. In addition to this, a computer vision Edge Detection Algorithm was developed and tested to convert construction site still images into edges of the objects in the images. The framework development of this study uses computer vision, robot vision, image compression, pattern recognition, internet transmission, network communication, and …

Adaptive Image Diffusion In Wavelet Domain, Kumar Mandava

College of Engineering: Graduate Celebration Programs

• Removing noise without sacrificing important structures
• Nonlinear strategies: Wavelet shrinkage and Nonlinear diffusion filtering based on features
• Clustering based wavelet diffusion

Derivation Of Hill's Equation From Scale Invariance, Andres Ortiz^, Vladik Kreinovich*

COURI Symposium Abstracts, Spring 2012

No abstract provided.

How One Trade Could Change The World: High Frequency Trading And The Flash Crash Of 2010, Sarah Perlman

Honors Projects in Finance

Financial markets are controlled directly by a small population of people, but have direct effects on almost every aspect of the global community. Financial markets are now flooded with computerized algorithms that have drastically changed the face of trading. As with any advances in technology, there are always unforeseen events that create new challenges, and adjustments that need to be made. In our increasingly global and technological world, one wrong click of the mouse in New York could affect the stock markets in London, Tokyo, and Brazil. On May 6th, 2010, such a situation occurred and caused the Dow Jones …

Random Number Generation: Types And Techniques, David F. Dicarlo

Senior Honors Theses

What does it mean to have random numbers? Without understanding where a group of numbers came from, it is impossible to know if they were randomly generated. However, common sense claims that if the process to generate these numbers is truly understood, then the numbers could not be random. Methods that are able to let their internal workings be known without sacrificing random results are what this paper sets out to describe. Beginning with a study of what it really means for something to be random, this paper dives into the topic of random number generators and summarizes the key …

Efficient Reinforcement Learning In Multiple-Agent Systems And Its Application In Cognitive Radio Networks, Jing Zhang

Dissertations

The objective of reinforcement learning in multiple-agent systems is to find an efficient learning method for the agents to behave optimally. Finding Nash equilibrium has become the common learning target for the optimality. However, finding Nash equilibrium is a PPAD (Polynomial Parity Arguments on Directed graphs)-complete problem. The conventional methods can find Nash equilibrium for some special types of Markov games.

This dissertation proposes a new reinforcement learning algorithm to improve the search efficiency and effectiveness for multiple-agent systems. This algorithm is based on the definition of Nash equilibrium and utilizes the greedy and rational features of the agents. When …

Context Aware Routing Management Architecture For Airborne Networks, Joan A. Betances

Theses and Dissertations

This thesis advocates the use of Kalman filters in conjunction with network topology information derived from the Air Tasking Order (ATO) during the planning phase for military missions. This approach is the basis for an algorithm that implements network controls that optimize network performance for Mobile Ad hoc Networks (MANET). The trajectories of relevant nodes (airborne platforms) participating in the MANET can be forecasted by parsing key information contained in the ATO. This information is used to develop optimum network routes that can significantly improve MANET performance. Improved MANET performance in the battlefield enables decision makers to access information from …

Combinatorics Using Computational Methods, Derrick Stolee

Department of Mathematics: Dissertations, Theses, and Student Research

Computational combinatorics involves combining pure mathematics, algorithms, and computational resources to solve problems in pure combinatorics. This thesis provides a theoretical framework for combinatorial search, which is then applied to several problems in combinatorics. Some results in space-bounded computational complexity are also presented.

An Algorithm For Quantum Circuit Optimization, Raymond Garwei Wong

Computer Science and Software Engineering

In the past 20 years, many researchers shifted their focus to developing computers based on quantum mechanical phenomenon as current computers started to plateau in performance. Some problems such as integer factorization have been shown to perform much more efficiently on a quantum computer than on its classical counterpart. However, quantum computers will continue to remain the object of theoretical research unless it can be physically manifested, and quantum circuit optimization hopes to be a useful aid in turning the theory into a reality. My project looks at a possible approach to solving the issue of circuit optimization by incorporating …

Stochastic Analysis Of Horizontal Ip Scanning, Derek Leonard, Zhongmei Yao, Xiaoming Wang, Dmitri Loguinov

Computer Science Faculty Publications

Intrusion Detection Systems (IDS) have become ubiquitous in the defense against virus outbreaks, malicious exploits of OS vulnerabilities, and botnet proliferation. As attackers frequently rely on host scanning for reconnaissance leading to penetration, IDS is often tasked with detecting scans and preventing them. However, it is currently unknown how likely an IDS is to detect a given Internet-wide scan pattern and whether there exist sufficiently fast scan techniques that can remain virtually undetectable at large-scale. To address these questions, we propose a simple analytical model for the window-expiration rules of popular IDS tools (i.e., Snort and Bro) and utilize a …

On Superposition Of Heterogeneous Edge Processes In Dynamic Random Graphs, Zhongmei Yao, Daren B. H. Cline, Dmitri Loguinov

Computer Science Faculty Publications

This paper builds a generic modeling framework for analyzing the edge-creation process in dynamic random graphs in which nodes continuously alternate between active and inactive states, which represent churn behavior of modern distributed systems. We prove that despite heterogeneity of node lifetimes, different initial out-degree, non-Poisson arrival/failure dynamics, and complex spatial and temporal dependency among creation of both initial and replacement edges, a superposition of edge-arrival processes to a live node under uniform selection converges to a Poisson process when system size becomes sufficiently large. Due to the convoluted dependency and non-renewal nature of various point processes, this result significantly …

Extreme Learning Machine Terrain-Based Navigation For Unmanned Aerial Vehicles, Ee May Kan, Meng Hiot Lim, Yew Soon Ong, Ah-Hwee Tan, Swee Ping Yeo

Research Collection School Of Computing and Information Systems

Unmanned aerial vehicles (UAVs) rely on global positioning system (GPS) information to ascertain its position for navigation during mission execution. In the absence of GPS information, the capability of a UAV to carry out its intended mission is hindered. In this paper, we learn alternative means for UAVs to derive real-time positional reference information so as to ensure the continuity of the mission. We present extreme learning machine as a mechanism for learning the stored digital elevation information so as to aid UAVs to navigate through terrain without the need for GPS. The proposed algorithm accommodates the need of the …

Derivation Of A Novel Efficient Supervised Learning Algorithm From Cortical-Subcortical Loops, Ashok Chandrashekar, Richard Granger

Dartmouth Scholarship

Although brain circuits presumably carry out powerful perceptual algorithms, few instances of derived biological methods have been found to compete favorably against algorithms that have been engineered for specific applications. We forward a novel analysis of a subset of functions of cortical-subcortical loops, which constitute more than 80% of the human brain, thus likely underlying a broad range of cognitive functions. We describe a family of operations performed by the derived method, including a non-standard method for supervised classification, which may underlie some forms of cortically dependent associative learning. The novel supervised classifier is compared against widely used algorithms for …

The Identification And Reduction Of Energy Streams Within The Pharmaceutical Sector Using Software Algorithms, Raymond Corbett

Theses

Pharmaceutical companies are under increasing financial pressure to optimise production costs, due to a growing number of products coming off patent, research and development costs increasing exponentially and the difficulty of bringing genuinely innovative products to market. Generic drug manufacturers are not exempt from these pressures; costs must be driven down by all drug manufacturers due to the increasingly competitive healthcare market.

The operating costs of a modern Pharmaceutical Plant run to several Million Euros per annum. Complex process’s involving the consumption of large amounts of energy, and hence costs, are a necessity. Any increase in the efficiency of a …

Reusing Random Walks In Monte Carlo Methods For Linear Systems, Hao Ji, Yaohang Li

Computer Science Faculty Publications

In this paper, we present an approach of reusing random walks in Monte Carlo methods for linear systems. The fundamental idea is, during the Monte Carlo sampling process, the random walks generated to estimate one unknown element can also be effectively reused to estimate the other unknowns in the solution vector. As a result, when the random walks are reused, a single random walk can contribute samples for estimations of multiple unknowns in the solution simultaneously while ensuring that the samples for the same unknown element are statistically independent. Consequently, the total number of random walk transition steps needed for …

Semantic Inference On Heterogeneous E-Marketplace Activities, Jingzhi Guo, Lida Xu, Zhiguo Gong, Chin-Pang Che, Sohail S. Chaudry

Information Technology & Decision Sciences Faculty Publications

An electronic marketplace (e-marketplace) is a common business information space populated with many entities of different system types. Each of them has its own context of how to process activities. This leads to heterogeneous e-marketplace activities, which are difficult to make interoperable and inferred from one entity to another. This study solves this problem by proposing a concept of separation strategy and implementing it through providing a semantic inference engine with a novel inference algorithm. The solution, called the RuleXPM approach, enables one to semantically infer a next e-marketplace activity across multiple contexts/domains. Experiments show that the cross-context/cross-domain semantic inference …

Fusion Of Visual And Thermal Images Using Genetic Algorithms, Sertan Erkanli, Jiang Li, Ender Oguslu, Shangce Gao (Ed.)

Electrical & Computer Engineering Faculty Publications

No abstract provided.

An Improved K-Nearest-Neighbor Algorithm For Text Categorization, Shengyi Jiang, Guansong Pang, Meiling Wu, Limin Kuang

Research Collection School Of Computing and Information Systems

Text categorization is a significant tool to manage and organize the surging text data. Many text categorization algorithms have been explored in previous literatures, such as KNN, Naive Bayes and Support Vector Machine. KNN text categorization is an effective but less efficient classification method. In this paper, we propose an improved KNN algorithm for text categorization, which builds the classification model by combining constrained one pass clustering algorithm and KNN text categorization. Empirical results on three benchmark corpora show that our algorithm can reduce the text similarity computation substantially and outperform the-state-of-the-art KNN, Naive Bayes and Support Vector Machine classifiers. …

Evolved Design Of A Nonlinear Proportional Integral Derivative (Npid) Controller, Shubham Chopra

Dissertations and Theses

This research presents a solution to the problem of tuning a PID controller for a nonlinear system. Many systems in industrial applications use a PID controller to control a plant or the process. Conventional PID controllers work in linear systems but are less effective when the plant or the process is nonlinear because PID controllers cannot adapt the gain parameters as needed. In this research we design a Nonlinear PID (NPID) controller using a fuzzy logic system based on the Mamdani type Fuzzy Inference System to control three different DC motor systems. This fuzzy system is responsible for adapting the …

Real-Time Anomaly Detection In Full Motion Video, Glenn Konowicz,, Jiang Li, Donnie Self (Ed.)

Electrical & Computer Engineering Faculty Publications

Improvement in sensor technology such as charge-coupled devices (CCD) as well as constant incremental improvements in storage space has enabled the recording and storage of video more prevalent and lower cost than ever before. However, the improvements in the ability to capture and store a wide array of video have required additional manpower to translate these raw data sources into useful information. We propose an algorithm for automatically detecting anomalous movement patterns within full motion video thus reducing the amount of human intervention required to make use of these new data sources. The proposed algorithm tracks all of the objects …

Sparse Coding For Hyperspectral Images Using Random Dictionary And Soft Thresholding, Ender Oguslu, Khan Iftekharuddin, Jiang Li, Mark Allen Neifeld (Ed.), Amit Ashok (Ed.)

Electrical & Computer Engineering Faculty Publications

Many techniques have been recently developed for classification of hyperspectral images (HSI) including support vector machines (SVMs), neural networks and graph-based methods. To achieve good performances for the classification, a good feature representation of the HSI is essential. A great deal of feature extraction algorithms have been developed such as principal component analysis (PCA) and independent component analysis (ICA). Sparse coding has recently shown state-of-the-art performances in many applications including image classification. In this paper, we present a feature extraction method for HSI data motivated by a recently developed sparse coding based image representation technique. Sparse coding consists of a …

Mathematical Model Development Of Super-Resolution Image Wiener Restoration, Amr H. Yousef, Jiang Li, Mohammad A. Karim

Electrical & Computer Engineering Faculty Publications

In super-resolution (SR), a set of degraded low-resolution (LR) images are used to reconstruct a higher-resolution image that suffers from acquisition degradations. One way to boost SR images visual quality is to use restoration filters to remove reconstructed images artifacts. We propose an efficient method to optimally allocate the LR pixels on the high-resolution grid and introduce a mathematical derivation of a stochastic Wiener filter. It relies on the continuous-discrete-continuous model and is constrained by the periodic and nonperiodic interrelationships between the different frequency components of the proposed SR system. We analyze an end-to-end model and formulate the Wiener filter …

Fast Stochastic Wiener Filter For Super-Resolution Image Restoration With Information Theoretic Visual Quality Assessment, Amr Hussein Yousef, Jiang Li, Mohammad Karim, Mark Allen Neifeld (Ed.), Amit Ashok (Ed.)

Electrical & Computer Engineering Faculty Publications

Super-resolution (SR) refers to reconstructing a single high resolution (HR) image from a set of subsampled, blurred and noisy low resolution (LR) images. The reconstructed image suffers from degradations such as blur, aliasing, photo-detector noise and registration and fusion error. Wiener filter can be used to remove artifacts and enhance the visual quality of the reconstructed images. In this paper, we introduce a new fast stochastic Wiener filter for SR reconstruction and restoration that can be implemented efficiently in the frequency domain. Our derivation depends on the continuous-discrete-continuous (CDC) model that represents most of the degradations encountered during the image-gathering …

Toward Automatic Subpixel Registration Of Unmanned Airborne Vehicle Images, Amr Hussein Yousef, Jiang Li, Mohammad Karim, Mark Allen Neifeld (Ed.), Amit Ashok (Ed.)

Electrical & Computer Engineering Faculty Publications

Many applications require to register images within subpixel accuracy like computer vision especially super-resolution (SR) where the estimated subpixel shifts are very crucial in the reconstruction and restoration of SR images. In our work we have an optical sensor that is mounted on an unmanned airborne vehicle (UAV) and captures a set of images that contain sufficient overlapped area required to reconstruct a SR image. Due to the wind, The UAV may encounter rotational effects such as yaw, pitch and roll which can distort the acquired as well as processed images with shear, tilt or perspective distortions. In this paper …