Leveraging temporal and topological selectivities in temporal-clique subgraph query processing

Kaijie Zhu (TU Eindhoven)

We study the problem of temporal-clique subgraph pattern matching. In such patterns, edges are required to jointly overlap in time within a given temporal window in addition to forming a topological sub-structure. This problem arises in many application domains, e.g., in social networks, life sciences, smart cities, telecommunications, and others. State-of-the-art subgraph matching techniques, however, are shown to be limited and inefficient in processing queries with both temporal and topological constraints. We propose an approach that takes full advantage of both topological and temporal selectivities during the processing of temporal-clique subgraph queries. Additionally, we investigate a number of optimizations that can be introduced into our approach to improve its efficiency. Our experimental results demonstrate that our approach outperforms the existing methods by a wide margin at a small additional storage cost. For more details, you can read our ICDE 2021 paper [1].

[1] Kaijie Zhu, George Fletcher, and Nikolay Yakovets. Leveraging temporal and topological selectivities in temporal-clique subgraph query processing. In proceedings of the IEEE International Conference on Data Engineering (ICDE). 2021: 672-683

Kaijie Zhu started a PhD project “Temporal graph query processing in scalable datasets” in the Department of Mathematics and Computer Science at Eindhoven University of Technology under the supervision of prof.dr. George Fletcher and dr. Nikolay Yakovets at Eindhoven, the Netherlands. And on November 9, 2021, he received his Ph.d degree. Now his interest lies in database query processing and database security.