Hybrid Indexing for Label-Constrained Reachability on Temporal Property Graphs
摘要
Reachability query is a fundamental primitive on graph analysis. Recently, label-constrained reachability(LCR) has drawn growing research attention on edge-label graphs. However, no research has studied this problem on temporal property graphs, which are widely used to model many real-world networks with time-related activities, such as social networks and cybersecurity knowledge graphs. Edges in these networks have both time and label attributes. In this paper, we define the Temporal Label-Constrained Reachability(TLCR) query problem for the first time and design a novel index called Temporal Labeled Vertex Labeling(TL) to accelerate this type of query. To further improve query performance, we propose a hybrid index strategy (HTL) by optimizing TL with an existing index strategy Topchain. Based on this hybrid index, we design a new query algorithm. Experiments on 5 real-world datasets show that our query algorithm can achieve up to 0.5–8 times faster than the baseline method.