TY - JOUR
T1 - Parallel operations on class hierarchies with double strand representation
AU - Lee, Eunice (Yugyung)
AU - Geller, James
N1 - Funding Information:
Most Knowledge Representation systems, as well as all object-oriented languages and databases, use an IS-A hierarchy as their backbone. An efficient hierarchy encoding technique would aid all these areas, especially for large hierarchies. The IS-A hierarchy has been especially important in the KL-ONE family of Knowledge Representation (KR) systems [1-9]. Object-oriented systems, based on SIMULA [13] and Smalltalk [14], always incorporate generalization hierarchies with inheritance behavior. Object-oriented methods have been applied to the design of programming languages, e.g., C++ [15], type systems [16], object-oriented extensions of existing languages, e.g., CLOS [17], and object-oriented database systems such as ORION [~0], o~ [~], and ONTOS [12]. Given the importance of the IS-A hierarchy, one would like to achieve the fastest possible processing for query and update operations in this hierarchy. If we assume that it is known that a Mammal is an Animal, a Dog is a Mammal, and a Collie is a Dog, then we want *This research was (partially) done under a cooperative agreement between the National Institute of Standards and Technology Advanced Technology Program (under the HIIT contract, number 70NANB5H1011) and the Healthcare Open Systems and Trials, Inc consortium. tThis work was conducted using the computational resources of the Northeast Parallel Architectures Center (NPAC) at Syracuse University, which is funded by and operates under contract to DARPA and the Air Force Systems Command, Rome Air Development Center (RADC), Griffiss Air Force Base, NY, under contract# F306002-88-C-0031. aThe Connection Machine is a trademark of Thinking Machines Corp.
PY - 1997
Y1 - 1997
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77957032544&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77957032544&partnerID=8YFLogxK
U2 - 10.1016/S0923-0459(97)80005-5
DO - 10.1016/S0923-0459(97)80005-5
M3 - Article
AN - SCOPUS:77957032544
SN - 0923-0459
VL - 20
SP - 69
EP - 94
JO - Machine Intelligence and Pattern Recognition
JF - Machine Intelligence and Pattern Recognition
IS - C
ER -