Digital Commons Network^™

Parallel H-V Drawings Of Binary Trees, Panagiotis T. Metaxas, Grammati E. Pantziou, Antonis Symvonis

Computer Science Technical Reports

In this paper we present a method to obtain optimal h-v and inclusion drawings in parallel. Based on parallel tree contraction, our method computes optimal (with respect to a class of cost functions of the enclosing rectangle) drawings in $O(\log^2 n)$ parallel time by using a polynomial number of EREW processors. The number of processors reduces substantially when we study minimum area drawings. The method can be extended to compute optimal inclusion layouts in the case where each leaf $l$ of the tree is represented by rectangle $l_x \times l_y$ (the dimensions of which are part of the input). For …

A Probabilistic Approach To Fault Diagnosis In Linear Lightwave Networks, Robert H. Deng, A. A. Lazar, W. Wang

Research Collection School Of Computing and Information Systems

The application of probabilistic reasoning to fault diagnosis in linear lightwave networks (LLNs) is investigated. The LLN inference model is represented by a Bayesian network (or causal network). An inference algorithm is proposed that is capable of conducting fault diagnosis (inference) with incomplete evidence and on an interactive basis. Two belief updating algorithms are presented which are used by the inference algorithm for performing fault diagnosis. The first belief updating algorithm is a simplified version of the one proposed by Pearl (1988) for singly connected inference models. The second belief updating algorithm applies to multiply connected inference models and is …

Developing Realistic Behaviors In Adversarial Agents For Air Combat Simulation, George S. Hluck

Theses and Dissertations

This thesis describes an initial effort into creating a rule-based, reactive system for air combat simulation. This program uses the object-oriented extension of the expert system tool known as the C Language Integrated Production System CLIPS. This effort rose out of the need for creating and integrating semi-autonomous forces for the Distributed Interactive System DIS. This thesis describes the basic maneuvers a pilot uses in present air-to-air combat. The methodology includes the design decisions, knowledge-base development, phase architecture, and maneuver architecture development. The actual implementation of the selected architecture is described. This thesis also discusses the results of experimental runs …

Alternative Architectures For Domain-Oriented Application Composition And Generation Systems, Warren E. Gool

Theses and Dissertations

This thesis presents a formalized framework for comparing the structure and semantics of software architectures. The framework uses object diagrams for analyzing the structure of the architectures and the axiomatic approach for analyzing the semantics. This framework is used to compare the Object Connection Update OCU model developed by the Software Engineering Institute against four other software architectures VHDL defined by Lipsett, MetaH defined by Honeywell, microRapide defined by Luckham, and hierarchical software systems as defined by Batory. The goal of the comparison was to evaluate the OCU model for suitability within prototype application composition and generation systems. This research …

Asynchronous Transaction Commitment In Federated Database Systems, San-Yih Hwang, Ee Peng Lim, Jaideep Srivastava

Research Collection School Of Computing and Information Systems

We propose a new (and restricted) model for global transactions which allows asynchronous commitment of subtransactions. Our model requires each global transaction to have a fixed structure with update to the data in at most one database. Based on this transaction model, we present two concurrency control algorithms, namely Asynchronous Site Graph and Asynchronous VirtGlobalSG, which employ asynchronous commitment and achieve global serializability. Compared to other proposed algorithms, our algorithms employ asynchronous commitment so as to increase transaction performance. Furthermore, our algorithms do not put restrictions on transaction data access or local histories.

Dynamic Decision Modeling In Medicine: A Critique Of Existing Formalisms, Tze-Yun Leong

Research Collection School Of Computing and Information Systems

Dynamic decision models are frameworks for modeling and solving decision problems that take into explicit account the effects of time. These formalisms are based on structural and semantical extensions of conventional decision models, e.g., decision trees and influence diagrams, with the mathematical definitions of finite-state semi-Markov processes. This paper identifies the common theoretical basis of existing dynamic decision modeling formalisms, and compares and contrasts their applicability and efficiency. It also argues that a subclass of such dynamic decision problems can be formulated and solved more effectively with non-graphical techniques. Some insights gained from this exercise on automating the dynamic decision …

Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh

Computer Science: Faculty Publications and Other Works

We examine the wormhole routing problem in terms of the "congestion" c and "dilation" d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cdη + cLηlog P) time, where L is the number of flits in a packet, and η = min {d,L]; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area Θ(A) can simulate wormhole routing on any network of comparable area with O(log 3 …

Towards A General Distributed Platform For Learning And Generalization, Brent W. Hughes, Tony R. Martinez

Faculty Publications

Different learning models employ different styles of generalization on novel inputs. This paper proposes the need for multiple styles of generalization to support a broad application base. The Priority ASOCS model (Priority Adaptive Self-organizing Concurrent System) is overviewed and presented as a potential platform which can support multiple generalization styles. PASOCS is an adaptive network composed of many simple computing elements operating asynchronously and in parallel. The PASOCS can operate in either a data processing mode or a learning mode. During data processing mode, the system acts as a parallel hardware circuit. During leaming mode, the PASOCS incorporates rules, with …

The Importance Of Using Multiple Styles Of Generalization, Tony R. Martinez, D. Randall Wilson

Faculty Publications

There are many ways for a learning system to generalize from training set data. There is likely no one style of generalization which will solve all problems better than any other style, for different styles will work better on some applications than others. This paper presents several styles of generalization and uses them to suggest that a collection of such styles can provide more accurate generalization than any one style by itself. Empirical results of generalizing on several real-world applications are given, and comparisons are made on the generalization accuracy of each style of generalization. The empirical results support the …

Genetic Algorithms For Soft Decision Decoding Of Linear Block Codes, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

Soft-decision decoding is an NP-hard problem of great interest to developers of communication systems. We show that this problem is equivalent to the problem of optimizing Walsh polynomials. We present genetic algorithms for soft-decision decoding of binary linear block codes and compare the performance with various other decoding algorithms. Simulation results show that our algorithms achieve bit-error-probabilities as low as 0.00183 for a [104, 52] code with a low signal-to-noise ratio of 2.5 dB, exploring only 30,000 codewords, whereas the search space contains 4.5 x 1015 codewords. We define a new crossover operator that exploits domain-specific information and compare it …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 9, Number 9, November 1993, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A fourteen page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

A Computerized Instructional System For Mechanical Motion Of Objects, Jian J. Zhang

Electronic Dissertations and Theses

No abstract provided.

On-Line And Dynamic Shortest Paths Through Graph Decompositions, Hristo N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis

Computer Science Technical Reports

We describe algorithms for finding shortest paths and distances in a planar digraph which exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. For outerplanar digraphs, for instance, the data structures can be updated after any such change in only $O(\log n)$ time, where $n$ is the number of vertices of the digraph. We also describe the first parallel algorithms for solving the dynamic version of the shortest path problem. Our …

Parallel Max Cut Approximations, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis

Computer Science Technical Reports

Given a graph with positive integer edge weights one may ask whether there exists an edge cut whose weight is bigger than a given number. This problem is NP-complete. We present here an approximation algorithm in NC which provides tight upper bounds to the proportion of edge cuts whose size is bigger than a given number. Our technique is based on the methods to convert randomized parallel algorithms into deterministic ones introduced by Karp and Wigderson. The basic idea of those methods is to replace an exponentially large sample space by one of polynomial size. In this work, we prove …

Asynchronous Parallel Schemes: A Survey, Eric Jui-Lin Lu, Michael Gene Hilgers, Bruce M. Mcmillin

Computer Science Technical Reports

It is well known that synchronization and communication delays are the major sources of performance degradation of synchronous parallel algorithms. It has been shown that asynchronous implementations have the potential to reduce the overhead to minimum. This paper surveys the existing asynchronous schemes and the sufficient conditions for the convergence of the surveyed schemes. Some comparisons among these schemes are also presented.

Ensuring Relaxed Atomicity For Flexible Transactions In Multidatabase Systems, Aidong Zhang, Marian H. Nodine, Omran Bukhres

Department of Computer Science Technical Reports

No abstract provided.

Curve Fitting With Cubic A-Splines, Chandrajit L. Bajaj, Guoliang Xu

Department of Computer Science Technical Reports

No abstract provided.

Project Isaac: Building Simulations For Virtual Environments, George Vanĕček, James Cremer

Department of Computer Science Technical Reports

No abstract provided.

Dealing With Mobility: Issues And Research Challenges, Evaggelia Pitoura, Bharat Bhargava

Department of Computer Science Technical Reports

No abstract provided.

The Design And Implementation Of Tripwire: A File System Integrity Checker, Gene H. Kim, Eugene H. Spafford

Department of Computer Science Technical Reports

No abstract provided.

Object-Oriented Design And Implementation Of A Parallel Ada Simulation System, James T. Belford

Theses and Dissertations

Simulations which model the behavior real world entities are often large and complex, and require frequent changes to the configuration. This research effort examines the benefits of using object-oriented techniques to develop a distributed simulation environment which supports modularity, modifiability, and portability. The components of the Parallel Discrete Event Simulation PDES environment are identified and modeled using the Rumbaugh modeling technique. From the model, a prototype implementation of a Parallel Ada Simulation Environment PASE is accomplished using Classic Ada. A system interface for the Intel ipsc2 Hypercube was developed to illustrate the concepts of modularity and portability. In addition, the …

An Adaptive Coding Scheme With Code Combining For Mobile Radio Systems, Robert H. Deng, Huafei Zhou

Research Collection School Of Computing and Information Systems

The authors propose and study an adaptive error-control coding scheme for binary digital FM (BFM) mobile radio transmission. The scheme employs code combining through packet retransmissions. The number of transmissions of a packet is in proportion to the channel fading/noise levels, which is in contrast to time diversity techniques where a fixed number of repetitions of a data packet is performed even in the absence of channel errors. Furthermore, the receiver uses received signal envelopes as channel state information, which significantly improves the throughput and bit error rate (BER) performance. Performance of the proposed scheme is analyzed for frequency-flat Rayleigh …

Multiple Query Optimization With Depth-First Branch-And-Bound, Ahmet Cosar, Ee Peng Lim, Jaideep Srivastava

Research Collection School Of Computing and Information Systems

In certain database applications such as deductive databases, batch query processing, and recursive query processing etc., a single query can be transformed into a set ofclosely related database queries. Great benefits can be obtained by executing a group of related queries all together in a single unijied multi-plan instead of executing each query separately. In order to achieve this, Multiple Query Optimization (MQO) identifies common task(s) (e.g. common subezpressions, joins, etc.) among a set of query plans and creates a single unified plan (multiplan) which can be executed to obtain the required outputs forall queries at once. In this paper, …

Query Optimization And Processing In Federated Database Systems, Ee Peng Lim, Jaideep Srivastava

Research Collection School Of Computing and Information Systems

No abstract provided.

Methodology For Modeling High Performance Distributed And Parallel Systems, Rakesh Kushwaha

Dissertations

Performance modeling of distributed and parallel systems is of considerable importance to the high performance computing community. To achieve high performance, proper task or process assignment and data or file allocation among processing sites is essential. This dissertation describes an elegant approach to model distributed and parallel systems, which combines the optimal static solutions for data allocation with dynamic policies for task assignment. A performance-efficient system model is developed using analytical tools and techniques.

The system model is accomplished in three steps. First, the basic client-server model which allows only data transfer is evaluated. A prediction and evaluation method is …

A Comprehensive Part Model And Graphical Schema Representation For Object-Oriented Databases, Michael H. Halper

Dissertations

Part-whole modeling plays an important role in the development of database schemata in data-intensive application domains such as manufacturing, design, computer graphics. text document processing, and so on. Object-oriented databases (OODBs) have been targeted for use in such areas. Thus, it is essential that OODBs incorporate a part relationship as one of their modeling primitives. In this dissertation, we present a comprehensive OODB part model which expands the boundaries of OODB part-whole modeling along three fronts. First, it identifies and codifies new semantics for the OODB part relationship. Second, it provides two novel realizations for part relationships and their associated …

Morphological Operations In Image Processing And Analysis, Chamim Christopher Pu

Dissertations

Morphological operations applied in image processing and analysis are becoming increasingly important in today's technology. Morphological operations which are based on set theory, can extract object features by suitable shape (structuring elements). Morphological filters are combinations of morphological operations that transform an image into a quantitative description of its geometrical structure which based on structuring elements. Important applications of morphological operations are shape description, shape recognition, nonlinear filtering, industrial parts inspection, and medical image processing.

In this dissertation, basic morphological operations are reviewed, algorithms and theorems are presented for solving problems in distance transformation, skeletonization, recognition, and nonlinear filtering. A …

Medium Access Control Mechanisms For High Speed Metropolitan Area Networks, Michail Papamichail

Dissertations

In this dissertation novel Medium Access Control mechanisms for High Speed Metropolitan Area networks are proposed and their performance is investigated under the presence of single and multiple priority classes of traffic. The proposed mechanisms are based on the Distributed Queue Dual Bus network, which has been adopted by the IEEE standardization committee as the 802.6 standard for Metropolitan Area Networks, and address most of its performance limitations. First, the Rotating Slot Generator scheme is introduced which uses the looped bus architecture that has been proposed for the 802.6 network. According to this scheme the responsibility for generating slots moves …

Characterization Of Three-Dimensional Shear Flows, Kurra Bhaswan

Theses

This work investigates techniques to analyze and characterize the presence of microstructure in moderately dilute three-dimensional shear flows. In three dimensional shear flows, a distinct structure develops as the coefficient of restitution is lowered with the particles exhibiting a strong tendency towards the formation of clusters. There exists a need to automatically detect and characterize this microstructure in the given flow. Several methods are examined for effective characterization of the microstructure. The techniques employed are based on the classification of the data based on the properties of the Voronoi diagram constructed from the positional parameters of the two-dimensional slices of …

Using Temporal Subsumption For Developing Efficient Error-Detecting Distributed Algorithms, Martina Schollmeyer, Bruce M. Mcmillin

Computer Science Technical Reports

Distributed algorithms can use executable assertions derived from program verification to detect errors at run-time. However, a complete verification proof outline contains a large number of assertions, and embedding all of them into the program to be checked at run-time would make error-detection very inefficient.

The technique of temporal subsumption examines the dependencies between the individual assertions along program execution paths. In contrast to classical subsumption, where all logical expressions to be examined are true simultaneously, an assertion need only be true when the corresponding statement in the distributed program has been executed. Thus, temporal subsumption based on the set …