Reasoning and querying over data streams rely on the ability to deliver a sequence of stream snapshots to the processing algorithms. These snapshots are typically provided using windows as views into streams and associated window management strategies. In this work, we explore a general notion of semantic importance that can be used for window management of RDF streaming data using semantically-aware processing algorithms. Semantic importance exploits the information in RDF streams and surrounding ontologies for ranking window data in terms of its contribution to solution mappings. We also consider how a stream window management strategy based on semantic importance could improve overall processing performance, especially as available window sizes decrease.
Stream reasoning has been proposed with the goal of bridging both
semantic reasoning and stream processing [
Keeping the eviction order linked to the arrival order for data works well
in systems like [
Our work is motivated by scenarios where stream reasoning needs more general window management strategies that preserve the most important data in the current window and preferentially evict the rest, so that the retained data can continue maximally leveraged.
The technical contributions include (1) the introduction of semantic importance along with an empirical de nition; (2) a conceptual model of semantic importance that includes RDF stream management metrics; (3) an exposition of how our semantic importance conceptual model can be used to encode orderings and improve stream reasoning system performance. 2
Semantic importance enables order-aware window management that considers not only the temporal attributes of the data, but also the data contributions to solution mappings. We de ne semantic importance using a set of key metrics, each of which captures di erent aspects, including but not limited to query contribution, provenance, trustworthiness and domain awareness.
Speci cally, for each datum 5 , its semantic importance is a priority vector
[
Figure 1 shows the current four aspects (in green color) of semantic importance. For query contribution, we further distinguish two components: frequency and recency. Frequency is an integer value that describes how many times a valid datum participates in the query, and recency describes the most recent timestamp for a valid datum participating in the query. Further, we distinguish two types of query contribution of a stream datum: query participation (direct graph pattern matching), and reasoning participation (intermediate graph pattern matching during reasoning) , where \participation" refers to the process in which the solution mapping6 is generated by SPARQL query and streaming data. Both query and reasoning participation have corresponding frequency and recency.
Provenance in Figure 1 is also a factor in judging the importance of a
streaming datum [
Trustworthiness is another aspect of semantic importance. Consider a smart
city application where many tra c sensors are installed, and a shifting number
of them are broken and issue erroneous readings. Assigning a speci c
trustworthiness score for each data element allows the system to manage the streaming
window based on whether the individual data elements can be trusted. [
Query contribution, provenance, and trustworthiness are largely independent of the precise subject matter of the RDF stream, and so they provide components of a generic model of semantic importance. However, speci c situated topics and reasoning tasks can contribute signi cant domain-dependent considerations. By examining the actual domain and speci c streaming data use cases, we can join generic aspects with domain-speci c ones, and model semantic importance in a more precise way. Our domain-aware aspect supports the modeling use case requirements, such as the goal of the streaming analysis, background knowledge and system constraints, etc. We are testing our approach in a soccer o side o ence detection use case, comprising data on the real-time position of the ball and everyone on the eld. Because only soccer players can commit o side o ences, we can conclude that positional data for the referees will never contribute to an o side o ence query7 , and can be ushed from the window. In order to enable domain-awareness in stream reasoning systems, we can provide a domain-aware importance ontology that encodes the domain information necessary for the pre-registered continuous queries. This is di erent from the background ontology that encodes the essential knowledge of the domain, and is speci cally focused on capturing domain knowledge that impacts querying and reasoning required to answer questions. 4
We discuss some interesting observations from our soccer use case experiments. First, window generation and moving is not constrained by semantic importance, 7 Referee's position would be relevant for being in a position to \see" the o ense but not actually to \a ect" if the o ense really occurs. whose focus is on window management. Second, semantic importance can interact with data arrival order. In FIFA Laws of the Game, a player commits an o side o ence by being in an o side position before interfering with the play. Thus :player :at :O sidePosition data must arrive earlier than :player :interfere :play. The query, who commits o side o ence, will not yield the result if these statements are not simultaneously in the window. Further, depending on the nature of the query, it is possible that neither alone will participate in the query, and so neither will be judged as semantically important without the other. And, if either datum is evicted from the window because it is not important, then the query will give an incorrect result. One possible solution is to decompose the query to alleviate query constraints.
We can decompose our o side query by asking who is at an o side position and who interferes with play. These two queries do not generate or combine results in stream, instead, they look for o side o ence relevant data so that the window can update the semantic importance and rank the data to preserve necessary information. Once all necessities are collected, the target query is executed to provide nal results.
Once the domain aware requirement ontology is in the system, domain literate ltering can be performed. Data can be ranked by its domain relevance, then irrelevant data can be ltered out because it is not important. Using the soccer o side example, any player information not used to calculate an o side position should not be considered as important. Domain literate ltering can signi cantly reduce the data space before the target query is executed, which enhances system response. It is typically suitable when the query relevant data is sparsely distributed in the data stream.
Semantic importance can be used to model several typical order-aware window management strategies: FIFO can be implemented as [ e; g], where e is the expiration timestamp and g is the generation timestamp. Least Frequently Used (LFU) as [ e; frp; g], where frp denotes the reasoning participation frequency and Least Recently Used (LRU) as [ e; rp; g], where rp denotes the reasoning participation recency timestamp. If domain literate ltering needs to be performed with FIFO, we can implement new strategy FIFO/DL as [dl; e; g] where dl denotes the domain literate ltering indicator.
Implementing semantic importance increases system overhead for computing the query contribution metrics because a reasoning explainer is required to trace back to the reasoning process to collect asserted statements. Domain literate ltering needs to perform a set of SPARQL queries that could potentially match a large fraction of the streaming data, which takes some time. 5
We presented our preliminary notion of semantic importance together with its key aspects, and described how to use semantic importance to enable orderawareness in stream reasoning. Semantic importance enables a exible, powerful, e cient and customizable framework to support window management that can maintain and potentially improve reasoning results in compute- and spacelimited settings. There are more details of our speci c use of semantic importance in the soccer o side o ence use case 8, where we have been able to show that semantic importance can be used to identi y important data, increase accuracy in reasoning-based query answers and be the basis of streaming window management strategies. In the future, we will further develop the conceptual model by both adding more aspects and enriching additional details of each aspect. 6
The research described in the paper is part of the Analysis in Motion research initiative at the Paci c Northwest National Laboratory, a multi-program national laboratory operated by Battelle for the U.S. Department of Energy under contract DE-AC06-76RLO-1830. The work was conducted under Laboratory Directed Research and Development (LDRD) funding from PNNL to RPI.