Discovering Frequent Closed Embedded Sub-DAGs in Spatio-Temporal Event Data

Jul 16, 2026

Upload by Oliver

A novel approach mines patterns in spatio-temporal event data by discovering frequent closed embedded sub-directed acyclic graphs (DAGs). Event instances are modeled as labeled nodes by event type, while edges encode spatio-temporal following relationships. The work defines the target pattern class and motivates closed sub-DAGs as compact, non-redundant summaries of recurring interactions. It introduces the DigDag algorithm and evaluates it against SLEUTH propagation mining and CSTPM cascading spatio-temporal pattern mining. Results show substantially higher efficiency under comparable settings, plus qualitative analysis of discovered patterns.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages12

Reading Time30 min

Introduction

Related Work

Spatio-temporal Sequential Patterns (STSPs)

Propagation and cascading pattern mining

arXiv :2607 .05995v 1 [ cs .DB] 7 Jul 2026 Discovering Frequent Closed Embedded Sub-DAGs in Spatio-Temporal Event Data Piotr S. Maciąg [0000−0001−5486−7927] Institute of Computer Science, Warsaw University of Technology, Nowowiejska 15/19, 00-661, [Warsaw](Warsaw piotr.maciag@pw.edu.pl)[ piotr.maciag@pw.edu.pl](Warsaw piotr.maciag@pw.edu.pl) Abstract. We propose a novel approach to mine patterns in spatiotemporal event data based on discovering frequent closed embedded subDirected Acyclic Graphs (DAGs) . In our method, event instances are represented as nodes labelled by event types, while edges capture spatiotemporal following relationships. We formally define the considered class of patterns and provide the rationale for focusing on closed sub-DAGsas compact and non-redundant representations of recurring interaction patterns. We implement the DigDag algorithm for mining such patterns and experimentally compare its efficiency with two related approaches: propagation pattern mining using the SLEUTH algorithm and Cascading Spatio-Temporal Pattern mining using the CSTPM algorithm. The experimental results demonstrate that our approach is substantially more efficient while operating under comparable parameter settings. Finally, we present a qualitative analysis of selected discovered patterns. Keywords: spatio-temporal pattern mining · frequent closed sub-DAGs · crime event analysis. 1 Introduction Discovering various spatio-temporal patterns has long been a topic attracting the attention of both researchers and practitioners. The literature in this area is extensive, as the nature of spatio-temporal data is inherently complex and multimodal. For example, researchers analysing trajectories of animal flocks are interested in different types of patterns than those attempting to extract knowledge from datasets of epidemic incidents, where only approximate spatial and temporal occurrences are available for each event [1, 8] . In this work, we focus on discovering spatio-temporal patterns from instances of crime events occurring in municipal areas. We assume that each event instance is described by a unique identifier, a geographical location, an occurrence time, and an event type. Our objective is to uncover mutual relationships between different types of crimes in the dataset. For example, we aim to investigate whether the occurrence of one crime type at a given location is followed by subsequent occurrences of other crime types within the same spatial area. To this end, we apply closed frequent embedded sub-Directed Acyclic Graph (DAG) mining. In our approach, the nodes of a DAG correspond to individual 2 Piotr Maciąg crime event instances, and their labels represent event types. The edges between nodes express the spatio-temporal following relationship between event instances. For example, they may capture the fact that the occurrence of an event instance of one crime type is followed by subsequent occurrences of other crime types within a given spatial and temporal neighbourhood. In this context, a frequent sub-DAG can be intuitively understood as asubgraph pattern that occurs sufficiently often across the constructed DAGsand therefore represents a recurring spatio-temporal interaction among different crime types. By focusing on closed patterns, we eliminate redundant substructures and retain only the most informative and non-redundant representations of such relationships. Contributions. The contributions of this article are as follows: – We propose an approach for discovering frequent closed (embedded) subDAGs in spatio-temporal event data. We introduce the necessary definitions in Section 3 and provide the rationale for focusing on this class of patterns. Furthermore, we implement the DigDag algorithm to discover frequent closed sub-DAGs from a set of crime event instances. – We experimentally compare the efficiency of discovering the proposed type of patterns with the efficiency of discover

FAQs

What are the key components of the proposed pattern representation?

Each event instance is represented as a node labeled by its event type, and edges represent spatio-temporal following relationships between instances.

Why focus on frequent closed embedded sub-DAGs?

Closed sub-DAGs provide compact, non-redundant representations of recurring interaction patterns while eliminating redundant substructures.

How does DigDag compare with SLEUTH and CSTPM?

Experimental results indicate DigDag is substantially more efficient than both SLEUTH-based propagation pattern mining and CSTPM-based cascading spatio-temporal pattern mining under comparable parameter settings.

Jul 16, 2026

Upload by Oliver