C.1.3 [Other Architecture Styles]: Data- ow architectures|stream reasoning ; D.2.11 [Software Architectures]: Patterns

1.

Streaming data are increasingly pervasive on the web, however many semantic applications may not be well aligned with the requirements of streaming data applications[ 17 ]. The Semantic Web[ 9 ] architecture has traditionally concentrated on storing and linking the web of data, rather than on managing rapidly changing data streams that become obsolete over time[ 16 ]. Although capable of processing data streams at large scale with a high velocity data rate, the primitive operations in the data-stream management systems[ 14 ] have not typically addressed the extraction of hidden knowledge via complex reasoning. In 2009, E. Della Valle et al.[ 15 ] introduced the research area of stream reasoning with the aim to bridge the gap between semantic reasoning and stream processing. Stream reasoning can provide many bene ts in application areas that demand generation and analysis of data streams. Examples include smart cities[ 27 ][ 22 ], social networks[ 5 ] and nancial market data feeds[ 26 ]. These data streams often have diverse conceptual models and physical formats and thus pose challenges for e ective semantic processing and reasoning.

The best practices for linking static information on the web have inspired several solutions to face these challenges. Examples include extending RDF and Linked Data principles to model data streams, extending SPARQL to continuously process RDF streams, and implementing e cient stream reasoning systems. 1.1

In 2009, E. Della Valle et al.[ 15 ] envisioned two alternative RDF stream formats, namely the RDF molecules stream and RDF statements stream. The former is an in nite number of pairs < , >, where is an RDF molecule[ 19 ], and is a timestamp denoting the arrival time of ; the latter is a special case of the former, where only contains one statement.

D. F. Barbieri et al.[ 8 ] proposed an approach to publish data streams as Linked Data. In this work, an RDF stream is de ned as an ordered sequence of pairs, each of which consists of an RDF triple and a monotonically non-decreasing timestamp .

An RDF stream[ 4 ] is identi ed by a unique IRI that is a streaming source locator, and is published in a named graph[ 13 ]. Each named graph is given an IRI that is designed following the guidelines of Cool URIs[ 25 ] and best practices on how to publish Linked Data on the Web[ 10 ].

RDF streams are generated and consumed in a certain order. This order can be a natural time-based order, or it may use another ranking criteria such as importance or precision. Thus, semantic RDF Stream Processing (RSP) systems should be able to manage data with rank-awareness and time sensitiveness. 1.2

Existing RDF Stream Processing Systems C-SPARQL[ 4 ], among the initial RSP1 languages, is a continuous extension of the standard SPARQL. It is tailored to semantically process data streams and facilitate reasoning. A C-SPARQL query is registered in a form of either a stream or a query, prior to the arrival of data streams. Its execution model is inherited from CQL[ 3 ], including operators of stream-to-relation, relation-to-relation and relationto-stream. Its built-in translator will translate a C-SPARQL query into static and dynamic parts, and execute them separately. The C-SPARQL engine can be used as a linked data stream publisher[ 8 ].

Other works such as EP-SPARQL[ 2 ], TrOWL[ 28 ] and Stream SPARQL[ 12 ] are either extensions of SPARQL from di erent angles or are built from scratch to ful ll the purpose of continuously processing and reasoning on data streams. The IMaRS[ 6 ] algorithm has been proposed by the same authors of C-SPARQL, and is focused on inferred statement management (mainly statement deletions) in a time-based sliding window. This algorithm assigns an expiration timestamp for each RDF statement entering into the window, labels and updates all the related inferences with this expiration timestamp. The expiration timestamp is the time

This paper proposes a cache-enabled, order-aware, ontologybased stream reasoning framework. This framework is able to process and reason across dynamic streaming data and provide correct results. It uses a background ontology that describes the domain knowledge where the streaming data is interpreted. It also leverages a data cache and a set of order-aware data management strategies. Our framework is built under the following assumptions.

The background ontology is provided by domain experts and does not change during processing.

The streaming sources encapsulate the streaming data in unique named graphs and assign expiration timestamps.

An arrival timestamp is assigned to each streaming graph by the framework.

Under these assumptions, we list the following contributions.

We leverage a data cache and order-aware algorithms2 in a stream reasoning context to manage and process RDF streams.

We de ne semantic importance as a ranking strategy and show its value to distinguish a cache from a window, facilitate order-awareness and data management in the cache.

We implement three prototypes3 based on o -the-shelf triplestores, and evaluate them under di erent cache con gurations4 from the following aspects: { runtime of query, reasoning, reasoning explanation and data eviction { the statistics of precision, recall and F-measure We discuss the trade-o s to deploy our framework in di erent scenarios where small, medium and large RDF streams are processed.

We use the cache as our framework's central component to manage the RDF streams. Similar to what a window does in other RSP settings, the cache works as a stream-to-relation (S2R) operator[ 7 ], isolating a portion of the unbounded RDF streams. However, crucial di erences between them lie in both their data consumption rules and data eviction strategies. The window consumes RDF streams by sliding along them. This restricts data eviction to only be FIFO, namely the window is only able to move forward by deleting some old data. The cache keeps static and is fed by RDF streams. It has exibility to utilize semantics (the background ontology and any processing results) to inform its eviction and potentially consumption. All cached RDF streams can be ranked using di erent types of criteria. Temporal orders (arrival and/or expiration) are most common although other considerations including precision, popularity, trust, certainty, and provenance have been proposed [ 17 ]. We can leverage all of these rankings in our data eviction policies and in addition, we add reasoning perspectives to the criteria for ranking.

FIFO can be realized by ranking arrival timestamps. First Expired First Out (FEFO) can be realized by ranking expiration timestamps to guarantee valid results. Semantic ranks can also be provided from the reasoning and/or query participation status of the data.

In order to present these semantic ranks, we would like to introduce the notion of semantic importance. For each named graph in the cache, its semantic importance (SI) is de ned as an indicator that measures its contribution to the reasoning and/or query results. The cache ranks all named graphs according to their SI. This notion is intentionally abstract so as not to limit its application in di erent data eviction strategies where a named graph's contributions are speci ed. For every named graph in FIFO, its SI is based on its arrival timestamp. For every named graph in FEFO, its SI is based on its expiration timestamp. The cache also uses Least-Frequently-Used and Least-Recently-Used algorithms to semantically rank the data. In Least-Frequently-Used, SI is embodied as a total reasoning-participation frequency counter of a named graph. In Least-Recently-Used, SI is embodied as the most recent reasoning-participation timestamp of a named graph. SI can also be composite under the scenario where multiple data eviction strategies are applied.

We have discussed above that there are distinctions between a window and a cache, and SI is among the keys to distinguish them. SI is mentioned in several published papers but never as a core topic. In[ 11 ], the authors use SI as an attribute of interface objects to improve the design of traditional GUIs in the Computer Human Interaction (CHI) domain. In[ 23 ], the authors use SI to lter Snooker balls in order to 3D reconstruct the game for analysis. In[ 31 ], the authors use SI to di erentiate the semantic components in semantic-linked network. Nonetheless, none of these works formally de ne SI. This, together with the value that the SI provides in the stream reasoning context, contributes to our motivation for de ning it for the stream reasoning context.

Our framework utilizes background knowledge encoded in OWL[ 24 ] when processing RDF streams. The ontology is loaded into the cache prior the data arrival, and provided by the domain experts. It describes the speci c domain knowledge necessary to interpret the RDF streams. However, its expressiveness should be considered together with the query and deployed reasoner ability. If the ontology is in a description logic (DL) pro le and the query requires DL reasoning, but the reasoner only provides RDFS reasoning, then the goal will not be achieved. Generally speaking, the purpose of the ontology is to provide enough domain background information and enable reasoning, which will help the query answer questions that cannot be answered directly from the explicit data. 2.1

Our framework consists of four sequential components: data consumption, querying and reasoning, reasoning explanation and data eviction. These four components are executed in order. The execution ow forms a loop to process data streams and to produce query results in a continuous fashion, as it is shown in Figure 1. 2.1.1

We have implemented our framework using two o -theshelf triplestores, AllegroGraph V5.0.27 and Stardog 4.0 RC38. Both provide Java APIs and step-by-step tutorials. AllegroGraph is a modern and e cient graph database and a commercial product of Franz Inc9. It supports up to OWL2 RL reasoning and full SPARQL 1.1. Stardog is a graph database by Complexible Inc10. It supports up to OWL2 DL & rulebased reasoning and SPARQL 1.1. We use the free versions of both products.

Stardog has an important feature - the ability to support reasoning explanation. An entailment is explained by tracking back to the original asserted statements, which form a proof tree that includes all the statements involved during the reasoning. Stardog also supports merging proof trees because the same inferred statements can be generated utiliz

The stream reasoning community has not yet come to consensus on the best method to evaluate stream reasoning applications. In 2012 SRbench[ 30 ] was proposed as a general benchmark system designed to test streaming RDF/SPARQl engines. In the same year, LSBench[ 21 ] was proposed to focus on assessing di erent Linked Stream Data (LSD) applications' capabilities. The following year CSRBench[ 18 ] was proposed with a special emphasis on the e ects of operation semantics for stream reasoning applications. More recently CityBench[ 1 ] was proposed to target smart city applications. We chose the LUBM benchmark[ 20 ] dataset because it is easy to use and satis es our needs. LUBM provides a wellconstructed ontology describing the relations among universities, professors and students etc. It also features a data generator which accepts customized parameters to generate arbitrary ABox data.

Our work produced 6,031,109 ABox triples. A data source generates streaming data by disk-reading this generated data line-by-line from a static n-triples le. We con gured the streaming throughput as follows:

The streaming source packs either 1, 10 or 100 triples per named graph, Tpg.

Each graph is assigned a unique graph id and expiration timestamp by the streaming source12. 11The team used Stardog to test OWL-DL reasoning on streaming data[ 29 ], but these results are not included within the scope of this paper. 12http://streamreasoning.org/slides/2015/10/sr4ld2015-02

The framework assigns an arrival timestamp to each arriving named graph in a monotonically non-decreasing order.

The streaming data is then streamed to our three prototypes, where the cache is con gured as follows:

Cs is either 10, 100 or 1000 graphs.

Ea is either 25%, 50%, 75% and 100% of Cs.

The pre-registered query, as shown in Figure 4, requires RDFS reasoning.

The background ontology is pre-loaded into the cache Our evaluation platform speci cations include 14.04 64bits Ubuntu LTS operating system, Intel(R) Xeon(R) CPU E52620 v2 @2.10GHz, 2040MB memory, and 16GB HDD.

Together with the generated ABox data and provided LUBM ontology we conducted 252 experiments and obtained a ground truth of 27,192 results as the basis to test the framework's correctness on precision, recall and F-measure. We also recorded each prototype's memory consumption, runtime of querying, reasoning explanation and data eviction under di erent con guration combinations of streaming data and cache. We did not record reasoning explanation time for all the FEFO strategy and other strategies with the Ea = 100% of Cs, because the FEFO does not need reasoning explanation, and it does not make sense to explain reasoning as the whole cache will be dumped.

Using these results we ask the following questions: 1. What are the e ects of di erent caches from di erent producers (AllegroGraph v.s. Stardog), types (diskbased v.s. memory-based) and con gurations (di erent combinations of Cs and Ea)? rsp-extensions.pdf, Page 7, from \Streaming Reasoning for Linked Data 2015\ by J-P Calbimonte, D. Dell'Aglio, E. Della Valle, M. I. Ali and A. Mileo. 2. How do various strategies perform under di erent combined con gurations of the streaming data and cache (currently we are using F-measure to evaluate the performance)? 3. What are the trade-o s to consider when deploying our framework in di erent scenarios? We show two gures of the total forty-six visualizations13 generated from the results to answer the rst two questions. The third one will be thoroughly discussed in the next section.

For the sake of convenience, we use the following abbreviations in the rest of this paper: prototypes are abbreviated such that SM denotes Stardog memory-based cache, SD denotes Stardog disk-based cache and AD denotes AllegroGraph disk-based cache. Each test case is labeled as < prototype abbreviation > < data management strategy > < streaming data con guration >. For example, SD FEFO 1 denotes a Stardog disk-based cache that performs FEFO strategy to process RDF streams with 1 triple per graph.

Figure 5 shows the F-measure performances brought by caches of di erent producers, types and con gurations. There are several facts that can be easily captured:

The F-measure increases as the streaming throughput increases.

The F-measure at 50% is always best, and 100% is always worst for all visualized cases. 13Please refer to out github repository for all visualizations. AD FEFO performs similarly as others do when streaming throughput is 1 triple per graph, but outperforms as the streaming con guration increases.

SD FEFO and SM FEFO compete with each other in each test run.

This can partially answer the rst question, with the points that di erent brands do a ect the F-measure performance, but di erent types do not have a signi cant in uence. The greater the streaming throughput, the more in uences are made on the F-measure. However, in order to give a thorough answer we need to look at other metrics before assessing the overall performances of these caches. For example, AD FEFO gives the best F-measure, but does it take more time to execute the query and data eviction?

Figure 6 shows the F-measure performance by di erent strategies for the SM cache with di erent streaming data con gurations. The observed facts are:

The F-measure score increases as the streaming throughput increases. 50% eviction amount has the biggest F-measure score, 100% has the smallest score for all the cases.

For the same streaming data con guration, LFU always performs best, followed by LRU and then FEFO. These observations can answer the second question from the perspective of big cache size. Nevertheless, does cache size a ect these strategies' performances? Does it take longer time to explain all of the inferences? If yes, is it worthwhile to sacri ce system responsiveness for a better F-measure? Additional observations are as follows:

F-measure score: Our raw experimental results have shown that F-measure increases as the cache size increases. The F-measure score is also a ected by different triplestores. We believe this is because AlllegroGraph's and Stardog's inner processing engines and mechanisms are di erent 14.

Memory consumption: when Cs = 10, cases of Tpg = 1 require 3 times on average the memory of bigger streaming con gured cases. When Cs = 100, the overall memory consumption decreases as the eviction amount increases. When Cs = 1000, the overall memory consumption increases as the eviction amount increases. However, within this evaluation, no signi cant di erences are observed between memory-based cache and disk-based cache. Small cache and streaming throughput cases usually requires more memory. Average FEFO strategy memory consumed is 41.93MB, LRU is 40.4MB and LFU is 39.59MB.

Query time: AD requires the most query time for all cases. SD requires less time than AD but more than SM. The query time increases as cache size and streaming throughput increases. One potential reason for this is because a disk-based cache needs some IO time when executing a query, which takes more time than a memory-based cache. Average query time for all FEFO cases is 18ms, LRU is 15ms, LFU is 13ms. 14Exploration and explanation of triplestores' inner implementations are out of the scope of this paper Explanation time: reasoning explanation time increases approximately linearly as cache and streaming throughput increases. In most cases, LFU takes longer time to explain. Average LFU explanation time for all LFUcases is 90371ms, LRU is 86100ms.

Eviction time: eviction time increases as eviction amount, cache size and streaming throughput increases. AD eviction time is very fast, 30ms on average. SD on average is 2879ms. SM on average is 4042ms.

According to the cache and streaming data con gurations, there can be either 10, 100, 1,000, 10,000 or 100,000 triples in the cache during one processing loop. We identify a small case where 10 or 100 triples are processed, a medium case where 1,000 or 10,000 triples are processed, and a large case where 100,000 triples are processed. Together with Table 2 We present a thorough comparison among triplestores, cache types and data management strategies under these scenarios.

We summarize our experimental results in Table 2 to help answer the third question in the previous section, i.e., what are the trade-o s to consider when deploying our framework in di erent scenarios?

Under the small case, AllegroGraph's query and eviction time is several times that of Stardog. Disk and memory performs equally on F-measure, though disk requires more time to query, evict and explain. LFU performs best in Fmeasure, followed by LRU then FEFO. Though FEFO needs more time to query and evict, the explanation time required by LRU and LFU is signi cantly greater. The trade-o s in deploying our framework under the small scenario is dependent on the use case. If system responsiveness is the rst class citizen, a FEFO strategy will be chosen since it does not require explanation and provides a ne F-measure. Stardog memory cache can be chosen since it provides faster execution time and better F-measure. If F-measure is most important, LFU is the right strategy. Stardog memory cache is the best as memory cache provides less explanation time. It is also noticed that Ea = 25% or 50% of Cs provides better F-measure.

For medium cases, Stardog's eviction time increases signi cantly. Though Stardog's query time is better than AllegroGraph's, the di erence is very small when compared with the eviction time. Disk cache provides less eviction time; its other metrics are similar as memory caches. LFU is the best at F-measure scores, but is traded for longer explanation time. Actually FEFO provides decent F-measure without explanation time. Overall, AllegroGraph disk cache with FEFO is most suitable for this scenario. Ea = 50% or 75% of Cs provides best F-measure as well.

For large cases, AllegroGraph's eviction time, F-measure and memory performs better, though query is slower. Disk cache query time is 9 times greater than the memory dependent graph database, but provides better F-measure, explanation , eviction time and memory. FEFO performs best in F-measure but it spends more time on query, with smallest eviction time and memory consumption. Hence, AllegroGraph disk cache with FEFO is most suitable for this experiment's use case. It is also recommended to use Ea = 50% of Cs to provide the best F-measure. 5.

CONCLUSIONS AND FUTURE WORK We have discussed the distinctions between a window and a cache, highlighted some challenges with a simple sliding window, and have described the enhanced data eviction exibility that a cache is able to provide. We have de ned semantic importance as a ranking strategy and showed how it can be exploited in a stream-reasoning context. We implemented semantic importance with a range of settings and evaluated them, laying the foundation for expanding the range of data management strategies. We have also presented our cache-enabled stream reasoning framework. By leveraging a cache and a set of data management strategies, this framework is able to consume RDF streams on the y while performing reasoning and answering standing queries. The cached RDF streams are ranked according to the semantic importance, and data are evicted when as less important or expired. We have implemented three prototypes of the proposed framework, and evaluated them by emulating an RDF stream generated by LUBM and time stamped with arrival and expiration times. We also discussed the trade-o s of deploying our framework in di erent scenarios.

In this work, our framework and prototypes are evaluated on a synthetic situation. Future work includes applying our framework on realistic data set benchmarks such as SRbench, as well as apply our work on some compelling use cases such as smart cities.15

Our current data eviction strategies are domain agnostic. We will also develop some domain literate strategies for our actual scenarios. (We have partially applied the framework in one streaming NMR setting with one simple domain-aware strategy yielding promising results). We noticed that the reasoning environment in this work is limited due to AllegroGraph's limited reasoning ability, and would like to explore more complex reasoning in OWL DL and/or rule-based reasoning as our future work as well. 6.

The research described in this paper is part of the Analysis in Motion Initiative at Paci c Northwest National Laboratory. It was conducted under the Laboratory Directed Research and Development Program at PNNL, a multi-program national laboratory operated by Battelle for the U.S. Department of Energy.

We would like to thank Dr. Mark T. Greaves from PNNL for his valuable thoughts and discussions that helped shape the work and this paper. We also want to thank Dr. Emanuele Della Valle from the Politecnico di Milano for his inspiring discussions and encouragement to this work. 7. 15We plan to http://dublinked.ie/ use

Dublin

City datasets from Each value in the table is calculated from raw experimental results. Please refer to our github repository for these raw results. In the 10 triples/cache scenario, for example, disk-based cache's F-measure score is averaged from AD FEFO, SD FEFO, SD LRU & SD LFU test cases, while memory-based cache's score is averaged from SM FEFO, SM LRU & SM LFU test cases.

We would like to highlight an empirical comparison of the two cache types, the disk-based cache (DC) and the memory-based cache (MC).

SPARQL query time: for every scenario, DC is slower than MC. As the scenario increases, DC grows much faster than MC. The ratio between 100,000 triples/cache and 10 triples/cache for DC is 15.45, whilst MC is 3.34. Though DC is less restricted by storage space, its query time slows down the system response time, and this e ect will become worse as the scenario size grows. However, this is expected, as accessing disk when executing query is always slower than accessing the memory.

F-measure: for every scenario, DC's and MC's F-measure scores are very similar. This means both types are able to provide same level correctness. F-measure increases as scenario increases, this is because the more data in the cache, the more correct results can be calculated, which raises the F-measure.

Reasoning Explanation Time: in most scenarios, MC's explanation time is slower than DC's. The di erence increases signi cantly as the scenario size increases. Reasoning explanation is very time-consuming. Strategies (such as LFU) requiring reasoning-explanation provide better F-measure when the scenario is small and explanation time is quick, but provide similar F-measure when the scenario is large and explanation time is slow.

Eviction Time: in small scenarios, DC is slower; in medium and large scenarios, MC is slower. The di erence between DC and MC increases signi cantly as the scenario size increases. This indicates a bias towards DC for large RDF streams, and MC for small RDF streams.

Memory Consumption: Both DC and MC consume similar memory for each scenario. This could be because Stardog triplestores are implemented very e ciently, but again, explaining this requires the knowledge of inner mechanisms of Stardog, which is out of the scope of this work.