Search Results

Documents authored by Weidlich, Matthias

Document
DOI: 10.4230/LIPIcs.ICDT.2022.18
Discovering Event Queries from Traces: Laying Foundations for Subsequence-Queries with Wildcards and Gap-Size Constraints

Authors: Sarah Kleest-Meißner, Rebecca Sattler, Markus L. Schmid, Nicole Schweikardt, and Matthias Weidlich

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)

Abstract
We introduce subsequence-queries with wildcards and gap-size constraints (swg-queries, for short) as a tool for querying event traces. An swg-query q is given by a string s over an alphabet of variables and types, a global window size w, and a tuple c = ((c^-_1, c^+_1), (c^-_2, c^+_2), …, (c^-_{|s|-1}, c^+_{|s|-1})) of local gap-size constraints over ℕ × (ℕ ∪ {∞}). The query q matches in a trace t (i. e., a sequence of types) if the variables can uniformly be substituted by types such that the resulting string occurs in t as a subsequence that spans an area of length at most w, and the i^{th} gap of the subsequence (i. e., the distance between the i^{th} and (i+1)^{th} position of the subsequence) has length at least c^-_i and at most c^+_i. We formalise and investigate the task of discovering an swg-query that describes best the traces from a given sample S of traces, and we present an algorithm solving this task. As a central component, our algorithm repeatedly solves the matching problem (i. e., deciding whether a given query q matches in a given trace t), which is an NP-complete problem (in combined complexity). Hence, the matching problem is of special interest in the context of query discovery, and we therefore subject it to a detailed (parameterised) complexity analysis to identify tractable subclasses, which lead to tractable subclasses of the discovery problem as well. We complement this by a reduction proving that any query discovery algorithm also yields an algorithm for the matching problem. Hence, lower bounds on the complexity of the matching problem directly translate into according lower bounds of the query discovery problem. As a proof of concept, we also implemented a prototype of our algorithm and tested it on real-world data.
Cite as

Sarah Kleest-Meißner, Rebecca Sattler, Markus L. Schmid, Nicole Schweikardt, and Matthias Weidlich. Discovering Event Queries from Traces: Laying Foundations for Subsequence-Queries with Wildcards and Gap-Size Constraints. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kleestmeiner_et_al:LIPIcs.ICDT.2022.18,
  author =	{Kleest-Mei{\ss}ner, Sarah and Sattler, Rebecca and Schmid, Markus L. and Schweikardt, Nicole and Weidlich, Matthias},
  title =	{{Discovering Event Queries from Traces: Laying Foundations for Subsequence-Queries with Wildcards and Gap-Size Constraints}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{18:1--18:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.18},
  URN =		{urn:nbn:de:0030-drops-158922},
  doi =		{10.4230/LIPIcs.ICDT.2022.18},
  annote =	{Keywords: event queries on traces, pattern queries on strings, learning descriptive queries, complexity of query evaluation and query learning}
}
Document
DOI: 10.4230/DagRep.6.8.21
Integrating Process-Oriented and Event-Based Systems (Dagstuhl Seminar 16341)

Authors: David Eyers, Avigdor Gal, Hans-Arno Jacobsen, and Matthias Weidlich

Published in: Dagstuhl Reports, Volume 6, Issue 8 (2017)

Abstract
This report documents the programme and the outcomes of Dagstuhl Seminar 16341 on "Integrating Process-Oriented and Event-Based Systems", which took place August 21--26, 2016, at Schloss Dagstuhl -- Leibniz Center for Informatics. The seminar brought together researchers and practitioners from the communities that have been established for research on process-oriented information systems on the one hand, and event-based systems on the other hand. By exploring the use of processes in event handling (from the distribution of event processing to the assessment of event data quality), the use of events in processes (from rich event semantics in processes to support for flexible BPM), and the role of events in process choreographies, the seminar identified the diverse connections between the scientific fields. This report summarises the outcomes of the seminar by reviewing the state-of-the-art and outlining research challenges on the intersection of process-oriented and event-based systems.
Cite as

David Eyers, Avigdor Gal, Hans-Arno Jacobsen, and Matthias Weidlich. Integrating Process-Oriented and Event-Based Systems (Dagstuhl Seminar 16341). In Dagstuhl Reports, Volume 6, Issue 8, pp. 21-64, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{eyers_et_al:DagRep.6.8.21,
  author =	{Eyers, David and Gal, Avigdor and Jacobsen, Hans-Arno and Weidlich, Matthias},
  title =	{{Integrating Process-Oriented and Event-Based Systems (Dagstuhl Seminar 16341)}},
  pages =	{21--64},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{8},
  editor =	{Eyers, David and Gal, Avigdor and Jacobsen, Hans-Arno and Weidlich, Matthias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.8.21},
  URN =		{urn:nbn:de:0030-drops-69108},
  doi =		{10.4230/DagRep.6.8.21},
  annote =	{Keywords: distributed systems, event-based systems, process-aware information systems}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact