On topology and time: efficient evaluation for temporal-clique subgraph queries

Abstract We investigate temporal-clique subgraph pattern matching, where edges must both form a specific topological sub-structure and temporally overlap within a specified window. This problem has widespread applications across domains including social networks, life sciences, smart cities, and telecommunications. However, existing subgraph matching techniques are inefficient at processing such queries that combine both temporal and structural constraints. We propose a novel approach that effectively leverages both topological and temporal selectivities of the query to significantly improve processing performance. Our solution introduces key innovations across the query processing pipeline, including a specialized multi-way join operator, an optimized query planner, and an accurate cardinality estimator. Through additional optimizations, we further enhance the efficiency of our approach. Extensive experiments demonstrate that our method substantially outperforms state-of-the-art techniques while requiring minimal additional storage overhead.