Computer Sciences Commons^™

Isomorph-Free Generation Of 2-Connected Graphs With Applications, Derrick Stolee

School of Computing: Technical Reports

Many interesting graph families contain only 2-connected graphs, which have ear decompositions. We develop a technique to generate families of unlabeled 2-connected graphs using ear augmentations and apply this technique to two problems. In the first application, we search for uniquely Kr-saturated graphs and find the list of uniquely K4-saturated graphs on at most 12 vertices, supporting current conjectures for this problem. In the second application, we verify the Edge Reconstruction Conjecture for all 2-connected graphs on at most 12 vertices. This technique can be easily extended to more problems concerning 2-connected graphs.

Tcp Congestion Avoidance Algorithm Identification (Caai), Peng Yang, Wen Luo, Lisong Xu, Jitender Deogun, Ying Lu

School of Computing: Conference and Workshop Papers

The Internet has recently been evolving from homogeneous congestion control to heterogeneous congestion control. Several years ago, Internet traffic was mainly controlled by the traditional AIMD algorithm, whereas Internet traffic is now controlled by many different TCP algorithms, such as AIMD, BIC, CUBIC, and CTCP. However, there is very little work on the performance and stability study of the Internet with heterogeneous congestion control. One fundamental reason is the lack of the deployment information of different TCP algorithms. In this paper, we first propose a tool called TCP Congestion Avoidance Algorithm Identification (CAAI) for actively identifying the TCP algorithm of …

Adaptive Neighborhood Inverse Consistence As Lookahead For Non-Binary Csps, Robert J. Woodward, Shant K. Karakashian, Berthe Y. Choueiry, Christian Bessiere

School of Computing: Conference and Workshop Papers

Contributions

1.The property Relational Neighborhood Inverse Consistency (RNIC)
2.Characterization of RNIC in relation to previously known properties
3.An efficient algorithm for enforcing RNIC, bounded by degree of the dual graph
4.Three reformulations of the dual graph to address topological limitations of the dual graph
5.An adaptive, automatic selection policy for choosing the appropriate dual graph
6.Empirical evidence on difficult CSP benchmarks

Definition

A Constraint Satisfaction Problem (CSP) is a combinatorial decision problem defined by a set of variables {A,B,C,…}, a set of domain values for these variables, and a set of constraints {R₁,R₂,R₃,…} restricting …

Classification For Mass Spectra And Comprehensive Two-Dimensional Chromatograms, Xue Tian

School of Computing: Dissertations, Theses, and Student Research

Mass spectra contain characteristic information regarding the molecular structure and properties of compounds. The mass spectra of compounds from the same chemically related group are similar. Classification is one of the fundamental methodologies for analyzing mass spectral data. The primary goals of classification are to automatically group compounds based on their mass spectra, to find correlation between the properties of compounds and their mass spectra, and to provide a positive identification of unknown compounds.

This dissertation presents a new algorithm for the classification of mass spectra, the most similar neighbor with a probability-based spectrum similarity measure (MSN-PSSM). Experimental results demonstrate …

Applying Data Mining Techniques To Evaluate Applications For Agricultural Loans, Emile J. Salame

Department of Agricultural Economics: Dissertations, Theses, and Student Research

Financial lending institutions continuously look at improving their credit risk models. This study examines the performance of three estimation methods: logistic regression, decision tree, and neural networks, in terms of their misclassification rates of credit default. The study uses 17,328 loans of grain producers for the period of 2006 - 2010. Those loans belong to the category of “diversified loans / core standard” originating from a large financial lending institution. The data has been split into nine different sets to acknowledge three factors: the shift in price of grains to a higher plateau after 2006, the contamination effect on defaulting …

Molecular Dynamics Simulation Based On Hadoop Mapreduce, Chen He

School of Computing: Dissertations, Theses, and Student Research

Molecular Dynamics (MD) simulation is a computationally intensive application used in multiple fields. It can exploit a distributed environment due to inherent computational parallelism. However, most of the existing implementations focus on performance enhancement. They may not provide fault-tolerance for every time-step.

MapReduce is a framework first proposed by Google for processing huge amounts of data in a distributed environment. The simplicity of the programming model and fault- tolerance for node failure during run-time make it very popular not only for commercial applications but also in scientific computing.

In this thesis, we develop a novel communication-free and each time-step fault- …

Real-Time Divisible Load Scheduling For Cluster Computing, Anwar Mamat

School of Computing: Dissertations, Theses, and Student Research

Cluster computing has become an important paradigm for solving large-scale problems. However, as the size of a cluster increases, so does the complexity of resource management and maintenance. Therefore, automated performance control and re- source management are expected to play critical roles in sustaining the evolution of cluster computing. The current cluster scheduling practice is similar in sophistication to early supercomputer batch scheduling algorithms, and no consideration is given to desired quality-of-service (QoS) attributes. To fully avail the power of computational clusters, new scheduling algorithms that provides high performance, QoS assurance, fault-tolerance, energy savings and streamlined management of the cluster …

Comparative Analysis Of Peak-Detection Techniques For Comprehensive Two-Dimensional Chromatography, Indu Latha, Stephen E. Reichenbach, Qingping Tao

School of Computing: Faculty Publications

Comprehensive two-dimensional gas chromatography (GC×GC) is a powerful technology for separating complex samples. The typical goal of GC×GC peak detection is to aggregate data points of analyte peaks based on their retention times and intensities. Two techniques commonly used for two-dimensional peak detection are the two-step algorithm and the watershed algorithm. A recent study [4] compared the performance of the two-step and watershed algorithms for GC×GC data with retention-time shifts in the second-column separations.In that analysis,the peak retention-time shifts were corrected while applying the two-step algorithm but the watershed algorithm was applied without shift correction. The results indicated that the …

A Study On Facility Planning Using Discrete Event Simulation: Case Study Of A Grain Delivery Terminal, Sarah M. Asio

Department of Industrial and Management Systems Engineering: Dissertations, Theses, and Student Research

The application of traditional approaches to the design of efficient facilities can be tedious and time consuming when uncertainty and a number of constraints exist. Queuing models and mathematical programming techniques are not able to capture the complex interaction between resources, the environment and space constraints for dynamic stochastic processes. In the following study discrete event simulation is applied to the facility planning process for a grain delivery terminal. The discrete event simulation approach has been applied to studies such as capacity planning and facility layout for a gasoline station and evaluating the resource requirements for a manufacturing facility. To …

A Reservation-Based Smart Parking System, Hongwei Wang

School of Computing: Dissertations, Theses, and Student Research

In metropolitan areas, parking management influences drivers search time and cost for parking spaces, parking revenue, and traffic congestion. The wide deployment of wireless parking meters with sensing and communications capabilities allows the parking authority to monitor the state of each parking space in real time and optimize the parking management.

In this thesis, we study state-of-the-art parking policies in smart parking systems, and show that the smart parking system needs to be "smarter". Our design goals of the smart parking systems include: (1) simplify the operations of parking systems, (2) improve drivers' satisfaction, (3) increase parking revenue, and (4) …

Simcol: A Simulation Tool For Computer-Supported Collaborative Learning, Nobel Khandaker, Leen-Kiat Soh

School of Computing: Faculty Publications

Researchers designing the multiagent tools and techniques for computer-supported collaborative learning (CSCL) environments are often faced with high cost, time, and effort required to investigate the effectiveness of their tools and techniques in large scale and longitudinal studies in a real-world environment containing human users. Here, we propose SimCoL, a multiagent environment that simulates collaborative learning among students and agents providing support to the teacher and the students. Our goal with SimCoL is to provide a comprehensive test bed for multiagent researchers to investigate 1) theoretical multiagent research issues, e.g., coalition formation, multiagent learning, and communication, where humans are involved …

The R Journal (June 2011) 3(1): Complete Issue, The R Foundation

The R Journal

Contributed Research Articles

testthat: Get Started with Testing, Hadley Wickham

Content-Based Social Network Analysis of Mailing Lists, Angela Bohn, Ingo Feinerer, Kurt Hornik, and Patrick Mair

Rmetrics: timeDate Package, Yohan Chalabi, Martin Mächler, and Diethelm Würtz

The digitize Package: Extracting Numerical Data from Scatterplots, Timothée Poisot

Differential Evolution with DEoptim, David Ardia, Kris Boudt, Peter Carl, Katharine M. Mullen, and Brian G. Peterson

rworldmap: A New R Package for Mapping Global Data, Andy South

Cryptographic Boolean Functions with R, Frédéric Lafitte, Dirk Van Heule and Julien Van hamme

Raster Images in R Graphics, Paul Murrell

Probabilistic Weather Forecasting in R, …

Raster Images In R Graphics, Paul Murrell

The R Journal

The R graphics engine has new support for rendering raster images via the functions rasterImage() and grid.raster(). This leads to better scaling of raster images, faster rendering to screen, and smaller graphics files. Several examples of possible applications of these new features are described.

Cryptographic Boolean Functions With R, Frédéric Lafitte, Dirk Van Heule, Julien Van Hamme

The R Journal

A new package called boolfun is avail able for R users. The package provides tools to handle Boolean functions, in particular for cryptographic purposes. This document guides the user through some (code) examples and gives a feel of what can be done with the package.

Rmetrics: Timedate Package, Yohan Chalabi, Martin Mächler, Diethelm Würtz

The R Journal

The management of time and holidays can prove crucial in applications that rely on historical data. Atypical example is the aggregation of a data set recorded in different time zones and under different daylight saving time rules. Be sides the time zone conversion function, which is well supported by default classes in R,one might need functions to handle special days or holidays. In this respect, the package timeDate enhances default date-time classes in R and brings new functionalities to time zone management and the creation of holiday calendars

The Digitize Package: Extracting Numerical Data From Scatterplots, Timothée Poisot

The R Journal

I present the small R package digitize, designed to extract data from scatter plots with a simple method and suited to small datasets. I present an application of this method to the ex traction of data from a graph whose source is not available.

Analyzing An Electronic Limit Order Book, David Kane, Andrew Liu, Khanh Nguyen

The R Journal

The orderbook package provides facilities for exploring and visualizing the data associated with an order book: the electronic collection of the outstanding limit orders for a financial instrument. This article provides an overview of the orderbook package and examples of its use.

Testthat: Get Started With Testing, Hadley Wickham

The R Journal

Software testing is important, but many of us don’t do it because it is frustrating and boring. testthat is a new testing framework for R that is easy learn and use, and integrates with your existing workflow. This paper shows how, with illustrations from existing packages.

Rworldmap: A New R Package For Mapping Global Data, Andy South

The R Journal

rworldmap is a relatively new package available on CRAN for the mapping and visualisation of global data. The vision is to make the display of global data easier, to facilitate understanding and communication. The initial focus is on data referenced by country or grid due to the frequency of use of such data in global assessments. Tools to link data referenced by country (either name or code) to a map, and then to display the map are provided as are functions to map global gridded data. Country and gridded functions accept the same arguments to specify the nature of categories …

Differential Evolution With Deoptim, David Ardia, Kris Boudt, Peter Carl, Katharine M. Mullen, Brian G. Peterson

The R Journal

The R package DEoptim implements the Differential Evolution algorithm. This algorithm is an evolutionary technique similar to classic genetic algorithms that is useful for the solution of global optimization problems. In this note we provide an introduction to the package and demonstrate its utility for financial applications by solving a non-convex portfolio optimization problem.

Probabilistic Weather Forecasting In R, Chris Fraley, Adrian Raftery, Tilmann Gneiting, Mclean Sloughter, Veronica Berrocol

The R Journal

This article describes two R packages for probabilistic weather forecasting, ensembleBMA, which offers ensemble post-processing via Bayesian model averaging (BMA), and Prob ForecastGOP, which implements the geostatistical output perturbation (GOP) method. BMA forecasting models use mixture distributions, in which each component corresponds to an ensemble member, and the form of the component distribution depends on the weather parameter (temperature, quantitative precipitation or wind speed). The model parameters are estimated from training data. The GOP technique uses geostatistical methods to produce probabilistic fore casts of entire weather fields for temperature or pressure, based on a single numerical forecast on …

Multiagent Coalition Formation In Uncertain Environments With Type-Changing Influences And Its Application Towards Forming Human Coalitions, Nobel A. Khandaker

School of Computing: Dissertations, Theses, and Student Research

We aim to solve the problem forming multiagent coalitions in uncertain environments where the coalition members’ capability of solving tasks change due to their learning. The MCFP-Mproblem for the agents refers to forming or joining coalitions on behalf of a set of human users so that those human users can solve tasks and improve their types (expertise) to improve their performances over time. MCFP-A problem for a set of agents refers to their forming or joining coalitions so that they are able to solve a set of assigned tasks while optimize their performance over time. We propose the Integrated Human …

Campus Grids: A Framework To Facilitate Resource Sharing, Derek J. Weitzel

School of Computing: Dissertations, Theses, and Student Research

It is common at research institutions to maintain multiple clusters. These might fulfill different needs and policies, or represent different owners or generations of hard- ware. Many of these clusters are under utilized while researchers at other departments may require these resources. This may be solved by linking clusters with grid mid- dleware. This thesis describes a distributed high throughput computing framework to link clusters without changing security or execution environments. The framework initially keeps jobs local to the submitter, overflowing if necessary to the campus, and regional grid. The framework is implemented spanning two campuses at the Holland Computing …

Protein Structure-Based Method For Identification Of Horizontal Gene Transfer In Bacteria, Swetha Billa

School of Computing: Dissertations, Theses, and Student Research

Horizontal Gene Transfer is defined as the movement of genetic material from one strain of species to another. Bacteria, being an asexual organism were always believed to transfer genes vertically. But recent studies provide evidence that shows bacteria can also transfer genes horizontally.

HGT plays a major role in evolution and medicine. It is the major contributor in bacterial evolution, enabling species to acquire genes to adapt to the new environments. Bacteria are also believed to develop drug resistance to antibiotics through the phenomenon of HGT. Therefore further study of HGT and its implications is necessary to understand the effects …

Ontology For Psychophysiological Dysregulation Of Anger/Aggression, Swathi Vasanthapuram

School of Computing: Dissertations, Theses, and Student Research

The advancement of Information Technology in the last four decades led to the use of computers in medicine. A new area called Medical Informatics has emerged. This area comprises the application of IT to healthcare with the aim of creating tools that help healthcare personnel diagnose and treat patients more accurately and efficiently. IT not only provides tools for storing, integrating, and updating patient information base but also for processing information efficiently. One of such tools is a Clinical Decision Support System. Ontologies are an integral part of clinical decision support systems because they help formalize and integrate domain knowledge. …

Exploiting Program And Property Structure For Efficient Runtime Monitoring, Rahul Purandare

School of Computing: Dissertations, Theses, and Student Research

Modern software systems are complex and often built using components that are provided with their application programming interface (API) to assist a user. However, this API is informal and if used incorrectly, may lead to bugs that are hard to detect. In order to address the problem of API conformance checking, researchers have proposed various analysis techniques including static and dynamic typestate analysis. However, it is extremely challenging to develop a static analysis that is both precise and scalable. On the other hand, dynamic analysis or runtime monitoring of programs may incur heavy overhead, thereby limiting its application only to …

Understanding User Generated Content Characteristics : A Hot-Event Perspective, Miao Wang, Guodong Li, Jie Feng, Lisong Xu, Byrav Ramamurthy, Wei Li, Xiaohong Guan

School of Computing: Conference and Workshop Papers

Nowadays, millions of Internet users watch and upload a large number of videos on User Generated Content (UGC) sites (e.g., Youtube) everyday. Moreover, online videos about hot events, such as breaking news and Olympic games, attract lots of users. In this paper, we study the characteristics of hot-event videos by collecting video traces of the largest UGC site in China for 28 days. We first empirically study statistical properties of such videos and find that hot-event videos contribute a large number of views, even though the total number of hotevent videos is relatively small. In addition, there exist extremely active …

Multi-Channel Peer-To-Peer Streaming Systems As Resource Allocation Problems, Miao Wang

School of Computing: Dissertations, Theses, and Student Research

In the past few years, the Internet has witnessed the success of Peer-to-Peer (P2P) streaming technology, which has attracted millions of users. More recently, commercial P2P streaming systems have begun to support multiple channels and a user in such systems is allowed to watch more than one channel at a time. We refer to such systems as multi-channel P2P streaming systems. In this dissertation, we focus on designing multi-channel P2P streaming systems with the goal of providing optimal streaming quality for all channels, termed as system-wide optimal streaming quality. Specifically, we design the systems from the perspective of how to …

Offline Optimization Of Advance Reservation Of Bandwidth Over Dynamic Circuit Networks, Pragatheeswaran Angu

School of Computing: Dissertations, Theses, and Student Research

E-science projects require very high-speed and reliable networks to transfer data across various destinations in the world. Dynamic Circuit Network (DCN) is a networking service to make advance reservation of bandwidth between a source and a destination in a network. In this thesis we solve the problem of advance reservation of bandwidth in next-generation wavelength-division multiplexing (WDM) networks using a simulation based approach.
We implement a greedy algorithm and a genetic algorithm in parallel, in separate threads. The request for advance reservation is processed by both but the user gets the response only from the greedy algorithm. The genetic algorithm …

Polygonal Spatial Clustering, Deepti Joshi

School of Computing: Dissertations, Theses, and Student Research

Clustering, the process of grouping together similar objects, is a fundamental task in data mining to help perform knowledge discovery in large datasets.  With the growing number of sensor networks, geospatial satellites, global positioning devices, and human networks tremendous amounts of spatio-temporal data that measure the state of the planet Earth are being collected every day.  This large amount of spatio-temporal data has increased the need for efficient spatial data mining techniques.  Furthermore, most of the anthropogenic objects in space are represented using polygons, for example – counties, census tracts, and watersheds.  Therefore, it is important to develop data mining …