An Empirical Analysis of Terminological Representation Systems

Jochen Heinsohn, Daniel Kudenko, Bernhard Nebel, Hans-Jürgen ProfitlichAAAI 1992

Abstract

In the early 1990s, the AI community saw a proliferation of terminological representation systems based on the KL-ONE framework. While the theoretical complexity of these systems was well-studied, empirical data regarding their practical performance and interoperability remained scarce. This paper provides a rigorous benchmark of six prominent systems—BACK, CLASSIC, KRIS, LOOM, MESON, and SB-ONE—using a combination of qualitative analysis and quantitative experiments on realistic and synthetic datasets. The results reveal massive performance gaps and a startling lack of a common functional core, underscoring the need for standardization in knowledge representation.

Introduction

By 1992, researchers had developed numerous systems for representing taxonomic knowledge, yet these systems often functioned as isolated silos. Despite a shared semantic heritage, moving a knowledge base from one engine to another was fraught with difficulty. The authors of this study, needing to select a system for their "WIP" project, initiated this benchmark to move beyond theoretical complexity results (which often suggested intractability) and understand how these systems behaved in real-world scenarios.

Methodology

The researchers employed a two-pronged approach to evaluate the six candidate systems. First, a qualitative analysis was performed by defining a "common terminological language" that served as a superset of all features. This allowed the team to map the specific capabilities and limitations of each system.

Second, a quantitative benchmark was established, consisting of five distinct experiment groups designed to measure classification time—the duration required for a system to compute a concept hierarchy.

Experimental setup for benchmarking terminological representation systems.

The experiments ranged from handling "problematical" cases to testing "easy" polynomial-time inferences and known "hard" cases designed to trigger worst-case exponential behavior.

Datasets and Experimental Design

The study utilized three primary types of data to ensure a comprehensive evaluation:

  • Realistic Knowledge Bases (KBs): Six KBs sourced from active AI projects, containing between 100 and 400 concepts.
  • Synthetic "Hard" Cases: Small, hand-crafted KBs (up to 40 concepts) specifically designed to exploit known NP-hardness results in subsumption algorithms.
  • Random KBs: A set of 30 generated KBs ranging from 15 to 5,000 concepts, used to test scaling within the narrow intersection of features supported by all systems.

Key Insights and Ideas

The "Tiny Intersection" Problem

One of the most surprising findings was the minimal overlap between the systems. The only features universally supported were concept conjunction, value restrictions, and number restrictions. This "tiny intersection" made the transport of knowledge bases nearly impossible without significant data bloat or loss of semantic meaning.

Structural Sensitivity

The performance of these systems was found to be highly sensitive to the internal structure of the knowledge base. In one realistic KB, a single "super-concept" referenced by half of all other concepts caused a massive performance spike. This demonstrated that the shape of the data is as critical as its size.

The Expressiveness Tax

While systems like KRIS provided complete inferences for highly expressive languages, they were often orders of magnitude slower than more restricted systems like CLASSIC. However, the authors noted that this was frequently a result of unoptimized implementation rather than an inherent "law of nature."

Key Results

The benchmarking revealed significant performance variance across the systems. In the largest realistic test cases, the slowest system (KRIS) was approximately 800 times slower than the fastest (CLASSIC).

Runtime performance on synthetic 'hard' cases designed to trigger exponential behavior.

Furthermore, the "hard" cases successfully triggered exponential growth in runtime for several systems, validating that theoretical intractability is indeed a practical concern. Across nearly all tests, runtime performance grew at least quadratically relative to the number of concepts, even on ostensibly "easy" data.

Limitations and Future Work

The study focused exclusively on the Terminological (TBox) component of these systems, leaving the Assertion (ABox) component—which handles specific individuals—for future research. Additionally, the need to use approximate translations between systems likely introduced some bias into the runtime results.

The authors concluded with a strong call for standardization. The lack of a shared language and test suites hindered the development of reliable, interchangeable AI components. This work served as a foundational step toward the eventual creation of standards like the Web Ontology Language (OWL).

Summary updated

BibTeX
@inproceedings{heinsohn1992empirical,
  author = {Jochen Heinsohn and Daniel Kudenko and Bernhard Nebel and Hans-Jürgen Profitlich},
  title = {{An Empirical Analysis of Terminological Representation Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}

Loading related content...

Figure