Large Scale Knowledge Base Systems: An Empirical Evaluation Perspective

Yuanbo Guo, Abir Qasem, Jeff HeflinAAAI 2006

Introduction

As the Semantic Web continues to expand, AI systems face a critical "Goldilocks" challenge: they must be sophisticated enough to perform complex reasoning using languages like OWL, yet efficient enough to process millions of data points. Traditional AI evaluations often focus on whether a system is "sound and complete"—meaning it identifies every correct answer without error. However, in a massive, distributed web environment, a system that is 100% complete but takes a week to respond is practically useless.

This paper introduces the Lehigh University Benchmark (LUBM), the first standardized tool designed to evaluate how Semantic Web knowledge base systems (KBSs) handle massive datasets. It moves beyond simple pass/fail reasoning tests to provide a nuanced look at the inevitable trade-offs between a system's scalability and its logical completeness.

The LUBM Benchmarking Framework

The authors developed a comprehensive framework consisting of four pillars to measure the performance-reasoning trade-off at scale:

  1. Custom Ontology: A moderately sized OWL ontology describing the university domain (departments, professors, students, etc.).
  2. Synthetic Data Generation: A tool that generates repeatable, realistic instance data. Crucially, this can be scaled to any size, allowing researchers to test how systems behave as data grows from thousands to millions of triples.
  3. Test Queries: Fourteen specific queries designed to test different aspects of a system, such as handling large input sizes, high selectivity, and complex logical inferences.
  4. New Performance Metrics: Beyond speed, the authors introduced metrics for the degree of completeness (doc) and degree of soundness (dos). Inspired by "recall" and "precision" from information retrieval, these metrics acknowledge that a partial but fast answer is often better than no answer at all in a web context.

The Scalability-Reasoning Frontier

A core insight of the research is the visualization of a "frontier" where current systems reside. Some systems are highly scalable but logically limited (like basic RDFS systems), while others possess high inference capabilities but suffer from poor performance. The goal of the field is to push this frontier outward, improving both dimensions simultaneously.

The Scalability-Reasoning Frontier illustrates the inherent trade-off between a system's ability to handle large datasets and its logical inference capabilities.

Empirical Results and Performance Trade-offs

The authors tested several prominent systems of the era, including Sesame, DLDB-OWL, and OWLJessKB. The results highlighted significant differences in how these systems manage the trade-off between reasoning depth and speed:

  • OWLJessKB supported the most complex reasoning but struggled significantly with scalability.
  • Sesame-Memory was capable of loading larger datasets than expected but hit a performance "wall" once a certain data threshold was crossed.
  • DLDB-OWL leveraged relational databases (SQL) for scalability, showing a clear path for handling massive datasets by sacrificing some reasoning depth.
Query response times for DLDB-OWL and Sesame-DB across 14 benchmark queries, illustrating performance variations on a logarithmic scale.

The research also highlights a major trade-off in system architecture: systems like Sesame perform all inferences during data loading, which makes queries fast but limits the total amount of data the system can ingest. In contrast, database-backed systems like DLDB-OWL can handle much larger volumes by deferring or simplifying reasoning.

Conclusion and Future Work

While LUBM provides a vital tool for evaluation, it is currently limited to the university domain. The authors acknowledge the need for a suite of benchmarks representing different workloads and domains. Future work includes developing algorithms that can "learn" from small amounts of real-world data to generate representative synthetic data for any domain. As Semantic Web standards evolve, the benchmark must continue to adapt to more expressive languages and new types of distributed reasoning.

Summary updated

BibTeX
@inproceedings{guo2006large,
  author = {Yuanbo Guo and Abir Qasem and Jeff Heflin},
  title = {{Large Scale Knowledge Base Systems: An Empirical Evaluation Perspective}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure