Computer Sciences Commons^™

Materialized View Algorithms, Yubo Fan

Dissertations and Theses

A data warehouse is a stand-alone repository of integrated information available for decision support OLAP querying and analysis. Aggregate views can be materialized (stored in disk) to improve query performance in a data warehouse.

Several static and dynamic algorithms for selecting materialized aggregate views (MA V) in a data warehouse are proposed in this thesis. The algorithms are then compared by running a simulation system, which can be configured to compare several algorithms on different type of data warehouses. Simulation results for static algorithms are presented to show that several proposed algorithms perform close to an existing good algorithm (HRU …

Velocity Estimation Via A Neural Network Enhanced By Classical Detection Algorithms, Zeki Berk Hamşioğlu

Electrical & Computer Engineering Theses & Dissertations

The goal of this research is to show how to solve a velocity estimation problem using a neural network connected to an array of sensors. Motivated by biological studies involving insect vision, the neural network utilized is a member of a class of shunting neural networks. When an object moves across the face of the sensor array, the neural network's pulse response is first temporally located using classical M-ary detection techniques. Both the deterministic and stochastic cases are considered. Then the network's pulse response is post-processed via an existing velocity estimation algorithm based on a Volterra series model of the …

Modeling And Comparison Of Wormhole Routed Mesh And Torus Networks, Ronald I. Greenberg, Lee Guan

Computer Science: Faculty Publications and Other Works

2D-mesh and torus networks have often been proposed as the interconnection pattern for parallel computers. In addition, wormhole routing has increasingly been advocated as a method of reducing latency. Most analysis of wormhole routed networks, however, has focused on the torus and the broader class of k-ary n-cubes to which it belongs. This paper presents a performance model for the wormhole routed mesh, and it compares the performance of the mesh and torus based on theoretical and empirical analyses.

Fast Discrete Polynomial Transforms With Applications To Data Analysis For Distance Transitive Graphs, J. R. Driscoll, D. M. Healy, D. N. Rockmore

Dartmouth Scholarship

Let $\poly = \{P_0,\dots,P_{n-1}\}$ denote a set of polynomials with complex coefficients. Let $\pts = \{z_0,\dots,z_{n-1}\}\subset \cplx$ denote any set of {\it sample points}. For any $f = (f_0,\dots,f_{n-1}) \in \cplx^n$, the {\it discrete polynomial transform} of f (with respect to $\poly$ and $\pts$) is defined as the collection of sums, $\{\fhat(P_0),\dots,\fhat(P_{n-1})\}$, where $\fhat(P_j) = \langle f,P_j \rangle = \sum_{i=0}^{n-1} f_iP_j(z_i)w(i)$ for some associated weight function w. These sorts of transforms find important applications in areas such as medical imaging and signal processing.

In this paper, we present fast algorithms for computing discrete orthogonal polynomial transforms. For a system …

An Improved Analytical Model For Wormhole Routed Networks With Application To Butterfly Fat-Trees, Ronald I. Greenberg, Lee Guan

Computer Science: Faculty Publications and Other Works

A performance model for wormhole routed interconnection networks is presented and applied to the butterfly fat-tree network. Experimental results agree very closely over a wide range of load rate. Novel aspects of the model, leading to accurate and simple performance predictions, include (1) use of multiple-server queues, and (2) a general method of correcting queuing results based on Poisson arrivals to apply to wormhole routing. These ideas can also be applied to other networks.

Dynamic Load Distribution In Mist, K. Al-Saqabi, R. M. Prouty, Dylan Mcnamee, Steve Otto, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This paper presents an algorithm for scheduling parallel applications in large-scale, multiuser, heterogeneous distributed systems. The approach is primarily targeted at systems that harvest idle cycles in general-purpose workstation networks, but is also applicable to clustered computer systems and massively parallel processors. The algorithm handles unequal processor capacities, multiple architecture types and dynamic variations in the number of processes and available processors. Scheduling decisions are driven by the desire to minimize turnaround time while maintaining fairness among competing applications. For efficiency, the virtual processors (VPs) of each application are gang scheduled on some subset of the available physical processors.

Specification And Verification Of Generic Cell Rate Algorithms In Pvs, Huseyin Ozgungor

Electrical & Computer Engineering Theses & Dissertations

Formal verification methods have been considered as a powerful complementary approach to define standards and to prove correctness of the systems. In this work, formal specification of Generic Cell Rate Algorithms are defined and proved. The specification process enables standardization for constructing Generic Cell Rate Algorithms. Standardization is an important process in the Asynchronous Transfer Mode (ATM) networks. By employing formal methods, the necessary standards could be constructed to allow different algorithms to be employed which still meet system requirements. Those system requirements are quantified in the Quality of Service (QOS).

Congestion management is a vital concept for networks in …

Single Row Routing: Theoretical And Experimental Performance Evaluation, And New Heuristic Development, David A. Hysom

Computer Science Theses & Dissertations

The Single Row Routing Problem (SRRP) is an abstraction arising from real-world multilayer routing concerns. While NP-Complete, development of efficient SRRP routing heuristics are of vital concern to VLSI design. Previously, researchers have introduced various heuristics for SRRP; however, a comprehensive examination of SRRP behavior has been lacking.

We are particularly concerned with the street-congestion minimization constraint, which is agreed to be the constraint of greatest interest to industry. Several theorems stating lower bounds on street congestion are known. We show that these bounds are not tight in general, and argue they may be in error by at least 50% …

Feedback Control Solutions To Network Level User-Equilibrium Real-Time Dynamic Traffic Assignment Problems, Pushkin Kachroo, Kaan Ozbay

Electrical & Computer Engineering Faculty Research

A new method for performing dynamic traffic assignment (DTA) is presented which is applicable in real time, since the solution is based on feedback control. This method employs the design of nonlinear H∞ feedback control systems which is robust to certain class of uncertainties in the system. The solution aims at achieving user equilibrium on alternate routes in a network setting.

Investigating The Use Of Kalman Filtering Approaches For Dynamic Origin-Destination Trip Table Estimation, Pushkin Kachroo, Kaan Ozbay, Arvind Narayanan

Electrical & Computer Engineering Faculty Research

This paper studies the applicability of Kalman filtering approaches for network wide traveler origin-destination estimation from link traffic volumes. The paper evaluates the modeling assumptions of the Kalman filters and examines the implications of such assumptions.

Cascade Artmap: Integrating Neural Computation And Symbolic Knowledge Processing, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

This paper introduces a hybrid system termed cascade adaptive resonance theory mapping (ARTMAP) that incorporates symbolic knowledge into neural-network learning and recognition. Cascade ARTMAP, a generalization of fuzzy ARTMAP, represents intermediate attributes and rule cascades of rule-based knowledge explicitly and performs multistep inferencing. A rule insertion algorithm translates if-then symbolic rules into cascade ARTMAP architecture. Besides that initializing networks with prior knowledge can improve predictive accuracy and learning efficiency, the inserted symbolic knowledge can be refined and enhanced by the cascade ARTMAP learning algorithm. By preserving symbolic rule form during learning, the rules extracted from cascade ARTMAP can be compared …

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

We give algorithms to minimize density for VLSI channel routing problems with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, we improve previous results for running time and space by a factor of L/\lgn and L, respectively, where L is the channel length, and n is the number of terminals.

Inductive Neural Logic Network And The Scm Algorithm, Ah-Hwee Tan, Loo-Nin Teow

Research Collection School Of Computing and Information Systems

Neural Logic Network (NLN) is a class of neural network models that performs both pattern processing and logical inferencing. This article presents a procedure for NLN to learn multi-dimensional mapping of both binary and analog data. The procedure, known as the Supervised Clustering and Matching (SCM) algorithm, provides a means of inferring inductive knowledge from databases. In contrast to gradient descent error correction methods, pattern mapping is learned by an inductive NLN using fast and incremental clustering of input and output patterns. In addition, learning/encoding only takes place when both the input and output match criteria are satisfied in a …

Genetic Algorithms For The Extended Gcd Problem, Jonathan P. Sorenson

Scholarship and Professional Work - LAS

We present several genetic algorithms for solving the extended greatest common divisor problem. After defining the problem and discussing previous work, we will state our results.

Adaptive Multicast Routing In Wormhole Networks, Ran Libeskind-Hadas, Tom Hehre '96, Andrew Hutchings '98, Mark Reyes '98, Kevin Watkins '97

All HMC Faculty Publications and Research

Multicast communication has applications in a number of fundamental operations in parallel computing. An effective multicast routing algorithm must be free from both livelock and deadlock while minimizing communication latency. We describe two classes of multicast wormhole routing algorithms that employ the multi-destination wormhole hardware mechanism proposed by Lin et al. [12] and Panda et al. [17]. Specific examples of these classes of algorithms are described and experimental results suggests that such algorithms enjoy low communication latencies across a range of network loads.

Resolution Of Local Inconsistency In Identification, Douglas Ray Anderson, Martin Zwick

Complex Systems Faculty Publications and Presentations

This paper reports an algorithm for the resolution of local inconsistency in information-theoretic identification. This problem was first pointed out by Klir as an important research area in reconstructability analysis. Local inconsistency commonly arises when an attempt is made to integrate multiple data sources, i.e., contingency tables, which have differing common margins. For example, if one ha)s an AB table and a BC table, the B margins obtained from the two tables may disagree. If the disagreement can be assigned to sampling error, then one can arrive at a compromise B margin, adjust the original AB and BC tables to …

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that are known to have linear- time sequential solutions rather than limiting attention to the "river-routing" context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O(lgN) time on a CREW PRAM or O(lgN / lglgN) time on a (common) CRCW PRAM, both with optimal work (processor- time product) of O(N), where N is the number of terminals. For the offset range problem, we obtain the same time and processor …

Weighted Mahalanobis Distance For Hyper-Ellipsoidal Clustering, Khaled S. Younis

Theses and Dissertations

Cluster analysis is widely used in many applications, ranging from image and speech coding to pattern recognition. A new method that uses the weighted Mahalanobis distance (WMD) via the covariance matrix of the individual clusters as the basis for grouping is presented in this thesis. In this algorithm, the Mahalanobis distance is used as a measure of similarity between the samples in each cluster. This thesis discusses some difficulties associated with using the Mahalanobis distance in clustering. The proposed method provides solutions to these problems. The new algorithm is an approximation to the well-known expectation maximization (EM) procedure used to …

Analysis Of Linkage-Friendly Genetic Algorithms, Laurence D. Merkle

Theses and Dissertations

Evolutionary algorithms (EAs) are stochastic population-based algorithms inspired by the natural processes of selection, mutation, and recombination. EAs are often employed as optimum seeking techniques. A formal framework for EAs is proposed, in which evolutionary operators are viewed as mappings from parameter spaces to spaces of random functions. Formal definitions within this framework capture the distinguishing characteristics of the classes of recombination, mutation, and selection operators. EAs which use strictly invariant selection operators and order invariant representation schemes comprise the class of linkage-friendly genetic algorithms (lfGAs). Fast messy genetic algorithms (fmGAs) are lfGAs which use binary tournament selection (BTS) with …

Refined Genetic Algorithms For Polypeptide Structure Prediction, Charles E. Kaiser Jr.

Theses and Dissertations

Accurate and reliable prediction of macromolecular structures has eluded researchers for nearly 40 years. Prediction via energy minimization assumes the native conformation has the globally minimal energy potential. An exhaustive search is impossible since for molecules of normal size, the size of the search space exceeds the size of the universe. Domain knowledge sources, such as the Brookhaven PDB can be mined for constraints to limit the search space. Genetic algorithms (GAs) are stochastic, population based, search algorithms of polynomial (P) time complexity that can produce semi-optimal solutions for problems of nondeterministic polynomial (NP) time complexity such as PSP. Three …

Inference Algorithm Performance And Selection Under Constrained Resources, Brett J. Borghetti

Theses and Dissertations

Knowing that reasoning over probabilistic networks is, in general, NP-hard, and that most reasoning environments have limited resources, we need to select algorithms that can solve a given problem as fast as possible. This thesis presents a method for predicting the relative performance of reasoning algorithms based on the domain characteristics of the target knowledge structure. Armed with this knowledge, the research shows how to choose the best algorithm to solve the problem. The effects of incompleteness of the knowledge base at the time of inference is explored, and requirements for reasoning over incompleteness are defined. Two algorithms for reasoning …

A Computational Paradigm On Network-Based Models Of Computation, Venkatavasu Bokka

Computer Science Theses & Dissertations

The maturation of computer science has strengthened the need to consolidate isolated algorithms and techniques into general computational paradigms. The main goal of this dissertation is to provide a unifying framework which captures the essence of a number of problems in seemingly unrelated contexts in database design, pattern recognition, image processing, VLSI design, computer vision, and robot navigation. The main contribution of this work is to provide a computational paradigm which involves the unifying framework, referred to as the multiple Query problem, along with a generic solution to the Multiple Query problem.

To demonstrate the applicability of the paradigm, a …

Monte Carlo Simulations Of Photoemission Characteristics From Gaas And Diamond, Abhishek Srivastava

Electrical & Computer Engineering Theses & Dissertations

Monte Carlo based numerical simulations were performed to study photoemission from GaAs and diamond. The central goal was to assess the potential for NEA photoemission from diamond, and to predict its characteristics. The GaAs material system was also included in the simulation study to provide: (i) calibration and validation of the numerical model developed by carefully matching the simulation results with available experimental data, and (ii) quantitative comparisons between the response characteristics of diamond and the better known GaAs system.

Predictions of the energy distribution, temporal response and angular distribution of emitted electrons were obtained. Effects of various parameters, such …

Resource/Dataflow Graph Operating System Development, Sriram J. Coimbatore

Electrical & Computer Engineering Theses & Dissertations

Implementation of a new dataflow schedule model is the objective of this thesis. The dataflow model algorithm called the resource/dataflow graph model is implemented on a peer-to-peer communication network comprising of six personal computers. This dataflow model is implemented making use of an earlier dataflow model called ATAMM (Algorithm to Architecture Mapping Model) developed by ODU and National Aeronautics and Space Administration (NASA). Development issues include modification of the RDFG testbed operating system and a scheme to transfer data buffers using the ethernet channel from one processor to another processor. This, in turn, equips each sub-module of an application with …

Single-Layer Channel Routing And Placement With Single-Sided Nets, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

This paper considers the optimal offset, feasible offset, and optimal placement problems for a more general form of single-layer VLSI channel routing than has usually been considered in the past. Most prior works require that every net has exactly one terminal on each side of the channel. As long as only one side of the channel contains multiple terminals of the same net, we provide linear-time solutions to all three problems. Such results are implausible if the placement of terminals is entirely unrestricted; in fact, the size of the output for the feasible offset problem may be Ω(n^2). The linear-time …

Neural Generalized Predictive Control For Real-Time Control, Donald I. Soloway

Electrical & Computer Engineering Theses & Dissertations

In this thesis a computationally efficient Generalized Predictive Control (GPC) algorithm is presented and implemented. The algorithm is more efficient than others because the number of iterations needed for convergence is significantly lower with Newton-Raphson. The main additional cost with Newton-Raphson algorithm is the calculation of the Hessian. This overhead is not a problem because of the reduced number of iterations, making the algorithm suitable for real-time control. For nonlinear control applications, a neural network is used as a dynamical system predictor leading to a Neural Generalized Predictive Control (NGPC) algorithm which is presented in detail in this thesis. An …

Visual Speech Recognition Using Multiple Deformable Lip Models, Devi Chandramohan

Electrical & Computer Engineering Theses & Dissertations

Motivated by the fact that human speech perception is a bimodal process (auditory and visual), several researchers have designed and implemented automatic speech recognition (ASR) systems consisting of both audio and visual subsystems, and shown improved performance relative to traditional purely auditory systems. Several visual speech reading approaches have used deformable templates to model the shape of a speaker's lips. Deformable templates are models of image objects, which can be deformed by adjusting a set of parameters to match the object in some optimal way, as defined by a cost function. Using a single deformable lip model has disadvantages such …

The Quest For The Gnarl, Rudy Rucker

SWITCH

The article describes some of the author’s own image-generating computer programs that he describes as “gnarly”. He began writing a simple spirograph program based off simple sine wave function called Spiro. Later transitioned into writing with C and better programs using more nonlinear feedback. Where Spiro is based on a simple sine wave function, Vine uses a nested sine function: the sine of the sine. The need for a more complicated computational approach lead to iteration and parallelism. Julgnarl uses Iteration and Calife uses parallelism. Calife shows one-dimensional cellular automata: spaces in which virtual computers are lined up like beads …

Gnarly Rantings About The Hacker And The Ants, Rudy Rucker

SWITCH

The article is an excerpt from Rucker’s book “The Happy Mutant”. It begins with his reflection of his career with GoMotion. He discusses the relation that he saw between design and cyberspace. Later he discusses his experience with a game a colleague found on the net: a virtual world where player is an ant. He talks about the struggles he goes through in this virtual world because of game difficulty and poor visuals. He ties it all in with how the Silicon Valley works in a similar way, and is filled with hackers and programers all needing each other to …

Web Fungus, Eric Matthews

SWITCH

This article explains the difference between digital worms, digital virus, and a fungus in the digital realm. A virus tends to be malicious towards our machines and replicates itself just like how it does in our real counterpart. A worm tends to just keep to itself and mind it's own business in a sense.The author goes in more depth on the topic of what a digital fungus’ purpose is within the digital realm. Just as fungi tend to branch out and live off of other living things in the physical world, this metaphor is extended into the digital realm. Digital …