Scalable Maintenance of Knowledge Discovery in an Ontology Stream

Freddy LécuéIJCAI 2015

Abstract

This paper introduces InKD (Incremental Knowledge Discovery), a framework for efficiently maintaining and updating semantic rules in dynamic ontology streams. By leveraging metrics such as "knowledge similarity" and "rarity" to prune unnecessary computations, InKD achieves high-accuracy rule discovery that scales significantly better than traditional "mine-from-scratch" approaches.

Introduction

In the modern Semantic Web, data is increasingly exposed as ontology streams—sequences of ABox assertions that evolve over time while adhering to a fixed TBox. A critical challenge in this domain is Knowledge Discovery: identifying hidden associations or stochastic rules (e.g., predicting bus delays based on traffic incidents) in real-time. Traditional methods often ignore the underlying semantics or suffer from exponential complexity by re-calculating rules from scratch at every update. This paper addresses the need for a scalable, incremental approach to rule maintenance in high-velocity environments.

Proposed Methodology

The authors propose InKD (Incremental Knowledge Discovery), which manages rules across a sliding window using three primary mechanisms:

  1. Knowledge Similarity ($\Phi$): This metric measures changes in logical entailments between successive windows. High similarity allows the system to bypass heavy re-computation.
  2. Knowledge Rarity ($\varepsilon$-rarity): By identifying and pruning rare information that is unlikely to yield significant general rules, the search space is effectively reduced.
  3. Incremental Algorithms: The framework employs Algorithm 1 (Interest Update) to adjust rule support and confidence as the window slides, and Algorithm 2 (Rule Expansion) to incorporate new knowledge.
Conceptual overview of windowed streams, knowledge similarity, and rarity.

The underlying logic uses the $\mathcal{EL}^{++}$ profile, ensuring that reasoning remains computationally efficient (polynomial time).

Experimental Setup

The InKD framework was evaluated using real-world data from Dublin City, Ireland. The dataset integrated five streams—Weather, Travel Time, Incident, Event, and Bus GPS—mapped to an $\mathcal{EL}^{++}$ ontology containing 55 concepts and 19 roles.

Results and Analysis

The evaluation focused on scalability and accuracy. InKD (A3) demonstrated superior performance compared to the baseline batch-mining approach (L15).

Scalability comparison of InKD (A3) against baselines across varying window sizes and sliding parameters.

Key findings include:

  • Scalability: While batch-mining computation times spiked with larger window sizes, InKD remained stable.
  • Accuracy: The system maintained approximately 91% accuracy relative to perfect batch results, despite pruning rare data.
  • Efficiency: Discarding "1-rare" knowledge (appearing only once) improved scalability by 11.4% with minimal impact on rule quality.

Conclusion

InKD demonstrates that maintaining a rule set incrementally is far more scalable than re-mining from scratch. By focusing on semantic similarity rather than syntactic changes, the framework provides a robust solution for real-time knowledge discovery. Future work will explore more expressive logics and compact stream representations to further enhance performance in highly volatile environments.

Reference: Lécué, F. (2015). Scalable Maintenance of Knowledge Discovery in an Ontology Stream. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015).

Summary updated

BibTeX
@inproceedings{lecue2015scalable,
  author = {Freddy Lécué},
  title = {{Scalable Maintenance of Knowledge Discovery in an Ontology Stream}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure