Computer Sciences Commons^™

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

School of Computing: Faculty Publications

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 the traffic, and bypass the traffic through the intermediate nodes has received a lot of attention from researchers recently. Moreover, the traffic pattern of the optical network changes from time to time. How to develop dynamic reconfiguration algorithms for traffic grooming is an important issue. In …

Two-Dimensional Cubic Convolution, Stephen E. Reichenbach, Frank Geng

School of Computing: Faculty Publications

This paper develops two-dimensional (2-D), nonseparable, piecewise cubic convolution (PCC) for image interpolation. Traditionally, PCC has been implemented based on a one-dimensional (1-D) derivation with a separable generalization to two dimensions. However, typical scenes and imaging systems are not separable, so the traditional approach is suboptimal. We develop a closed-form derivation for a two-parameter, 2-D PCC kernel with support [-2, 2] [-2, 2] that is constrained for continuity, smoothness, symmetry, and flat-field response. Our analyses using several image models, including Markov random fields, demonstrate that the 2-D PCC yields small improvements in interpolation fidelity over the traditional, separable approach. The …

Authoritative Citation Knn Learning With Noisy Training Datasets, Leen-Kiat Soh, Joseph Bernadt

School of Computing: Technical Reports

In this paper, we investigate the effectiveness of Citation K-Nearest Neighbors (KNN) learning with noisy training datasets. We devise an authority measure associated with each training instance that changes based on the outcome of Citation KNN classification. The authority is increased when a citer’s classification had been right; and vice versa. We show that by modifying only these authority measures, the classification accuracy of Citation KNN improves significantly in a variety of datasets with different noise levels. We also identify the general characteristics of a dataset that affect the improvement percentages. We conclude that the new algorithm is able to …

Dvsst: A Dynamic Voltage Scaling Algorithm For Sporadic 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 canonical sporadic task model. A DVS algorithm, called DVSST, is presented that can be used with sporadic tasks in conjunction with the preemptive EDF scheduling algorithm. The algorithm is proven to guarantee each task meets its deadline while saving the maximum amount of energy possible with processor frequency scaling when tasks execute with their worst-case execution times.
DVSST was implemented in the &#;C/OS-II real-time operating …

User Interface Improvement For Mlpq System, Shasha Wu

School of Computing: Dissertations, Theses, and Student Research

This thesis describes the experience of migrating the MLPQ constraint database system, a complex standalone Multiple Document Interface (MDI) application, to a server-based remote accessible application. Centralized, standalone MDI application is a common style for personal software products in Windows. For a database management system, server-based, thin-client computing is a more popular infrastructure. Migrating an existing standalone constraint database application to be a web accessible constraint database server is the main goal of this thesis. This migration process provides a method for the constraint database system to collaborate with other specific applications. We rebuild the desktop MLPQ constraint database system …

E-Commerce Broker Prototype Implementation And Investigation, Rohini Krishnapura

School of Computing: Technical Reports

Personalization has become a popular solution to today’s Ecomerce challenges. Various personalization techniques have been researched and marketed. But, one technique may not suit all businesses. What is required is a mechanism to enable different policies based possibly on different personalization techniques. The Ebroker architecture presented here provides a mechanism to enable different policies with minimal effort. We present here the various components of the architecture as well as the features that the architecture provides. The details of a prototype design and implementation are also discussed.

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.

A Dynamic Real-Time Scheduling Algorithm For Reduced Energy Consumption In I/O Devices, Rohini Krishnapura, Steve Goddard

School of Computing: Technical Reports

In real-time systems, Dynamic Power Management (DPM) techniques have traditionally centered on the CPU with less focus given to I/O. However, I/O-based DPM techniques have been popularly researched in non-real-time systems. These techniques focus on switching I/O devices to low power states based on some policy. These methods, however, are not applicable to realtime environments because of the non-deterministic nature of the policies. Recently, scheduling techniques to reduce power consumption of I/O devices in real-time systems have emerged. In this paper, we propose an online task scheduling algorithm, Slack Utilization for Reduced Energy (SURE), which utilizes slack in periodic task …

On Modeling Protein Superfamilies With Low Primary Sequence Conservation, Stephen Scott, H. Ji, P. Wen, Dmitri E. Fomenko, Vadim N. Gladyshev

School of Computing: Technical Reports

We present several algorithms for identifying thioredoxin (Trx)-fold proteins containing a conserved CxxC motif (two cysteines separated by two residues). The low conservation of primary sequence in this protein superfamily makes conventional methods 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 Trx-fold proteins via hidden Markov models, decision trees, and algorithms in the multipleinstance learning model. In 9-fold and 12-fold jack-knife tests, some of our models performed quite well, with high …

On Generalized Multiple-Instance Learning, Stephen Scott, Jun Zhang, Joshua Brown

School of Computing: Technical Reports

We describe a generalization of the multiple-instance learning model in which a bag’s label is not based on a single instance’s proximity to a single target point. Rather, a bag is positive if and only if it contains a collection of instances, each near one of a set of target points. We list potential applications of this model (robot vision, content-based image retrieval, protein sequence identification, and drug discovery) and describe target concepts for these applications that cannot be represented in the conventional multiple-instance learning model. We then adapt a learning-theoretic algorithm for learning in this model and present empirical …

Low-Energy Bist Design For Scan-Based Logic Circuits, Bhargab B. Bhattacharya, Sharad C. Seth, Sheng Zhang

School of Computing: Conference and Workshop Papers

In a random testing environment, a significant amount of energy is wasted in the LFSR and in the CUT by useless patterns that do not contribute to fault dropping. Another major source of energy drainage is the loss due to random switching activity in the CUT and in the scan path between applications of two successive vectors. In this work, a new built-in self-test (BIST) scheme for scan-based circuits is proposed for reducing such energy consumption. A mapping logic is designed which modifies the state transitions of the LFSR such that only the useful vectors are generated according to a …

Digitization In An Archival Environment, Sally Mckay

E-JASL: Electronic Journal of Academic and Special Librarianship (1999-2009, Volumes 1-10)

Introduction

Cultural institutions such as museums, libraries, archives, and historical societies house remarkable collections of cultural artifacts. It is the responsibility of the staff working for those institutions to preserve, protect and provide responsible stewardship for the materials, and to the best of their ability, provide continued long-term access (Russell, 2000).

Advances in technology allow institutions to provide expanded access and education; however, there are important priorities that must be addressed prior to embarking on a digital conversion project.

Digitization in an archival environment includes taking a physical object or analog item, such as an art object, a tape recording, …

Double-Tree Scan: A Novel Low-Power Scan-Path Architecture, Bhargab B. Bhattacharya, Sharad C. Seth, Sheng Zhang

School of Computing: Conference and Workshop Papers

In a scan-based system with a large number of flip-flops, a major component of power is consumed during scan-shift and clocking operation in test mode. In this paper, a novel scan-path architecture called double-tree scan (DTS) is proposed that drastically reduces the scan-shift and clock activity during testing. The inherent combinatorial properties of double-tree structure are employed to design the scan architecture, clock gating logic, and a simple shift controller. The design is independent of the structure of the circuit-under-test (CUT) or its test set. It provides a significant reduction both in instantaneous and average power needed for clocking and …

Priority-Based Lambda Scheduler, Kalpana Ganesan, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Optical networks provide a new dimension to meet the demands of exponentially growing traffic. Optical packet switching requires a good switch architecture, which eliminates the O/E/O conversion as much as possible. Wavelength Division Multiplexing (WDM) provides a breakthrough to exploit the huge bandwidth of the optical fiber. Different applications have different requirements, which necessitate employing differentiated services. This paper presents the idea of a priority-based λ-scheduler, where the packets are differentiated into different classes and services are provided accordingly. For example, class 0 can correspond to non real time applications like email and ftp, while class 1 can correspond to …

Learning Monotone Dnf Using Spp Teaching Assistant, N. V. Vinodchandran

School of Computing: Technical Reports

In this paper we prove a new upper bound on learning monotone DNF formulae in an exact learning model called the teaching assistant model. This model, introduced in one of our earlier works, uses teaching assistant classes for classifying the complexity of learning problems. Teaching assistant classes are a learning-theoretic analog of complexity classes. We show that monotone DNF are learnable using a teaching assistant in the class SPP. On the other hand, concept classes such as k-CNF or Boolean circuits are not learnable using an SPP teaching assistant unless Np SPP. We also observe that the recent SPP algorithm …

Agent Based Intrusion Detection And Response System For Wireless Lans, Mohan K Chirumamilla, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Wireless LAN technology, despite the numerous advantages it has over competing technologies, has not seen widespread deployment. A primary reason for markets not adopting this technology is its failure to provide adequate security. Data that is sent over wireless links can be compromised with utmost ease. In this project, we propose a distributed agent based intrusion detection and response system for wireless LANs that can detect unauthorized wireless elements like access points, wireless clients that are in promiscuous mode etc. The system reacts to intrusions by either notifying the concerned personnel, in case of rogue access points and promiscuous nodes, …

A Literature Review On Learner Control Strategies In Software Tutoring Systems, Xin Li, Leen-Kiat Soh

School of Computing: Technical Reports

This paper is a comprehensive research review on the learner control strategies in software tutoring systems. With the application of more computer techniques in education and the involvement of more adults in software tutoring systems, the learner control strategy has become more appreciated than tutor control or program control. In this paper, the efficiency and necessity of learner control in software tutoring systems is discussed through the description of learning mechanism. Some typical applications of learner control strategies in software tutoring systems are presented. The available learner control strategies are classified from two perspectives: educational theory, and software mechanism. Finally, …

Inter-Domain Dynamic Routing In Multi-Layer Optical Transport Networks, Xi Yang, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Next-generation optical transport networks will automatically and dynamically provision end-to-end connections. In this paper, we study the problem of inter-domain dynamic routing under a multi-layer multi-domain network model, which allows the end-to-end connections to be set up not only across multiple routing domains but also through two transport layers: the optical layer and the digital layer. In this model, a connection can traverse the domain boundary either through optical bypass or through optical-electrical-optical (O/E/O) processing. We propose an inter-domain dynamic routing scheme with modest time complexity to address the problem from an algorithmic perspective.

Teaching A Multiagent Systems Class With Game Days: Designs And Lessons Learned, Leen-Kiat Soh

School of Computing: Technical Reports

In the Fall semester of 2002, I introduced and taught a class in Multiagent Systems. The class was aimed for seniors (with special permission) and graduate students in Computer Science, covering some breadth and depth of issues in multiagent systems. One of the requirements was participation in four Game Days. On each Game Day, student teams competed against each other in games related to issues such as auction, task allocation, coalition formation, and negotiation. This article documents my designs of and lessons learned from these Game Days. The Game Days were very successful. Through role-playing, the students were motivated and …

A Novel Fiber Delay Line Buffering Architecture For Optical Packet Switching, Lin Li, Stephen Scott, Jitender S. Deogun

School of Computing: Conference and Workshop Papers

Due to the lack of optical random access memory, optical fiber delay line (FDL) is currently the only way to implement optical buffering. Feed-forward and feedback are two kinds of FDL structures in optical buffering. Both have advantages and disadvantages. In this paper, we propose a more effective hybrid FDL architecture that combines the merits of both schemes. The core of this switch is the arrayed waveguide grating (AWG) and the tunable wavelength converter (TWC). It requires smaller optical device sizes and fewer wavelengths and has less noise than feedback architecture. At the same time, it can facilitate preemptive priority …

Patterns And Trends Of Soil Climate Regimes And Drought Events In The Northern Great Plains, William J. Waltman, Stephen M. Goddard, S. E. Reichenbach, Mark Svoboda, Michael Hayes, J. S. Peake

School of Computing: Conference and Workshop Papers

Drought is the dominant process of crop loss nationally and within Nebraska. Nearly twothirds of the 18.6 million harvested acres are covered by crop insurance (USDA/RMA, 2003; USDA/NASS, 2003). For the most part, Nebraska’s crop losses range from $50 to 75 million in non-drought years, but the losses approach nearly $200 million in drought years, such as 2000. The past growing season (2002) crop losses are projected to greatly exceed $375 million in Nebraska and more than $4 billion nationally (USDA/RMA, 2003). The analysis and understanding of drought processes in the Great Plains is an important component to developing drought …

A New Efficient Algorithm For Solving The Simple Temporal Problem, Lin Xu, Berthe Y. Choueiry

School of Computing: Conference and Workshop Papers

Motivation for Simple Temporal Problem (STP)

STP - TCSP - DTP

Consistency properties & algorithms

General CSPs

STP

Contributions

Use (improved) PPC for STP

Refine it into ΔSTP

Evaluation on random instances, 3 generators

Summary & new results

A New Efficient Algorithm For Solving The Simple Temporal Problem, Lin Xu, Berthe Y. Choueiry

School of Computing: Conference and Workshop Papers

In this paper we propose a new efficient algorithm, the Δ STP-solver, for computing the minimal network of the Simple Temporal Problem (STP). This algorithm achieves high performance by exploiting a topological property of the constraint graph (i.e., triangulation) and a semantic property of the constraints (i.e., convexity) in light of the results reported by Bliek and Sam-Haroud [1], which were presented for general CSPs and have not yet been applied to temporal networks. Importantly, we design the constraint propagation in Δ STP-solver to operate on triangles instead of operating on edges and implicitly guarantee the decomposition of …

On Approximating Weighted Sums With Exponentially Many Terms, Deepak Chawla, Lin Li, Stephen Scott

School of Computing: Technical Reports

Multiplicative weight-update algorithms such as Winnow and Weighted Majority have been studied extensively due to their on-line mistake bounds’ logarithmic dependence on N, the total number of inputs, which allows them to be applied to problems where N is exponential. However, a large N requires techniques to efficiently compute the weighted sums of inputs to these algorithms. In special cases, the weighted sum can be exactly computed efficiently, but for numerous problems such an approach seems infeasible. Thus we explore applications of Markov chain Monte Carlo (MCMC) methods to estimate the total weight. Our methods are very general and …

Indirect Symbolic Correlation Approach To Unsegmented Text Recognition, George Nagy, Sharad C. Seth, Y. Lin, Shashank K. Mehta

School of Computing: Conference and Workshop Papers

The new non-parametric approach to unsegmented text recognition builds two bipartite graphs that result from the feature-level and lexical comparisons of the same word against a reference string which need not include the query word. The lexical graph preserves the relative order of edges in the feature graph corresponding to correctly recognized features. This observation leads to a subgraph-matching formulation of the recognition problem. An initial implementation proves the robustness of the approach for up-to 20% noise introduced in the feature-level graph.

Testing Homogeneous Spreadsheet Grids With The “What You See Is What You Test” Methodology, Margaret Burnett, Andrei Sheretov, Gregg Rothermel

School of Computing: Faculty Publications

Although there has been recent research into ways to design environments that enable end users to create their own programs, little attention has been given to helping these end users systematically test their programs. To help address this need in spreadsheet systems - the most widely used type of end-user programming language - we previously introduced a visual approach to systematically testing individual cells in spreadsheet systems. However, the previous approach did not scale well in the presence of largely homogeneous grids, which introduce problems somewhat analogous to the array-testing problems of imperative programs. In this paper, we present two …

A Generator For Random Non-Binary Finite Constraint Satisfaction Problems, Hui Zou, Berthe Y. Choueiry, Amy M. Davis

School of Computing: Technical Reports

The paper describes an implementation of a generator of random instances of non-binary constraint satisfaction problems that meets a given set of specifications. This is a continuation of the work we started in Hui Zou, Amy M. Beckwith, and Berthe Y. Choueiry. A Generator of Random Instances of Binary Finite Constraint Satisfaction Problems with Controllable Levels of Interchangeability. Working note, Department of Computer Science and Engineering, University of Nebraska-Lincoln, 2001. July, 2001.

The program is designed to generate random instances of Constraint Satisfaction Problems (CSPs) that meet a set of specified parameters, such as the number of variables, domain size, …

Test Case Prioritization: A Family Of Empirical Studies, Sebastian Elbaum, Alexey G. Malishevsky, Gregg Rothermel

School of Computing: Faculty Publications

To reduce the cost of regression testing, software testers may prioritize their test cases so that those which are more important, by some measure, are run earlier in the regression testing process. One potential goal of such prioritization is to increase a test suite’s rate of fault detection. Previous work reported results of studies that showed that prioritization techniques can significantly improve rate of fault detection. Those studies, however, raised several additional questions: 1) Can prioritization techniques be effective when targeted at specific modified versions; 2) what trade-offs exist between fine granularity and coarse granularity prioritization techniques; 3) can the …

Cxquery: A Novel Xml Query Language, Peter Revesz, Yi Chen

School of Computing: Conference and Workshop Papers

XML is becoming the data exchange standard on the Internet. Previously proposed XML query languages, such as XQuery, Quilt, YALT, Lorel, and XML-QL, lack schema definition of the query result; therefore, they are limited for defining views, integrating data, updating, and further querying, all of which are often needed in e-Business applications. We propose a novel XML query language called CXQuery, which defines the schema of the query results explicitly and can easily define views, and integrate, update, and query XML data. In addition, CXQuery can express spatial and spatio-temporal queries using a constraint-based querying approach.

Techniques For Bundling The Solution Space Of Finite Constraint Satisfaction Problems, Berthe Y. Choueiry, Amy Beckwith

School of Computing: Technical Reports

We study the backtrack-search procedure with forward checking (FCBT) for finding all solutions to a finite Constraint Satisfaction Problem (CSP). We describe how to use dynamic interchangeability to enhance the performance of search and represent the solution space in a compact manner. We evaluate this strategy (FC-DNPI) in terms of the numbers of nodes visited, constraints checked, and solution bundles generated by comparing it, theoretically and empirically, to other search strategies. We show that FC-DNPI is equivalent to search with the Cross Product Representation (FC-CPR) of [Hubbe and Freuder 1992] in terms of the numbers of solution bundles and constraint …