Enhancing the Scalability of Expressive Stream Reasoning via input-driven Parallelisation

Tracking #: 1750-2962

This paper is currently under review
Thu-Le Pham
Ali Intizar
Alessandra Mileo

Responsible editor: 
Guest Editors Stream Reasoning 2017

Submission type: 
Full Paper
Stream reasoning is an emerging research area focused on providing continuous reasoning solutions for data streams. The exponential growth in the availability of streaming data on the Web has seriously hindered the applicability of state-of-the-art expressive reasoners to be applied to streaming information in a scalable way. However, we can leverage advances in continuous processing of Semantic Web streams to reduce the amount of data to reason upon at each iteration. Following this principle, in previous work we have combined semantic query processing and non-monotonic reasoning over data streams in the StreamRule system. We specifically focus on the scalability of a rule layer based on a fragment of Answer Set Programming (ASP). We recently expanded on this approach by designing an algorithm to analyse input dependency so as to enable parallel execution and combine the results. In this paper, we expand on this solution by providing i) a proof of correctness for the approach, ii) an extensive experimental evaluation for different levels of complexity of the input program, and iii) a clear characterization of all the algorithms involved in generating and splitting the graph and identifying heuristics for node duplication, as well as partitioning the reasoning process and combining the results.
Full PDF Version: 
Under Review