Computer Sciences Commons^™

Least Space-Time First Scheduling Algorithm : Scheduling Complex Tasks With Hard Deadline On Parallel Machines, Bo-Chao Cheng

Dissertations

Both time constraints and logical correctness are essential to real-time systems and failure to specify and observe a time constraint may result in disaster. Two orthogonal issues arise in the design and analysis of real-time systems: one is the specification of the system, and the semantic model describing the properties of real-time programs; the other is the scheduling and allocation of resources that may be shared by real-time program modules.

The problem of scheduling tasks with precedence and timing constraints onto a set of processors in a way that minimizes maximum tardiness is here considered. A new scheduling heuristic, Least …

Safe Code Transfromations For Speculative Execution In Real-Time Systems, Mohamed Mohamed Younis

Dissertations

Although compiler optimization techniques are standard and successful in non-real-time systems, if naively applied, they can destroy safety guarantees and deadlines in hard real-time systems. For this reason, real-time systems developers have tended to avoid automatic compiler optimization of their code. However, real-time applications in several areas have been growing substantially in size and complexity in recent years. This size and complexity makes it impossible for real-time programmers to write optimal code, and consequently indicates a need for compiler optimization. Recently researchers have developed or modified analyses and transformations to improve performance without degrading worst-case execution times. Moreover, these optimization …

Massively Parallel Reasoning In Transitive Relationship Hierarchies, Yugyung Lee

Dissertations

This research focuses on building a parallel knowledge representation and reasoning system for the purpose of making progress in realizing human-like intelligence. To achieve human-like intelligence, it is necessary to model human reasoning processes by programs. Knowledge in the real world is huge in size, complex in structure, and is also constantly changing even in limited domains. Unfortunately, reasoning algorithms are very often intractable, which means that they are too slow for any practical applications. One technique to deal with this problem is to design special-purpose reasoners. Many past Al systems have worked rather nicely for limited problem sizes, but …

Application Of Geometric Hashing Techniques To Retrieval Of High Dimensional Objects In Scientific Databases, Joyce Ye Lu

Theses

An approach to designing very fast algorithms for tackling the problem of approximate object matching in very large databases of high-dimensional objects is proposed. Given are a target object C and a database D containing information about a set of high-dimensional objects each of which is represented as a set of points. Our algorithms have an off-line object preprocessing (shape representation) phase and a recognition phase. The described algorithms determine those objects from D which are the closest to object C, according to delete or insert some points, move and rotation. All of these can be achieved very efficiently with …

Abstraction Of An Object-Oriented Vocabulary By Providing A Standardized Interface, Hemant Kothavade

Theses

Controlled vocabularies are ubiquitous in varied application fields. They are particularly helpful in the medical field since they can unify disparate terminologies and provide information in a compact, comprehensible manner. In this thesis, we present a mechanism to efficiently retrieve and update knowledge stored in a controlled vocabulary modeled as an Object-Oriented Database (OODB) system. We aim to provide a standardized interface to the vocabulary, such that the implementation details of the vocabulary are transparent to all users. The user of this standardized interface will typically be an application programmer who is trying to provide the vocabulary's knowledge-base to end …

Oodini 2.1 : An Enhanced Graphical Schema Representation For Object-Oriented Database, Rajashekar Rao

Theses

The graphical representation of an object-oriented database (OODB) schema is useful for the designers and users of a database system. The purpose of my thesis was to enhance the existing version of OOdini, an interactive graphical tool for editing an OODB schema. The new features include interactive modification and description of objects in the schema. Data structures for representing classes and attributes have been altered to incorporate object/data types as well as a descriptive string. The software has been implemented using the ObjectMaker toolkit to design our own methodology using the ObjectMaker Extension Language.

Towards Designing A Knowledge-Based Tutoring System : Sql-Tutor As An Example, Gang Zhou

Dissertations

A Knowledge-Based Tutoring System, also sometimes called an Intelligent Tutoring System, is a computer based instructional system that uses artificial intelligence techniques to help people learn some subject. The goal of the system is to provide private tutoring to its students based on their different backgrounds, requests, and interests. The system knows what subject materials it should teach, when and how to teach them, and can diagnose the mistakes made by the students and help them correct the mistakes.

The major objective of this dissertation is to investigate and develop a generic framework upon which we can build a Knowledge-Based …

Pattern Discovery In Sequence Databases : Algorithms And Applications To Dna/Protein Classification, Gung-Wei Chirn

Dissertations

Sequence databases comprise sequence data, which are linear structural descriptions of many natural entities. Approximate pattern discovery in a sequence database can lead to important conclusions or prediction of new phenomena. Traditional database technology is not suitable for accomplishing the task, and new techniques need to be developed.

In this dissertation, we propose several new techniques for discovering patterns in sequence databases. Our techniques incorporate pattern matching algorithms and novel heuristics for discovery and optimization. Experimental results of applying the techniques to both generated data and DNA/proteins show the effectiveness of the proposed techniques.

We then develop several classifiers using …

Knowledge Discovering For Document Classification Using Tree Matching In Texpros, Ching-Song Wei

Dissertations

This dissertation describes a knowledge-based system for classifying documents based upon the layout structure and conceptual information extracted from the content of the document. The spatial elements in a document are laid out in rectangular blocks which are represented by nodes in an ordered labelled tree, called the "layout structure tree" (L-S Tree). Each leaf node of a L-S Tree points to its corresponding block content. A knowledge Acquisition Tool (KAT) is devised to create a Document Sample Tree from L-S Tree, in which each of its leaves contains a node content conceptually describing its corresponding block content. Then, applying …

Integrating Hypertext With Information Systems Through Dynamic Mapping, Jiangling Wan

Dissertations

This dissertation presents a general hypertext model (GHMI) supporting integration of hypertext and information systems through dynamic mapping. Information systems integrated based on this model benefit from hypertext function-alities (such as linking, backtracking, history, guided tours, annotations, etc.) while preserving their own computation capabilities. Although systems supporting integration of hypertext and interface-oriented information systems do exist in hypertext literature, there is no existing model or system effectively supporting integration of hypertext and computation-oriented information systems. GHMI makes its major contributions by both extending and specifying the well-known Dexter Hypertext Reference Model. GHMI extends the Dexter model to overcome its limitations. …

Theory And Design Of Portable Parallel Programs For Heterogeneous Computing Systems And Networks, Ying-Chieh Wu

Dissertations

A recurring problem with high-performance computing is that advanced architectures generally achieve only a small fraction of their peak performance on many portions of real applications sets. The Amdahl's law corollary of this is that such architectures often spend most of their time on tasks (codes/algorithms and the data sets upon which they operate) for which they are unsuited. Heterogeneous Computing (HC) is needed in the mid 90's and beyond due to ever increasing super-speed requirements and the number of projects with these requirements. HC is defined as a special form of parallel and distributed computing that performs computations using …

Identifying And Exploiting Concurrency In Object-Based Real-Time Systems, Guohui Yu

Dissertations

The use of object-based mechanisms, i.e., abstract data types (ADTs), for constructing software systems can help to decrease development costs, increase understandability and increase maintainability. However, execution efficiency may be sacrificed due to the large number of procedure calls, and due to contention for shared ADTs in concurrent systems. Such inefficiencies are a concern in real-time applications that have stringent timing requirements. To address these issues, the potentially inefficient procedure calls are turned into a source of concurrency via asynchronous procedure calls (ARPCs), and contention for shared ADTS is reduced via ADT cloning. A framework for concurrency analysis in object-based …

Automatic Visual Recognition Using Parallel Machines, Yui-Liang Chen

Dissertations

Invariant features and quick matching algorithms are two major concerns in the area of automatic visual recognition. The former reduces the size of an established model database, and the latter shortens the computation time. This dissertation, will discussed both line invariants under perspective projection and parallel implementation of a dynamic programming technique for shape recognition. The feasibility of using parallel machines can be demonstrated through the dramatically reduced time complexity.

In this dissertation, our algorithms are implemented on the AP1000 MIMD parallel machines. For processing an object with a features, the time complexity of the proposed parallel algorithm is O(n) …

Automatic Office Document Classification And Information Extraction, Xiaolong Hao

Dissertations

TEXPR.OS (TEXt PROcessing System) is a document processing system (DPS) to support and assist office workers in their daily work in dealing with information and document management. In this thesis, document classification and information extraction, which are two of the major functional capabilities in TEXPROS, are investigated.

Based on the nature of its content, a document is divided into structured and unstructured (i.e., of free text) parts. The conceptual and content structures are introduced to capture the semantics of the structured and unstructured part of the document respectively. The document is classified and information is extracted based on the analyses …

Application Of Approximate Graph Matching Techniques For Searching Databases Of Two-Dimensional Chemical Structures, Karen R. Pysniak

Theses

This paper proposes the application of approximate graph matching techniques for best-match searching of two-dimensional chemical structure databases based upon topology. Chemical structures are represented as labeled graphs, each atom a node in the graph and each bond an edge. By inserting; deleting and renaming nodes/edges, one structure may be transformed into another. We define similarity as the weighted sum of the costs of these edit operations. An algorithm for approximating the minimum distance between two graphs based on simulated annealing is applied. Best-match searches are performed utilizing this pre-computed distance information and applying the concepts of triangle inequality to …

Mapping Of Portable Parallel Programs, Song Chen

Dissertations

An efficient parallel program designed for a parallel architecture includes a detailed outline of accurate assignments of concurrent computations onto processors, and data transfers onto communication links, such that the overall execution time is minimized. This process may be complex depending on the application task and the target multiprocessor architecture. Furthermore, this process is to be repeated for every different architecture even though the application task may be the same. Consequently, this has a major impact on the ever increasing cost of software development for multiprocessor systems. A remedy for this problem would be to design portable parallel programs which …

Document Preprocessing And Fuzzy Unsupervised Character Classification, Shy-Shyan Chen

Dissertations

This dissertation presents document preprocessing and fuzzy unsupervised character classification for automatically reading daily-received office documents that have complex layout structures, such as multiple columns and mixed-mode contents of texts, graphics and half-tone pictures. First, the block segmentation algorithm is performed based on a simple two-step run-length smoothing to decompose a document into single-mode blocks. Next, the block classification is performed based on the clustering rules to classify each block into one of the types such as text, horizontal or vertical lines, graphics, and pictures. The mean white-to-black transition is shown as an invariance for textual blocks, and is useful …

Visual Pattern Recognition Using Neural Networks, Jenlong Moh

Dissertations

Neural networks have been widely studied in a number of fields, such as neural architectures, neurobiology, statistics of neural network and pattern classification. In the field of pattern classification, neural network models are applied on numerous applications, for instance, character recognition, speech recognition, and object recognition. Among these, character recognition is commonly used to illustrate the feature and classification characteristics of neural networks.

In this dissertation, the theoretical foundations of artificial neural networks are first reviewed and existing neural models are studied. The Adaptive Resonance Theory (ART) model is improved to achieve more reasonable classification results. Experiments in applying the …

Requirements, Design And Business Process Reengineering As Vital Parts Of Any System Development Methodology, Alicja Ruszala

Theses

This thesis analyzes different aspects of system development life cycle, concentrating on the requirements and design stages. It describes various methodologies, methods and tools that have been developed over the years. It evaluates them and compares them against each other. Finally a conclusion is made that there is a very important stage missing in the system development life cycle, which is the Business Process Reengineering Stage.

Off-Line Hand-Printed Chinese Character Recognition Based On Stroke Matching, Sunshine Chang

Theses

The specific purpose of this thesis is the automated recognition of the off-line Chinese hand-printed characters by using a blue ball-point pen. Through mask processing, the main components in a Chinese character such as vertical, horizontal, and slant strokes can be extracted. Then, the connected components with the coordinates of the top, bottom, leftmost, and rightmost ends of each stroke extracted are found. From these coordinates, the length and position of each stroke can be computed.

According to the number, relative length, and relative position of each stroke, both of the coarse and fine rule-based classification can be made, and …

An Office Document Retrieval System With The Capability Of Processing Incomplete And Vague Queries, Qianhong Liu

Dissertations

TEXPROS (TEXt PROcessing System) is an intelligent document processing system. The system is a combination of filing and retrieval systems, which supports storing, classifying, categorizing, retrieving and reproducing documents, as well as extracting, browsing, retrieving and synthesizing information from a variety of documents. This dissertation presents a retrieval system for TEXPROS, which is capable of processing incomplete or vague queries and providing semantically meaningful responses to the users. The design of the retrieval system is highly integrated with various mechanisms for achieving these goals. First, a system catalog including a thesaurus is used to store the knowledge about the database. …

Parallel Exact Enumeration Of Self-Avoiding Walk On Cubic Lattices And Its Applications To Protein Folding Studies, Anek Vorapanya

Theses

Exact enumeration of self-avoiding walk on many lattices have been studied extensively recently. Even a short chain polymer (about 30 monomers) represented as a chain of cubic lattice sites requires a considerable amount of computer time to exhaustively search for all unique conformations. However, self-avoiding walk process can be modified such that it exhibits a high degree of independence among subprocesses. Parallel implementation of such subprocesses can reduce a great amount of enumeration time. Parallel enumeration makes longer chain enumeration possible.

Enumerating only unique conformations requires that all rotation and mirror conformations be removed. An algorithm to avoid generating such …

Extracting Parallelism At Compile-Time Through Dependence Analysis & Cloning Techniques In An Object-Based Paradigm, Binoy Ravindran

Theses

The construct of Abstract Data Type (ADT) modules and Abstract Data Object (ADO) modules supported by most object-based languages are a great source for developing reusable code. To improve the run time performance of such object-based programs, we consider the asynchronous remote procedure call (ARPC) model of parallel execution, in which concurrency is achieved by having the caller and the callee (which are module instances) running on different processors. Frequently, an ADT module is needed simultaneously by other modules, thus causing contention. To resolve this, we clone the module instance in demand and distribute the copies across different processors, so …

Concurrent Use Of Two Programming Tools For Heterogeneous Supercomputers, Javier G. Vasquez

Theses

In this thesis, a demostration of the heterogeneous use of two programming paradigms for heterogeneous computing called Cluster-M and HAsC is presented. Both paradigms can efficiently support heterogeneous networks by preserving a level of abstraction which does not include any architecture mapping details. Furthermore, they are both machine independent and hence are scalable. Unlike, almost all existing heterogeneous orchestration tools which are MIMD based, HAsC is based on the fundamental concepts of SIMD associative computing. HAsC models a heterogeneous network as a coarse grained associative computer and is designed to optimize the execution of problems with large ratios of computations …

Authentication For Mobile Computing, Andreas Keppler

Theses

Host mobility is becoming an increasingly important feature with the recent arrival of laptop and palmtop computers, the development of wireless network interfaces and the implementation of global networks. Unfortunately, this mobile environment is also much more vulnerable to penetration by intruders. A possible means of protection can be authentication. This guarantees the identity of a communication peer.

This thesis studies the constraints imposed on the mobile environment with respect to authentication. It compares the two prevailing authentication mechanisms, Kerberos and SPX, and tries to make suggestions of how a mechanism can be adapted to the mobile environment.

Design And Implementation Of Ipis : An X-Window Based Image Processing Interactive System, Eduardo Morales

Theses

Most of image processing systems are based on command line functions or can only display one image at a time. This is a serious inconvenience for those who need an interactive system session or want to compare two images processed by different techniques at the same time.

The system was designed with these problems in mind. It is able to display the processed image right after an operation and to display several images simultaneously, making it simple to compare techniques. The system was also created with the purpose to be used in an academic environment. Its structured design makes it …

Implementation Of An Automatic Mapping Tool For Massively Parallel Computing, Ajitha Gadangi

Theses

In this thesis, an implementation of a generic technique for fine grain mapping of portable parallel algorithms onto multiprocessor architectures is presented. The implemented mapping algorithm is a component of Cluster-M. Cluster-M is a novel parallel programming tool which facilitates the design and mapping of portable softwares onto various parallel systems. The other components of Cluster-M are the Specifications and the Representations. Using the Specifications, machine independent parallel algorithms are presented in a "clustered" fashion specifying the concurrent computations and communications at every step of the overall execution. The Representations, on the other hand, are a form of clustering the …

Graphical Oodb Modeling For Medical Information Standards (Gommis), Jiping Liu

Theses

The graphical representation of database schemata has been a useful tool for the designer and users of database systems. Such a tool for OODB schemata should incorporate a wide variety of symbols which cover most concepts of existing Object-Oriented Database (OODB), so it is sufficient to support a diverse group of object-oriented data models.

In this paper we created a. graphical representation, using the OOdini system and language, of the European Prestandard for Medical Informatics on Message Exchange of Laboratory Information. This European Prestandard describes a standardized format for messages to be exchanged between a. health care provider and a …

Graphical Oodb Modeling For Medical Information Standards (Gommis), Nagesh K. Puppala

Theses

Our task is to create a graphical representation of the European Prestandard for Medical Informatics on Message Exchange of Laboratory Information. This document, made available to us through Columbia Presbyterian, describes a standardized format for messages to be exchanged between a healthcare provider and a medical laboratory. The prestandard represents important information in a very disconnected way.

We have used OODINI system and language to develop our GOMMIS system. OODINI is a graphical editor for object-oriented database schemas that was developed at NJIT during the past three years. OODINI features a poweful set of icons that cover most concepts of …

Translation Of Semantic Aspects Of Oodini Graphical Representation To Onto Oodb Data Definition Language, Xiaoyong Wang

Theses

In this thesis we present a system to translate the semantic elements in the graphical schema language of OODINI from API of OODAL to the Type definition of ONTOS DB. To translate semantic constraints of the graphical language, we patch more information to existent class data structure in API of OODAL. After a brief review of OODINI, ONTOS DB and the existent translator without the ability to translate semantic constraints, we describe in detail the methods to translate the essential relationship. dependent relationship, multi-valued essential relationship and multi-valued dependent relationship. We employ an Inverse Reference to a "Set of" Type …