Classification and Retrieval of Knowledge on Parallel Marker Passing Architecture.

Jun-Tae Kim, Dan I. Moldovan: Classification and Retrieval of Knowledge on Parallel Marker Passing Architecture. IEEE Trans. Knowl. Data Eng. 5(5): 753-761(1993)
  author    = {Jun-Tae Kim and
               Dan I. Moldovan},
  title     = {Classification and Retrieval of Knowledge on Parallel Marker
               Passing Architecture},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {5},
  number    = {5},
  year      = {1993},
  pages     = {753-761},
  ee        = {db/journals/tkde/KimKM93.html},
  bibsource = {DBLP,}


Frame-based systems or semantic networks have been generally used for knowledge representation. In such a knowledge representation system, concepts in the knowledge base are organized based on the subsumption relation between concepts, and classification is a process of constructing a concept hierarchy according to the subsumption relationships. Since the classification process involves search and subsumption test between concepts, classification on a large knowledge base may become unacceptably slow, especially for real-time applications. In this paper, a massively parallel classification and property retrieval algorithm on a marker passing architecture is presented. The subsumption relation is first defined by using the set relationship, and the parallel classification algorithm is described based on that relationship. In this algorithm, subsumption test between two concepts is done by parallel marker passing and multiple subsumption tests are performed simultaneously. To investigate the performance of the algorithm, time complexities of sequential and parallel classification are compared. Simulation of the parallel classification algorithm was performed using the SNAP (Semantic Network Array Processor) simulator, and the influence of several factors on the execution time is discussed.

Copyright © 1993 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 3, TKDE 1993-1995" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


Daniel G. Bobrow, Terry Winograd: On Overview of KRL, a Knowledge Representation Language. Cognitive Science 1(1): 3-46(1977) BibTeX
Ronald J. Brachman, Hector J. Levesque: The Tractability of Subsumption in Frame-Based Description Languages. AAAI 1984: 34-37 BibTeX
Ronald J. Brachman, James G. Schmolze: An Overview of the KL-ONE Knowledge Representation System. Cognitive Science 9(2): 171-216(1985) BibTeX
Robert M. MacGregor: A Deductive Pattern Matcher. AAAI 1988: 403-408 BibTeX
Bernhard Nebel: Computational Complexity of Terminological Reasoning in BACK. Artif. Intell. 34(3): 371-383(1988) BibTeX
James G. Schmolze, Thomas A. Lipkis: Classification in the KL-ONE Knowledge Representation System. IJCAI 1983: 330-332 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
IEEE Transactions on Data and Knowledge Engineering: Copyright © by IEEE,
Joint ACM SIGMOD / IEEE Computer Society Anthology: Copyright © by ACM ( and IEEE, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sun May 17 00:27:51 2009