Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/40180
Title: | Temporal graph patterns by timed automata | Authors: | Aghasadeghi, Amir VAN DEN BUSSCHE, Jan Stoyanovich, Julia |
Issue Date: | 2023 | Publisher: | SPRINGER | Source: | VLDB JOURNAL, | Status: | Early view | Abstract: | Temporal graphs represent graph evolution over time, and have been receiving considerable research attention. Work on expressing temporal graph patterns or discovering temporal motifs typically assumes relatively simple temporal constraints, such as journeys or, more generally, existential constraints, possibly with finite delays. In this paper we propose to use timed automata to express temporal constraints, leading to a general and powerful notion of temporal basic graph pattern (BGP). The new difficulty is the evaluation of the temporal constraint on a large set of matchings. An important benefit of timed automata is that they support an iterative state assignment, which can be useful for early detection of matches and pruning of non-matches. We introduce algorithms to retrieve all instances of a temporal BGP match in a graph, and present results of an extensive experimental evaluation, demonstrating interesting performance trade-offs. We show that an on-demand algorithm that processes total matchings incrementally over time is preferable when dealing with cyclic patterns on sparse graphs. On acyclic patterns or dense graphs, and when connectivity of partial matchings can be guaranteed, the best performance is achieved by maintaining partial matchings over time and allowing automaton evaluation to be fully incremental. The code and datasets used in our analysis are available at http://github.com/amirpouya/TABGP. | Notes: | Stoyanovich, J (corresponding author), NYU, New York, NY 10003 USA. amirpouya@nyu.edu; jan.vandenbussche@uhasselt.be; stoyanovich@nyu.edu |
Keywords: | Temporal graphs;Property graphs;Graph query languages;Timed automata;dataflow systems | Document URI: | http://hdl.handle.net/1942/40180 | ISSN: | 1066-8888 | e-ISSN: | 0949-877X | DOI: | 10.1007/s00778-023-00795-z | ISI #: | 000982939400001 | Rights: | The Author(s) 2023. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecomm ons.org/licenses/by/4.0/. | Category: | A1 | Type: | Journal Contribution |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Temporal graph patterns by timed automata.pdf | Early view | 1.08 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.