Publication Date

4-22-1976

Abstract

Document retrieval systems accept a user request for information and respond with a list of documents which contain information relevant to the request. When the documents (or abstracts of the documents) are stored in a computer memory, a function can be defined which estimates the semantic distance between documents. If this function together with the set of documents forms a metric space, a graph, which I call a progressive graph, can be constructed to aid the search for the documents with relevant information.

Progressive graphs are studied and the search algorithms which use this graph structure are presented. The search algorithms always perform correctly on any progressive graph, but the presence of the progressive property in a graph is not sufficient to insure that the algorithms will work efficiently. The characteristics of a progressive graph which will optimize the search algorithms are discussed and algorithms to build and optimize progressive graphs are given. The results 6t a small problem show that the search process using the graph created by these algorithms can be very efficient. Finally, the distance function property which determines when a graph is a progressive graph is isolated and studied.

Degree Name

Mathematics

Level of Degree

Doctoral

Department Name

Mathematics & Statistics

First Committee Member (Chair)

Donald Ross Morrison

Second Committee Member

John Wade Ulrich

Third Committee Member

Cleve Barry Moler

Project Sponsors

The research reported in this dissertation was done while I was employed by the Los Alamos Scientific Laboratory. Support was provided by the U.S. Energy Research and Development Administration under contract with the Laboratory.

Language

English

Document Type

Dissertation

Download

Share

COinS