Computer Sciences Commons^™

Arktos: An Intelligent System For Satellite Sea Ice Image Analysis, Leen-Kiat Soh

School of Computing: Technical Reports

We present an intelligent system for satellite sea ice image analysis named ARKTOS (Advanced Reasoning using Knowledge for Typing Of Sea ice). The underlying methodology of ARKTOS is to perform fully automated analysis of sea ice images by mimicking the reasoning process of sea ice experts and photo-interpreters. Hence, our approach is feature-based, rule-based classification supported by multisource data fusion and knowledge bases. A feature can be an ice floe, for example. ARKTOS computes a host of descriptors for that feature and then applies expert rules to classify the floe into one of several ice classes. ARKTOS also incorporates information …

Negotiation-Based Coalition Formation Model For Agents With Incomplete Information And Time Constraints, Leen-Kiat Soh

School of Computing: Technical Reports

In this paper we describe a coalition formation model for a cooperative multiagent system in which each agent has incomplete information about its dynamic and uncertain world and must respond to sensed events within time constraints. With incomplete information and uncertain world parameters while lacking time, an agent cannot afford organizing a rationally optimal coalition formation. Instead, our agents use a two-stage methodology. When an agent detects an event in the world, it first compiles a list of coalition candidates that it thinks would be useful, and then negotiates with the candidates. A negotiation is an exchange of information and …

Automated Ontology Learning For A Semantic Web, Christopher N. Hammack, Qingfeng Lin, Hai Huang, Stephen Scott, Sharad C. Seth

School of Computing: Technical Reports

By expressing web page content in a format that machines can understand, the semantic web provides huge possibilities for the Internet and for machine reasoning. Unfortunately, there is a considerable distance between the present-day World Wide Web and the semantic web of the future. The process of annotating the Web to make it semantic web-ready is quite long and not without resistance. In this paper one mechanism for semanticizing the Web is presented. This system is known as AutoSHOE, and it is capable of categorizing pages according to one of the present HTML semantic representations (Simple HTML Ontology Extensions) by …

Centralized Vs. Distributed Connection Management Schemes Under Different Traffic Patterns In Wavelength-Convertible Optical Networks, Lu Shen, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Centralized and Distributed methods are two connection management schemes in wavelength convertible optical networks. In the earlier work, the centralized scheme is said to have lower network blocking probability than the distributed one. Hence, much of the previous work in connection management has focused on the comparison of different algorithms in only distributed scheme or in only centralized scheme. However, we believe that the network blocking probability of these two connection management schemes depends, to a great extent, on the network traffic patterns and reservation times. Our simulation results reveal that the performance improvement (in terms of blocking probability) of …

An Analytical Model For Virtual Topology Reconfiguration In Optical Networks And A Case Study, Xi Yang, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

An analytical model for Virtual Topology Reconfiguration (VTR) in optical networks is developed. It aims at the optical networks with a circuit-based data plane and an IPlike control plane. By identifying and analyzing the important factors impacting the network performance due to VTR operations on both planes, we can compare the benefits and penalties of different VTR algorithms and policies. The best VTR scenario can be adaptively chosen from a set of such algorithms and policies according to the real-time network situations. For this purpose, a cost model integrating all these factors is created to provide a comparison criterion independent …

Two Algorithms For Shaped-Based Porosity Measures, Leen-Kiat Soh

School of Computing: Technical Reports

In this paper, we present two algorithms for shape-based porosity measures. Specifically, we describe two innovative attributes called perimeter porosity and area porosity as feature descriptors. Perimeter porosity refers to how “porous” or “weak” an image object is, while area porosity determines the degree of “branchiness” of an object. We show the applicability of the two measures through a SAR sea ice image classification example.

Dynamic Routing In Translucent Wdm Optical Networks, Xi Yang, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Translucent WDM optical networks use sparse placement of regenerators to overcome the impairments and wavelength contention introduced by fully transparent networks, and achieve a performance close to fully opaque networks with much less cost. Our previous study proved the feasibility of translucent networks using sparse regeneration technique. We addressed the placement of regenerators based on static schemes allowing only fixed number of regenerators at fixed locations. This paper furthers the study by proposing a suite of dynamical routing schemes. Dynamic allocation, advertisement and discovery of regeneration resources are proposed to support sharing transmitters and receivers between regeneration and access functions. …

A Set Of New Sea Ice Feature Descriptors For Sar Images, Leen-Kiat Soh

School of Computing: Technical Reports

In this paper, we present a set of algorithms for describing sea ice features in SAR images. These algorithms we have implemented and incorporated in the ARKTOS software package, an intelligent sea ice classification. These algorithms have unique characteristics. Some are extensions or adaptations of existing image processing techniques to the specific problem domain of satellite sea ice classification, while some are innovative designs, inspired by the aforementioned problem domain. These feature descriptors may be generalized to other remote sensing applications.

Dynamic Traffic Grooming Algorithms For Reconfigurable Sonet Over Wdm Networks, Shu Zhang, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

The emergence of Wavelength Division Multiplexing (WDM) technology provides the capability for increasing the bandwidth of Synchronous Optical Network (SONET) rings by grooming low-speed traffic streams onto different high-speed wavelength channels. Since the cost of SONET add-drop multiplexers (SADM) at each node dominates the total cost of these networks, how to assign the wavelength, groom in the traffic and bypass the traffic through the intermediate nodes has received a lot of attention from researchers recently.

Constraint Modeling And Reformulation In The Context Of Academic Task Assignment, Robert Glaubius, Berthe Y. Choueiry

School of Computing: Conference and Workshop Papers

We discuss the modeling and reformulation of a resource allocation problem, the assignment of graduate teaching assistants (GTAs) to courses. Our research contributes the following:

• Formulation of the GTA assignment problem as a nonbinary CSP.

• Design of a new convention for consistency checking to deal with over-constrained problem.

• Definition of a new network-decomposable nonbinary confinement constraint.

• Evaluation of the reformulation of confinement and equality constraints on 3 real-world data sets.

Constraint Modeling And Reformulation In The Context Of Academic Task Assignment, Robert Glaubius, Berthe Y. Choueiry

School of Computing: Conference and Workshop Papers

We discuss the modeling and reformulation of a resource allocation problem, the assignment of Graduate Teaching Assistants to courses in the University of Nebraska-Lincoln Computer Science Department. We formulate this problem as a non-binary Constraint Satisfaction Problem (CSP) and provide a new convention for consistency checking to deal with the over-constraindness of the problem and the practical requirement of our application. We introduce a new decomposable non-binary constraint, which we call confinement constraint, and describe its relevance in practical requirements of our application. We introduce an new decomposable non-binary constraint, which we call confinement constraint, and describe its relevance in …

A Novel Method To Improve The Test Efficiency Of Vlsi Tests, Hailong Cui, Sharad C. Seth, Shashank K. Mehta

School of Computing: Conference and Workshop Papers

This paper considers reducing the cost of test application by permuting test vectors to improve their defect coverage. Algorithms for test reordering are developed with the goal of minimizing the test cost. Best and worst case bounds are established for the performance of a reordered sequence compared to the original sequence of test application. SEMATECH test data and simulation results are used throughout to illustrate the ideas.

Prioritizing Test Cases For Regression Testing, Gregg Rothermel, Roland H. Untch, Chengyun Chu, Mary Jean Harrold

School of Computing: Faculty Publications

Test case prioritization techniques schedule test cases for execution in an order that attempts to increase their effectiveness at meeting some performance goal. Various goals are possible; one involves rate of fault detection - a measure of how quickly faults are detected within the testing process. An improved rate of fault detection during testing can provide faster feedback on the system under test and let software engineers begin correcting faults earlier than might otherwise be possible. One application of prioritization techniques involves regression testing - the retesting of software following modifications; in this context, prioritization techniques can take advantage of …

The Impact Of Test Suite Granularity On The Costeffectiveness Of Regression Testing, Gregg Rothermel, Sebastian Elbaum, Alexey Malishevsky, Praveen Kallakuri, Brian Davia

School of Computing: Technical Reports

Regression testing is an expensive testing process used to validate software following modifications. The cost-effectiveness of regression testing techniques varies with characteristics of test suites. One such characteristic, test suite granularity, involves the way in which test inputs are grouped into test cases within a test suite. Various cost-benefits tradeoffs have been attributed to choices of test suite granularity, but almost no research has formally examined these tradeoffs. To address this lack, we conducted several controlled experiments, examining the effects of test suite granularity on the costs and benefits of several controlled experiments, examining the effects of test suite granularity …

Restoration And Reconstruction From Overlapping Images For Multi-Image Fusion, Stephen E. Reichenbach, Jing Li

School of Computing: Faculty Publications

This paper describes a technique for restoring and reconstructing a scene from overlapping images. In situations where there are multiple, overlapping images of the same scene, it may be desirable to create a single image that most closely approximates the scene, based on the data in all of the available images. For example, successive swaths acquired by NASA’s moderate imaging spectrometer (MODIS) will overlap, particularly at wide scan angles, creating a severe visual artifact in the output image. Resampling the overlapping swaths to produce a more accurate image on a uniform grid requires restoration and reconstruction. The one-pass restoration and …

Understanding And Measuring The Sources Of Variation In The Prioritization Of Regression Test Suites, Sebastian Elbaum, David Gable, Gregg Rothermel

School of Computing: Conference and Workshop Papers

Test case prioritization techniques let testers order their test cases so that those with higher priority, according to some criterion, are executed earlier than those with lower priority. In previous work, we examined a variety of prioritization techniques to determine their ability to improve the rate of fault detection of test suites. Our studies showed that the rate of fault detection of test suites could be significantly improved by using more powerful prioritization techniques. In addition, they indicated that rate of fault detection was closely associated with the target program. We also observed a large quantity of unexplained variance, indicating …

Empirical Studies Of A Prediction Model For Regression Test Selection, Mary Jean Harrold, David Rosenblum, Gregg Rothermel, Elaine Weyuker

School of Computing: Faculty Publications

Regression testing is an important activity that can account for a large proportion of the cost of software maintenance. One approach to reducing the cost of regression testing is to employ a selective regression testing technique that 1) chooses a subset of a test suite that was used to test the software before the modifications, then 2) uses this subset to test the modified software. Selective regression testing techniques reduce the cost of regression testing if the cost of selecting the subset from the test suite together with the cost of running the selected subset of test cases is less …

Design Verification And Functional Testing Of Finite State Machines, Mark W. Weiss, Sharad C. Seth, Shashank K. Mehta, Kent L. Einspahr

School of Computing: Conference and Workshop Papers

The design of a finite state machine can be verified by simulating all its state transitions. Typically, state transitions involve many don’t care inputs that must be fully expanded for an exhaustive functional verification. However, by exploiting the knowledge about the design structure it is shown that only a few vectors from the fully expanded set suffice for both design verification and testing for manufacturing defects. The main contributions of the paper include a unified fault model for design errors and manufacturing faults and a function-based analysis of the circuit structure for the purpose of generating tests under the unified …

Diffserver: Application Level Differentiated Services For Web Servers, Gautam Rao, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Web content hosting, in which a Web server stores and provides Web access to documents for different customers, is becoming increasingly common. For example, a web server can host webpages for several different companies and individuals. Traditionally, Web Service Providers (WSPs) provide all customers with the same level of performance (best-effort service). Most service differentiation has been in the pricing structure (individual vs. business rates) or the connectivity type (dial-up access vs. leased line, etc.). This report presents DiffServer, a program that implements two simple, server-side, application-level mechanisms (server-centric and client-centric) to provide different levels of web service. The results …

A Generator Of Random Instances Of Binary Finite Constraint Satisfaction Problems With Controllable Levels Of Interchangeability, Hui Zou, Amy Beckwith, Berthe Y. Choueiry

School of Computing: Technical Reports

In order to test the performance of algorithms for solving Constraint Satisfaction Problems (CSPs), we must establish a large collection of CSP instances that meet a given set of specifications, such as the number of variables, domain size, constraint density, tightness, etc. The goal of this report is to describe a generator of instances that have a specified degree of interchangeability. An example of such a generator is described in (Freuder and Sabin 1997), which generates non-reflexive constraints and does not allow us to control concurrently the degree of interchangeability and tightness. We have developed a technique and written a …

Infrastructure Support For Controlled Experimentation With Software Testing And Regression Testing Techniques, Hyunsook Do, Sebastian Elbaum, Gregg Rothermel

School of Computing: Technical Reports

Where the creation, understanding, and assessment of software testing and regression testing techniques are concerned, controlled experimentation is an indispensable research methodology. Obtaining the infrastructure necessary to support such experimentation, however, is difficult and expensive. As a result, progress in experimentation with testing techniques has been slow, and empirical data on the costs and effectiveness of techniques remains relatively scarce. To help address this problem, we have been designing and constructing infrastructure to support controlled experimentation with testing and regression testing techniques. This paper reports on the challenges faced by researchers experimenting with testing techniques, including those that inform the …

Hierarchy-Based Access Control In Distributed Environments, Jean-Camille Birget, Xukai Zou, Guevara Noubir, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Access control is a fundamental concern in any system that manages resources, e.g., operating systems, file systems, databases and communications systems. The problem we address is how to specify, enforce, and implement access control in distributed environments. This problem occurs in many applications such as management of distributed project resources, e-newspaper and payTV subscription services.

Starting from an access relation between users and resources, we derive a user hierarchy, a resource hierarchy, and a unified hierarchy. The unified hierarchy is then used to specify the access relation in a way that is compact and that allows efficient queries. It is …

Hierarchical Ring Network Configuration And Performance Modeling, V. Carl Hamacher, Hong Jiang

School of Computing: Faculty Publications

Approximate analytical queuing network models for expected message packet delay in 2-level and 3-level hierarchical ring interconnection networks (INs) are developed. A major class of traffic carried by these INs consists of cache line transfers between processor caches and remote memory modules in shared-memory multiprocessors. Such traffic consists of short, fixed-length messages; they can be conveniently transported by the slotted-ring transmission technique which is studied here. The packet delay results derived from the models are shown to be quite accurate when checked against a simulation study. As well as facilitating analysis, the analytical models can be used to determine optimal …

Optimization Of Amplifier Placements In Switch-Based Optical Networks, Ling Zong, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Wavelength division multiplexing (WDM) offers a solution to the problem of exploiting the large bandwidth on optical links; it is the current favorite multiplexing technology for optical communication networks. Due to the high cost of an optical amplifier, it is desirable to strategically place the amplifiers throughout the network in a way that guarantees that all the signals are adequately amplified while minimizing the total number amplifiers being used. Previous studies all consider a star-based network. This paper demonstrates an original approach for solving the problem in switch-based WDM optical network assuming the traffic matrix is always the permutation of …

The Impact Of Software Evolution On Code Coverage Information, Sebastian Elbaum, David Gable, Gregg Rothermel

School of Computing: Conference and Workshop Papers

Many tools and techniques for addressing software maintenance problems rely on code coverage information. Often, this coverage information is gathered for a specific version of a software system, and then used to perform analyses on subsequent versions of that system without being recalculated. As a software system evolves, however, modifications to the software alter the software’s behavior on particular inputs, and code coverage information gathered on earlier versions of a program may not accurately reflect the coverage that would be obtained on later versions. This discrepancy may affect the success of analyses dependent on code coverage information. Despite the importance …

Combining Ordering Heuristics And Bundling Techniques For Solving Finite Constraint Satisfaction Problems, Amy Beckwith, Berthe Y. Choueiry

School of Computing: Technical Reports

We investigate techniques to enhance the performance of backtrack search procedure with forward-checking (FC-BT) for finding all solutions to a finite Constraint Satisfaction Problem (CSP). We consider ordering heuristics for variables and/or values and bundling techniques based on the computation of interchangeability. While the former methods allow us to traverse the search space more effectively, the latter allow us to reduce it size. We design and compare strategies that combine static and dynamic versions of these two approaches. We show empirically the utility of dynamic variable ordering combined with dynamic bundling in both random problems and puzzles.

Adaptive Segmentation Of Document Images, Don Sylwester, Sharad C. Seth

School of Computing: Conference and Workshop Papers

A single-parameter text-line extraction algorithm is described along with an efficient technique for estimating the optimal value for the parameter for individual images without need for ground truth. The algorithm is based on three simple tree operations, cut, glue and flip. An XY-tree representing the segmentation is incrementally transformed to reflect a change in the parameter while intrinsic measures of the cost of the transformation are used to detect when specific tree operations would cause an error if they were performed, allowing these errors to be avoided. The algorithm correctly identified 98.8% of the area of the ground truth bounding …

Scalable Web Server Clustering Technologies, Trevor Schroeder, Steve Goddard, Byrav Ramamurthy

School of Computing: Faculty Publications

The exponential growth of the Internet, coupled with the increasing popularity of dynamically generated content on the World Wide Web, has created the need for more and faster Web servers capable of serving the over 100 million Internet users. Server clustering has emerged as a promising technique to build scalable Web servers. In this article we examine the seminal work, early products, and a sample of contemporary commercial offerings in the field of transparent Web server clustering. We broadly classify transparent server clustering into three categories.

Operational Evaluation Of A Knowledge-Based Sea Ice Classification System, Denise Gineris, Cheryl Bertoia, Mary Ruth Keller, Leen-Kiat Soh, Costas Tsatsoulis

School of Computing: Conference and Workshop Papers

ARKTOS (Advanced Reasoning Using Knowledge for Typing of Sea Ice) is a fully automated intelligent sea ice classification system. ARKTOS is in use at the U.S. National Ice Center (NIC) for daily operations related to the NIC’S task of mapping the ice covered oceans. ARKTOS incorporates image processing, input from ancillary data, and artificial intelligence (AI) to analyze and classify RADARSAT Synthetic Aperture Radar (SAR) imagery. The NIC and Naval Research Laboratory (NRL/ERIM) have been testing and evaluating ARKTOS through the freeze-up, winter, melt-out and summer seasons of the Beaufort Sea. In this paper we outline the development and evolution …

An Empirical Study Of The Effects Of Incorporating Fault Exposure Potential Estimates Into A Test Data Adequacy Criterion, Wei Chen, Gregg Rothermel, Roland H. Untch, Jeffery Von Ronne

School of Computing: Technical Reports

Code-coverage-based test data adequacy criteria typically treat all code components as equal. In practice, however, the probably that a test case can expose a fault in a code component varies: some faults are more easily revealed than others. Thus, researchers have suggested that if we could estimate the probability that a fault in a code component will cause a failure, we could use this estimate to determine the number of executions of a component that are required to achieve a certain level of confidence in that component’s correctness. This estimate in turn could be used to improve the fault-detection effectiveness …