Physical Sciences and Mathematics Commons^™

Spatiotemporal Databases: Models For Attracting Students To Research, Ágnes Bércesné Novák, Peter Revesz, Zsolt Tuza

CSE Conference and Workshop Papers

In higher education professors often make much effort to introduce their students to research. Unfortunately, the present standard database systems curriculum is composed of well-settled subjects that do not lead to research. The challenge is to bring the research frontier closer to students at beginner level. In this paper we describe how it can be done in the area of spatiotemporal databases. We propose a new database systems curriculum and illustrate its benefits by mentioning several highly succsesful student projects in some recent experimental introductory database systems courses that followed the new curriculum.

Flocking Over 3d Terrain, Joel Gompert

CSE Technical Reports

A method is presented for animating herds of animals that can follow terrain while being efficient enough to run in real-time. This method involves making simple modifications to Reynolds’ agent-based flocking algorithm. The modifications use only local properties of the terrain, and thus have low complexity. This method focuses on using terrain that can be described as an elevation grid, but it may be extendible to arbitrary terrain. The flocking algorithm with these modifications produces naturally behaving herds that follow the terrain. They will swerve around hills and attempt to follow paths that reduce energy expenditure. The terrain-following rule added …

Constraint Datalog In Trust Management, Scot Anderson

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

Constraint Datalog holds an increasing role in Trust Management. We discuss several Trust Management systems and give a description of the environment and requirements for Trust Management. Constraint Datalog using addition constraints and approximation theory provides an expressive semantic with which to describe security policies for credentials, delegations and authorizations. Approximation theory allows halting in Constraint Datalog over addition constraints. We use the decision problem of Diophantine equations to show that Constraint Datalog over addition constraints is complete. Combining these two concepts provides an approximately complete, safe language. The problem of constant additions to closed languages provides reasons for using …

Middleware Infrastructure For Parallel And Distributed Programming Models In Heterogeneous Systems, Jameela Al-Jaroodi, Nader Mohamed, Hong Jiang, David Swanson

School of Computing: Faculty Publications

In this paper, we introduce a middleware infrastructure that provides software services for developing and deploying high-performance parallel programming models and distributed applications on clusters and networked heterogeneous systems. This middleware infrastructure utilizes distributed agents residing on the participating machines and communicating with one another to perform the required functions. An intensive study of the parallel programming models in Java has helped identify the common requirements for a runtime support environment, which we used to define the middleware functionality. A Java-based prototype, based on this architecture, has been developed along with a Java Object-Passing Interface (JOPI) class library. Since this …

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

CSE 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

CSE 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

Department of Computer Science and Engineering: 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 …

Digitization In An Archival Environment, Sally Mckay

E-JASL 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, …

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

CSE 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 …

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

CSE 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.

E-Commerce Broker Prototype Implementation And Investigation, Rohini Krishnapura

CSE 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.

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

CSE 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 …

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

CSE 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, …

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

CSE 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 …

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

CSE 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 …

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

CSE 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 …

Priority-Based Lambda Scheduler, Kalpana Ganesan, Byrav Ramamurthy

CSE 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 …

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

CSE 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.

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

CSE 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 …

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

CSE 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 …

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

CSE 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, …

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

CSE 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.

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

CSE 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

CSE 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

CSE 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

CSE 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 Modeling Protein Superfamilies With Low Primary Sequence Conservation, Stephen Scott, H. Ji, P. Wen, Dmitri E. Fomenko, Vadim N. Gladyshev

CSE 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 …