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:
- Knowledge Similarity ($\Phi$): This metric measures changes in logical entailments between successive windows. High similarity allows the system to bypass heavy re-computation.
- Knowledge Rarity ($\varepsilon$-rarity): By identifying and pruning rare information that is unlikely to yield significant general rules, the search space is effectively reduced.
- 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.
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).
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