C-Sprite: Efficient Hierarchical Reasoning for Rapid RDF Stream Processing

Many domains, such as the Internet of Things and Social Media, demand to combine data streams with background knowledge to enable meaningful analysis in real-time. When background knowledge takes the form of taxonomies and class hierarchies, Semantic Web technologies are valuable tools and their extension to data streams, namely RDF Stream processing (RSP), offers the opportunity to integrate the background knowledge with RDF streams. In particular, RSP Engines can continuously answer SPARQL queries while performing reasoning. However, current RSP engines are at risk of failing to perform reasoning at the required throughput. In this paper, we formalize continuous hierarchical reasoning. We propose an optimized algorithm, namely C-Sprite, that operates in constant time and scales linearly in the number of continuous queries (to be evaluated in parallel). We present two implementations of C-Sprite: one exploits a language feature often found in existing Stream Processing engines while the other is an optimized implementation. The empirical evaluation shows that the proposed solution is at least twice as fast as current approaches.