Tutorial on Stream Reasoning at KR 2018

a project with a background image

Sunday, October 28, 2018 Tempe, Arizona , USA Collocated with the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR 2018)

Abstract Motivation Program The team of presenters References

Abstract

We live in a streaming world. New information is continually being produced by sensors and humans. A stream is such a sequence of incrementally available information. Streaming information is always dynamic and temporal, and usually also spatial in nature. Reasoning over these streams is necessary to draw conclusions and make decisions in real-time. Since streams are conceptually infinite, this reasoning has to be done incrementally as new information becomes available. The incremental reasoning over streams is called stream reasoning. Stream reasoning addresses all the four V’s in BigData: Velocity, Volume, Variety and Veracity. Stream reasoning is an emerging research area with great potential and strategic relevance for autonomous systems, the Internet of Things and real-time data analytics. In this tutorial, we will present two major classes of approaches to Stream Reasoning. The first comes from the Semantic Web where efforts were devoted to extending the Semantic Web stack with the notions of RDF stream, continuous SPARQL and continuous reasoning as well as to investigating new algorithms, methods, architectures, and systems for scaling to high velocity SPARQL query answering and incremental reasoning. An important application is in continuous analysis of heterogeneous information flows. The second comes from AI using logic-based spatio-temporal stream reasoning to guarantee the safety of autonomous systems in the face of incomplete information. An important application is online verification of autonomous systems. These systems are too large and too complex to be modeled in detail. Therefore model checking is not a viable option. Instead, stream reasoning can be used to provide run-time verification by continually monitoring the system execution with formal guarantees to make sure that it behaves as expected.

Objective

  •  Introduce novices to major topics of KR research.
  • Provide instruction in established practices and methodologies.
  • Survey a mature area of KR research or practice.
  • Motivate and explain an KR topic of emerging importance.
  • Introduce expert non-specialists to an KR area.
  • Survey an area of KR research especially relevant for people from industry
  • Present a novel synthesis combining distinct lines of KR work.
  • Introduce KR audiences to an external topic that can motivate or use KR research.

Program

The tutorial presents an overview of the existing algorithms, techniques, and technologies that enable reasoning on streaming data. It builds on an IJCAI 2016 tutorial by Fredrik Heintz and several tutorials at conferences such as DEBS and ISWC by Emanuele Della Valle.

Introduction to Stream Reasoning [slides]

The first part of the tutorial prepares the ground for the following discussion by introducing the terminology adopted in the tutorial and by giving an overview of the theory and practice of the research on stream reasoning. We present related work such as Data Stream Management Systems and Complex Event Processing. We also present a number of use cases and scenarios that require low latency processing of large volumes of heterogeneous streaming data, and thus motivate the need for stream reasoning. We focus on Autonomous Systems, Internet of Things scenarios, traffic monitoring, and smart cities management. We highlight the key requirements of these scenarios and show why existing technologies for event and stream processing and for reasoning alone are not sufficient to satisfy all of them. We use the case studies to define the scope of the stream reasoning research area.

Stream Reasoning from an Autonomous Systems Perspective [slides]

The second part of the tutorial focuses on logic-based spatio-temporal stream reasoning for autonomous systems especially run-time verification to guarantee the safety of autonomous systems.

  • Introduction to Autonomous Systems as an application area for stream reasoning
  • Related work: Answer Set Programming (ASP) for streams such as StreamRule, LARS, Laser.
  • Stream Reasoning using Metric Temporal Logic through Progression over complete information
  • Execution Monitoring through Stream Reasoning for Safe Autonomous Systems
  • Spatio-Temporal Stream Reasoning with Incomplete Information
  • Grounding Logic-Based Stream Reasoning for Autonomous Systems
  • Future Work: Probabilistic and Anticipatory Stream Reasoning

Stream Reasoning from a Semantic Web Perspective [slides]

The third part of the tutorial focuses on Semantic Web approaches to stream reasoning. It starts with an introduction of the main concepts related to the Semantic Web and to reasoning.

In particular, this part covers the following topics:

  • Semantically annotated data and the RDF format;
  • Knowledge representation, ontologies, and the Web Ontology Language (OWL);
  • Querying RDF data: the SPARQL language;
  • Reasoning: definitions, approaches, and challenges.

Then, we present and compare the following state-of-the-art techniques for stream reasoning on the Semantic Web [2, 5]

  • languages and systems for querying RDF streams such as C-SPARQL, CQELS and SPARQL_stream and RSP-QL
  • algorithms and systems for scalable incremental reasoning such as IMaRS, Sparkwave, TrOWL and RDFox
  • stream reasoning and complex event processing such as ETALIS/EP-SPARQL, STARQL, DELP, OBEP

Conclusions [slides]

This part of the tutorial draws conclusions and present future work.

The team of presenters

Fredrik Heintz, Associate Professor of Computer Science, Linköping University, Sweden and President of the Swedish AI Society He has been doing research on stream reasoning and its integration in autonomous systems for more than 10 years. You could argue that the area has independently been developed by him [3, 6, 8] and the Semantic Web community [2, 4]. He currently leads the Stream Reasoning research group within the Artificial Intelligence and Integrated Computer Systems division at Linköping University. Together with his PhD students he has recently extended their original metric-temporal logic stream reasoning approach for complete information to spatio-temporal stream reasoning with incomplete information [1, 7]. A sign of his role in the community is that he gave one of two keynotes at the first invitation only Stream Reasoning workshop in Vienna. The other was given by Emanuele Della Valle, who has been the leading stream reasoning researcher in the Semantic Web community. Dr. Heintz has extensive teaching experience where he has given courses on for example AI programming (2000-2011), AI Project (2015–), Algorithmic Problem Solving (2013–), and Functional and Imperative Programming in Python (2015–). He has also extensive experience in giving both technical and popular science presentations to varying types of audiences

Emanuele Della Valle, Assistant Professor at the Department of Electronics, Information and Bioengineering of Politecnico di Milano. In more than 15 years of research, his research interests covered Big Data, Stream Processing, Semantic technologies, Data Science, Web Information Retrieval, and Service Oriented Architectures. He branded the stream reasoning research field [4]. The semantic and syntactic extensions, which he proposed to the Semantic Web stack (i.e., RDF streams and Continuous SPARQL), are currently on the path towards standardization at a W3C in the RDF Stream Processing community group. His work on Stream Reasoning was applied in analysing Social Media, Mobile Telecom and IoT data streams in collaboration with Telecom Italia, IBM, Siemens, Oracle, Indra, and Statoil. In 2015, he started up a company (Fluxedo) to commercialize the open source results of Stream Reasoning research. His education activities include lecturing on Web Science, Software Project Management, Semantic Technologies, Stream Processing and Big Data technologies. He offered Stream Reasoning tutorials at SemTech 2011, ESWC 2011, ISWC 2013, ESWC 2014, ISWC 2014, ISWC 2015, ISWC 2016, DEBS 2016, ISWC 2017, and RW 2018.

References

[1] D. de Leng and F. Heintz. Qualitative spatio-temporal stream reasoning with unobservable intertemporal spatial relations using landmarks. In Proc. AAAI, 2016.

[2] D. Dell’Aglio, E. Della Valle, F. van Harmelen, and A. Bernstein. Stream reasoning: A survey and outlook. Data Science, 1(1-2):59–83, 2017.

[3] P. Doherty, J. Kvarnström, and F. Heintz. A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems. J. of Autonomous Agents and Multi-Agent Systems, 19(3):332–377, 2009.

[4] E. Della Valle, S. Ceri, F. van Harmelen, and D. Fensel. It’s a streaming world! reasoning upon rapidly changing information. IEEE Intelligent Systems, 24(6):83–89, 2009.

[5] E. Della Valle, D. Dell’Aglio, and A. Margara. Taming velocity and variety simultaneously in big data with stream reasoning: tutorial. In DEBS, pages 394–401. ACM, 2016.

[6] F. Heintz. DyKnow: A Stream-Based Knowledge Processing Middleware Framework. PhD thesis, Linköpings universitet, 2009.

[7] F. Heintz and D. de Leng. Spatio-temporal stream reasoning with incomplete spatial information. In Proc. ECAI, 2014.

[8] F. Heintz and P. Doherty. DyKnow: An approach to middleware for knowledge processing. J. of Intelligent & Fuzzy Systems, 15(1), 2004.