Discovering Multi-Dimensional Subsequence Queries from Traces -- From Theory to Practice
| dc.contributor.author | Kleest-Meißner, Sarah | |
| dc.contributor.author | Sattler, Rebecca | |
| dc.contributor.author | Schmid, Markus L. | |
| dc.contributor.author | Schweikardt, Nicole | |
| dc.contributor.author | Weidlich, Matthias | |
| dc.contributor.editor | König-Ries, Birgitta | |
| dc.contributor.editor | Scherzinger, Stefanie | |
| dc.contributor.editor | Lehner, Wolfgang | |
| dc.contributor.editor | Vossen, Gottfried | |
| dc.date.accessioned | 2023-02-23T13:59:51Z | |
| dc.date.available | 2023-02-23T13:59:51Z | |
| dc.date.issued | 2023 | |
| dc.description.abstract | Subsequence-queries with wildcards and gap-size constraints (swg-queries, for short) are an expressive model for sequence data, in which queries are described by patterns over an alphabet of variables and types, along with a global window size and a number of gap-size constraints. They are evaluated over a trace, i.e., a sequence of types, by replacing variables by single types, while satisfying the window and the gap-size constraints. Kleest-Meißner et al. (Proc. ICDT 2022) formalised the task of discovering an swg-query that describes best a given sample consisting of a finite number of traces, and developed a discovery algorithm solving this task. However, in practical application scenarios, traces are often multi-dimensional, i.e., a trace corresponds to a sequence of tuples of types, which renders the existing technique inapplicable.In this paper, we lift the notion of swg-queries to such a multi-dimensional setting, thereby enlarging the applicability of the query model and the techniques for query discovery. We introduce a mapping between one-dimensional and multi-dimensional sequence data, such that a multi-dimensional trace matches a multi-dimensional query if and only if the corresponding one-dimensional trace matches the corresponding one-dimensional query. We complement our formal results with a description of our prototypical implementation of query discovery for multi-dimensional sequence data. Results from evaluation experiments with real-world data indicate feasibility of our approach. | en |
| dc.identifier.doi | 10.18420/BTW2023-24 | |
| dc.identifier.isbn | 978-3-88579-725-8 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/40329 | |
| dc.language.iso | en | |
| dc.publisher | Gesellschaft für Informatik e.V. | |
| dc.relation.ispartof | BTW 2023 | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Proceedings, Volume P-331 | |
| dc.subject | multi-dimensional subsequence queries on traces | |
| dc.subject | descriptive multi-dimensional queries | |
| dc.subject | subsequences | |
| dc.subject | embeddings | |
| dc.title | Discovering Multi-Dimensional Subsequence Queries from Traces -- From Theory to Practice | en |
| dc.type | Text/Conference Paper | |
| gi.citation.endPage | 533 | |
| gi.citation.publisherPlace | Bonn | |
| gi.citation.startPage | 511 | |
| gi.conference.date | 06.-10. März 2023 | |
| gi.conference.location | Dresden, Germany |
Dateien
Originalbündel
1 - 1 von 1