Physical Sciences and Mathematics Commons^™

Pattern Discovery In Trees : Algorithms And Applications To Document And Scientific Data Management, Chia-Yo Chang

Dissertations

Ordered, labeled trees are trees in which each node has a label and the left-to-right order of its children (if it has any) is fixed. Such trees have many applications in vision, pattern recognition, molecular biology and natural language processing.

In this dissertation we present algorithms for finding patterns in the ordered labeled trees. Specifically we study the largest approximately common substructure (LACS) problem for such trees. We consider a substructure of a tree T to be a connected subgraph of T. Given two trees T₁, T₂ and an integer d, the LACS problem is to find …

Parallelization For Image Processing Algorithms Based Chain And Mid-Crack Codes, Wai-Tak Wong

Dissertations

Freeman chain code is a widely-used description for a contour image. Another mid-crack code algorithm was proposed as a more precise method for image representation. We have developed a coding algorithm which is suitable to generate either chain code description or mid-crack code description by switching between two different tables. Since there is a strong urge to use parallel processing in image related problems, a parallel coding algorithm is implemented. This algorithm is developed on a pyramid architecture and a N cube architecture. Using link-list data structure and neighbor identification, the algorithm gains efficiency because no sorting or neighborhood pairing …

Testing Statistical Significance In Sequence Classification Algorithms, Tom Tien-Hua Shih

Theses

Multiple sequence alignment has proven to be a successful method of representing and organizing of protein sequence data. It is crucial to medical researches on the structure and function of proteins.

There have been numerous tools published on how to abstract meaningful relationship from an unknown sequence and a set of known sequences. One study used a method for discovering active motifs in a set of related protein sequences. These are meaningful knowledge abstracted from the known protein database since most protein families are characterized by multiple local motifs. Another study abstracts knowledge regarding the input sequence using a preconstructed …

Algorithms For Generation Of Path-Methods In Object-Oriented Databases, Ashish Mehta

Dissertations

A path-method is a mechanism in object-oriented databases (OODBs) to retrieve or to update information relevant to one class that is not stored with that class but with some other class. A path-method is a method which traverses from one class through a chain of connections between classes to access information at another class. However, it is a difficult task for a user to write path-methods, because it might require comprehensive knowledge of many classes of the conceptual schema, while a typical user has often incomplete or even inconsistent knowledge of the schema.

This dissertation proposes an approach to the …