Distributed Heterogenous Stream Reasoning

With the development of the Web and data interlinkage, distributed computation has become essential for modern information systems. To facilitate real life applications in such distributed and heterogeneous environmentswhere information might be incompleteagents need intelligent decision making components (IDMCs) for advanced and complex reasoning tasks. Furthermore, an increasing involvement of sensors, networks, mobile devices, generates a trend towards pushing rather than pulling data in information processing, and streamed data has become important. Therefore, IDMCs dealing with such data must perform efficiently. Stream Reasoning thus recently gained interest from different communities that focus on different aspects. On one hand, stream processing concentrates on low-level, high rate input data for tasks like cross-joining data, pattern matching; while in Knowledge Representation and Reasoning (KRR), preliminary works have been carried out to deal with streaming input, but they are not positioned to deal with high data rate. Among these two approaches, few works consider distributed environments, and none has investigated frameworks allowing heterogeneous processing/reasoning powers cooperating in a streaming fashion. Furthermore, the relationships between different proposals are unclear since they were independently developed under different principles, thus hinder systematic/comparative views among them. This project aims at extending advanced reasoning to handle stream data. Although this ultimate purpose is challenged by the fact that data may arrive, change at very high rates, while solving complex reasoning tasks may take considerable time, it seems achievable as (1) often those complex tasks need only high-level, abstract instead of low-level view of data, and (2) at this level, changes occur much less frequently. Under this hypothesis, our goals are to (i) develop formal semantics for stream reasoning, including an ideal semantics serving incomplete information and non-monotonicity, and an adaptive semantics for changing high-level data rate; (ii) bring in distributedness, heterogeneity; (iii) understand the frontier of scalability to develop algorithms, approximation/optimization techniques for efficient evaluation; and (iv) build rigorous means to compare stream processing/reasoning approaches on both theoretical and practical aspects. This project will yield thorough theoretical results on distributed heterogeneous stream reasoning, an experimental prototype implementation that scales, and a benchmarking framework for qualitative/systematic comparisons of stream processing/reasoning approaches. We believe that our goal is achievable as besides the hypothesis techniques from related fields will be useful. For example, theories behind model-oriented formalisms from KRR (SAT solving, Answer Set Programming) can be a starting point to pursue an ideal semantics; adaptive evaluation, incremental evaluation/reasoning (resp., load shedding, semantics relaxation) can be investigated for optimizations (resp. approximation). Furthermore, the S2Gen data generator can be employed to generate social network scenarios to evaluate the implementation, and our preliminary work on comparing linked stream data engines as a starting point to develop the benchmarking framework. Our system shall be publicly available as open source software.

This project deals with logic-oriented processing of data streams. The rapid increase of data during the last two decades has led to a multitude of novel developments, specifically for the processing of streaming data. Applications range from the continuous evaluation of sensor data, to real-time analysis of server log files to the evaluation of running entries in social networks. Existing techniques usually focus on scalability and efficient, often parallel or distributed processing of relatively easy computations such as aggregations. In particular, query languages for static data, like SQL or SPARQL (for the Semantic Web), have been extended for streaming data that allows one to access recent information from data streams via so-called windows (e.g. time windows).Declarative languages in particular should come with a definition of their exact semantics, which in the streaming context often have not been specified due to a lack of a formal theory to express them. More specifically, there was no mathematical basis for logical reasoning over streaming data using windows. Knowledge Representation & Reasoning research, for instance, provides such logic-oriented languages and methods for inherently difficult problems. However, they work almost exclusively on static data; comparable approaches for streaming data were not available.The central result of this project is precisely such a formal language for logical reasoning over streaming data. The proposed framework can be used for analyzing and comparing existing approaches but it may also serve as stream reasoning language on its own. Our research was carried out along both lines: on the one hand we formalized the informal semantics of selected existing languages, on the other hand our language itself was utilized to further explore fundamental questions. These included the potential for optimization of queries and programs based on their semantic equivalence and the study of a novel distributed semantics that can arise in a network of arbitrary, heterogeneous nodes (such as servers) when they continuously exchange data.Since the computation of results may take too long when data is continuously streaming in, incremental evaluation becomes a central challenge, in particular when dealing with non-monotonic reasoning, where previous conclusions might have to be retracted. We developed algorithms for incremental reasoning over data streams and implemented them, leading to two prototypical stream reasoning systems that have been empirically tested.