Back to Search
Start Over
Subgraph matching on temporal graphs
- Source :
- Information Sciences. 578:539-558
- Publication Year :
- 2021
- Publisher :
- Elsevier BV, 2021.
-
Abstract
- Temporal graphs are graphs whose edges are associated with timestamps. Subgraph matching on temporal graphs retrieves temporal subgraphs whose edge timestamps satisfy user-specified temporal orders. In this paper, a temporal query pattern is composed of a query graph with an arbitrary structure and a partial order on the edge set of the query graph. Moreover, the time span between the minimum and the maximum edge timestamps in a matching is required to be less than or equal to a specified threshold. This paper proposes a temporal subgraph matching algorithm based on two key techniques. First, a memory-efficient index structure called TO-tree is designed to compactly store all necessary information required for finding all temporal subgraph matchings. The TO-tree constructed for a temporal query pattern is much smaller than the temporal graph because unnecessary information is mostly excluded from the TO-tree by three powerful filters. The second technique is a temporal subgraph matching enumeration method that runs on the TO-tree instead of on the temporal graph. This enumeration method expands temporal subgraph matchings in an edge-by-edge manner. Since the TO-tree can fit into the main memory, the enumeration method runs very fast on the TO-tree. An extensive experimental evaluation has been carried out. The experimental results show that the TO-tree index structure is memory-efficient, which in turn enables a fast temporal subgraph matching enumeration. Overall, our algorithm is at least 3X faster than the baseline algorithm adapted from the state-of-the-art non-temporal subgraph matching algorithm CECI and is at least 4X faster than the temporal subgraph matching algorithm HASSE .
- Subjects :
- Structure (mathematical logic)
Information Systems and Management
Matching (graph theory)
Computer science
Computer Science Applications
Theoretical Computer Science
Set (abstract data type)
Artificial Intelligence
Control and Systems Engineering
Enumeration
Key (cryptography)
Timestamp
Enhanced Data Rates for GSM Evolution
Algorithm
Software
Blossom algorithm
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- ISSN :
- 00200255
- Volume :
- 578
- Database :
- OpenAIRE
- Journal :
- Information Sciences
- Accession number :
- edsair.doi...........83b3361d7cb5a99f0c1f14f6af8a6a92