The trade-off between language expressiveness and system scalability (E&S) is a well-known problem in RDF stream reasoning. Higher expressiveness supports more complex reasoning logic, however, it may also hinder system scalability. Current research mainly focuses on logical frameworks suitable for stream reasoning as well as the implementation and the evaluation of prototype systems. These systems are normally developed in a centralized setting which suffer from inherent limited scalability, while an in-depth study of applying distributed solutions to cover E&S is still missing. In this paper, we aim to explore the feasibility of applying modern distributed computing frameworks to meet E&S all together. To do so, we first propose BigSR, a technical demonstrator that supports a positive fragment of the LARS framework. For the sake of generality and to cover a wide variety of use cases, BigSR relies on the two main execution models adopted by major distributed execution frameworks: Bulk Synchronous Processing (BSP) and Record-at-A-Time (RAT). Accordingly, we implement BigSR on top of Apache Spark Streaming (BSP model) and Apache Flink (RAT model). In order to conclude on the impacts of BSP and RAT on E&S, we analyze the ability of the two models to support distributed stream reasoning and identify several types of use cases characterized by their levels of support. This classification allows for quantifying the E&S trade-off by assessing the scalability of each type of use case its level of expressiveness. Then, we conduct a series of experiments with 15 queries from 4 different datasets. Our experiments show that BigSR over both BSP and RAT generally scales up to high throughput beyond million-triples per second (with or without recursion), and RAT attains sub-millisecond delay for stateless query operators.
Both StreamRule @cite_29 and its recent parallelized version StreamRule @math @cite_3 use a RSP engine for data stream pre-filtering and Clingo as the ASP solver. The expressiveness of BSP implementation in BigSR can fully cover StreamRule and StreamRule @math , since the implementation in these two reasoners stay on positive stratified Datalog program. Evaluation of StreamRule StreamRule @math showcases that the average throughput is around thousand-triples second with second-level delay. Comparatively, our BSP implementation has almost three orders of magnitude gains. Laser @cite_12 and Ticker @cite_7 are both stream processing systems based on the LARS framework but do not concentrate on scalability. Ticker concentrates incremental model maintenance and sacrifices performance by relying on an external ASP engine (Clingo). Laser also proposes an incremental model based on time interval annotations which can prevent unnecessary re-computations. Although Laser claims to represent a trade-off between expressiveness and data throughput, it cannot scale the way BigSR enables to. This is mainly due to Laser's inability to distribute stream processing.
@cite_7 @cite_29 @cite_12 @cite_3
2738428769 2140044869 2740522510
An increasing number of use cases require a timely extraction of non-trivial knowledge from semantically annotated data streams, especially on the Web and for the Internet of Things (IoT). Often, this extraction requires expressive reasoning, which is challenging to compute on large streams. We propose Laser, a new reasoner that supports a pragmatic, non-trivial fragment of the logic LARS which extends Answer Set Programming (ASP) for streams. At its core, Laser implements a novel evaluation procedure which annotates formulae to avoid the re-computation of duplicates at multiple time points. This procedure, combined with a judicious implementation of the LARS operators, is responsible for significantly better runtimes than the ones of other state-of-the-art systems like C-SPARQL and CQELS, or an implementation of LARS which runs on the ASP solver Clingo. This enables the application of expressive logic-based reasoning to large streams and opens the door to a wider range of stream reasoning use cases. In complex reasoning tasks, as expressible by Answer Set Programming (ASP), problems often permit for multiple solutions. In dynamic environments, where knowledge is continuously changing, the question arises how a given model can be incrementally adjusted relative to new and outdated information. This paper introduces Ticker, a prototypical engine for well-defined logical reasoning over streaming data. Ticker builds on a practical fragment of the recent rule-based language LARS which extends Answer Set Programming for streams by providing flexible expiration control and temporal modalities. We discuss Ticker's reasoning strategies: First, the repeated one-shot solving mode calls Clingo on an ASP encoding. We show how this translation can be incrementally updated when new data is streaming in or time passes by. Based on this, we build on Doyle's classic justification-based truth maintenance system (TMS) to update models of non-stratified programs. Finally, we empirically compare the obtained evaluation mechanisms. This paper is under consideration for acceptance in TPLP. We introduce a new flexible paradigm of grounding and solving in Answer Set Programming (ASP), which we refer to as multi-shot ASP solving, and present its implementation in the ASP system clingo. Multi-shot ASP solving features grounding and solving processes that deal with continuously changing logic programs. In doing so, they remain operative and accommodate changes in a seamless way. For instance, such processes allow for advanced forms of search, as in optimization or theory solving, or interaction with an environment, as in robotics or query-answering. Common to them is that the problem specification evolves during the reasoning process, either because data or constraints are added, deleted, or replaced. This evolutionary aspect adds another dimension to ASP since it brings about state changing operations. We address this issue by providing an operational semantics that characterizes grounding and solving processes in multi-shot ASP solving. This characterization provides a semantic account of grounder and solver states along with the operations manipulating them. The operative nature of multi-shot solving avoids redundancies in relaunching grounder and solver programs and benefits from the solver's learning capacities. clingo accomplishes this by complementing ASP's declarative input language with control capacities. On the declarative side, a new directive allows for structuring logic programs into named and parameterizable subprograms. The grounding and integration of these subprograms into the solving process is completely modular and fully controllable from the procedural side. To this end, clingo offers a new application programming interface that is conveniently accessible via scripting languages. Real-time processing of data streams emanating from sensors is becoming a common task in Internet of Things scenarios. The key implementation goal consists in efficiently handling massive incoming data streams and supporting advanced data analytics services like anomaly detection. In an on-going, industrial project, a 24 7 available stream processing engine usually faces dynamically changing data and workload characteristics. These changes impact the engine’s performance and reliability. We propose Strider, a hybrid adaptive distributed RDF Stream Processing engine that optimizes logical query plan according to the state of data streams. Strider has been designed to guarantee important industrial properties such as scalability, high availability, fault tolerance, high throughput and acceptable latency. These guarantees are obtained by designing the engine’s architecture with state-of-the-art Apache components such as Spark and Kafka. We highlight the efficiency (e.g., on a single machine machine, up to 60x gain on throughput compared to state-of-the-art systems, a throughput of 3.1 million triples second on a 9 machines cluster, a major breakthrough in this system’s category) of Strider on real-world and synthetic data sets.