Author name cluster

Harald Beck

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

AIJ Journal 2018 Journal Article

LARS: A Logic-based framework for Analytic Reasoning over Streams

Harald Beck
Minh Dao-Tran
Thomas Eiter

The increasing availability of streaming data has accelerated advances in information processing tools that no longer store data for static querying but push information to consumers as soon as it becomes available. Stream processing aims at providing languages and tools for data that changes at a high rate. To cope with the volume of data, query languages often extend existing approaches for static data by means of window operators that return snapshots of recent data. However, the semantics of these languages are often given only informally or operationally, which makes their analysis and comparison difficult. A formal means to express the declarative semantics of such systems seems to be missing. This lack of theory is of particular relevance for the emerging research in stream reasoning which shifts the focus from throughput to higher expressiveness. To fill this gap, we present LARS, a Logic-based framework for Analytic Reasoning over Streams. At its core, LARS formulas extend propositional logic with generic window operators and additional controls to handle temporal information. On top of this, LARS programs extend Answer Set Programming (ASP) with rich stream reasoning capabilities; the latter can be exploited to target AI applications in a streaming context, such as diagnosis, configuration or planning. Specifically, we study in this article the computational complexity of LARS formulas and programs, their relationship to Linear Temporal Logic (LTL) and the well-known Continuous Query Language (CQL). Furthermore, we discuss the modeling capabilities of LARS in notes on the SPARQL extensions C-SPARQL and CQELS, and on the interval-based approach of the complex event processing language ETALIS. We finally briefly touch available implementations, in particular, the recent prototype engines Laser and Ticker that aim for high throughput and high expressiveness, respectively. Notably, both engines specify their semantics in LARS, indicating the desired flexibility of the framework and its potential as stream reasoning language itself, which is further explored in other works.

Details DOI

IJCAI Conference 2016 Conference Paper

Equivalent Stream Reasoning Programs

Harald Beck
Minh Dao-Tran
Thomas Eiter

The emerging research field of stream reasoning faces the challenging trade-off between expressiveness of query programs and data throughput. For optimizing programs methods are needed to tell whether two programs are equivalent. Towards providing practical reasoning techniques on streams, we consider LARS programs, which is a powerful extension of Answer Set Programming (ASP) for stream reasoning that supports windows on streams for discarding information. We define different notions of equivalence between such programs and give semantic characterizations in terms of models. We show how a practically relevant fragment can be alternatively captured usingHere-and-There models, yielding an extension of equilibrium semantics of ASP to this class of programs. Finally, we characterize the computational complexity of deciding the considered equival encerelations.

PDF Details

JELIA Conference 2016 Conference Paper

Rule-based Stream Reasoning for Intelligent Administration of Content-Centric Networks

Harald Beck
Bruno Bierbaumer
Minh Dao-Tran
Thomas Eiter
Hermann Hellwagner
Konstantin Schekotihin

Abstract Content-Centric Networking (CCN) research addresses the mismatch between the modern usage of the Internet and its outdated architecture. Importantly, CCN routers use various caching strategies to locally cache content frequently requested by end users. However, it is unclear which content shall be stored and when it should be replaced. In this work, we employ novel techniques towards intelligent administration of CCN routers. Our approach allows for autonomous switching between existing strategies in response to changing content request patterns using rule-based stream reasoning framework LARS which extends Answer Set Programming for streams. The obtained possibility for flexible router configuration at runtime allows for faster experimentation and may result in significant performance gains, as shown in our evaluation.

Details

IJCAI Conference 2015 Conference Paper

Answer Update for Rule-Based Stream Reasoning

Harald Beck
Minh Dao-Tran
Thomas Eiter

Stream reasoning is the task of continuously deriving conclusions on streaming data. To get results instantly one evaluates a query repeatedly on recent data chunks selected by window operators. However, simply recomputing results from scratch is impractical for rule-based reasoning with semantics similar to Answer Set Programming, due to the trade-off between complexity and data throughput. To address this problem, we present a method to efficiently update models of a rule set. In particular, we show how an answer stream (model) of a LARS program can be incrementally adjusted to new or outdated input by extending truth maintenance techniques. We obtain in this way a means towards practical rule-based stream reasoning with nonmonotonic negation, various window operators and different forms of temporal reference.

PDF Details

IJCAI Conference 2015 Conference Paper

Expressive Rule-Based Stream Reasoning

Harald Beck

Stream reasoning is the task of continuously deriving conclusions on streaming data. As a research theme, it is targeted by different communities which emphasize different aspects, e. g. , throughput vs. expressiveness. This thesis aims to advance the theoretical foundations underlying diverse stream reasoning approaches and to convert obtained insights into a prototypical expressive rule-based reasoning system that is lacking to date.

PDF Details

AAAI Conference 2015 Conference Paper

LARS: A Logic-Based Framework for Analyzing Reasoning over Streams

Harald Beck
Minh Dao-Tran
Thomas Eiter
Michael Fink

The recent rise of smart applications has drawn interest to logical reasoning over data streams. Different query languages and stream processing/reasoning engines were proposed. However, due to a lack of theoretical foundations, the expressivity and semantics of these diverse approaches were only informally discussed. Towards clear specifications and means for analytic study, a formal framework is needed to characterize their semantics in precise terms. We present LARS, a Logic-based framework for Analyzing Reasoning over Streams, i. e. , a rule-based formalism with a novel window operator providing a flexible mechanism to represent views on streaming data. We establish complexity results for central reasoning tasks and show how the prominent Continuous Query Language (CQL) can be captured. Moreover, the relation between LARS and ETALIS, a system for complex event processing is discussed. We thus demonstrate the capability of LARS to serve as the desired formal foundation for expressing and analyzing different semantic approaches to stream processing/reasoning and engines.

PDF Details

JELIA Conference 2012 Conference Paper

Inconsistency Management for Traffic Regulations: Formalization and Complexity Results

Harald Beck
Thomas Eiter
Thomas Krennwallner

Abstract Smart Cities is a vision driven by the availability of governmental data that fosters many challenging applications. One of them is the management of inconsistent traffic regulations, i. e. , the handling of inconsistent traffic signs and measures in urban areas such as wrong sign posting, or errors in data acquisition in traffic sign administration software. We investigate such inconsistent traffic scenarios and formally model traffic regulations using a logic-based approach for traffic signs and measures, and logical theories describe emerging conflicts on a graph-based street model. Founded on this model, we consider major reasoning tasks including consistency testing, diagnosis, and repair, and we analyze their computational complexity for different logical representation formalisms. Our results provide a basis for an ongoing implementation of the approach.

Details