Computer Sciences Commons^™

Assessing The Cost-Benefits Of Using Type Inference Algorithms To Improve The Representation Of Exceptional Control Flow In Java, Alex Kinneer, Gregg Rothermel

School of Computing: Technical Reports

Accurate representations of program control flow are important to the soundness and efficiency of program analysis and testing techniques. The Java programming language has introduced structured exception handling features that complicate the task of constructing safe and precise representations of the possible control flow in Java programs. Prior work has considered applying various type inference algorithms to exceptions, but has not yet investigated whether the use of higher cost algorithms is necessarily justified. It is important to understand and assess the tradeoffs associated with the use of more powerful yet costly algorithms, thus we conducted an empirical study to evaluate …

Neighborhood Interchangeability And Dynamic Bundling For Non-Binary Csps, Anagh Lal, Berthe Y. Choueiry, Eugene C. Freuder

School of Computing: Conference and Workshop Papers

1. Interchangeability: An algorithm for computing interchangeability in non-binary CSPs.

2. Dynamic bundling: Integration of the above with backtrack search for solving non-binary CSPs.

3. Experiments demonstrating the benefits of dynamic bundling

·Finding multiple, robust solutions.

·Decreasing computational cost of search.

Neighborhood Interchangeability And Dynamic Bundling For Non-Binary Finite Csps, Anagh Lal, Berthe Y. Choueiry, Eugene C. Freuder

School of Computing: Conference and Workshop Papers

Neighborhood Interchangeability (NI) identifies the equivalent values in the domain of a variable of a Constraint Satisfaction Problem (CSP) by considering only the constraints that directly apply to the variable. Freuder described an algorithm for efficiently computing NI values in binary CSPs. In this paper, we show that the generalization of this algorithm to non-binary CSPs is not straightforward, and introduce an efficient algorithm for computing NI values in the presence of non-binary constraints. Further, we show how to interleave this mechanism with search for solving CSPs, thus yielding a dynamic bundling strategy. While the goal of dynamic bundling is …

Exploiting The Advantages Of Object-Based Dsm In A Heterogeneous Cluster Environment, Xuli Liu, Hong Jiang, Leen-Kiat Soh

School of Computing: Conference and Workshop Papers

In recent years, increasing effort has been made by the cluster and grid computing community to build object- based Distributed Shared Memory systems (DSM) in a cluster environment. In most of these systems, a shared object is simply used as a data-exchanging unit so as to alleviate the false-sharing problem, and the advantages of sharing objects remain to be fully exploited. Thus, this paper is motivated to investigate the potential advantages of object-based DSM. For example, the performance of a distributed application may be significantly improved by adaptively and judiciously setting the size of the shared objects, i.e., granularity. This …

Real-Time Divisible Load Scheduling For Cluster Computing, Xuan Lin, Ying Lu, Jitender S. Deogun, Steve Goddard

School of Computing: Technical Reports

Cluster Computing has emerged as a new paradigm for solving large-scale problems. To enhance QoS and provide performance guarantees in cluster computing environments, various workload models and real-time scheduling algorithms have been investigated. The divisible load model, propagated by divisible load theory, models computations that can be arbitrarily divided into independent pieces and provides a good approximation of many real-world applications. However, researchers have not yet investigated the problem of providing performance guarantees to divisible load applications. Two contributions are made in this paper: (1) divisible load theory is extended to compute the minimum number of processors required to meet …

Disseminating Usability Design Knowledge Through Ontology-Based Pattern Languages, Scott Henninger, Padmapriya Ashokkumar

School of Computing: Technical Reports

Usability patterns represent knowledge about known ways to design graphical user interfaces that are usable and meet the needs and expectations of users. There is currently a plethora of usability patterns published in books, private repositories and the World-Wide Web. The dominance of pattern discovery efforts has neglected the emerging need to organize the patterns so they can become a proactive resource for developing interfaces. This paper presents an approach using Semantic Web concepts that turns informal patterns into formal representations capable of supporting systematic design methods. Through this method, loosely coupled pattern collections can be turned into strongly coupled …

Dgkd: Distributed Group Key Distribution With Authentication Capability, Pratima Adusumilli, Xukai Zou, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Group key management (GKM} is the most important issue in secure group communication (SCC). The existing GKM protocols fall into three typical classes: centralized group key distribution (CGKD), decentralized group key management (DGKM), and distributed/contributory group key agreement (CGKA). Serious problems remains in these protocols, as they require existence of central trusted entities (such as group controller or subgroup controllers), relaying of messages (by subgroup controllers), or strict member synchronization (JOT multiple round stepwise key agreement), thus suffering from the single point of failure and attack, performance bottleneck, or mis-operations in the situation of transmission delay or network failure. In …

Disseminating Usability Design Knowledge Through Ontology-Based Pattern Languages, Scott Henninger, Padmapriya Ashokkumar

School of Computing: Technical Reports

Usability patterns represent knowledge about known ways to design graphical user interfaces that are usable and meet the needs and expectations of users. There is currently a plethora of usability patterns published in books, private repositories and the World-Wide Web. The dominance of pattern discovery efforts has neglected the emerging need to organize the patterns so they can become a proactive resource for developing interfaces. This paper presents an approach using Semantic Web concepts that turns informal patterns into formal representations capable of supporting systematic design methods. Through this method, loosely coupled pattern collections can be turned into strongly coupled …

Crtdh: An Efficient Key Agreement Scheme For Secure Group Communications In Wireless Ad Hoc Networks, Ravi K Balachandran, Byrav Ramamurthy, Xukai Zou, N.V. Vinodchandran

School of Computing: Conference and Workshop Papers

As a result of the growing popularity of wireless networks, in particular ad hoc networks, security over such networks has become very important. In this paper, we study the problem of secure group communications (SGC) and key management over ad hoc networks. We identify the key features of any SGC protocol for such networks. We also propose an efficient key agreement scheme for SGC. The scheme solves two important problems that exist in most current SGC schemes: requirement of member serialization and existence of a central entity. Besides this, the protocol also has many highly desirable properties such as contributory …

Same-Destination-Intermediate Grouping Vs. End-To-End Grouping For Waveband Switching In Wdm Mesh Networks, Mengke Li, Wang Yao, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

We investigate waveband switching (WBS) with different grouping strategies in wavelength-division multiplexing (WDM) mesh networks. End-to-end waveband switching (ETEWBS) and same-destination-intermediate waveband switching (SD-IT-WBS) are analyzed and compared in terms of blocking probability and cost savings. First, an analytical model for ETEWBS is proposed to determine the network blocking probability in a mesh network. For SD-IT-WBS, a simple waveband switching algorithm is presented. An analytical model to determine the network blocking probability is proposed for SD-IT-WBS based on the algorithm. The analytical results are validated by comparing with simulation results. Both results match well and show that ETE-WBS slightly outperforms …

A Novel Cost-Efficient On-Line Intermediate Waveband-Switching Scheme In Wdm Mesh Networks, Mengke Li, Wang Yao, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Waveband switching (WBS) is an important technique to save switching and transmission cost in wavelength -division multiplexed (WDM) optical networks. A cost-efficient WBS scheme would enable network carriers to increase the network throughput (revenue) while achieving significant cost savings. We identify the critical factors that determine the WBS network throughput and switching cost and propose a novel intermediate waveband switching (IT-WBS) algorithm, called the minimizing-weighted-cost (MWC) algorithm. The MWC algorithm defines a cost for each candidate route of a call. By selecting the route with the smallest weighted cost, MWC balances between minimizing the call blocking probability and minimizing the …

Discontinuous Waveband Switching In Wdm Optical Networks, Bhavana Lekkala, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Routing techniques used in wavelength routed optical networks (WRN) do not give an efficient solution with Waveband routed optical networks (WBN) as the objective of routing in WRN is to reduce the blocking probability and that in WBN is to reduce the number of switching ports. Routing in WBN can be divided two parts, finding the route and grouping the wavelength assigned into that route with some existing wavelengths/wavebands. In this paper, we propose a heuristic for waveband routing, which uses a new grouping strategy called discontinuous waveband grouping to group the wavelengths into a waveband. The main objective of …

Performance Analysis Of Sparse Traffic Grooming In Wdm Mesh Networks, Wang Yao, Mengke Li, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Sparse traffic grooming is a practical problem to be addressed in heterogeneous multi-vendor optical WDM networks where only some of the optical cross-connects (OXCs) have grooming capabilities. Such a network is called as a sparse grooming network. The sparse grooming problem under dynamic traffic in optical WDM mesh networks is a relatively unexplored problem. In this work, we propose the maximize-lightpath-sharing multi-hop (MLS-MH) grooming algorithm to support dynamic traffic grooming in sparse grooming networks. We also present an analytical model to evaluate the blocking performance of the MLS-MH algorithm. Simulation results show that MLSMH outperforms an existing grooming algorithm, the …

An Empirical Study Of Fault Localization For End-User Programmers, Joseph R. Ruthruff, Margaret Burnett, Gregg Rothermel

School of Computing: Conference and Workshop Papers

End users develop more software than any other group of programmers, using software authoring devices such as e-mail filtering editors, by-demonstration macro builders, and spreadsheet environments. Despite this, there has been little research on finding ways to help these programmers with the dependability of their software. We have been addressing this problem in several ways, one of which includes supporting end-user debugging activities through fault localization techniques. This paper presents the results of an empirical study conducted in an end-user programming environment to examine the impact of two separate factors in fault localization techniques that affect technique effectiveness. Our results …

Technical Reports (1999 - 2005)

School of Computing: Technical Reports

Authors of Technical Reports (1999-2005):
Choueiry, Berthe
Elbaum, Sebastian
Goddard, Steve
Henninger, Scott
Jiang, Hong
Rothermel, Gregg
Scott, Stephen
Seth, Sharad
Soh, Leen-Kiat
Variyam, Vinodchandran

Balancing Exploration And Exploitation: A New Algorithm For Active Machine Learning, Thomas Osugi, Deng Kun, Stephen Scott

School of Computing: Conference and Workshop Papers

Active machine learning algorithms are used when large numbers of unlabeled examples are available and getting labels for them is costly (e.g. requiring consulting a human expert). Many conventional active learning algorithms focus on refining the decision boundary, at the expense of exploring new regions that the current hypothesis misclassifies. We propose a new active learning algorithm that balances such exploration with refining of the decision boundary by dynamically adjusting the probability to explore at each step. Our experimental results demonstrate improved performance on data sets that require extensive exploration while remaining competitive on data sets that do not. Our …

Utilizing Device Slack For Energy-Efficient I/O Device Scheduling In Hard Real-Time Systems With Non-Preemptible Resources, Hui Cheng, Steve Goddard

School of Computing: Technical Reports

The challenge in conserving energy in embedded real-time systems is to reduce power consumption while preserving temporal correctness. Much research has focused on power conservation for the processor, while power conservation for I/O devices has received little attention. In this paper, we analyze the problem of online energy-aware I/O scheduling for hard real-time systems based on the preemptive periodic task model with non-preemptible shared resources. We extend the concept of device slack proposed in [2] to support non-preemptible shared resources; and propose an online energy-aware I/O scheduling algorithm: Energy-efficient Device Scheduling with Non-preemptible Resources (EEDS NR). The EEDS NR algorithm …

On Finding Consecutive Test Vectors In A Random Sequence For Energy-Aware Bist Design, Sheng Zhang, Sharad C. Seth, Bhargab B. Bhattacharya

School of Computing: Conference and Workshop Papers

During pseudorandom testing, a significant amount of energy and test application time is wasted for generating and for applying “useless” test vectors that do not contribute to fault dropping. For low-power testing, modification logic/ROM may be used to skip the LFSR states that generate useless test patterns. The overhead of extra logic increases rapidly with the number of such jumps. Since identification of useless patterns strongly depends on the order in which incremental fault simulation is performed, an elegant solution to this problem would be to find a minimum set of segments in the LFSR sequence, where each segment corresponds …

Scaling A Dataflow Testing Methodology To The Multiparadigm World Of Commercial Spreadsheets, Marc Randall Fisher Ii, Gregg Rothermel, Tyler Creelan, Margaret Burnett

School of Computing: Technical Reports

Spreadsheet languages are widely used by end users to perform a broad range of important tasks. Evidence shows, however, that spreadsheets often contain faults. Thus, in prior work we presented a dataflow testing methodology for use with spreadsheets, that provides feedback about the coverage of cells in spreadsheets via visual devices. Studies have shown that this methodology, which we call WYSIWYT (What You See Is What You Test), can be used cost-effectively by end-user programmers. To date, however, the methodology has been investigated across a limited set of spreadsheet language features. Commercial spreadsheet environments are multiparadigm languages, utilizing features often …

A Performance And Schedulability Analysis Of An Autonomous Mobile Robot, Ala' Adel Qadi, Steve Goddard, Jiangyang Huang, Shane Farritor

School of Computing: Technical Reports

We present an autonomous, mobile, robotics application that requires dynamic adjustments of task execution rates to meet the demands of an unpredictable environment. The Robotic Safety Marker (RSM) system consists of one lead robot, the foreman, and a group of guided robots, called robotic safety markers (a.k.a., barrels). An extensive analysis is conducted of two applications running on the foreman. Both applications require adjusting task periods to achieve desired performance metrics with respect to the speed at which a system task is completed, the accuracy of RSM placement, or the number of RSMs controlled by the foreman. A static priority …

Applications Of Decision And Utility Theory In Multi-Agent Systems, Xin Li, Leen-Kiat Soh

School of Computing: Technical Reports

This report reviews the applications of decision-related theories (decision theory, utility theory, probability theory, and game theory) in various aspects of multi-agent systems. In recent years, multi-agent systems (MASs) have become a highly active research area as multi-agent systems have a wide range of applications. However, most of real-world environments are very complex and of uncertainty. An agent’s knowledge about the world is rather incomplete and uncertain. The actions of the agent are non-deterministic with a range of possible outcomes. The agent may have many desires that conflict each other. The agent also needs to know about other agents and …

An Adaptive Mechanism For Improving File Transfer Performance, Eric Moss, Leen-Kiat Soh

School of Computing: Technical Reports

A variant of instance-based learning is described which detects periodic patterns in the presence of sparse data. A weighted average gives higher weight to values in the recent past as well as those at expected periods in the past. After each new measurement, the space of weights near the current set is searched for a set that minimizes the error of prediction, thus providing a learning mechanism. The method is described in terms of an application which minimizes file download times by choosing between available servers.

An Online Survey Framework Using The Life Events Calendar, Jared Kite, Leen-Kiat Soh

School of Computing: Technical Reports

We describe an online survey framework programmed as a Java applet with a MySQL back-end. Our framework is built specifically as a Event History Calendar for the study of tobacco users and their behavior over a six month period. We introduce the notion of a Life Events Calendar and the relevance of an intelligent survey system in this context. We describe our methods and our component application approach and expand on the opportunities for artificial intelligence research with the system.

An Analysis Of Mcmc Sampling Methods For Estimating Weighted Sums In Winnow, Qingping Tao, Stephen Scott

School of Computing: Technical Reports

Chawla et al. introduced a way to use the Markov chain Monte Carlo method to estimate weighted sums in multiplicative weight update algorithms when the number of inputs is exponential. But their algorithm still required extensive simulation of the Markov chain in order to get accurate estimates of the weighted sums. We propose an optimized version of Chawla et al.’s algorithm, which produces exactly the same classifications while often using fewer Markov chain simulations. We also apply two other sampling techniques and empirically compare them with Chawla et al.’s Metropolis sampler to determine how effective each is in drawing good …

Ai In Computer Games: From The Player’S Goal To Ai’S Role, Jeremy A. Glasser, Leen-Kiat Soh

School of Computing: Technical Reports

This paper addresses the role of Artificial Intelligence (AI) in a variety of game genres. Every game aims to entertain (though educational games have secondary objectives). Each genre approaches entertainment in a unique way. We explore the methods used to draw the game player’s attention. We then consider how the AI interacts with the player to promote both entertainment and an interactive environment. We also consider some of the techniques that will shape tomorrow’s games. Included are opponent strategies, interactive environments, and multiagent systems (MAS). While different, each approach can aid in creating more immersive and challenging gaming experiences. Our …

Reasoning And Learning With Imperfect Casebases: An Agent Perspective With An Expert Model, Leen-Kiat Soh

School of Computing: Technical Reports

Traditionally, case-based reasoning (CBR) (e.g., Watson and Marir 1994) assumes that the cases in the casebase are correct, useful in both time and space. Otherwise, the cases would not have been stored in the casebase in the first place. Cases are supposed to be useful in guiding us to a successful solution, or in preventing us from repeating the same failure.

A Study In Modeling Low-Conservation Protein Superfamilies, Chang Wang, Stephen Scott, Jun Zhang, Qingping Tao, Dmitri E. Fomenko, Vadim N. Gladyshev

School of Computing: Technical Reports

We present several algorithms for identification of new proteins in superfamilies with low primary sequence conservation. The low conservation of primary sequence in protein superfamilies such as Thioredoxin-fold (Trxfold) makes conventional methods such as hidden Markov models (HMMs) difficult to use. Therefore, we use structural properties to build our classifiers. These structural properties include secondary structure patterns as well as various properties of the residues in the protein sequences. We use this information to model proteins via hidden Markov models, support vector machines and algorithms in the multiple-instance learning model. In 20-fold jackknife tests, some of our models performed well, …

Comparison Of Modis And Avhrr 16-Day Normalized Difference Vegetation Index Composite Data, Kevin P. Gallo, Lei Ji, Brad Reed, John Dwyer, Jeffrey Eidenshink

School of Natural Resources: Faculty Publications

Normalized difference vegetation index (NDVI) data derived from visible and near-infrared data acquired by the MODIS and AVHRR sensors were compared over the same time periods and a variety of land cover classes within the conterminous USA. The relationship between the AVHRR derived NDVI values and those of future sensors is critical to continued long term monitoring of land surface properties. The results indicate that the 16-day composite values are quite similar over the 23 intervals of 2001 that were analyzed, and a linear relationship exists between the NDVI values from the two sensors. The composite AVHRR NDVI data were …

Dynamic Voltage Scaling For Sporadic And Periodic Tasks, Ala' Adel Qadi, Steve Goddard, Shane Farritor

School of Computing: Technical Reports

Dynamic voltage scaling (DVS) algorithms save energy by scaling down the processor frequency when the processor is not fully loaded. Many algorithms have been proposed for periodic and aperiodic task models but none support the periodic and sporadic task models when the deadlines are not equal to their periods. A DVS algorithm, called General Dynamic Voltage Scaling (GDVS), that can be used with sporadic or periodic tasks in conjunction with the preemptive EDF scheduling algorithm with no constraints on the deadlines is presented here. The algorithm is proven to guarantee each task meets its deadline while saving the maximum amount …

Arktos: An Intelligent System For Sar Sea Ice Image Classification, Leen-Kiat Soh, Costas Tsatsoulis, Denise Gineris, Cheryl Bertoia

School of Computing: Faculty Publications

We present an intelligent system for satellite sea ice image analysis named Advanced Reasoning using Knowledge for Typing Of Sea ice (ARKTOS). ARKTOS performs fully automated analysis of synthetic aperture radar (SAR) sea ice images by mimicking the reasoning process of sea ice experts. ARKTOS automatically segments a SAR image of sea ice, generates descriptors for the segments of the image, and then uses expert system rules to classify these sea ice features. ARKTOS also utilizes multisource data fusion to improve classification and performs belief handling using Dempster–Shafer. As a software package, ARKTOS comprises components in image processing, rule-based classification, …