Parallel operations on class hierarchies with double strand representation

Eunice (Yugyung) Lee, James Geller

Research output: Contribution to journalArticlepeer-review

Abstract

This paper continues a series of papers dealing with the problems of (1) fast verification of the existence of a transitive relation in an IS-A hierarchy, and (2) dynamic update of such a hierarchy. As in our previous work, a directed acyclic graph (DAG) of IS-A relationships is replaced by a set of nodes, annotated by number pairs, and stored on a massively parallel computer. In this paper a new mapping of this set of nodes onto the processors is described, called the Double Strand Representation (DSR). The DSR improves the processor usage compared to our previously used Grid Representation (GR). This paper shows IS-A verification and number pair propagation algorithms for the Double Strand Representation. Test runs on a CM-5 Connection Machine3 are reported.

Original languageEnglish (US)
Pages (from-to)69-94
Number of pages26
JournalMachine Intelligence and Pattern Recognition
Volume20
Issue numberC
DOIs
StatePublished - Dec 1 1997

All Science Journal Classification (ASJC) codes

  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Cite this