Theory and Algorithms Commons^™

A Comparison Of Evidence Fusion Rules For Situation Recognition In Sensor-Based Environments, Susan Mckeever, Juan Ye

Conference papers

Dempster-Shafer (DS) theory, and its associated Dempster rule of combination, has been widely used to determine belief based on uncertain evi-dence sources. Variations to the original Dempster rule of combination have appeared in the literature to support particular scenarios where unreliable results may result from the use of original DS theory. While theoretical explanations of the rule variations are explained, there is a lack of empirical comparisons of the DS theory and its variations against real data sets. In this work, we examine several variations to DS theory. Using two real-world sensor data sets, we com-pare the performance of DS …

An Analysis Of Peer-To-Peer Distributed Hash Algorithms In Improving Fault Tolerance In The Hadoop Running Environment, Benjamin R. Knaus

Honors Theses

Cloud computing is a “new frontier” in the world of computing. One of the cloud architectures widely used is the Hadoop running environment. Hadoop consists of many parts—including MapReduce, TaskTrackers, and JobTrackers. Right now, there is no fault-tolerance for JobTrackers in Hadoop. This paper analyzes four different distributed hash algorithms (Pastry, Tapestry, CAN, and Chord) that could be implemented inside Hadoop to improve JobTracker fault-tolerance. We recommend Chord as the best suited for integration and improvement of Hadoop.

An Efficient Partial Shape Matching Algorithm For 3d Tooth Recognition, Zhiyuan Zhang, Xin Zhong, Sim Heng Ong, Kelvin W. C. Foong

Research Collection School Of Computing and Information Systems

As a new biometric strategy, tooth recognition has drawn much attention in recent years. However, most existing work focus mainly on 2D dental radiographs which are less informative and vulnerable to noise and pose variance. Although there are already several attempts on 3D tooth recognition, the results are still inaccurate and performance is inefficient. Moreover, existing methods cannot recognize precisely when the post-mortem data contains incomplete teeth. In this work, we propose an efficient and accurate partial shape matching algorithm to recognize 3D teeth for human identification. Given the ante-mortem and post-mortem teeth models which were taken from patients using …

Application Of Ntru Cryptographic Algorithm For Securing Scada Communication, Amritha Puliadi Premnath

UNLV Theses, Dissertations, Professional Papers, and Capstones

Supervisory Control and Data Acquisition (SCADA) system is a control system which is widely used in Critical Infrastructure System to monitor and control industrial processes autonomously. Most of the SCADA communication protocols are vulnerable to various types of cyber-related attacks. The currently used security standards for SCADA communication specify the use of asymmetric cryptographic algorithms like RSA or ECC for securing SCADA communications. There are certain performance issues with cryptographic solutions of these specifications when applied to SCADA system with real-time constraints and hardware limitations. To overcome this issue, in this thesis we propose the use of a faster and …

In Perfect Xen, A Performance Study Of The Emerging Xen Scheduler, Ryan Hnarakis

Master's Theses

Fifty percent of Fortune 500 companies trust Xen, an open-source bare-metal hypervisor, to virtualize their websites and mission critical services in the cloud. Providing superior fault tolerance, scalability, and migration, virtualization allows these companies to run several isolated operating systems simultaneously on the same physical server. These isolated operating systems, called virtual machines, require a virtual traffic guard to cooperate with one another. This guard known as the Credit2 scheduler along with the newest Xen hypervisor was recently developed to supersede the older schedulers. Since wasted CPU cycles can be costly, the Credit2 prototype must undergo significant performance validation before …

Object Detection Using Contrast Enhancement And Dynamic Noise Reduction, Justin Lee Baker

UNLV Theses, Dissertations, Professional Papers, and Capstones

Edge detection is one of the most important steps a computer must perform to gain understanding of an object in a digital image either from disk or from video feed. Edge detection allows for the computer to describe the shape of the objects in an image and create a pixel boundary defining what is considered part of an object, and what is not. Cannys edge detection algorithm is one of the most robust and accurate of these edge detection algorithms. However, as with many algorithms in image processing, there are many cases where the algorithm does not perform as well …

Algorithms For Grid Graphs In The Mapreduce Model, Taylor P. Spangler

School of Computing: Dissertations, Theses, and Student Research

The MapReduce programming paradigm has seen widespread use in analyzing large data sets. Often these large data sets can be formulated as graphs. Many algorithms, such as filtering based algorithms, are designed to work efficiently for dense graphs - graphs with substantially more number of edges than the number of vertices. These algorithms are not optimized for sparse graphs - graphs where the number of edges is of the same order as the number of vertices. However, sparse graphs are also common in big data sets. In this thesis we present algorithms for maximal matching, approximate edge covering, and approximate …

Consistent Stereo Image Editing, Tao Yan, Shengfeng He, Rynson W.H. Lau, Yun Xu

Research Collection School Of Computing and Information Systems

Stereo images and videos are very popular in recent years, and techniques for processing this media are attracting a lot of attention. In this paper, we extend the shift-map method for stereo image editing. Our method simultaneously processes the left and right images on pixel level using a global optimization algorithm. It enforces photo consistence between the two images and preserves 3D scene structures. It also addresses the occlusion and disocclusion problem, which may enable many stereo image editing functions, such as depth mapping, object depth adjustment and non-homogeneous image resizing. Our experiments show that the proposed method produces high …

Parallel Implementations Of The Frank-Wolfe Algorithms For The Traffic Assignment Problem, Shawn Eugene Allen

Computational Modeling & Simulation Engineering Theses & Dissertations

Transportation planners seek to understand how to best invest limited resources for future transportation network development. The traffic assignment problem is one algorithm of great importance to planners because it provides insight into how traffic will flow within the network. The Frank-Wolfe algorithm is a traditional solution method for this optimization problem, but it has been characterized by its slow rate of convergence and poor computational performance. This thesis examines and implements several modern advancements in this algorithm which are designed to improve the rate of convergence.

In addition to algorithm changes, another method to improve the performance of an …

Todmis: Mining Communities From Trajectories, Siyuan Liu, Shuhui Wang, Kasthuri Jayarajah, Archan Misra, Rammaya Krishnan

Research Collection School Of Computing and Information Systems

Existing algorithms for trajectory-based clustering usually rely on simplex representation and a single proximity-related distance (or similarity) measure. Consequently, additional information markers (e.g., social interactions or the semantics of the spatial layout) are usually ignored, leading to the inability to fully discover the communities in the trajectory database. This is especially true for human-generated trajectories, where additional fine-grained markers (e.g., movement velocity at certain locations, or the sequence of semantic spaces visited) can help capture latent relationships between cluster members. To address this limitation, we propose TODMIS: a general framework for Trajectory cOmmunity Discovery using Multiple Information Sources. TODMIS combines …

A Robust Rgbd Slam System For 3d Environment With Planar Surfaces, Po-Chang Su, Ju Shen, Sen-Ching S. Cheung

Computer Science Faculty Publications

With the increasing popularity of RGB-depth (RGB-D) sensors such as the Microsoft Kinect, there have been much research on capturing and reconstructing 3D environments using a movable RGB-D sensor. The key process behind these kinds of simultaneous location and mapping (SLAM) systems is the iterative closest point or ICP algorithm, which is an iterative algorithm that can estimate the rigid movement of the camera based on the captured 3D point clouds. While ICP is a well-studied algorithm, it is problematic when it is used in scanning large planar regions such as wall surfaces in a room. The lack of depth …

Computing The Grounded Semantics In All The Subgraphs Of An Argumentation Framework: An Empirical Evaluation, Pierpaolo Dondio

Articles

Given an argumentation framework – with a finite set of arguments and the attack relation identifying the graph – we study how the grounded labelling of a generic argument a varies in all the subgraphs of . Since this is an intractable problem of above-polynomial complexity, we present two non-naïve algorithms to find the set of all the subgraphs where the grounded semantic assigns to argument a specific label . We report the results of a series of empirical tests over graphs of increasing complexity. The value of researching the above problem is two-fold. First, knowing how an argument behaves …

Reaper – Toward Automating Mobile Cloud Communication, Daniel R. Ward

LSU New Orleans Theses and Dissertations

Mobile devices connected to cloud based services are becoming a mainstream method of delivery up-to-date and context aware information to users. Connecting mobile applications to cloud service require significant developer effort. Yet this communication code usually follows certain patterns, varying accordingly to the specific type of data sent and received from the server. By analyzing the causes of theses variations, we can create a system that can automate the code creation for communication from a mobile device to a cloud server. To automate code creation, a general pattern must extracted. This general solution can then be applied to any database …

Using Contracts To Guide The Search-Based Verification Of Concurrent Programs, Christopher M. Poskitt, Simon Poulding

Research Collection School Of Computing and Information Systems

Search-based techniques can be used to identify whether a concurrent program exhibits faults such as race conditions, deadlocks, and starvation: a fitness function is used to guide the search to a region of the program’s state space in which these concurrency faults are more likely occur. In this short paper, we propose that contracts specified by the developer as part of the program’s implementation could be used to provide additional guidance to the search. We sketch an example of how contracts might be used in this way, and outline our plans for investigating this verification approach.

Vigilance Adaptation In Adaptive Resonance Theory, Lei Meng, Ah-Hwee Tan, Donald C. Winsch

Research Collection School Of Computing and Information Systems

Despite the advantages of fast and stable learning, Adaptive Resonance Theory (ART) still relies on an empirically fixed vigilance parameter value to determine the vigilance regions of all of the clusters in the category field (F 2 ), causing its performance to depend on the vigilance value. It would be desirable to use different values of vigilance for different category field nodes, in order to fit the data with a smaller number of categories. We therefore introduce two methods, the Activation Maximization Rule (AMR) and the Confliction Minimization Rule (CMR). Despite their differences, both ART with AMR (AM-ART) and with …

Applying Search In An Automatic Contract-Based Testing Tool, Alexey Kolesnichenko, Christopher M. Poskitt, Bertrand Meyer

Research Collection School Of Computing and Information Systems

Automated random testing has been shown to be effective at finding faults in a variety of contexts and is deployed in several testing frameworks. AutoTest is one such framework, targeting programs written in Eiffel, an object-oriented language natively supporting executable pre- and postconditions; these respectively serving as test filters and test oracles. In this paper, we propose the integration of search-based techniques—along the lines of Tracey—to try and guide the tool towards input data that leads to violations of the postconditions present in the code; input data that random testing alone might miss, or take longer to find. Furthermore, we …

An Empirical Analysis Of A Network Of Expertise, Le Truc Viet, Minh Thap Nguyen

Research Collection School Of Computing and Information Systems

In this paper, we analyze the network of expertise constructed from the interactions of users on the online questionanswering (QA) community of Stack Overflow. This community was built with the intention of helping users with their programming tasks and, thus, questions are expected to be highly factual. This also indicates that the answers one provides may be highly indicative of one's level of expertise on the subject matter. Therefore, our main concern is how to model and characterize the user's expertise based on the constructed network and its centrality measures. We used the user's reputation established on Stack Overflow as …

Adaptive Collective Routing Using Gaussian Process Dynamic Congestion Models, Siyuan Liu, Yisong Yue, Ramayya Krishnan

Research Collection School Of Computing and Information Systems

We consider the problem of adaptively routing a fleet of cooperative vehicles within a road network in the presence of uncertain and dynamic congestion conditions. To tackle this problem, we first propose a Gaussian Process Dynamic Congestion Model that can effectively characterize both the dynamics and the uncertainty of congestion conditions. Our model is efficient and thus facilitates real-time adaptive routing in the face of uncertainty. Using this congestion model, we develop an efficient algorithm for non-myopic adaptive routing to minimize the collective travel time of all vehicles in the system. A key property of our approach is the ability …

Near-Duplicate Video Retrieval: Current Research And Future Trends, Jiajun Liu, Zi Huang, Hongyun Cai, Heng Tao Shen, Chong-Wah Ngo, Wei Wang

Research Collection School Of Computing and Information Systems

The exponential growth of online videos, along with increasing user involvement in video-related activities, has been observed as a constant phenomenon during the last decade. User's time spent on video capturing, editing, uploading, searching, and viewing has boosted to an unprecedented level. The massive publishing and sharing of videos has given rise to the existence of an already large amount of near-duplicate content. This imposes urgent demands on near-duplicate video retrieval as a key role in novel tasks such as video search, video copyright protection, video recommendation, and many more. Driven by its significance, near-duplicate video retrieval has recently attracted …

Optimization Of Solar Cell Arrays Using The Fibonacci Search Algorithm, Felicia Tyyan Farrow

Electrical & Computer Engineering Theses & Dissertations

In our energy hungry world, there is a growing demand to develop creative mechanisms to extract, conserve, and use energy from different resources. The use of solar cells to extract and convert solar energy into electrical energy is a growing and popular field of study because solar energy is clean, free, and renewable. One limitation for photovoltaic (PU) or solar technology is its loss in efficiency and availability as a result of shading or partial shading. Shading or partial shading decreases the total capable output power that the PV system can produce because the array is receiving irradiation from the …

Linear Programming Algorithm With Mixed Real-Integer Variables In Matlab Environments, Gelareh Bakhtyar

Civil & Environmental Engineering Theses & Dissertations

Efficient numerical procedures for solving general Linear Programming (LP) problems with mixed real-integer variables are developed in this work. The proposed algorithms employ the revised dual simplex with Branch and Bound (B&B) algorithms, with special procedures for limited search of subsequent branches. Computational time can be significantly reduced by incorporating the updated inverse formulas into the developed procedures. Both generic LP problems and deterministic pavement maintenance and rehabilitation (M&R) problems are used in this study to vaiidate the developed procedures. Medium to large-scale examples ( 11 pavement M&R) presented in this work have demonstrated that the developed numerical procedures consistently …

Guidance In Feature Extraction To Resolve Uncertainty, Boris Kovalerchuk, Michael Kovalerchuk, Simon Streltsov, Matthew Best

Computer Science Faculty Scholarship

Automated Feature Extraction (AFE) plays a critical role in image understanding. Often the imagery analysts extract features better than AFE algorithms do, because analysts use additional information. The extraction and processing of this information can be more complex than the original AFE task, and that leads to the “complexity trap”. This can happen when the shadow from the buildings guides the extraction of buildings and roads. This work proposes an AFE algorithm to extract roads and trails by using the GMTI/GPS tracking information and older inaccurate maps of roads and trails as AFE guides.

Protocases, Christopher M. Polis

Computer Engineering

Design and implementation of a 3D printing web application.

Integrated Collision Avoidance System Sensor Evaluation Final Design Project, Alex F. Graebe, Bridgette S. Kimball, Drew T. Lavoise

Mechanical Engineering

Following the development of Aircraft Collision Avoidance Technology (ACAT) by the National Aeronautics and Space Administration (NASA), a need arose to transition the life-saving technology to aid the general aviation community. Considering the realistic cost of implementation, it was decided that the technology should be adapted to function on any smartphone, using that device as an end-to-end solution to sense, process, and alert the pilot to imminent threats. In September of 2012, the SAS (Sense and Survive) Senior Project Team at California Polytechnic University (Cal Poly), San Luis Obispo was assigned the task of using smartphone technology to accurately sense …

Understanding Sequential Decisions Via Inverse Reinforcement Learning, Siyuan Liu, Miguel Araujo, Emma Brunskill, Rosaldo Rossetti, Joao Barros, Ramayya Krishnan

Research Collection School Of Computing and Information Systems

The execution of an agent's complex activities, comprising sequences of simpler actions, sometimes leads to the clash of conflicting functions that must be optimized. These functions represent satisfaction, short-term as well as long-term objectives, costs and individual preferences. The way that these functions are weighted is usually unknown even to the decision maker. But if we were able to understand the individual motivations and compare such motivations among individuals, then we would be able to actively change the environment so as to increase satisfaction and/or improve performance. In this work, we approach the problem of providing highlevel and intelligible descriptions …

Visual Tracking Via Locality Sensitive Histograms, Shengfeng He, Qingxiong Yang, Rynson W.H. Lau, Jian Wang, Ming-Hsuan Yang

Research Collection School Of Computing and Information Systems

This paper presents a novel locality sensitive histogram algorithm for visual tracking. Unlike the conventional image histogram that counts the frequency of occurrences of each intensity value by adding ones to the corresponding bin, a locality sensitive histogram is computed at each pixel location and a floating-point value is added to the corresponding bin for each occurrence of an intensity value. The floating-point value declines exponentially with respect to the distance to the pixel location where the histogram is computed, thus every pixel is considered but those that are far away can be neglected due to the very small weights …

Iterative Statistical Verification Of Probabilistic Plans, Colin M. Potts

Lawrence University Honors Projects

Artificial intelligence seeks to create intelligent agents. An agent can be anything: an autopilot, a self-driving car, a robot, a person, or even an anti-virus system. While the current state-of-the-art may not achieve intelligence (a rather dubious thing to quantify) it certainly achieves a sense of autonomy. A key aspect of an autonomous system is its ability to maintain and guarantee safety—defined as avoiding some set of undesired outcomes. The piece of software responsible for this is called a planner, which is essentially an automated problem solver. An advantage computer planners have over humans is their ability to consider and …

Scheduling Jobs On Two Uniform Parallel Machines To Minimize The Makespan, Sandhya Kodimala

UNLV Theses, Dissertations, Professional Papers, and Capstones

The problem of scheduling n independent jobs on m uniform parallel machines such that the total completion time is minimized is a NP-Hard problem. We propose several heuristic-based online algorithms for machines with different speeds called Q₂||C_max. To show the efficiency of the proposed online algorithms, we compute the optimal solution for Q₂||C_max using pseudo-polynomial algorithms based on dynamic programming method. The pseudo-polynomial algorithm has time complexity O (n T²) and can be run on reasonable time for small number of jobs and small processing times. This optimal offline algorithm is …

Detecting Student Dropouts Using Fuzzy Inferencing, Shahriar Husainy

Theses and Dissertations

Fuzzy logic provides a methodology for reasoning using imprecise rules and assertions. Fuzzy inference is the process of formulating the mapping from a given input to an output using fuzzy logic. The mapping then provides a basis from which decisions can be made, or patterns discerned. This study concerns the development of a Fuzzy Inference System (FIS) for identifying likely student dropouts at Columbus State University (CSU). The fuzzy inference based model uses a hybrid knowledge extraction process to predict how likely each freshman student will be to drop their program of study at the end of their first semester. …

Real Time Digital Night Vision Using Nonlinear Contrast Enhancement, Nishikar Sapkota

UNLV Theses, Dissertations, Professional Papers, and Capstones

This thesis describes a nonlinear contrast enhancement technique to implement night vision in digital video. It is based on the global histogram equalization algorithm. First, the effectiveness of global histogram equalization is examined for images taken in low illumination environments in terms of Peak signal to noise ratio (PSNR) and visual inspection of images. Our analysis establishes the existence of an optimum intensity for which histogram equalization yields the best results in terms of output image quality in the context of night vision. Based on this observation, an incremental approach to histogram equalization is developed which gives better results than …