Computer Sciences Commons^™

Easier Parallel Computing In R With Snowfall And Sfcluster, Jochen Knaus, Christine Porzelius, Harald Binder, Guido Schwarzer

The R Journal

Many statistical analysis tasks in areas such as bioinformatics are computationally very intensive, while lots of them rely on embarrassingly parallel computations (Grama et al., 2003). Multiple computers or even multiple processor cores on standard desktop computers, which are widespread nowadays, can easily contribute to faster analyses.

R itself does not allow parallel execution. There are some existing solutions for R to distribute calculations over many computers — a cluster — for ex ample Rmpi, rpvm, snow, nws or papply. However these solutions require the user to setup and manage the cluster on his own and …

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

The R Journal

Contributed Research Articles

Facets of R, John M. Chambers

Collaborative Software Development Using R-Forge, Stefan Theußl and Achim Zeileis

Drawing Diagrams with R, Paul Murrell

The hwriter package: Composing HTML Documents with R Objects, Gregoire Pau and Wolfgang Huber

AdMit, David Ardia, Lennart F. Hoogerheide, and Herman K. van Dijk

expert: Modeling Without Data Using Expert Opinion, Vincent Goulet, Michel Jacques, and Mathieu Pigeon

New Numerical Algorithm for Multivariate Normal Probabilities in Package mvtnorm, Xuefei Mi, Tetsuhisa Miwa, and Torsten Hothorn

EMD: A Package for Empirical Mode Decomposition and Hilbert Spectrum, Donghoh Kim, and Hee-Seok Oh

Sample Size Estimation while …

Drawing Diagrams With R, Paul Murrell

The R Journal

R provides a number of well-known high-level facilities for producing sophisticated statistical plots, including the “traditional” plots in the graphics pack age (R Development Core Team, 2008), the Trellis style plots provided by lattice (Sarkar, 2008), and the grammar-of-graphics-inspired approach of ggplot2 (Wickham, 2009). However, R also provides a powerful set of low level graphics facilities for drawing basic shapes and, more importantly, for arranging those shapes relative to each other, which can be used to draw a wide variety of graphical images. This article highlights some of R’s low-level graphics facilities by demonstrating their use in the production of …

Pmml: An Open Standard For Sharing Models, Alex Guazzelli, Michael Zeller, Wen-Ching Lin, Graham Williams

The R Journal

The PMML package exports a variety of predictive and descriptive models from R to the Predictive Model Markup Language (Data Mining Group, 2008). PMML is an XML-based language and has become the de-facto standard to represent not only predictive and descriptive models, but also data pre- and post-processing. In so doing, it allows for the interchange of models among different tools and environments, mostly avoiding proprietary issues and incompatibilities.

The PMML package itself (Williams et al., 2009) was conceived at first as part of Togaware’s data mining toolkit Rattle, the R Analytical Tool To Learn Easily (Williams, 2009). Although it …

P-Code: A New Raid-6 Code With Optimal Properties, Chao Jin, Hong Jiang, Dan Feng, Lei Tian

School of Computing: Conference and Workshop Papers

RAID-6 significantly outperforms the other RAID levels in disk-failure tolerance due to its ability to tolerate arbitrary two concurrent disk failures in a disk array. The underlying parity array codes have a significant impact on RAID-6’s performance. In this paper, we propose a new XOR-based RAID-6 code, called the Partition Code (P-Code). P-Code is a very simple and flexible vertical code, making it easy to understand and implement. It works on a group of (prime – 1) or (prime) disks, and its coding scheme is based on an equal partition of a specified two-integer-tuple set. P-Code has the following properties: …

Deployed Software Analysis, Madeline M. Diep

School of Computing: Dissertations, Theses, and Student Research

Profiling can offer a valuable characterization of software behavior. The richer the characterization is, the more effective the client analyses are in supporting quality assurance activities. For today's complex software, however, obtaining a rich characterization with the input provided by in-house test suites is becoming more difficult and expensive. Extending the profiling activity to deployed environments can mitigate this shortcoming by exposing more program behavior reflecting real software usage. To make profiling of deployed software plausible, however, we need to take into consideration that there are fundamental differences between the development and the deployed environments. Deployed environments allow for less …

An Efficient Algorithm For Real-Time Divisible Load Scheduling, Anwar Mamat, Ying Lu, Jitender S. Deogun, Steve Goddard

School of Computing: Technical Reports

Providing QoS and performance guarantees to arbitrarily divisible loads has become a significant problem for many cluster-based research computing facilities. While progress is being made in scheduling arbitrarily divisible loads, existing approaches are not very efficient and cannot scale to large clusters. In this paper we propose an efficient algorithm for real-time divisible load scheduling, which has a time complexity linear to the number of tasks and the number of nodes in the cluster.

Network Coding For Wdm All-Optical Multicast, Eric D. Manley, Jitender S. Deogun, Lisong Xu, Dennis R. Alexander

School of Computing: Technical Reports

Network coding has become a useful means for achieving efficient multicast, and the optical community has started to examine its application to optical networks. However, a number of challenges, including limited processing capability and coarse bandwidth granularity, need to be overcome before network coding can be effectively used in optical networks. In this paper, we address some of these problems. We consider the problem of finding efficient routes to use with coding, and we study the effectiveness of using network coding for optical-layer dedicated protection of multicast traffic. We also propose architectures for all-optical circuits capable of performing the processing …

Using Gis To Locate Areas For Growing Quality Coffee In Honduras, Ellen Mickle

Department of Environmental Studies: Undergraduate Student Theses

Abstract Small-scale coffee producers worldwide remain vulnerable to price fluctuations after the 1999-2003 coffee crisis. One way to increase small-scale farmer economic resilience is to produce a more expensive product, such as quality coffee. There is growing demand in coffee-producing and coffee-importing countries for user-friendly tools that facilitate the marketing of quality coffee. The purpose of this study is to develop a prototypical quality coffee marketing tool in the form of a GIS model that identifies regions for producing quality coffee in a country not usually associated with quality coffee, Honduras. Maps of areas for growing quality coffee were produced …

Spa: On-Line Availability Upgrades For Parity-Based Raids Through Supplementary Parity Augmentations, Lei Tian, Hong Jiang, Dan Feng, Qiang Cao, Changsheng Xie, Qin Xin

School of Computing: Technical Reports

In this paper, we propose a simple but powerful on-line availability upgrade mechanism, Supplementary Parity Augmentations (SPA), to address the availability issue for parity-based RAID systems. The basic idea of SPA is to store and update the supplementary parity units on one or a few newly augmented spare disks for on-line RAID systems in the operational mode, thus achieving the goals of improving the reconstruction performance while tole-rating multiple disk failures and latent sector errors simultaneously. By applying the exclusive OR operations appropriately among supplementary parity, full parity and data units, SPA can reconstruct the data on the failed disks …

Carving And Replaying Differential Unit Test Cases From System Test Cases, Sebastian Elbaum, Hui Nee Chin, Matthew B. Dwyer, Matthew Jorde

School of Computing: Faculty Publications

Unit test cases are focused and efficient. System tests are effective at exercising complex usage patterns. Differential unit tests (DUTs) are a hybrid of unit and system tests that exploits their strengths. They are generated by carving the system components, while executing a system test case, that influence the behavior of the target unit and then reassembling those components so that the unit can be exercised as it was by the system test. In this paper, we show that DUTs retain some of the advantages of unit tests, can be automatically generated, and have the potential for revealing faults related …

Agent Sensing In Limited Resource Environments, Adam Eck, Leen-Kiat Soh

School of Computing: Technical Reports

One of the key challenges for multiagent systems (MAS) is optimizing performance in limited resource environments. Previous research in this area has focused on the problems of 1) resource allocation and arbitration, and 2) bounded rationality, which describe the relationship between resource constraints and both agent reasoning and actuation. However, less work exists ad-dressing the effect of consuming resources during agent sensing, particularly two important tradeoffs. First, sensing can reduce resource availability, resulting in a tradeoff between overall system performance and an agent’s sensing behavior (the Performance Tradeoff). Second, consuming resources during sensing can alter the outcome of the measurement …

Multiagent Simulation Of Collaboration And Scaffolding Of A Cscl Environment, Nobel Khandaker, Leen-Kiat Soh

School of Computing: Technical Reports

Multiagent techniques improves student learning in Computer-Supported Collaborative Learning (CSCL) environments through multiagent coalition formation and intelligent support to the instructors and students. Researchers designing the multiagent tools and techniques for 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 testbed for multiagent researchers …

A Multiagent Framework For Human Coalition Formation, Nobel Khandaker, Leen-Kiat Soh

School of Computing: Technical Reports

Human users form coalitions to solve complex tasks and earn rewards. Examples of such coalition formation can be found in the military, education, and business domains. Multiagent coalition formation techniques cannot be readily used to form human coalitions due to the unique aspects of the human coalition formation problem, e.g., uncertainty in human user behavior and changes in human user behaviors due to human learning. Thus, a multiagent system designed to form human coalitions has to solve a learning problem, that is further made difficult by the limited learning opportunities and usability issues (i.e., actions or decisions being perceived as …

Debar: A Scalable High-Performance De-Duplication Storage System For Backup And Archiving, Tianming Yang, Hong Jiang, Dan Feng, Zhongying Niu

School of Computing: Technical Reports

We present DEBAR, a scalable and high-performance de-duplication storage system for backup and archiving, to overcome the throughput and scalability limitations of the state-of-the-art data de-duplication schemes, including the Data Domain De-duplication File System (DDFS). DEBAR uses a two-phase de-duplication scheme (TPDS) that exploits memory cache and disk index properties to judiciously turn the notoriously random and small disk I/Os of fingerprint lookups and updates into large sequential disk I/Os, hence achieving a very high de-duplication throughput. The salient feature of this approach is that both the system backup and archiving capacity and the de-duplication performance can be dynamically and …

Exploring Parameterized Relational Consistency, Shant K. Karakashian, Robert J. Woodward, Berthe Y. Choueiry

School of Computing: Technical Reports

Consistency properties and algorithms for achieving them are at the heart of the success of Constraint Programming. For non-binary Constraint Satisfaction Problems (CSPs), the relational-consistency property R(i,j)C of [Dechter and van Beek 1997] may add new non-binary constraints to the constraint network, thus modifying its topology. The domain-filtering properties of [Bessiere et al. 2008] filter the domains of the variables and leave the constraints unchanged but are restricted to combinations of two constraints. We restate the property of m-wise consistency [Gyssens 1986; Jegou 1993] as relational (*,m)-consistency, R(*,m)C. R(*,m)C ensures that any tuple in a relation is consistent in every …

Classification And Cluster Analysis Of Complex Time-Of-Flight Secondary Ion Mass Spectrometry For Biological Samples, Stephen E. Reichenbach, Xue Tian, Qingping Tao, Alex Henderson

School of Computing: Conference and Workshop Papers

Identifying and separating subtly different biological samples is one of the most critical tasks in biological analysis. Time-of-flight secondary ion mass spectrometry (ToF-SIMS) is becoming a popular and important technique in the analysis of biological samples, because it can detect molecular information and characterize chemical composition. ToF-SIMS spectra of biological samples are enormously complex with large mass ranges and many peaks. As a result the classification and cluster analysis are challenging. This study presents a new classification algorithm, the most similar neighbor with a probability-based spectrum similarity measure (MSN- PSSM), which uses all the information in the entire ToF- SIMS …

Spatio-Temporal Event Model For Cyber-Physical Systems, Ying Tan, Mehmet C. Vuran, Steve Goddard

School of Computing: Conference and Workshop Papers

The emerging Cyber-Physical Systems (CPSs) are envisioned to integrate computation, communication and control with the physical world. Therefore, CPS requires close interactions between the cyber and physical worlds both in time and space. These interactions are usually governed by events, which occur in the physical world and should autonomously be reflected in the cyber-world, and actions, which are taken by the CPS as a result of detection of events and certain decision mechanisms. Both event detection and action decision operations should be performed accurately and timely to guarantee temporal and spatial correctness. This calls for a flexible architecture and task …

Empirical Usage Metadata In Learning Objects, Gwen Nugent, Kevin Kupzyk, S. A. Riley, L.D. Miller, Jesse Hostetler, Leen-Kiat Soh, Ashok Samal

School of Computing: Conference and Workshop Papers

The iLOG Project (Intelligent Learning Object Guide) is designed to augment multimedia learning objects with information about (1) how a learning object has been used, (2) how it has impacted instruction and learning, and (3) how it should be used. The goal of the project is to generate metadata tags from data collected while students interact with learning objects; these metadata tags can then be used to help teachers identify learning objects that match the educational and experiential backgrounds of their students. The project involves the development of an agent-based intelligent system for tracking student interaction with learning objects, in …

Density-Based Clustering Of Polygons, Deepti Joshi, Ashok Samal, Leen-Kiat Soh

School of Computing: Conference and Workshop Papers

Clustering is an important task in spatial data mining and spatial analysis. We propose a clustering algorithm P-DBSCAN to cluster polygons in space. PDBSCAN is based on the well established density-based clustering algorithm DBSCAN. In order to cluster polygons, we incorporate their topological and spatial properties in the process of clustering by using a distance function customized for the polygon space. The objective of our clustering algorithm is to produce spatially compact clusters. We measure the compactness of the clusters produced using P-DBSCAN and compare it with the clusters formed using DBSCAN, using the Schwartzberg Index. We measure the effectiveness …

Redistricting Using Heuristic-Based Polygonal Clustering, Deepti Joshi, Leen-Kiat Soh, Ashok K. Samal

School of Computing: Conference and Workshop Papers

Redistricting is the process of dividing a geographic area into districts or zones. This process has been considered in the past as a problem that is computationally too complex for an automated system to be developed that can produce unbiased plans. In this paper we present a novel method for redistricting a geographic area using a heuristic-based approach for polygonal spatial clustering. While clustering geospatial polygons several complex issues need to be addressed – such as: removing order dependency, clustering all polygons assuming no outliers, and strategically utilizing domain knowledge to guide the clustering process. In order to address these …

Joint Computing And Network Resource Scheduling In A Lambda Grid Network, Vaidhehi Lakshmiraman, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Data-intensive Grid applications require huge data transfers between grid computing nodes. These computing nodes, where computing jobs are executed, are usually geographically separated. A grid network that employs optical wavelength division multiplexing (WDM) technology and optical switches to interconnect computing resources with dynamically provisioned multi-gigabit rate bandwidth lightpath is called a Lambda Grid network. A computing task may be executed on any one of several computing nodes which possesses the necessary resources. In order to reflect the reality in job scheduling, allocation of network resources for data transfer should be taken into consideration. However, few scheduling methods consider the communication …

Regression Model Checking, Guowei Yang, Matthew B. Dwyer, Gregg Rothermel

School of Computing: Conference and Workshop Papers

Model checking is a promising technique for verifying program behavior and is increasingly finding usage in industry. To date, however, researchers have primarily considered model checking of single versions of programs. It is well understood that model checking can be very expensive for large, complex programs. Thus, simply reapplying model checking techniques on subsequent versions of programs as they evolve, in the limited time that is typically available for validating new releases, presents challenges. To address these challenges, we have developed a new technique for regression model checking (RMC), that applies model checking incrementally to new versions of systems. We …

Revealing The Copy And Paste Habits Of End Users, Kathryn T. Stolee, Sebastian Elbaum, Gregg Rothermel

School of Computing: Conference and Workshop Papers

Transferring data across applications is a common end user task, and copying and pasting via the clipboard lets users do so relatively easily. Using the clipboard, however, can also introduce inefficiencies and errors in user tasks. To help researchers and tool developers understand and address these problems, we studied how end users interact with the clipboard through cut, copy, and paste actions. This study was performed by logging clipboard interactions while end users performed everyday tasks. From the clipboard usage data, we have identified several usage patterns that describe how data is transferred within the desktop environment. Such patterns help …

Projection Methods Require Black Border Removal, George Nagy, Sharad C. Seth, Mahesh Viswanathan

School of Computing: Faculty Publications

A persistent flaw in the evaluation of page segmentation algorithms is examined.

Jor: A Journal-Guided Reconstruction Optimization For Raid-Structured Storage Systems, Suzhen Wu, Dan Feng, Hong Jiang, Bo Mao, Lingfang Zeng, Jianxi Chen

School of Computing: Conference and Workshop Papers

This paper proposes a simple and practical RAID reconstruction optimization scheme, called JOurnal-guided Reconstruction (JOR). JOR exploits the fact that significant portions of data blocks in typical disk arrays are unused. JOR monitors the storage space utilization status at the block level to guide the reconstruction process so that only failed data on the used stripes is recovered to the spare disk. In JOR, data consistency is ensured by the requirement that all blocks in a disk array be initialized to zero (written with value zero) during synchronization while all blocks in the spare disk also be initialized to zero …

An Adaptive Steganography Scheme For Voice Over Ip, Hui Tian, Ke Zhou, Hong Jiang, Yongfeng Huang, Jin Liu, Dan Feng

School of Computing: Conference and Workshop Papers

This paper presents an adaptive steganography scheme for Voice over IP (VoIP). Differing from existing steganography techniques for VoIP, this scheme enhances the embedding transparency by taking into account the similarity between Least Significant Bits (LSBs) and embedded messages. Moreover, we introduce the notion of Partial Similarity Value (PSV). By properly setting the threshold PSV, we can adaptively balance the embedding transparency and capacity. We evaluate the effectiveness of this scheme with G.729a as the codec of the cover speech in StegTalk, a covert communication system based on VoIP. The experimental results demonstrate that our technique provides better performance than …

An Adaptive Steganography Scheme For Voice Over Ip, Hui Tian, Ke Zhou, Hong Jiang, Yongfeng Huang, Jin Liu, Dan Feng

School of Computing: Conference and Workshop Papers

This paper presents an adaptive steganography scheme for Voice over IP (VoIP). Differing from existing steganography techniques for VoIP, this scheme enhances the embedding transparency by taking into account the similarity between Least Significant Bits (LSBs) and embedded messages. Moreover, we introduce the notion of Partial Similarity Value (PSV). By properly setting the threshold PSV, we can adaptively balance the embedding transparency and capacity. We evaluate the effectiveness of this scheme with G.729a as the codec of the cover speech in StegTalk, a covert communication system based on VoIP. The experimental results demonstrate that our technique provides better performance than …

Joint Computing And Network Resource Scheduling In A Lambda Grid Network, Vaidhehi Lakshmiraman, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Data-intensive Grid applications require huge data transfers between grid computing nodes. These computing nodes, where computing jobs are executed, are usually geographically separated. A grid network that employs optical wavelength division multiplexing (WDM) technology and optical switches to interconnect computing resources with dynamically provisioned multi-gigabit rate bandwidth lightpath is called a Lambda Grid network. A computing task may be executed on any one of several computing nodes which possesses the necessary resources. In order to reflect the reality in job scheduling, allocation of network resources for data transfer should be taken into consideration. However, few scheduling methods consider the communication …

A Cooperative Scheme For Dynamic Window Resizing In P2p Live Streaming, Zhipeng Ouyang, Lisong Xu, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Due to their widespread popularity, Peer-to-Peer (P2P) live streaming systems have become a great challenge for Internet Service Providers (ISPs) as they consume huge amount of Internet bandwidth. By observing that different users may watch a channel with different window sizes, we propose a cooperative scheme called Partial Participation Scheme (PPS) in which different peers request a video stream at different rates based on their window sizes, and a subset of peers viewing the video stream using a small window work as helpers to forward extra data to help other peers using a large window. By reducing streaming rate received …